LeetCode(74) && Insertion Sort -- 460, 456

P460. LFU Cache (Hard)

Design and implement a data structure for Least Frequently Used (LFU) cache. It should support the following operations: get and put.

My Solution

public class P460_LFUCache {

    Map<Integer, Node> map;
    Map<Integer, List<Node>> freq;
    int capacity;

    class Node {
        int key;
        int value;
        int freq;
    }

    public P460_LFUCache(int capacity) {
        map = new HashMap<>(capacity);
        freq = new HashMap<>();
        this.capacity = capacity;
    }

    public int get(int key) {
        int result = -1;
        if (capacity == 0) {
            return result;
        }
        Node node = map.get(key);
        if (node != null) {
            result = node.value;
            increaseFreq(node);
        }
        return result;
    }

    public void put(int key, int value) {
        if (capacity == 0) {
            return;
        }
        Node node = map.get(key);
        if (node != null) {
            node.value = value;
            increaseFreq(node);
        } else {
            if (map.size() == capacity) {
                int min = Integer.MAX_VALUE;
                for (Integer freqKey : freq.keySet()) {
                    min = Math.min(min, freqKey);
                }
                List<Node> list = freq.get(min);
                int toRemove = list.get(0).key;
                map.remove(toRemove);
                list.remove(0);
            }
            Node newNode = new Node();
            newNode.key = key;
            newNode.value = value;
            newNode.freq = 0;
            map.put(key, newNode);
            increaseFreq(newNode);
        }
    }

    private void increaseFreq(Node node) {
        int freq = node.freq;
        List<Node> list = this.freq.get(freq);
        if (list != null) {
            list.remove(node);
            if (list.size() == 0) {
                this.freq.remove(freq);
            }
        }
        node.freq = freq + 1;
        List<Node> newList = this.freq.get(freq + 1);
        if (newList == null) {
            newList = new ArrayList<>();
        }
        newList.add(node);
        this.freq.put(freq + 1, newList);
    }

    public static void main(String[] args) {
        P460_LFUCache cache = new P460_LFUCache(0);
        cache.put(0, 0);
        int i = cache.get(0);
        System.out.println("i = " + i);
    }
}

75%

The Best Solution

class LFUCache {
    Map<Integer, Node> cache;
    DoublyLinkedList firstLinkedList;
    DoublyLinkedList lastLinkedList;
    int size;
    int capacity;

    public LFUCache(int capacity) {
        cache = new HashMap<> (capacity);
        firstLinkedList = new DoublyLinkedList();
        lastLinkedList = new DoublyLinkedList();
        firstLinkedList.post = lastLinkedList;
        lastLinkedList.pre = firstLinkedList;
        this.capacity = capacity;
    }
    
    public int get(int key) {
        Node node = cache.get(key);
        if (node == null) {
            return -1;
        }
        freqInc(node);
        return node.value;
    }
    
    public void put(int key, int value) {
        if (capacity == 0) {
            return;
        }
        Node node = cache.get(key);
        if (node != null) {
            node.value = value;
            freqInc(node);
        } else {
            if (size == capacity) {
                // 如果缓存满了，删除lastLinkedList.pre链表中的tail.pre的Node，如果该链表中的元素删空了，则删掉该链表
                cache.remove(lastLinkedList.pre.tail.pre.key);
                lastLinkedList.removeNode(lastLinkedList.pre.tail.pre);
                size--;
                if (lastLinkedList.pre.head.post == lastLinkedList.pre.tail) {
                    removeDoublyLinkedList(lastLinkedList.pre);
                } 
            }
            Node newNode = new Node(key, value); /////////
            cache.put(key, newNode);
            if (lastLinkedList.pre.freq != 1) {
                DoublyLinkedList newDoublyLinedList = new DoublyLinkedList(1);
                addDoublyLinkedList(newDoublyLinedList, lastLinkedList.pre);
                newDoublyLinedList.addNode(newNode);
            } else {
                lastLinkedList.pre.addNode(newNode);
            }
            size++;
        }
    }

