Leetcode 707設計チェーンテーブル
16605 ワード
Leetcode 707設計チェーンテーブル
チェーンテーブルの実装を設計します.シングルチェーンテーブルまたはダブルチェーンテーブルを選択できます.単一チェーンテーブルのノードには、valとnextの2つの属性がある必要があります.valは現在のノードの値であり、nextは次のノードへのポインタ/参照である.双方向チェーンテーブルを使用する場合は、チェーンテーブルの前のノードを示すプロパティprevも必要です.チェーンテーブルのすべてのノードが0-indexであると仮定します.
これらの機能は、チェーンテーブルクラスで実装されます.
get(index):チェーンテーブルのindex番目のノードの値を取得します.インデックスが無効な場合は、-1を返します.addAtHead(val):チェーンテーブルの最初の要素の前にvalの値を持つノードを追加します.挿入すると、新しいノードがチェーンテーブルの最初のノードになります.addAtTail(val):valの値を持つノードをチェーンテーブルの最後の要素に追加します.addAtIndex(index,val):チェーンテーブルのindex番目のノードの前にvalの値を持つノードを追加します.indexがチェーンテーブルの長さに等しい場合、ノードはチェーンテーブルの末尾に付加されます.indexがチェーンテーブルの長さより大きい場合は、ノードは挿入されません.deleteAtIndex(index):インデックスindexが有効である場合、チェーンテーブルのindex番目のノードを削除します.
例:
MyLinkedList linkedList = new MyLinkedList(); linkedList.addAtHead(1); linkedList.addAtTail(3); linkedList.addAtIndex(1,2);//チェーンテーブルは1->2->3 linkedListとなる.get(1);//2 linkedListを返します.deleteAtIndex(1);//チェーンテーブルは1->3 linkedListです.get(1);//は、3を返します.
ヒント:
すべての値は[1,1000]以内です.操作回数は[1,1000]以内になります.内蔵のLinkedListライブラリは使用しないでください.チェーン時計を習って手を練習して、まず私が発見した問題を話します:彼のindexは0から、私は1からだと思っています.次にindex<0の時、addAtIndex(-1,0)のサンプルがあります.これはindex<0の時に挿入できることを示しています.addAtHeadを呼び出すには、他のindexの状況問題に説明されています.チェーンテーブルを習ったばかりで、最適化できるところがたくさんあるはずです.自分のjavaコードを添付します.
チェーンテーブルの実装を設計します.シングルチェーンテーブルまたはダブルチェーンテーブルを選択できます.単一チェーンテーブルのノードには、valとnextの2つの属性がある必要があります.valは現在のノードの値であり、nextは次のノードへのポインタ/参照である.双方向チェーンテーブルを使用する場合は、チェーンテーブルの前のノードを示すプロパティprevも必要です.チェーンテーブルのすべてのノードが0-indexであると仮定します.
これらの機能は、チェーンテーブルクラスで実装されます.
get(index):チェーンテーブルのindex番目のノードの値を取得します.インデックスが無効な場合は、-1を返します.addAtHead(val):チェーンテーブルの最初の要素の前にvalの値を持つノードを追加します.挿入すると、新しいノードがチェーンテーブルの最初のノードになります.addAtTail(val):valの値を持つノードをチェーンテーブルの最後の要素に追加します.addAtIndex(index,val):チェーンテーブルのindex番目のノードの前にvalの値を持つノードを追加します.indexがチェーンテーブルの長さに等しい場合、ノードはチェーンテーブルの末尾に付加されます.indexがチェーンテーブルの長さより大きい場合は、ノードは挿入されません.deleteAtIndex(index):インデックスindexが有効である場合、チェーンテーブルのindex番目のノードを削除します.
例:
MyLinkedList linkedList = new MyLinkedList(); linkedList.addAtHead(1); linkedList.addAtTail(3); linkedList.addAtIndex(1,2);//チェーンテーブルは1->2->3 linkedListとなる.get(1);//2 linkedListを返します.deleteAtIndex(1);//チェーンテーブルは1->3 linkedListです.get(1);//は、3を返します.
ヒント:
すべての値は[1,1000]以内です.操作回数は[1,1000]以内になります.内蔵のLinkedListライブラリは使用しないでください.チェーン時計を習って手を練習して、まず私が発見した問題を話します:彼のindexは0から、私は1からだと思っています.次にindex<0の時、addAtIndex(-1,0)のサンプルがあります.これはindex<0の時に挿入できることを示しています.addAtHeadを呼び出すには、他のindexの状況問題に説明されています.チェーンテーブルを習ったばかりで、最適化できるところがたくさんあるはずです.自分のjavaコードを添付します.
class MyLinkedList {
private static class Node{
int val;
Node next;
public Node(int val) {
this.val=val;
}
}
private Node head;
private Node last;
private int size;
public int get(int index) {
if(index<0||index>=size)return -1;
//index--;
Node tmp=head;
for(int i=1;i<=index;i++) {
tmp=tmp.next;
}
return tmp.val;
}
public void output() {
Node tmp=head;
while(tmp!=null) {
System.out.println(tmp.val);
tmp=tmp.next;
}
}
public Node gett(int index) {
//index--;
Node tmp=head;
for(int i=1;i<=index;i++) {
tmp=tmp.next;
}
return tmp;
}
public void addAtHead(int val) {
Node tmp=head;
Node insertNode=new Node(val);
if(size==0){
head=insertNode;
last=insertNode;
}
else
{head=insertNode;
insertNode.next=tmp;}
size++;
}
public void addAtTail(int val) {
Node insertNode=new Node(val);
if(size==0) {
head=insertNode;
last=insertNode;
}
else {
Node lastt=gett(size-1);
lastt.next=insertNode;
last=insertNode;
}
size++;
}
public void addAtIndex(int index,int val) {
//index=index+1;
if(index<0)
{addAtHead(val);
//
return;
}
Node insertNode=new Node(val);
if(index==size) {
addAtTail(val);return;
}
else if(index>size) {return;}
else if(index==0) {
addAtHead(val);return;
}
else {
Node prevNode=gett(index-1);
Node nextNode=prevNode.next;
prevNode.next=insertNode;
insertNode.next=nextNode;
}
size++;
}
public void deleteAtIndex(int index) {
if(index<0||index>=size)return;
//index--;
Node removeNode=null;
if(index==0) {
removeNode=head;
head=head.next;
}
else if(index==size-1) {
Node prevNode=gett(size-2);
removeNode=prevNode.next;
prevNode.next=null;
}else {
Node prevNode=gett(index-1);
Node tmp=prevNode.next.next;
prevNode.next=tmp;
}
size--;
}}