本節的內容比較難, 大多是leetcodeHard難度級別的題目

1. 帶有setAll功能的哈希表

哈希表常見的三個操作時put、get和containsKey，而且這三個操作的時間復雜度為O(1)。現在想加一個setAll功能，就是把所有記錄value都設成統一的值。請設計并實現這種有setAll功能的哈希表，并且put、get、containsKey和setAll四個操作的時間復雜度都為O(1)。

思路分析 :
原始的哈希表的put,get,containsKey方法的時間復雜度都是O(1), 現在我們需要添加一個setAll方法, 把表中所有元素的值都改為一個特定的value,顯然直接遍歷的時間復雜度肯定不是O(1)
為了做到時間復雜度是O(1)我們采用時間戳計數的方法
給定一個屬性time記錄下本次操作的時間節點, 然后給定一個屬性是setAllValue和setAllTime,記錄下來我們的setAll調用時候是時間節點和設置的變量, 然后get方法返回的時候如果是大于該節點我們就進行返回原有的值, 如果小于該節點, 我們就返回setAllValue的值
代碼實現如下…

/*** 下面這個高頻的數據結構是帶有setAll功能的HashMap實現* 原理就是傳入一個時間戳, 然后進行模擬的判斷*/
class HashMapConSetAll {//基礎的HashMap結構private HashMap<Integer, int[]> map = new HashMap<>();//定義一個時間戳private int time = 0;//定義一個是用setAll方法的時間節點以及相關的值private int setAllValue = 0;private int setAllTime = -1;//給一個無參的構造方法public HashMapConSetAll() {}//我們實現的特殊HashMap的put方法public void put(int key, int value) {if (!map.containsKey(key)) {map.put(key, new int[]{value, time++});} else {int[] temp = map.get(key);temp[0] = value;temp[1] = time++;}}//我們實現的特殊的HashMap的get方法public int get(int key) {if (!map.containsKey(key)) {return -1;}//代碼執行到這里說明我們的map里面沒有這個元素int[] temp = map.get(key);if (temp[1] > setAllTime) {return temp[0];} else {return setAllValue;}}//特殊的containsKey方法public boolean containsKey(int key) {return map.containsKey(key);}//最重要的setAll方法public void setAll(int value) {this.setAllTime = time++;this.setAllValue = value;}
}

2. LRU緩存結構

該數據結構的實現借助的是哈希表加上雙向鏈表的方式, 我們定義一個節點類Node, 里面的基礎屬性就是key與val, 我們的哈希表中的key就是節點中的key,我們的val就是該節點的地址, 為什么要用節點的地址作為val其實也非常的好理解, 用Node作為地址我們可以直接找到這個節點的位置然后進行操作,下面是我們的代碼實現

/*** LRU緩存結構* 實現的方法就是雙向鏈表 + 哈希表, 可以直接通過哈希表在O(1)的時間復雜度下獲取到位置節點的地址* 手寫一個雙向鏈表就行了*/
class LRUCache {// 首先定義的是雙向鏈表的節點類public static class Node {int key;int val;Node prev;Node next;public Node(int key, int val) {this.key = key;this.val = val;}}// 雙向鏈表的實現方式public static class DoubleLinkedList {// 鏈表的頭部(代表的是最早操作的數據)public Node first;// 鏈表的尾部(代表的是最新操作的數據)public Node last;// 給一個無參數的構造方法public DoubleLinkedList() {first = null;last = null;}// 添加節點的方法public void addNode(Node node) {if (node == null) {return;}if (first == null && last == null) {first = node;last = node;return;}last.next = node;node.prev = last;last = node;}//重構一下remove()和removeToLast()方法public Node remove() {//沒節點你刪除個damn啊if (first == null && last == null) {return null;}//只有一個節點的情況Node node = first;if (first == last) {last = null;first = null;} else {Node next = first.next;first.next = null;first = next;next.prev = null;}return node;}//下面是重構的removeToLast方法public void removeToLast(Node node) {//首先排除掉特殊的情況if (node == null || first == null) {return;}//如果只有一個的話或者是尾巴節點if (first == last || node == last) {return;}//如果是頭節點的節點 / 普通的節點if (node == first) {Node next = node.next;node.next = null;first = next;first.prev = null;} else {node.prev.next = node.next;node.next.prev = node.prev;node.prev = null;node.next = null;}//此時node節點完全是一個獨立的節點last.next = node;node.prev = last;last = node;}}private HashMap<Integer, Node> map = new HashMap<>();DoubleLinkedList list = new DoubleLinkedList();private int capacity;public LRUCache(int capacity) {this.capacity = capacity;}public int get(int key) {if (!map.containsKey(key)) {return -1;}Node node = map.get(key);list.removeToLast(node);return node.val;}public void put(int key, int value) {if (map.containsKey(key)) {Node node = map.get(key);node.val = value;list.removeToLast(node);} else {Node node = new Node(key, value);if (map.size() < capacity) {map.put(key, node);list.addNode(node);} else {Node nde = list.remove();map.remove(nde.key);list.addNode(node);map.put(key, node);}}}public static void main(String[] args) {LRUCache lruCache = new LRUCache(2);lruCache.put(1, 0);lruCache.put(2, 2);int res = lruCache.get(1);lruCache.put(3, 3);int res1 = lruCache.get(2);lruCache.put(4, 4);int res2 = lruCache.get(1);int res3 = lruCache.get(3);int res4 = lruCache.get(4);}
}