    void freqInc(Node node) {
        // 将node从原freq对应的链表里移除, 如果链表空了则删除链表,
        DoublyLinkedList linkedList = node.doublyLinkedList;
        DoublyLinkedList preLinkedList = linkedList.pre;
        linkedList.removeNode(node);
        if (linkedList.head.post == linkedList.tail) { 
            removeDoublyLinkedList(linkedList);
        }

        // 将node加入新freq对应的链表，若该链表不存在，则先创建该链表。
        node.freq++;
        if (preLinkedList.freq != node.freq) {
            DoublyLinkedList newDoublyLinedList = new DoublyLinkedList(node.freq);
            addDoublyLinkedList(newDoublyLinedList, preLinkedList);
            newDoublyLinedList.addNode(node);
        } else {
            preLinkedList.addNode(node);
        }
    }

    void addDoublyLinkedList(DoublyLinkedList newDoublyLinedList, DoublyLinkedList preLinkedList) {
        newDoublyLinedList.post = preLinkedList.post;
        newDoublyLinedList.post.pre = newDoublyLinedList;
        newDoublyLinedList.pre = preLinkedList;
        preLinkedList.post = newDoublyLinedList; 
    }

    void removeDoublyLinkedList(DoublyLinkedList doublyLinkedList) {
        doublyLinkedList.pre.post = doublyLinkedList.post;
        doublyLinkedList.post.pre = doublyLinkedList.pre;
    }
}

class Node {
    int key;
    int value;
    int freq = 1;
    Node pre;
    Node post;
    DoublyLinkedList doublyLinkedList;    

    public Node() {}
    
    public Node(int key, int value) {
        this.key = key;
        this.value = value;
    }
}

class DoublyLinkedList {
    int freq;
    DoublyLinkedList pre;
    DoublyLinkedList post;
    Node head;
    Node tail;

    public DoublyLinkedList() {
        head = new Node();
        tail = new Node();
        head.post = tail;
        tail.pre = head;
    }

    public DoublyLinkedList(int freq) {
        head = new Node();
        tail = new Node();
        head.post = tail;
        tail.pre = head;
        this.freq = freq;
    }

    void removeNode(Node node) {
        node.pre.post = node.post;
        node.post.pre = node.pre;
    }

    void addNode(Node node) {
        node.post = head.post;
        head.post.pre = node;
        head.post = node;
        node.pre = head;
        node.doublyLinkedList = this;
    }

}

P456. 132 Pattern (Medium)

Given a sequence of n integers a1, a2, …, an, a 132 pattern is a subsequence ai, aj, ak such that i < j < k and ai < ak < aj. Design an algorithm that takes a list of n numbers as input and checks whether there is a 132 pattern in the list.

Note: n will be less than 15,000.

Input: [3, 1, 4, 2]

Output: True

Explanation: There is a 132 pattern in the sequence: [1, 4, 2].

The Best Solution

class Solution {
    public boolean find132pattern(int[] nums) {
        int n = nums.length, top = n, third = Integer.MIN_VALUE;

        for (int i = n - 1; i >= 0; i--) {
            if (nums[i] < third) {
                return true;
            }
            while (top < n && nums[i] > nums[top]) {
                third = nums[top++];
            }
            nums[--top] = nums[i];
        }
        return false;
    }
}

public class P456_132Pattern {
    public boolean find132pattern(int[] nums) {
        if (nums.length < 3) {
            return false;
        }
        int[] min = new int[nums.length];
        min[0] = nums[0];
        for (int i = 1; i < nums.length; i++) {
            min[i] = Math.min(min[i - 1], nums[i]);
        }
        for (int j = nums.length - 1, k = nums.length; j >= 0; j--) {
            if (nums[j] > min[j]) {
                while (k < nums.length && nums[k] <= min[j]) {
                    k++;
                }
                if (k < nums.length && nums[k] < nums[j]) {
                    return true;
                }
                nums[--k] = nums[j];
            }
        }
        return false;
    }
}

The Insertion-Sort Algorithm

Algorithm InsertionSort(A):
   Input: An array A of n comparable elements
   Output: The array A with elements rearranged in nondecreasing order
    for k from 1 to n - 1 do
        Insert A[k] at its proper location within A[0], A[1], ..., A[k].

Example

public class InsertionSort {

    public static void insertionSort(char[] data) {
        int n = data.length;
        for (int i = 1; i < n; i++) {
            char c = data[i];
            int j = i;
            while (j > 0 && c < data[j - 1]) {
                data[j] = data[j - 1];
                j--;
            }
            data[j] = c;
        }
    }

    public static void main(String[] args) {
        char[] data = {'B','C','D','A','E','H','G','F'};
        insertionSort(data);
        System.out.println("data = " + Arrays.toString(data));
    }

}