做城通網(wǎng)盤資源網(wǎng)站的源碼關(guān)鍵詞app下載
2024.4.14
- 題目來源
- 我的題解
- 方法一 鏈表數(shù)組
題目來源
力扣每日一題;題序:705
我的題解
方法一 鏈表數(shù)組
由于給定限制次數(shù)為10000,所以構(gòu)造一個長度為10001的鏈表數(shù)組。對于add操作先看數(shù)組對應(yīng)的位置是否為null或者為空,若是則直接加入,否則遍歷整個鏈表看是否有與加入的值相同的元素。對于remove操作,先看數(shù)組對應(yīng)的位置是否為null或者為空,若是則直接退出,否則遍歷整個鏈表看是否有與加入的值相同的元素,若相同則刪除對應(yīng)的鏈表節(jié)點。對于contains操作,先看數(shù)組對應(yīng)的位置是否為null或者為空,若是則直接返回false,否則遍歷整個鏈表看是否有與加入的值相同的元素,若有直接返回true,否則返回false。
對于哈希函數(shù)的設(shè)計:取key對應(yīng)的哈希值mod 10000
哈希沖突的解決:使用鏈地址法解決
class MyHashSet {class LinkedList{int val;LinkedList next;public LinkedList(){}public LinkedList(int v){val=v;}public int size(){LinkedList root=this;int sz=0;while(root!=null){sz++;root=root.next;}return sz;}}private LinkedList[] keys;int n=10001;public MyHashSet() {keys=new LinkedList[n];// Arrays.fill(keys,new LinkedList());}public void add(int key) {int index=myHash(key);// 節(jié)點為空if(keys[index]==null){keys[index]=new LinkedList(key);// 還未有元素}else if(keys[index].size()==0){keys[index].val=key;//已經(jīng)有元素}else{LinkedList root=keys[index];if (root.val==key)return ;while(root.next!=null&&root.next.val!=key){root=root.next;}if(root.next==null)root.next=new LinkedList(key);}}public void remove(int key) {int index=myHash(key);// 節(jié)點為空 || 還未有元素if(keys[index]==null||keys[index].size()==0)return ;//已經(jīng)有元素else{LinkedList root=keys[index];if(root.val==key){keys[index]=root.next;}else{while(root.next!=null&&root.next.val!=key){root=root.next;}if(root.next!=null)root.next=root.next.next;}}}public boolean contains(int key) {int index=myHash(key);// 節(jié)點為空 || 還未有元素if(keys[index]==null||keys[index].size()==0)return false;//已經(jīng)有元素else{LinkedList root=keys[index];while(root!=null){if(root.val==key)return true;root=root.next;}return false;}}public int myHash(int key){int iHash=Integer.hashCode(key);return iHash%(n-1);}@Overridepublic String toString() {return Arrays.toString(keys);}
}
有任何問題,歡迎評論區(qū)交流,歡迎評論區(qū)提供其它解題思路(代碼),也可以點個贊支持一下作者哈😄~