3. O(1)時間插入刪除隨機(去重)

這個類的實現還是基于的哈希表, 外加上一個動態數組, key就是該數字, val是在動態數組里面的下標的位置, 如果刪除元素, 動態數組中的那個空位置我們就用最后一個元素去填充, 然后刪掉最后一個游戲(這樣就保證了這個時間的復雜度O(1)), 同時在哈希表里面刪除該值, 并該變最后一個元素的val為刪除元素的之前的下標, 代碼實現如下

class RandomizedSet {//其實現的方式是通過動態數組也就是我們的ArrayList跟HashMap共同實現的//其實從我們的經驗可以了解到, 凡是涉及到O(1)的操作一般都是通過散列表的形式實現的HashMap<Integer, Integer> map = new HashMap<>();ArrayList<Integer> list = new ArrayList<>();//構造方法這里其實沒什么用, 我們直接設置為空方法體的public RandomizedSet() {}//常規的insert方法, 我們的map結構第一個整數存儲的就是值, 第二個是下標public boolean insert(int val) {if (!map.containsKey(val)) {list.add(val);map.put(val, list.size() - 1);return true;}return false;}//remove方法是一個比較重要的方法public boolean remove(int val) {if (map.containsKey(val)) {int valIndex = map.get(val);int endValue = list.get(list.size() - 1);map.put(endValue, valIndex);list.set(valIndex, endValue);map.remove(val);list.remove(list.size() - 1);return true;}return false;}public int getRandom() {int randIndex = (int) (Math.random() * list.size());return list.get(randIndex);}public static void main1(String[] args) {RandomizedSet randomizedSet = new RandomizedSet();randomizedSet.remove(0);randomizedSet.remove(0);randomizedSet.insert(0);int res = randomizedSet.getRandom();randomizedSet.remove(0);randomizedSet.insert(0);}
}

4. O(1)時間插入刪除隨機(不去重)

這個題目跟上一個題目只有一個不一樣的地方就是這個哈希表的val是我們的HashSet,也就是一個下標集合, 我們進行元素刪除的時候我們就隨意選擇一個待刪除元素的下標進行刪除即可, 我們的getRandom方法是用動態順序表的數據進行返回的, 所以自帶加權的功能, 代碼實現如下

