塘沽建設(shè)網(wǎng)站北京網(wǎng)站開發(fā)
1. LRU緩存
請(qǐng)你設(shè)計(jì)并實(shí)現(xiàn)一個(gè)滿足??LRU (最近最少使用) 緩存?約束的數(shù)據(jù)結(jié)構(gòu)。
實(shí)現(xiàn)?LRUCache?類：
LRUCache(int capacity)?以?正整數(shù)?作為容量?capacity?初始化 LRU 緩存int get(int key)?如果關(guān)鍵字?key?存在于緩存中，則返回關(guān)鍵字的值，否則返回?-1?。void put(int key, int value)?如果關(guān)鍵字?key?已經(jīng)存在，則變更其數(shù)據(jù)值?value?；如果不存在，則向緩存中插入該組?key-value?。如果插入操作導(dǎo)致關(guān)鍵字?jǐn)?shù)量超過?capacity?，則應(yīng)該?逐出?最久未使用的關(guān)鍵字。
函數(shù)?get?和?put?必須以?O(1)?的平均時(shí)間復(fù)雜度運(yùn)行。
示例：
輸入
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
輸出
[null, null, null, 1, null, -1, null, -1, 3, 4]解釋
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // 緩存是 {1=1}
lRUCache.put(2, 2); // 緩存是 {1=1, 2=2}
lRUCache.get(1); // 返回 1
lRUCache.put(3, 3); // 該操作會(huì)使得關(guān)鍵字 2 作廢，緩存是 {1=1, 3=3}
lRUCache.get(2); // 返回 -1 (未找到)
lRUCache.put(4, 4); // 該操作會(huì)使得關(guān)鍵字 1 作廢，緩存是 {4=4, 3=3}
lRUCache.get(1); // 返回 -1 (未找到)
lRUCache.get(3); // 返回 3
lRUCache.get(4); // 返回 4
提示：
1 <= capacity <= 30000 <= key <= 100000 <= value <= 10^5- 最多調(diào)用?
2 * 10^5?次?get?和?put
解法一：LinkedHashMap
import java.util.LinkedHashMap;
import java.util.Map; class LRUCache { private int capacity; private LinkedHashMap<Integer, Integer> cache; public LRUCache(int capacity) { this.capacity = capacity; this.cache = new LinkedHashMap<>(capacity, 0.75f, true) { @Override protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) { // 當(dāng)緩存容量超過capacity時(shí)自動(dòng)移除最近最少使用的元素return size() > capacity; } }; } public int get(int key) { if (!cache.containsKey(key)) { return -1; } // 訪問key后將其移到最前面 return cache.get(key); } public void put(int key, int value) { cache.put(key, value); }
} /** * Your LRUCache object will be instantiated and called as such: * LRUCache obj = new LRUCache(capacity); * int param_1 = obj.get(key); * obj.put(key,value); */解法二：自定義節(jié)點(diǎn)類 + 自定義雙端隊(duì)列
- map中存儲(chǔ)node，可以省去在雙向鏈表中查找node的時(shí)間，這樣讓使用最近訪問的節(jié)點(diǎn)移動(dòng)到鏈表頭時(shí)達(dá)到O(1)的需求
class LRUCache {static class Node {Node prev;Node next;int key;int value;public Node() {}public Node(int key, int value) {this.key = key;this.value = value;}}// 雙向鏈表static class DoubleLinkedList {Node head;Node tail;public DoubleLinkedList() {head = tail = new Node();head.next = tail;tail.prev = head;}// 頭部添加public void addFirst(Node newFirst) {Node oldFirst = head.next;newFirst.next = oldFirst;newFirst.prev = head;head.next = newFirst;oldFirst.prev = newFirst;}// 已知節(jié)點(diǎn)刪除public void remove(Node node) {Node prev = node.prev;Node next = node.next;prev.next = next;next.prev = prev;}// 尾部刪除public Node removeLast() {Node last = tail.prev;remove(last);return last;}}private int capacity;private final HashMap<Integer, Node> map = new HashMap<>();private final DoubleLinkedList list = new DoubleLinkedList();public LRUCache(int capacity) {this.capacity = capacity;}public int get(int key) {if(!map.containsKey(key)) {return -1;}Node node = map.get(key);list.remove(node);list.addFirst(node);return node.value;}public void put(int key, int value) {if(map.containsKey(key)) {// 更新Node node = map.get(key);node.value = value;list.remove(node);list.addFirst(node);} else {// 新增Node node = new Node(key, value);map.put(key, node);list.addFirst(node);if(map.size() > capacity) {Node removed = list.removeLast();map.remove(removed.key);}}}
}2. LFU緩存
請(qǐng)你為?最不經(jīng)常使用（LFU）緩存算法設(shè)計(jì)并實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)。
實(shí)現(xiàn)?LFUCache?類：
LFUCache(int capacity)?- 用數(shù)據(jù)結(jié)構(gòu)的容量?capacity?初始化對(duì)象int get(int key)?- 如果鍵?key?存在于緩存中，則獲取鍵的值，否則返回?-1?。void put(int key, int value)?- 如果鍵?key?已存在，則變更其值；如果鍵不存在，請(qǐng)插入鍵值對(duì)。當(dāng)緩存達(dá)到其容量?capacity?時(shí)，則應(yīng)該在插入新項(xiàng)之前，移除最不經(jīng)常使用的項(xiàng)。在此問題中，當(dāng)存在平局（即兩個(gè)或更多個(gè)鍵具有相同使用頻率）時(shí)，應(yīng)該去除?最久未使用?的鍵。
為了確定最不常使用的鍵，可以為緩存中的每個(gè)鍵維護(hù)一個(gè)?使用計(jì)數(shù)器?。使用計(jì)數(shù)最小的鍵是最久未使用的鍵。
當(dāng)一個(gè)鍵首次插入到緩存中時(shí)，它的使用計(jì)數(shù)器被設(shè)置為?1?(由于 put 操作)。對(duì)緩存中的鍵執(zhí)行?get?或?put?操作，使用計(jì)數(shù)器的值將會(huì)遞增。
函數(shù)?get?和?put?必須以?O(1)?的平均時(shí)間復(fù)雜度運(yùn)行。
示例：
輸入： ["LFUCache", "put", "put", "get", "put", "get", "get", "put", "get", "get", "get"] [[2], [1, 1], [2, 2], [1], [3, 3], [2], [3], [4, 4], [1], [3], [4]] 輸出： [null, null, null, 1, null, -1, 3, null, -1, 3, 4]解釋： // cnt(x) = 鍵 x 的使用計(jì)數(shù) // cache=[] 將顯示最后一次使用的順序（最左邊的元素是最近的） LFUCache lfu = new LFUCache(2); lfu.put(1, 1); // cache=[1,_], cnt(1)=1 lfu.put(2, 2); // cache=[2,1], cnt(2)=1, cnt(1)=1 lfu.get(1); // 返回 1// cache=[1,2], cnt(2)=1, cnt(1)=2 lfu.put(3, 3); // 去除鍵 2 ，因?yàn)?cnt(2)=1 ，使用計(jì)數(shù)最小// cache=[3,1], cnt(3)=1, cnt(1)=2 lfu.get(2); // 返回 -1（未找到） lfu.get(3); // 返回 3// cache=[3,1], cnt(3)=2, cnt(1)=2 lfu.put(4, 4); // 去除鍵 1 ，1 和 3 的 cnt 相同，但 1 最久未使用// cache=[4,3], cnt(4)=1, cnt(3)=2 lfu.get(1); // 返回 -1（未找到） lfu.get(3); // 返回 3// cache=[3,4], cnt(4)=1, cnt(3)=3 lfu.get(4); // 返回 4// cache=[3,4], cnt(4)=2, cnt(3)=3
提示：
1 <= capacity?<= 10^40 <= key <= 10^50 <= value <= 10^9- 最多調(diào)用?
2 * 10^5?次?get?和?put?方法
解法一：
class LFUCache {static class Node {Node prev;Node next;int key;int value;int freq;public Node() {}public Node(int key, int value, int freq) {this.key = key;this.value = value;this.freq = freq;}}static class DoubleLinkedList {private final Node head;private final Node tail;int size = 0;public DoubleLinkedList() {head = tail = new Node();head.next = tail;tail.prev = head;}public void remove(Node node) {Node prev = node.prev;Node next = node.next;prev.next = next;next.prev = prev;node.prev = node.next = null;size--;}public void addFirst(Node newFirst) {Node oldFirst = head.next;newFirst.prev = head;newFirst.next = oldFirst;head.next = newFirst;oldFirst.prev = newFirst;size++;}public Node removeLast() {Node last = tail.prev;remove(last);return last;}public boolean isEmpty() {return size == 0;}}// 頻度鏈表private final HashMap<Integer, DoubleLinkedList> freqMap = new HashMap<>();// key和value鏈表private final HashMap<Integer, Node> kvMap = new HashMap<>();private final int capacity;private int minFreq = 1; // 最小頻度public LFUCache(int capacity) {this.capacity = capacity;}/*key不存在，返回-1key存在，返回value值，增加節(jié)點(diǎn)的使用頻度，將其轉(zhuǎn)移到頻度+1的鏈表當(dāng)中*/public int get(int key) {if(!kvMap.containsKey(key)) {return -1;}// 將節(jié)點(diǎn)頻度+1，從舊鏈表轉(zhuǎn)移至新鏈表Node node = kvMap.get(key);// 先刪freqMap.get(node.freq).remove(node);if(freqMap.get(node.freq).isEmpty() && node.freq == minFreq) {minFreq++;}node.freq++;/*DoubleLinkedList list = freqMap.get(node.freq);// 后加if(list == null) {list = new DoubleLinkedList();freqMap.put(node.freq, list);}list.addFirst(node);*/freqMap.computeIfAbsent(node.freq, k -> new DoubleLinkedList()).addFirst(node);return node.value;}/*更新：將節(jié)點(diǎn)的value更新，增加節(jié)點(diǎn)的使用頻度，將其轉(zhuǎn)移到頻度+1的鏈表當(dāng)中新增：檢查是否超過容量，若超過，淘汰minFreq鏈表的最后節(jié)點(diǎn)。創(chuàng)建新節(jié)點(diǎn)，放入kvMap，并加入頻度為1的雙向鏈表*/public void put(int key, int value) {if(kvMap.containsKey(key)) {// 更新Node node = kvMap.get(key);freqMap.get(node.freq).remove(node);if(freqMap.get(node.freq).isEmpty() && node.freq == minFreq) {minFreq++;}node.freq++;freqMap.computeIfAbsent(node.freq, k -> new DoubleLinkedList()).addFirst(node);node.value = value;} else {// 新增if(kvMap.size() == capacity) {Node last = freqMap.get(minFreq).removeLast();kvMap.remove(last.key);}Node node = new Node(key, value, 1);kvMap.put(key, node);minFreq = 1;freqMap.computeIfAbsent(node.freq, k -> new DoubleLinkedList()).addFirst(node);}}
}/*** Your LFUCache object will be instantiated and called as such:* LFUCache obj = new LFUCache(capacity);* int param_1 = obj.get(key);* obj.put(key,value);*/3. 隨機(jī)數(shù)
3.1 線性同余發(fā)生器
- 公式：nextSeed = (seed * a + c) % m
- 32位隨機(jī)數(shù)生成器
- 乘法會(huì)超過int范圍導(dǎo)致隨機(jī)性被破壞
package com.itheima.algorithms.leetcode;import java.util.Arrays;
import java.util.stream.IntStream;/*線性同余發(fā)生器*/
public class MyRandom {private final int a;private final int c;private final int m;private int seed;public MyRandom(int a, int c, int m, int seed) {this.a = a;this.c = c;this.m = m;this.seed = seed;}public int nextInt() {return seed = (a * seed + c) % m;}public static void main(String[] args) {MyRandom r1 = new MyRandom(7, 0, 11, 1);System.out.println(Arrays.toString(IntStream.generate(r1::nextInt).limit(30).toArray()));MyRandom r2 = new MyRandom(7, 0, Integer.MAX_VALUE, 1);System.out.println(Arrays.toString(IntStream.generate(r2::nextInt).limit(30).toArray()));}
}
3.2 Java版
- 0x5DEECE66DL * 0x5DEECE66DL 不會(huì)超過 long 的范圍
- m決定只取48位隨機(jī)數(shù)
- 對(duì)于nextInt，只取48位隨機(jī)數(shù)的高32位
package com.itheima.algorithms.leetcode;import java.util.Arrays;
import java.util.Random;
import java.util.stream.IntStream;public class MyRandom2 {private static final long a = 0x5DEECE66DL;private static final long c = 0xBL;private static final long m = 1L << 48;private long seed;public MyRandom2(long seed) {this.seed = (seed ^ a) & (m - 1);}public int nextInt() {seed = (a * seed + c) & (m - 1);return ((int) (seed >>> 16));}public static void main(String[] args) {Random r1 = new Random(1);MyRandom2 r2 = new MyRandom2(1);System.out.println(Arrays.toString(IntStream.generate(r1::nextInt).limit(10).toArray()));System.out.println(Arrays.toString(IntStream.generate(r2::nextInt).limit(10).toArray()));}
}
4. 跳表
4.1 randomLevel
設(shè)計(jì)一個(gè)方法調(diào)用若干次，每次返回 1~max 的數(shù)字，從 1 開始，返回?cái)?shù)字的比例減半，例如 max = 4，讓大概
-
50% 的幾率返回 1
-
25% 的幾率返回 2
-
12.5% 的幾率返回 3
-
12.5% 的幾率返回 4
package com.itheima.algorithms.leetcode;import java.util.HashMap;
import java.util.Map;
import java.util.Random;
import java.util.stream.Collectors;/*跳表*/
public class SkipList {public static void main(String[] args) {HashMap<Integer, Integer> map = new HashMap<>();for (int i = 0; i < 1000; i++) {int level = randomLevel(4);map.compute(level, (k, v) -> v == null ? 1 : v + 1);}System.out.println(map.entrySet().stream().collect(Collectors.toMap(Map.Entry::getKey,e -> String.format("%d%%", e.getValue() * 100 / 1000))));}/*設(shè)計(jì)一個(gè)方法，方法會(huì)隨機(jī)返回 1 ~ max的數(shù)字從1開始，數(shù)字的幾率逐級(jí)減半，例如max = 4，讓大概- 50% 的幾率返回1- 25% 的幾率返回2- 12.5% 的幾率返回3- 12.5% 的幾率返回4*/static Random r = new Random();static int randomLevel(int max) {// return r.nextBoolean() ? 1 : r.nextBoolean() ? 2 : r.nextBoolean() ? 3 : 4;int x = 1;while(x < max) {if(r.nextBoolean()) {return x;}x++;}return x;}}
4.2 跳表
下樓梯規(guī)則：
- 若next指針為null，或者next指向的節(jié)點(diǎn)值 >= 目標(biāo)，向下找
- 若next指針不為null，且next指向的節(jié)點(diǎn)值 < 目標(biāo)，向右找
節(jié)點(diǎn)的【高度】
- 高度并不需要額外屬性來記錄，而是由之前節(jié)點(diǎn)next == 本節(jié)點(diǎn)的個(gè)數(shù)來決定，或是本節(jié)點(diǎn)next數(shù)組長(zhǎng)度
- 本實(shí)現(xiàn)選擇了第一種方式來決定高度，本節(jié)點(diǎn)的next數(shù)組長(zhǎng)度統(tǒng)一為MAX
4.3 設(shè)計(jì)跳表
不使用任何庫(kù)函數(shù)，設(shè)計(jì)一個(gè)?跳表?。
跳表?是在?O(log(n))?時(shí)間內(nèi)完成增加、刪除、搜索操作的數(shù)據(jù)結(jié)構(gòu)。跳表相比于樹堆與紅黑樹，其功能與性能相當(dāng)，并且跳表的代碼長(zhǎng)度相較下更短，其設(shè)計(jì)思想與鏈表相似。
例如，一個(gè)跳表包含?[30, 40, 50, 60, 70, 90]?，然后增加?80、45?到跳表中，以下圖的方式操作：
跳表中有很多層，每一層是一個(gè)短的鏈表。在第一層的作用下，增加、刪除和搜索操作的時(shí)間復(fù)雜度不超過?O(n)。跳表的每一個(gè)操作的平均時(shí)間復(fù)雜度是?O(log(n))，空間復(fù)雜度是?O(n)。
了解更多 :?跳表 - OI Wiki
在本題中，你的設(shè)計(jì)應(yīng)該要包含這些函數(shù)：
bool search(int target)?: 返回target是否存在于跳表中。void add(int num):?插入一個(gè)元素到跳表。bool erase(int num): 在跳表中刪除一個(gè)值，如果?num?不存在，直接返回false. 如果存在多個(gè)?num?，刪除其中任意一個(gè)即可。
注意，跳表中可能存在多個(gè)相同的值，你的代碼需要處理這種情況。
示例 1:
輸入 ["Skiplist", "add", "add", "add", "search", "add", "search", "erase", "erase", "search"] [[], [1], [2], [3], [0], [4], [1], [0], [1], [1]] 輸出 [null, null, null, null, false, null, true, false, true, false]解釋 Skiplist skiplist = new Skiplist(); skiplist.add(1); skiplist.add(2); skiplist.add(3); skiplist.search(0); // 返回 false skiplist.add(4); skiplist.search(1); // 返回 true skiplist.erase(0); // 返回 false，0 不在跳表中 skiplist.erase(1); // 返回 true skiplist.search(1); // 返回 false，1 已被擦除
提示:
0 <= num, target <= 2 * 10^4- 調(diào)用
search,?add, ?erase操作次數(shù)不大于?5 * 10^4?
class Skiplist {static Random r = new Random();static int randomLevel(int max) {int x = 1;while (x < max) {if (r.nextBoolean()) {return x;}x++;}return x;}private static final int MAX = 16; // redis 32 java 62private final Node head = new Node(-1);static class Node {int val; // 值Node[] next = new Node[MAX]; // next指針數(shù)組public Node(int val) {this.val = val;}@Overridepublic String toString() {return "Node(" + val + ")";}}public Skiplist() {}public Node[] find(int target) {Node[] path = new Node[MAX];Node curr = head;for (int level = MAX - 1; level >= 0; level--) { // 從下向下找while (curr.next[level] != null && curr.next[level].val < target) { // 向右找curr = curr.next[level];}path[level] = curr;}return path;}public boolean search(int target) {Node[] path = find(target);Node node = path[0].next[0];return node != null && node.val == target;}public void add(int num) {// 1. 確定添加位置Node[] path = find(num);// 2. 創(chuàng)建新節(jié)點(diǎn)隨機(jī)高度Node node = new Node(num);int level = randomLevel(MAX);// 3. 修改路徑節(jié)點(diǎn)next指針，以及新結(jié)點(diǎn)next指針for (int i = 0; i < level; i++) {node.next[i] = path[i].next[i];path[i].next[i] = node;}}public boolean erase(int num) {// 1. 確定刪除位置Node[] path = find(num);Node node = path[0].next[0];if (node == null || node.val != num) {return false;}for (int i = 0; i < MAX; i++) {if (path[i].next[i] != node) {break;}path[i].next[i] = node.next[i];}return true;}
}5. 最小棧
設(shè)計(jì)一個(gè)支持?push?，pop?，top?操作，并能在常數(shù)時(shí)間內(nèi)檢索到最小元素的棧。
實(shí)現(xiàn)?MinStack?類:
MinStack()?初始化堆棧對(duì)象。void push(int val)?將元素val推入堆棧。void pop()?刪除堆棧頂部的元素。int top()?獲取堆棧頂部的元素。int getMin()?獲取堆棧中的最小元素。
示例 1:
輸入： ["MinStack","push","push","push","getMin","pop","top","getMin"] [[],[-2],[0],[-3],[],[],[],[]]輸出： [null,null,null,null,-3,null,0,-2]解釋： MinStack minStack = new MinStack(); minStack.push(-2); minStack.push(0); minStack.push(-3); minStack.getMin(); --> 返回 -3. minStack.pop(); minStack.top(); --> 返回 0. minStack.getMin(); --> 返回 -2.
提示：
-2^31?<= val <= 2^31?- 1pop、top?和?getMin?操作總是在?非空棧?上調(diào)用push,?pop,?top, and?getMin最多被調(diào)用?3 * 10^4?次
解法一：
class MinStack {LinkedList<Integer> stack = new LinkedList<>();LinkedList<Integer> min = new LinkedList<>();public MinStack() {min.push(Integer.MAX_VALUE);}public void push(int val) {stack.push(val);min.push(Math.min(val, min.peek()));}public void pop() {if (stack.isEmpty()) {return;}stack.pop();min.pop();}public int top() {return stack.peek();}public int getMin() {return min.peek();}
}6. TinyURL的加密與解密
TinyURL 是一種 URL 簡(jiǎn)化服務(wù)， 比如：當(dāng)你輸入一個(gè) URL?https://leetcode.com/problems/design-tinyurl?時(shí)，它將返回一個(gè)簡(jiǎn)化的URL?http://tinyurl.com/4e9iAk?。請(qǐng)你設(shè)計(jì)一個(gè)類來加密與解密 TinyURL 。
加密和解密算法如何設(shè)計(jì)和運(yùn)作是沒有限制的，你只需要保證一個(gè) URL 可以被加密成一個(gè) TinyURL ，并且這個(gè) TinyURL 可以用解密方法恢復(fù)成原本的 URL 。
實(shí)現(xiàn)?Solution?類：
Solution()?初始化 TinyURL 系統(tǒng)對(duì)象。String encode(String longUrl)?返回?longUrl?對(duì)應(yīng)的 TinyURL 。String decode(String shortUrl)?返回?shortUrl?原本的 URL 。題目數(shù)據(jù)保證給定的?shortUrl?是由同一個(gè)系統(tǒng)對(duì)象加密的。
示例：
輸入：url = "https://leetcode.com/problems/design-tinyurl" 輸出："https://leetcode.com/problems/design-tinyurl"解釋： Solution obj = new Solution(); string tiny = obj.encode(url); // 返回加密后得到的 TinyURL 。 string ans = obj.decode(tiny); // 返回解密后得到的原本的 URL 。
提示：
1 <= url.length <= 10^4- 題目數(shù)據(jù)保證?
url?是一個(gè)有效的 URL
解法一：
要讓【長(zhǎng)】【短】網(wǎng)址一一對(duì)應(yīng) 1. 用【隨機(jī)數(shù)】作為短網(wǎng)址標(biāo)識(shí) 2. 用【hash碼】作為短網(wǎng)址標(biāo)識(shí) 3. 用【遞增數(shù)】作為短網(wǎng)址標(biāo)識(shí)
public class TinyURLLeetcode535 {public static void main(String[] args) {/*CodecSequence codec = new CodecSequence();String encoded = codec.encode("https://leetcode.cn/problems/1");System.out.println(encoded);encoded = codec.encode("https://leetcode.cn/problems/2");System.out.println(encoded);*/
// for (int i = 0; i <= 62; i++) {
// System.out.println(i + "\t" + CodecSequence.toBase62(i));
// }System.out.println(CodecSequence.toBase62(237849728));}/*要讓【長(zhǎng)】【短】網(wǎng)址一一對(duì)應(yīng)1. 用【隨機(jī)數(shù)】作為短網(wǎng)址標(biāo)識(shí)2. 用【hash碼】作為短網(wǎng)址標(biāo)識(shí)3. 用【遞增數(shù)】作為短網(wǎng)址標(biāo)識(shí)1) 多線程下可以使用嗎？2) 分布式下可以使用嗎？3) 4e9iAk 是怎么生成的？a-z 0-9 A-Z 62進(jìn)制的數(shù)字0 1 2 3 4 5 6 7 8 9 a b c d e f十進(jìn)制 => 十六進(jìn)制31 1f31 % 16 = 1531 / 16 = 11 % 16 = 11 / 16 = 0長(zhǎng)網(wǎng)址： https://leetcode.cn/problems/encode-and-decode-tinyurl/description/對(duì)應(yīng)的短網(wǎng)址： http://tinyurl.com/4e9iAk*/static class CodecSequence {private static final char[] toBase62 = {'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M','N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z','a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm','n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z','0', '1', '2', '3', '4', '5', '6', '7', '8', '9'};public static String toBase62(int number) {if (number == 0) {return String.valueOf(toBase62[0]);}StringBuilder sb = new StringBuilder();while (number > 0) {int r = number % 62;sb.append(toBase62[r]);number = number / 62;}return sb.toString();}private final Map<String, String> longToShort = new HashMap<>();private final Map<String, String> shortToLong = new HashMap<>();private static final String SHORT_PREFIX = "http://tinyurl.com/";private static int id = 1;public String encode(String longUrl) {String shortUrl = longToShort.get(longUrl);if (shortUrl != null) {return shortUrl;}// 生成短網(wǎng)址shortUrl = SHORT_PREFIX + id;longToShort.put(longUrl, shortUrl);shortToLong.put(shortUrl, longUrl);id++;return shortUrl;}public String decode(String shortUrl) {return shortToLong.get(shortUrl);}}static class CodecHashCode {private final Map<String, String> longToShort = new HashMap<>();private final Map<String, String> shortToLong = new HashMap<>();private static final String SHORT_PREFIX = "http://tinyurl.com/";public String encode(String longUrl) {String shortUrl = longToShort.get(longUrl);if (shortUrl != null) {return shortUrl;}// 生成短網(wǎng)址int id = longUrl.hashCode(); // intwhile (true) {shortUrl = SHORT_PREFIX + id;if (!shortToLong.containsKey(shortUrl)) {longToShort.put(longUrl, shortUrl);shortToLong.put(shortUrl, longUrl);break;}id++;}return shortUrl;}public String decode(String shortUrl) {return shortToLong.get(shortUrl);}}static class CodecRandom {private final Map<String, String> longToShort = new HashMap<>();private final Map<String, String> shortToLong = new HashMap<>();private static final String SHORT_PREFIX = "http://tinyurl.com/";public String encode(String longUrl) {String shortUrl = longToShort.get(longUrl);if (shortUrl != null) {return shortUrl;}// 生成短網(wǎng)址while (true) {int id = ThreadLocalRandom.current().nextInt();// 1shortUrl = SHORT_PREFIX + id;if (!shortToLong.containsKey(shortUrl)) {longToShort.put(longUrl, shortUrl);shortToLong.put(shortUrl, longUrl);break;}}return shortUrl;}public String decode(String shortUrl) {return shortToLong.get(shortUrl);}}
}7. 設(shè)計(jì)Twitter
設(shè)計(jì)一個(gè)簡(jiǎn)化版的推特(Twitter)，可以讓用戶實(shí)現(xiàn)發(fā)送推文，關(guān)注/取消關(guān)注其他用戶，能夠看見關(guān)注人（包括自己）的最近?10?條推文。
實(shí)現(xiàn)?Twitter?類：
Twitter()?初始化簡(jiǎn)易版推特對(duì)象void postTweet(int userId, int tweetId)?根據(jù)給定的?tweetId?和?userId?創(chuàng)建一條新推文。每次調(diào)用此函數(shù)都會(huì)使用一個(gè)不同的?tweetId?。List<Integer> getNewsFeed(int userId)?檢索當(dāng)前用戶新聞推送中最近??10?條推文的 ID 。新聞推送中的每一項(xiàng)都必須是由用戶關(guān)注的人或者是用戶自己發(fā)布的推文。推文必須?按照時(shí)間順序由最近到最遠(yuǎn)排序?。void follow(int followerId, int followeeId)?ID 為?followerId?的用戶開始關(guān)注 ID 為?followeeId?的用戶。void unfollow(int followerId, int followeeId)?ID 為?followerId?的用戶不再關(guān)注 ID 為?followeeId?的用戶。
示例：
輸入 ["Twitter", "postTweet", "getNewsFeed", "follow", "postTweet", "getNewsFeed", "unfollow", "getNewsFeed"] [[], [1, 5], [1], [1, 2], [2, 6], [1], [1, 2], [1]] 輸出 [null, null, [5], null, null, [6, 5], null, [5]]解釋 Twitter twitter = new Twitter(); twitter.postTweet(1, 5); // 用戶 1 發(fā)送了一條新推文 (用戶 id = 1, 推文 id = 5) twitter.getNewsFeed(1); // 用戶 1 的獲取推文應(yīng)當(dāng)返回一個(gè)列表，其中包含一個(gè) id 為 5 的推文 twitter.follow(1, 2); // 用戶 1 關(guān)注了用戶 2 twitter.postTweet(2, 6); // 用戶 2 發(fā)送了一個(gè)新推文 (推文 id = 6) twitter.getNewsFeed(1); // 用戶 1 的獲取推文應(yīng)當(dāng)返回一個(gè)列表，其中包含兩個(gè)推文，id 分別為 -> [6, 5] 。推文 id 6 應(yīng)當(dāng)在推文 id 5 之前，因?yàn)樗窃?5 之后發(fā)送的 twitter.unfollow(1, 2); // 用戶 1 取消關(guān)注了用戶 2 twitter.getNewsFeed(1); // 用戶 1 獲取推文應(yīng)當(dāng)返回一個(gè)列表，其中包含一個(gè) id 為 5 的推文。因?yàn)橛脩?1 已經(jīng)不再關(guān)注用戶 2
提示：
1 <= userId, followerId, followeeId <= 5000 <= tweetId <= 10^4- 所有推特的 ID 都互不相同
postTweet、getNewsFeed、follow?和?unfollow?方法最多調(diào)用?3 * 10^4?次
解法一：
class Twitter {// 文章類static class Tweet {int id;int time;Tweet next;public Tweet(int id, int time, Tweet next) {this.id = id;this.time = time;this.next = next;}public int getId() {return id;}public int getTime() {return time;}}// 用戶類static class User {int id;Set<Integer> followees = new HashSet<>();Tweet head = new Tweet(-1, -1, null);public User(int id) {this.id = id;}}private final Map<Integer, User> userMap = new HashMap<>();private static int time;public Twitter() {}// 發(fā)布文章public void postTweet(int userId, int tweetId) {User user = userMap.computeIfAbsent(userId, User::new);user.head.next = new Tweet(tweetId, time++, user.head.next);}// 獲取最新10篇文章（包括自己和關(guān)注者)public List<Integer> getNewsFeed(int userId) {// 思路：合并k個(gè)有序鏈表User user = userMap.get(userId);if(user == null) {return List.of();}PriorityQueue<Tweet> queue = new PriorityQueue<>(Comparator.comparingInt(Tweet::getTime).reversed());if(user.head.next != null) {queue.offer(user.head.next);}for (Integer id : user.followees) {User followee = userMap.get(id);if(followee.head.next != null) {queue.offer(followee.head.next);}}List<Integer> res = new ArrayList<>();int count = 0;while(!queue.isEmpty() && count < 10) {Tweet max = queue.poll();res.add(max.id);if(max.next != null) {queue.offer(max.next);}count++;}return res;}// 新增關(guān)注public void follow(int followerId, int followeeId) {User follower = userMap.computeIfAbsent(followerId, User::new);User followee = userMap.computeIfAbsent(followeeId, User::new);follower.followees.add(followee.id);}// 取消關(guān)注public void unfollow(int followerId, int followeeId) {User user = userMap.get(followerId);if(user != null) {user.followees.remove(followeeId);}}
}/*** Your Twitter object will be instantiated and called as such:* Twitter obj = new Twitter();* obj.postTweet(userId,tweetId);* List<Integer> param_2 = obj.getNewsFeed(userId);* obj.follow(followerId,followeeId);* obj.unfollow(followerId,followeeId);*/