Design (Java) - ShuweiLeung/Thinking GitHub Wiki

1.（146:Hard）（非常非常经典题）LRU Cache

  • The problem can be solved with a hashtable that keeps track of the keys and its values in the double linked list. One interesting property about double linked list is that the node can remove itself without other reference(从而可以保证在O(1)时间复杂度内完成结点的删除，可以直接得到当前结点的前一个结点引用). In addition, it takes constant time to add and remove nodes from the head or tail.
  • One particularity about the double linked list that I implemented is that I create a pseudo head and tail to mark the boundary, so that we don't need to check the NULL node during the update. This makes the code more concise and clean, and also it is good for the performance as well.
  • 总结起来，用一个Map来存储key和对应的value结点引用（从而在get的时候直接获取结点的引用进行O(1)时间复杂度的操作），用一个自己构建的双向链表存储所有的结点。注意，每次操作完一个结点以后，都应该将其move至head双向链表的头部，因为它是最近使用的。

2.（432:Hard）（非常非常经典题）All O`one Data Structure

  • 这道题让我们实现一个全是O(1)复杂度的数据结构，包括了增加key，减少key，获取最大key，获取最小key，这几个函数。由于需要常数级的时间复杂度，我们首先第一反应就是要用哈希表来做，不仅如此，我们肯定还需要用list来保存所有的key，那么哈希表就是建立key和list中位置迭代器之间的映射，这不由得令人想到了之前那道LRU Cache，也是用了类似的方法来解，但是感觉此题还要更加复杂一些。由于每个key还要对应一个次数，所以list中不能只放key，而且相同的次数可能会对应多个key值，所以我们用set来保存次数相同的所有key值，我们建立在Java中使用两个Map（map和vals）来分别保存key及次数val，和保存value值的及对应key值的元素集合。解题思路主要是，我们建立一个次数分层的结构，次数多的在顶层，每一层放相同次数的key值，例如下面这个例子：

"A": 4, "B": 4, "C": 2, "D": 1

那么用我们设计的结构保存出来就是：

row0: val = 4, keys = {"A", "B"}
row1: val = 2, keys = {"C"}
row2: val = 1, keys = {"D"}

好，我们现在来分析如何实现inc函数，我们来想，如果我们插入一个新的key，跟我们插入一个已经存在的key，情况是完全不一样的，那么我们就需要分情况来讨论:

  • 如果我们插入一个新的key，那么由于该key没有出现过，所以加入后次数一定为1，那么就有两种情况了，如果map中没有val为1的这一行，那么我们需要插入该行，如果已经有了val为1的这行，我们直接将key加入集合vals中即可。

  • 如果我们插入了一个已存在的key，那么由于个数增加了1个，所以该key值肯定不能在当前行继续待下去了，要往上升职啊，那么这里就有两种情况了，如果该key要升职到的那行不存在，我们需要手动添加那一行；如果那一行存在，我们之间将key加入集合vals中，记得都要将原来行中的key值删掉。

下面我们再来看dec函数如何实现，其实理解了上面的inc函数，那么dec函数也就没什么难度了：

  • 如果我们要删除的key不存在，那么直接返回即可。

  • 如果我们要删除的key存在，那么我们看其val值是否为1，如果为1的话，那么直接在vals中删除该key即可，然后还需要判断如果该key是集合中的唯一一个，那么该行也需要删除。如果key的次数val不为1的话，我们要考虑降级问题，跟之前的升职很类似，如果要降级的行不存在，我们手动添加上，如果存在，则直接将key值添加到vals集合中即可。

  • 当我们搞懂了inc和dec的实现方法，那么getMaxKey()和getMinKey()简直就是福利啊，不要太简单啊，直接返回首层和尾层的key值即可。在自己的Java实现版本中，maxKey和minKey都是随着increase key和decrease key函数进行更新的。在每次increase或decrease key之后，都要检查maxKey,minKey,max,min值是否需要更新，并且删除一些空行。

3.（622:Medium）（非常非常经典题）Design Circular Queue

class MyCircularQueue {
    final int[] a;
    int front, rear = -1, len = 0;
    /** Initialize your data structure here. Set the size of the queue to be k. */
    public MyCircularQueue(int k) {
        a = new int[k];
    }
    
    /** Insert an element into the circular queue. Return true if the operation is successful. */
    public boolean enQueue(int value) {
        if (!isFull()) {
            rear = (rear + 1) % a.length;
            a[rear] = value;
            len++;
            return true;
        } else return false;
    }
    
    /** Delete an element from the circular queue. Return true if the operation is successful. */
    public boolean deQueue() {
        if (!isEmpty()) {
            front = (front + 1) % a.length;
            len--;
            return true;
        } else return false;
    }
    
    /** Get the front item from the queue. */
    public int Front() {
        return isEmpty() ? -1 : a[front];
    }
    
    /** Get the last item from the queue. */
    public int Rear() {
        return isEmpty() ? -1 : a[rear];
    }
    
    /** Checks whether the circular queue is empty or not. */
    public boolean isEmpty() {
        return len == 0;
    }
    
    /** Checks whether the circular queue is full or not. */
    public boolean isFull() {
        return len == a.length;
    }
}

4.（641:Medium）（非常非常经典题）Design Circular Deque

  • 在Leetcode 622题的基础上进行修改，代码如下：
class MyCircularDeque {
    int[] arr;
    int front = 0, rear = -1, len = 0, size;
    /** Initialize your data structure here. Set the size of the deque to be k. */
    public MyCircularDeque(int k) {
        arr = new int[k];
        size = k;  
    }
    
    /** Adds an item at the front of Deque. Return true if the operation is successful. */
    public boolean insertFront(int value) {
        if(isFull()){
            return false;
        }else{
            front = (front - 1) % size;
            if(front < 0){
                front += size;
            }
            arr[front] = value;
            len++;
            //  Corner case： add Front -> get Rear
            //  This kind of case which can be handled in: Add rear -> get front
            //  In which rear has a initial of -1
            if(len == 1){
                rear = front;
            }
            return true;
        }
    }
    
    /** Adds an item at the rear of Deque. Return true if the operation is successful. */
    public boolean insertLast(int value) {
        if(isFull()){
            return false;
        }else{
            rear = (rear + 1) % size;
            arr[rear] = value;
            len++;
            return true;
        }
    }
    
    /** Deletes an item from the front of Deque. Return true if the operation is successful. */
    public boolean deleteFront() {
        if(isEmpty()){
            return false;
        }else{
            front = (front + 1) % size;
            len--;
            return true;
        }
    }
    
    /** Deletes an item from the rear of Deque. Return true if the operation is successful. */
    public boolean deleteLast() {
        if(isEmpty()){
            return false;
        }else{
            rear = (rear - 1) % size;
            if(rear < 0){
                rear += size;
            }
            len--;
            return true;
        }
    }
    
    /** Get the front item from the deque. */
    public int getFront() {
        if(isEmpty()){
            return -1;
        }else{
            return arr[front];
        }
    }
    
    /** Get the last item from the deque. */
    public int getRear() {
        if(isEmpty()){
            return -1;
        }else{
            return arr[rear];
        }
    }
    
    /** Checks whether the circular deque is empty or not. */
    public boolean isEmpty() {
        return len == 0;
    }
    
    /** Checks whether the circular deque is full or not. */
    public boolean isFull() {
        return len == size;
    }
}

5.（284:Medium）（经典题）Peeking Iterator

  • 该题可以设置一个list将iterator中的所有元素都存入list中，然后用index进行索引判断，但需要额外的空间。下面的代码是O(1)空间复杂度的实现方法，用一个变量peek存储当前顶端的元素。
    Integer peek = null;
    Iterator<Integer> itr;

    public PeekingIterator(Iterator<Integer> iterator) {
        // initialize any member here.
        itr = iterator;
        if(itr.hasNext())
            peek =itr.next();
    }

    // Returns the next element in the iteration without advancing the iterator.
    public Integer peek() {
        return peek;
    }

    // hasNext() and next() should behave the same as in the Iterator interface.
    // Override them if needed.
    @Override
    public Integer next() {
        Integer temp = peek;
        peek = itr.hasNext()?itr.next():null;
        return temp;
    }
    @Override
    public boolean hasNext() {
        return peek != null;
    }

6.（353:Medium）（非常非常经典题）Design Snake Game

  • 设计题目，直接看下面的代码就能理解
    //2D position info is encoded to 1D and stored as two copies
    Set<Integer> set; // this copy is good for fast loop-up for eating body case，用来判断蛇头是否与身体相撞
    Deque<Integer> body; // this copy is good for updating tail，利用dequeue的双向增减性质来控制头尾
    int score;
    int[][] food;
    int foodIndex;
    int width;
    int height;
    
    /** Initialize your data structure here.
        @param width - screen width
        @param height - screen height 
        @param food - A list of food positions
        E.g food = [[1,1], [1,0]] means the first food is positioned at [1,1], the second is at [1,0]. */
    public SnakeGame(int width, int height, int[][] food) {
        this.width = width;
        this.height = height;
        this.food = food;
        set = new HashSet<>();
        set.add(0); //intially at [0][0]
        body = new LinkedList<>();
        body.offerLast(0); //编码方式为val = rowHead * width + colHead;
    }
    
    /** Moves the snake.
        @param direction - 'U' = Up, 'L' = Left, 'R' = Right, 'D' = Down 
        @return The game's score after the move. Return -1 if game over. 
        Game over when snake crosses the screen boundary or bites its body. */
    public int move(String direction) {
        //case 0: game already over: do nothing
        if (score == -1) {
            return -1;
        }

        // compute new head，注意编码方式为val = rowHead * width + colHead;
        int rowHead = body.peekFirst() / width;
        int colHead = body.peekFirst() % width;
        switch (direction) {
            case "U" : rowHead--;
                break;
            case "D" : rowHead++;
                break;
            case "L" : colHead--;
                break;
            default :  colHead++;
        }
        int head = rowHead * width + colHead;

        //case 1: out of boundary or eating body
        set.remove(body.peekLast()); // new head is legal to be in old tail's position, remove from set temporarily
        // set.contains(head)判断新的头部是否与身体相撞，其他条件判断是否与边界相撞
        if (rowHead < 0 || rowHead == height || colHead < 0 || colHead == width || set.contains(head)) {
            return score = -1;
        }

        // add head for case2 and case3
        set.add(head);
        body.offerFirst(head);

        //case2: eating food, keep tail, add head
        if (foodIndex < food.length && rowHead == food[foodIndex][0] && colHead == food[foodIndex][1]) {
            set.add(body.peekLast()); // old tail does not change, so add it back to set
            foodIndex++;
            return ++score;
        }

        //case3: normal move, remove tail, add head
        body.pollLast();
        return score;
    }

7.（460:Hard）（非常非常经典题）LFU Cache

  • 参考视频讲解：花花视频讲解。直接看下边的代码及注释就可以理解思路。
HashMap<Integer, Integer> vals;  //用来存key-value
HashMap<Integer, Integer> counts; //用来存key-frequency
HashMap<Integer, LinkedHashSet<Integer>> lists; //用来存frequency-List of keys，排在list中的位置越靠前，说明越不是最近访问的key，应该在tie时踢出
int cap; //cache的容量
int min = -1; //最小的频率
public LFUCache(int capacity) {
    cap = capacity;
    vals = new HashMap<>();
    counts = new HashMap<>();
    lists = new HashMap<>();
    lists.put(1, new LinkedHashSet<>());
}
    
public int get(int key) {
    if(!vals.containsKey(key))
        return -1;
    int count = counts.get(key); //要将当前访问的key的频率加1
    counts.put(key, count+1);
    lists.get(count).remove(key); //将当前的key从原来的frequency list中remove掉，然后加到高一个频率值的frequency list中
    if(count==min && lists.get(count).size()==0) //如果原来最小的频率值就是和访问的key值频率相同，且相同频率的key只有它一个，那么需要将min值加一，因为当前的key频率只增加一，如果它原来频率就最小，那么加一以后的频率也一样是最小的
        min++;
    if(!lists.containsKey(count+1))
        lists.put(count+1, new LinkedHashSet<>());
    lists.get(count+1).add(key);
    return vals.get(key);
}
    
public void put(int key, int value) {
    if(cap<=0)
        return;
    if(vals.containsKey(key)) {
        vals.put(key, value);
        get(key); //通过get函数来修改key的频率
        return;
    } 
    if(vals.size() >= cap) {
        int evit = lists.get(min).iterator().next(); //踢出的是min频率的frequency list中的第一个元素
        lists.get(min).remove(evit);
        vals.remove(evit);
    }
    vals.put(key, value);
    counts.put(key, 1);
    min = 1; //更新min frequency，肯定是1
    lists.get(1).add(key);
}

8.（635:Medium）（非常经典题）Design Log Storage System

  • 该题的关键是如何存储id-timestamp pairs以及如何查找不同粒度时间范围内对应的id，直接查看下面的代码及注释
    private String min, max;
    private HashMap<String, Integer> map;
    private TreeMap<String, LinkedList<Integer>> logs;
    public LogSystem() {
        min = "2000:01:01:00:00:00";
        max = "2017:12:31:23:59:59";
        map = new HashMap<>();
        //map存储的是对应granularity情况下，timestamp中对应时间粒度的结尾index位置
        map.put("Year", 4);
        map.put("Month", 7);
        map.put("Day", 10);
        map.put("Hour", 13);
        map.put("Minute", 16);
        map.put("Second", 19);
        logs = new TreeMap<>();
    }

    public void put(int id, String timestamp) {
        if(!logs.containsKey(timestamp)) logs.put(timestamp, new LinkedList<>());
        logs.get(timestamp).add(id);
    }

    public List<Integer> retrieve(String s, String e, String gra) {
        int index = map.get(gra);
        //通过字符串拼接获得time range的最小值及最大值
        String start = s.substring(0, index)+min.substring(index), end = e.substring(0, index)+max.substring(index);
        //通过subMap方法获得指定范围内的key-value对
        Map<String, LinkedList<Integer>> sub = logs.subMap(start, true, end, true);
        LinkedList<Integer> ans = new LinkedList<>();
        for (Map.Entry<String, LinkedList<Integer>> entry : sub.entrySet()) {
            ans.addAll(entry.getValue());
        }
        return ans;
    }

9.（706:Easy）（非常非常经典题）Design HashMap

  • 通过hash table和链表来避免碰撞，具体设计细节请参看下边的代码
    //Collisions are resolved using linked list
    final ListNode[] nodes = new ListNode[10000];

    /** value will always be non-negative. */
    public void put(int key, int value) {
        int i = idx(key);
        if (nodes[i] == null)
            nodes[i] = new ListNode(-1, -1);
        ListNode prev = find(nodes[i], key);
        if (prev.next == null)
            prev.next = new ListNode(key, value);
        else prev.next.val = value;
    }

    /** Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key */
    public int get(int key) {
        int i = idx(key);
        if (nodes[i] == null)
            return -1;
        ListNode node = find(nodes[i], key);
        return node.next == null ? -1 : node.next.val;
    }

    /** Removes the mapping of the specified value key if this map contains a mapping for the key */
    public void remove(int key) {
        int i = idx(key);
        if (nodes[i] == null) return;
        ListNode prev = find(nodes[i], key);
        if (prev.next == null) return;
        prev.next = prev.next.next;
    }

    //得到key的hash值
    int idx(int key) { return Integer.hashCode(key) % nodes.length;}

    //找到key值对应的node的前一个结点
    ListNode find(ListNode bucket, int key) {
        ListNode node = bucket, prev = null;
        while (node != null && node.key != key) {
            prev = node;
            node = node.next;
        }
        return prev;
    }

    //自定义node
    class ListNode {
        int key, val;
        ListNode next;

        ListNode(int key, int val) {
            this.key = key;
            this.val = val;
        }
    }

10.（706:Easy）（非常非常经典题）Design HashMap

  • Only thing more than a normal Trie is added a map of sentence to count in each of the Trie node to facilitate process of getting top 3 results.
    class TrieNode {
        Map<Character, TrieNode> children;
        Map<String, Integer> counts;
        boolean isWord;
        public TrieNode() {
            children = new HashMap<Character, TrieNode>();
            counts = new HashMap<String, Integer>();
            isWord = false;
        }
    }
    
    class Pair {
        String s;
        int c;
        public Pair(String s, int c) {
            this.s = s; this.c = c;
        }
    }
    
    TrieNode root;
    String prefix;
    
    
    public AutocompleteSystem(String[] sentences, int[] times) {
        root = new TrieNode();
        prefix = "";
        
        for (int i = 0; i < sentences.length; i++) {
            add(sentences[i], times[i]);
        }
    }
    
    private void add(String s, int count) {
        TrieNode curr = root;
        for (char c : s.toCharArray()) {
            TrieNode next = curr.children.get(c);
            if (next == null) {
                next = new TrieNode();
                curr.children.put(c, next);
            }
            curr = next;
            curr.counts.put(s, curr.counts.getOrDefault(s, 0) + count);
        }
        curr.isWord = true;
    }
    
    public List<String> input(char c) {
        if (c == '#') {
            add(prefix, 1);
            prefix = "";
            return new ArrayList<String>();
        }
        
        prefix = prefix + c;
        TrieNode curr = root;
        for (char cc : prefix.toCharArray()) {
            TrieNode next = curr.children.get(cc);
            if (next == null) {
                return new ArrayList<String>();
            }
            curr = next;
        }
        
        PriorityQueue<Pair> pq = new PriorityQueue<>((a, b) -> (a.c == b.c ? a.s.compareTo(b.s) : b.c - a.c));
        for (String s : curr.counts.keySet()) {
            pq.add(new Pair(s, curr.counts.get(s)));
        }

        List<String> res = new ArrayList<String>();
        for (int i = 0; i < 3 && !pq.isEmpty(); i++) {
            res.add(pq.poll().s);
        }
        return res;
    }
⚠️ **GitHub.com Fallback** ⚠️