class RandomizedCollection {// 這個其實原來的HashMap中的value不再是整數, 而是一個HashSet集合ArrayList<Integer> arr = new ArrayList<>();HashMap<Integer, HashSet<Integer>> map = new HashMap<>();public RandomizedCollection() {}//insert方法是比較簡單的, 就是直接放入元素即可public boolean insert(int val) {HashSet<Integer> set = map.get(val);if(set == null){HashSet<Integer> tempSet = new HashSet<>();tempSet.add(arr.size());map.put(val,tempSet);arr.add(val);return true;}else{set.add(arr.size());arr.add(val);return false;}}public boolean remove(int val) {HashSet<Integer> set = map.get(val);if(set == null){return false;}int indexValue = set.iterator().next();int swapValue = arr.get(arr.size() - 1);int swapIndex = arr.size() - 1;if(swapValue == val){arr.remove(arr.size() - 1);set.remove(arr.size());}else{HashSet<Integer> end = map.get(swapValue);end.remove(swapIndex);end.add(indexValue);set.remove(indexValue);arr.set(indexValue,swapValue);arr.remove(swapIndex);}if(set.size() == 0){map.remove(val);}return true;}public int getRandom() {return arr.get((int) (Math.random() * arr.size()));}
}/*** Your RandomizedCollection object will be instantiated and called as such:* RandomizedCollection obj = new RandomizedCollection();* boolean param_1 = obj.insert(val);* boolean param_2 = obj.remove(val);* int param_3 = obj.getRandom();*/

5. 快速獲取數據流中的中位數

該數據結構的實現就是通過我們的堆結構來實現的, 建立一個大根堆來裝入小半部分的數據, 建立一個小根堆來建立大半部分的數據, 記住在裝入數據的過程中我們要保持我們的堆中的元素的大小, 也就是通過一個balance方法, 來保持兩邊的數量差值不超過1, 獲取中位數的時候我們, 如果兩邊數量不一致, 就返回多的哪一方的堆頂, 如果一致, 我們就返回兩個堆頂的平均值, 代碼實現如下

class MedianFinder {private PriorityQueue<Integer> maxHeap = new PriorityQueue<>(new Comparator<Integer>() {@Overridepublic int compare(Integer o1, Integer o2) {return o2 - o1;}});// 默認就是小根堆private PriorityQueue<Integer> minHeap = new PriorityQueue<>();public MedianFinder() {}public void addNum(int num) {if (maxHeap.isEmpty() || num < maxHeap.peek()) {maxHeap.offer(num);} else {minHeap.offer(num);}balance();}public double findMedian() {if (minHeap.size() == maxHeap.size()) {return (minHeap.peek() + maxHeap.peek()) / 2.0;} else if (maxHeap.size() < minHeap.size()) {return minHeap.peek();} else {return maxHeap.peek();}}// 平衡堆結構的方法private void balance() {if (Math.abs(minHeap.size() - maxHeap.size()) == 2) {if (minHeap.size() - maxHeap.size() == 2) {maxHeap.offer(minHeap.poll());} else {minHeap.offer(maxHeap.poll());}}}
}/*** Your MedianFinder object will be instantiated and called as such:* MedianFinder obj = new MedianFinder();* obj.addNum(num);* double param_2 = obj.findMedian();

6. 最大頻率棧

這道題目的思路就是用兩個哈希表, 第一個哈希表存儲的是詞頻統計, 第二個哈希表是一個類似桶的結構, key就是出現的詞頻, val是一個動態的順序表, 代碼實現如下

class FreqStack {//本質就是通過哈希來模擬//哈希表的key是詞頻統計, val是一個動態的順序表, 里面存放這該詞頻的數字HashMap<Integer,ArrayList<Integer>> map = new HashMap<>();//再創建一個哈希表用于詞頻的統計HashMap<Integer,Integer> frq = new HashMap<>();//最大的詞頻(用于pop()操作指示)private int maxFrq = 0;public FreqStack() {//構造方法里面不寫東西}public void push(int val){//首先進行詞頻的統計frq.put(val,frq.getOrDefault(val,0) + 1);maxFrq = Math.max(maxFrq,frq.get(val));ArrayList res = map.get(frq.get(val));if(res == null){ArrayList<Integer> arr = new ArrayList<>();arr.add(val);map.put(frq.get(val),arr);}else{res.add(val);}}//pop方法的時候應該進行的元素的刪除操作public int pop() {ArrayList<Integer> arr = map.get(maxFrq);if(arr.size() == 1){int temp = arr.remove(0);map.remove(maxFrq--);if(frq.get(temp) == 1){frq.remove(temp);}else{frq.put(temp,frq.get(temp) - 1);}return temp;}else{int temp = arr.remove(arr.size() - 1);if(frq.get(temp) == 1){frq.remove(temp);}else{frq.put(temp,frq.get(temp) - 1);}return temp;}}
}/*** Your FreqStack object will be instantiated and called as such:* FreqStack obj = new FreqStack();* obj.push(val);* int param_2 = obj.pop();*/

