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コードを添付します.
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--;
}}