7. 全O(1)結構

這個就是哈希表加上雙向鏈表桶的思路, 哈希表中保存的是該字符串的所在桶的地址, 桶里面存放的是該詞頻的字符串的情況, 代碼實現如下, 下面有一個LFU緩存也是這樣的一個結構, 雙向鏈表(桶), 桶里面再嵌套一個雙向鏈表實現的堆結構…

class RandomizedCollection {//這個其實原來的HashMap中的value不再是整數, 而是一個HashSet集合ArrayList<Integer> arr = new ArrayList<>();HashMap<Integer, HashSet<Integer>> map = new HashMap<>();public RandomizedCollection() {}//insert方法是比較簡單的, 就是直接放入元素即可public boolean insert(int val) {HashSet<Integer> set = map.get(val);if (set == null) {HashSet<Integer> tempSet = new HashSet<>();tempSet.add(arr.size());map.put(val, tempSet);arr.add(val);return true;} else {set.add(arr.size());arr.add(val);return false;}}public boolean remove(int val) {HashSet<Integer> set = map.get(val);if (set == null) {return false;}int indexValue = set.iterator().next();int swapValue = arr.get(arr.size() - 1);int swapIndex = arr.size() - 1;if (swapValue == val) {arr.remove(arr.size() - 1);set.remove(arr.size());} else {HashSet<Integer> end = map.get(swapValue);end.remove(swapIndex);end.add(indexValue);set.remove(indexValue);arr.set(indexValue, swapValue);arr.remove(swapIndex);}if (set.size() == 0) {map.remove(val);}return true;}public int getRandom() {return arr.get((int) (Math.random() * arr.size()));}public static void main(String[] args) {RandomizedCollection set = new RandomizedCollection();set.insert(1);set.remove(1);set.insert(1);}
}

8. LFU緩存結構

/*** LFU緩存 :* 1. 首先定義一個節點的對象, 里面保存的是該傳入數據的key和value(ListNode)* 這個東西也是一個雙向鏈表的結構(模擬隊列使用) --> 不可以用LinkedList(源碼的remove方法是遍歷刪除的結構)* 2. 其次我們定義一個桶結構, 里面有一個val用來保存操作的次數, 還有一個雙向的鏈表(也就是我們的上面定義的隊列結構)* 這個桶的結構也是類似于雙端的鏈表(模擬雙向鏈表使用)* 3. 然后我們需要定義兩個哈希表* 第一個HashMap中的val保存的是該數字的所在桶的地址(方便定位桶的位置進行操作)* 第二個HashMap中的val保存的是該數字本身的ListNode的地址(方便進行刪除操作)* 4. 返回使用量最小的元素就去最左邊的桶里面拿隊列中的first元素* 5. 桶的左右兩側我們定義了0操作次數, 以及Integer.MAX_VALUE桶, 減少了邊界位置的判斷*/class LFUCache {/*** 基礎的節點的元素定義*/static class Node {int key;int val;Node prev;Node next;public Node(int key, int val) {this.key = key;this.val = val;}}/*** 模擬的隊列的實現類*/static class MQueue {//屬性定義為這樣是為了和下面的桶結構區分開Node head;Node tail;int size;//無參數的構造方法public MQueue() {this.head = null;this.tail = null;}//remove方法用來移除掉指定位置的節點public Node remove(Node node) {if (head == null || tail == null) {throw new RuntimeException("沒有節點無法移動");}if (head == tail) {tail = null;head = null;} else if (node == this.head) {Node temp = this.head.next;this.head.next = null;this.head = temp;this.head.prev = null;} else if (node == tail) {Node temp = tail.prev;tail.prev = null;tail = temp;tail.next = null;} else {node.prev.next = node.next;node.next.prev = node.prev;node.next = null;node.prev = null;}size--;return node;}//下面是我們的pop方法public Node pop() {return remove(head);}//下面是我們的offer()方法public void offer(Node node) {if (head == null && tail == null) {head = node;tail = node;size++;return;}tail.next = node;node.prev = tail;tail = node;size++;}}/*** 下面我們要完成我們的桶結構的實現(桶結構的val是出現的次數, 桶結構里面有一個我們手寫的一個隊列結構)*/static class Bucket {//出現的頻率int time;//我們想要的隊列結構MQueue mQueue;//模擬雙向鏈表必須的實現Bucket prev;Bucket next;//構造方法public Bucket(int time) {this.time = time;mQueue = new MQueue();}}static class MBucket {//用作基石的兩個桶Bucket min = new Bucket(0);Bucket max = new Bucket(Integer.MAX_VALUE);public MBucket(){min.next = max;max.prev = min;}//桶的插入插入操作(cur是參照結構)public void insert(Bucket cur, Bucket pos) {cur.next.prev = pos;pos.next = cur.next;cur.next = pos;pos.prev = cur;}//桶的刪除操作public void remove(Bucket cur) {cur.prev.next = cur.next;cur.next.prev = cur.prev;}}//那個容量大小int capacity;//兩個重要的HashMap結構HashMap<Integer, Node> nodeIndexMap = new HashMap<>();HashMap<Integer, Bucket> bucketIndexMap = new HashMap<>();MBucket mBucket = new MBucket();public LFUCache(int capacity) {this.capacity = capacity;}public int get(int key) {if (!nodeIndexMap.containsKey(key)) {return -1;} else {Bucket curBucket = bucketIndexMap.get(key);Node curNode = nodeIndexMap.get(key);if (curBucket.next.time > curBucket.time + 1) {Bucket newBucket = new Bucket(curBucket.time + 1);mBucket.insert(curBucket, newBucket);curBucket.mQueue.remove(curNode);newBucket.mQueue.offer(curNode);} else {curBucket.mQueue.remove(curNode);curBucket.next.mQueue.offer(curNode);}bucketIndexMap.put(key, curBucket.next);//判斷先前的那個桶是不是空的(是空桶就刪掉)if (curBucket.mQueue.size == 0) {mBucket.remove(curBucket);}return curNode.val;}}public void put(int key, int value) {if (nodeIndexMap.containsKey(key)) {Node curNode = nodeIndexMap.get(key);Bucket curBucket = bucketIndexMap.get(key);curNode.val = value;if (curBucket.next.time > curBucket.time + 1) {Bucket newBucket = new Bucket(curBucket.time + 1);mBucket.insert(curBucket, newBucket);curBucket.mQueue.remove(curNode);newBucket.mQueue.offer(curNode);} else {curBucket.mQueue.remove(curNode);curBucket.next.mQueue.offer(curNode);}bucketIndexMap.put(key, curBucket.next);//判斷先前的那個桶是不是空的(是空桶就刪掉)if (curBucket.mQueue.size == 0) {mBucket.remove(curBucket);}} else {Node newNode = new Node(key, value);if (nodeIndexMap.size() < capacity) {if (mBucket.min.next.time != 1) {Bucket newBucket = new Bucket(1);newBucket.mQueue.offer(newNode);mBucket.insert(mBucket.min, newBucket);nodeIndexMap.put(key, newNode);bucketIndexMap.put(key, newBucket);} else {Bucket oneBucket = mBucket.min.next;oneBucket.mQueue.offer(newNode);nodeIndexMap.put(key, newNode);bucketIndexMap.put(key, oneBucket);}} else {Node removeNode = mBucket.min.next.mQueue.pop();nodeIndexMap.remove(removeNode.key);bucketIndexMap.remove(removeNode.key);if(mBucket.min.next.mQueue.size == 0){mBucket.remove(mBucket.min.next);}if(mBucket.min.next.time != 1){Bucket newBucket = new Bucket(1);newBucket.mQueue.offer(newNode);mBucket.insert(mBucket.min, newBucket);nodeIndexMap.put(key, newNode);bucketIndexMap.put(key, newBucket);}else{Bucket oneBucket = mBucket.min.next;oneBucket.mQueue.offer(newNode);nodeIndexMap.put(key, newNode);bucketIndexMap.put(key, oneBucket);}}}}public static void main(String[] args) {LFUCache lfu = new LFUCache(2);lfu.put(1,1);lfu.put(2,2);lfu.get(1);lfu.put(3,3);lfu.get(2);lfu.get(3);lfu.put(4,4);lfu.get(1);lfu.get(3);lfu.get(4);}
}