449. Serialize and Deserialize BST

参考 297. Serialize and Deserialize Binary Tree

Version #4 LC DFS Iteration

二刷
Version # 1 DFS Recursion using the property of binary search tree

Since we can guarantee that the root node value is larger than nodes in its left subtree and less than nodes in its right substree, we can deserialize a tree from its pre-order traversal
89.68 %
public class Codec {

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        seHelper(root, sb);
        return sb.toString();
    }
    private void seHelper(TreeNode node, StringBuilder sb) {
        if (node == null) {
            return;
        }
        sb.append(node.val);
        sb.append(",");
        seHelper(node.left, sb);
        seHelper(node.right, sb);
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if (data == null || data.length() == 0) {
            return null;
        }
        String[] strs = data.split(",");
        return deHelper(strs, 0, strs.length);
    }
   
    // [start, end)
    private TreeNode deHelper(String[] strs, int start, int end) {
        if (start >= end) {
            return null;
        }
        int val = Integer.valueOf(strs[start]);
        TreeNode node = new TreeNode(val);
        int mid = start + 1;
        // left -> [start + 1, mid) right -> [mid, end)
        while (mid < end && Integer.valueOf(strs[mid]) < val) {
            mid++;
        }
        node.left = deHelper(strs, start + 1, mid);
        node.right = deHelper(strs, mid, end);
        return node;
    }
}


一刷
Version #3 LC DFS Recursion
自己写了一个Tuple Class 用了Recursion
是一个general binary tree的写法 没有利用BST的性质

80.02 %
class Tuple {
    int index;
    TreeNode node;
    public Tuple(int index, TreeNode node) {
        this.index = index;
        this.node = node;
    }
}
public class Codec {

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
   
        StringBuilder sb = new StringBuilder();
        traversal(root, sb);
        sb.deleteCharAt(sb.length() - 1);
        //System.out.println(sb.toString());
        return sb.toString();
    }
    // pre-order traversal
    private void traversal(TreeNode root, StringBuilder sb) {
        if (root == null) {
            sb.append("#,");
            return;
        }
        sb.append(root.val + ",");
        traversal(root.left, sb);
        traversal(root.right, sb);
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if (data == null) return null;
        String[] nodes = data.trim().split(",");
        return build(nodes,  0).node;
    }
    private Tuple build(String[] nodes, int index) {
        if (nodes[index].equals("#")) return new Tuple(index, null);
   
        TreeNode root = new TreeNode(Integer.valueOf(nodes[index]));
        Tuple left = build(nodes, index + 1);
        Tuple right = build(nodes, left.index + 1);
        root.left = left.node;
        root.right = right.node;
        return new Tuple(right.index, root);
    }
}

295. Find Median from Data Stream

四刷 06/2022

Version #1 Two Heaps

一开始写了一个bug就是无脑向maxHeap里面offer然后再balance

这样会造成很小的值被balance到larger half的minHeap里面

需要先和两个heap的peek value比较之后再往里面塞

Time - addNum O(logN), findMedian O(1)

Space - O(N)

Runtime: 183 ms, faster than 50.19% of Java online submissions for Find Median from Data Stream.

Memory Usage: 125.3 MB, less than 34.18% of Java online submissions for Find Median from Data Stream.

class MedianFinder {

    Queue<Integer> minHeap;

    Queue<Integer> maxHeap;

    public MedianFinder() {

        minHeap = new PriorityQueue<>();

        maxHeap = new PriorityQueue<>(Collections.reverseOrder());

    }

    

    public void addNum(int num) {

        // maxHeap contains smaller half of numbers

        // minHeap contains larger half of numbers

        // maxHeap.size() == minHeap.size()

        // or maxHeap.size() == minHeap.size() + 1;

        if (maxHeap.isEmpty() || num <= maxHeap.peek()) {

            maxHeap.offer(num);

        } else {

            minHeap.offer(num);

        }

        if (maxHeap.size() < minHeap.size()) {

            maxHeap.offer(minHeap.poll());

        }

        if (maxHeap.size() > minHeap.size() + 1) {

            minHeap.offer(maxHeap.poll());

        }

    }

    

    public double findMedian() {

        if (maxHeap.size() == minHeap.size()) {

            return (maxHeap.peek() + minHeap.peek()) / 2.0;

        }

        return maxHeap.peek();

    }

}

/**

 * Your MedianFinder object will be instantiated and called as such:

 * MedianFinder obj = new MedianFinder();

 * obj.addNum(num);

 * double param_2 = obj.findMedian();

 */

三刷

Follow up


Version #1 Two Heaps

76.63 %
class MedianFinder {

    /** initialize your data structure here. */
    PriorityQueue<Integer> maxHeap, minHeap;
    public MedianFinder() {
        // 2 heap
        // maxHeap, minHeap -> to keep maxHeap size == minHeap size or minHeap size + 1
        maxHeap = new PriorityQueue<>(Collections.reverseOrder());
        minHeap = new PriorityQueue<>();
    }
   
    public void addNum(int num) {
        if (maxHeap.isEmpty()) {
            maxHeap.offer(num);
            return;
        }
        if (num < maxHeap.peek()) {
            maxHeap.offer(num);
        } else {
            minHeap.offer(num);
        }
        adjust();
    }
   
    public double findMedian() {
        if (maxHeap.size() == minHeap.size()) {
            return (maxHeap.peek() + minHeap.peek()) / 2.0;
        }
        return maxHeap.peek();
    }
   
    private void adjust() {
        while (maxHeap.size() < minHeap.size()) {
            maxHeap.offer(minHeap.poll());
        }
        while (maxHeap.size() > minHeap.size() + 1) {
            minHeap.offer(maxHeap.poll());
        }
    }
}

二刷 LC

41.34 % 
class MedianFinder {

    // divide data into two parts ->   smaller half(size1) + larger half(size2)
    // always make sure that size1 == size2/ size2+1 -> if size1 == size2, median =  (maxOfSmallerHalf + minOfLargerHalf) / 2
    // else median = maxOfSmallerHalf
 
    /** initialize your data structure here. */
    PriorityQueue<Integer> smallerHalf;
    PriorityQueue<Integer> largerHalf;
    public MedianFinder() {
        smallerHalf = new PriorityQueue<>(10, Collections.reverseOrder());
        largerHalf = new PriorityQueue<>();
    }
 
    public void addNum(int num) {
        if (smallerHalf.isEmpty()) {
            smallerHalf.offer(num);
            return;
        }
     
        if (num <= smallerHalf.peek()) {
            smallerHalf.offer(num);
        } else {
            largerHalf.offer(num);
        }
         
        if (smallerHalf.size() < largerHalf.size()) {
            smallerHalf.offer(largerHalf.poll());
        } else if (smallerHalf.size() > largerHalf.size() + 1) {
            largerHalf.offer(smallerHalf.poll());
        }
    }
 
    public double findMedian() {
        if (smallerHalf.isEmpty()) {
            throw new RuntimeException("Empty number set");
        }
        if (smallerHalf.size() == largerHalf.size()) {
            return (smallerHalf.peek() + largerHalf.peek()) / 2.0;
        } else {
            return smallerHalf.peek();
        }
    }
}




一刷 LintCode
Using two heap
Time O(nlogn)
Space O(n)
public class Solution {
    /**
     * @param nums: A list of integers.
     * @return: the median of numbers
     */
    public int[] medianII(int[] nums) {
        // write your code here
        if (nums == null || nums.length == 0) return nums;
        int[] med = new int[nums.length];
        //max heap
        PriorityQueue<Integer> heap1 = new PriorityQueue<>(1, new Comparator<Integer>() {
            public int compare(Integer a, Integer b) {
                return b - a;
            }
        });
        //min heap
        PriorityQueue<Integer> heap2 = new PriorityQueue<>();
        int newNum;
        int currMed = nums[0];
        for (int i = 0; i < nums.length; i++) {
            newNum = nums[i];
            if (newNum <= currMed) heap1.offer(newNum);
            else heap2.offer(newNum);
            //heap2's size is at least 1 number
            if (heap1.size() < heap2.size()) {
                heap1.offer(heap2.poll());
            }
            if (heap1.size() > heap2.size() + 1) {
                heap2.offer(heap1.poll());
            }
            currMed = heap1.peek();
            med[i] = currMed;
        }
        return med;
    }
}

305. Number of Islands II

Version# 1 Union Find

[2ND TRY]

1 defect that I didn't fix
-> the initial size for all nodes should be 0 since initially they are not added to the graph
-> When the coming position is added, set size[label] = 1, id[label] = label

39.25 %
class Solution {
    private int getLabel(int y, int x) {
return y * cols + x;
}

private int rows;
private int cols;
private int[] dx = new int[]{1, 0, -1, 0};
private int[] dy = new int[]{0, -1, 0, 1};
private int[] id;
private int[] size;

public List<Integer> numIslands2(int m, int n, int[][] positions) {
List<Integer> result = new ArrayList<>();
rows = m;
cols = n;
if (positions == null || positions.length == 0 || positions[0] == null || positions[0].length == 0) {
return result;
}

id = new int[m * n];
size = new int[m * n];
Arrays.fill(id, -1);
Arrays.fill(size, 1);
int count = 0;
for (int[] position : positions) {
// Assume a new node is added
count++;
int currLabel = getLabel(position[0], position[1]);
id[currLabel] = currLabel;
for (int i = 0; i < 4; i++) {
int y = position[0] + dy[i];
int x = position[1] + dx[i];
int nextLabel = getLabel(y, x);
if (x < 0 || y < 0 || x >= cols || y >= rows || id[nextLabel] == -1) {
continue;
}
if (union(currLabel, nextLabel)) {
count--;
}
}
            result.add(count);
}
return result;
}

private void union() {

}

private int root(int i) {
while (i != id[i]) {
id[i] = id[id[i]];
i = id[i];
}
return i;
}

private boolean union(int p, int q) {
int rootP = root(p);
int rootQ = root(q);
if (rootP == rootQ) {
return false;
}
if (size[rootP] < size[rootQ]) {
id[rootP] = rootQ;
size[rootQ] += size[rootP];
} else {
id[rootQ] = rootP;
size[rootP] += size[rootQ];
}
return true;
}
}

[1ST TRY]
在LintCode上面做的，和leetcode的interface不太一样
完全自己写的，没有优化过
有空再做一下

有两个问题
1.在用dx, dy进行bfs的时候，一定要检查是不是出界！！！！！
  因为我用一维array表示的二维matrix，所以在这里犯了一个错误
  要在原始的二维matrix里面check valid 而不是只要在一维里不出界就可以了

2.算是题目的一个坑吧，就是同一个点重复加入
  改正方法很简单，如果当前点已经是island了的话就不用count++了


/**
 * Definition for a point.
 * class Point {
 *     int x;
 *     int y;
 *     Point() { x = 0; y = 0; }
 *     Point(int a, int b) { x = a; y = b; }
 * }
 */
public class Solution {
    /**
     * @param n an integer
     * @param m an integer
     * @param operators an array of point
     * @return an integer array
     */
    private int[] dx = {1, 0, -1, 0};
    private int[] dy = {0, 1, 0, -1};
    private int[] father;
    private boolean[] isIsland;
    private int count;
    public List<Integer> numIslands2(int n, int m, Point[] operators) {
        // Write your code here
        List<Integer> result = new ArrayList<>();
        if (n <= 0 || m <= 0 || operators == null || operators.length == 0) return result;
        father = new int[n * m];
        isIsland = new boolean[n * m];
        count = 0;
        for (int i = 0 ; i < father.length; i++) {
            father[i] = i;
        }
        for (int j = 0; j < operators.length; j++) {
            Point curr = operators[j];
            int x = curr.x, y = curr.y;
            int hash = x * m + y;
            int newHash;
            if (!isIsland[hash]) {
                isIsland[hash] = true;
                count++;
            }
         
            for (int k = 0; k < 4; k++) {
                newHash = (x + dx[k]) * m + y + dy[k];
                if (isValid(n, m, x + dx[k], y + dy[k]) && isIsland[newHash]) union(hash, newHash);
            }
            result.add(count);
            /*
            if (j >= 21) {
                System.out.println("(" + x + ", " + y + ")" + count);
            for (int row = 0; row < n; row++) {
                for (int col = 0; col < m; col++) {
                    int value = isIsland[row * m + col] ? 1 : 0;
                    System.out.print(value + " ");
                }
                System.out.println();
            }
            System.out.println();
            }
            */
         
         
        }
        return result;
    }
    private boolean isValid(int rows, int cols, int x, int y) {
        return x >= 0 && x < rows && y >= 0 && y < cols;
    }
    private int find(int x) {
        if (father[x] == x) return x;
        father[x] = find(father[x]);
        return father[x];
    }
    private void union(int a, int b) {
        int rootA = find(a);
        int rootB = find(b);
        if (rootA != rootB) {
            father[rootA] = rootB;
            count--;
        }
    }
}

208. Implement Trie (Prefix Tree)

二刷

 20.99 %
class Trie {
    TrieNode root;
    class TrieNode {
        TrieNode[] children;
        boolean isWord;
        public TrieNode() {
            children = new TrieNode[26]; // a - z
            isWord = false;
        }
    }
    /** Initialize your data structure here. */
    public Trie() {
        root = new TrieNode();
    }
 
    /** Inserts a word into the trie. */
    public void insert(String word) {
        TrieNode curr = root;
        int i = 0;
        while (i < word.length()) {
            int index = word.charAt(i) - 'a';
            if (curr.children[index] == null) curr.children[index] = new TrieNode();
            curr = curr.children[index];
            i++;
        }
        curr.isWord = true;
    }
 
    /** Returns if the word is in the trie. */
    public boolean search(String word) {
        TrieNode curr = root;
        int i = 0;
        while (i < word.length()) {
            int index = word.charAt(i) - 'a';
            if (curr.children[index] == null) return false;
            curr = curr.children[index];
            i++;
        }
        return curr.isWord;
    }
 
    /** Returns if there is any word in the trie that starts with the given prefix. */
    public boolean startsWith(String prefix) {
        TrieNode curr = root;
        int i = 0;
        while (i < prefix.length()) {
            int index = prefix.charAt(i) - 'a';
            if (curr.children[index] == null) return false;
            curr = curr.children[index];
            i++;
        }
        return true;
    }
}

一刷
/**
 * Your Trie object will be instantiated and called as such:
 * Trie trie = new Trie();
 * trie.insert("lintcode");
 * trie.search("lint"); will return false
 * trie.startsWith("lint"); will return true
 */
class TrieNode {
    // Initialize your data structure here.
    public boolean isWord;
    public TrieNode[] children;
    public TrieNode() {
        this.children = new TrieNode[26];
    }
}

public class Trie {
    private TrieNode root;

    public Trie() {
        root = new TrieNode();
    }

    // Inserts a word into the trie.
    public void insert(String word) {
        TrieNode curr = root;
        int index;
        for (int i = 0; i < word.length(); i++) {
            index = word.charAt(i) - 'a';
            if (curr.children[index] == null) {
                curr.children[index] = new TrieNode();
            }
            curr = curr.children[index];
        }
        curr.isWord = true;
    }

    // Returns if the word is in the trie.
    public boolean search(String word) {
        TrieNode curr = root;
        int index;
        for (int i = 0; i < word.length(); i++) {
            index = word.charAt(i) - 'a';
            if (curr.children[index] == null) return false;
            curr = curr.children[index];
        }
        return curr.isWord;
    }

    // Returns if there is any word in the trie
    // that starts with the given prefix.
    public boolean startsWith(String prefix) {
         TrieNode curr = root;
        int index;
        for (int i = 0; i < prefix.length(); i++) {
            index = prefix.charAt(i) - 'a';
            if (curr.children[index] == null) return false;
            curr = curr.children[index];
        }
        return true;
    }
}

146. LRU Cache

五刷 06/2022

Version #1 Doubly Linked List + HashMap

Runtime: 96 ms, faster than 30.82% of Java online submissions for LRU Cache.

Memory Usage: 125.7 MB, less than 47.57% of Java online submissions for LRU Cache.

class LRUCache {

    class ListNode {

        public ListNode prev, next;

        public int key;

        public int val;

        public ListNode(int key, int val) {

            this.key = key;

            this.val = val;

        }

    }

    private Map<Integer, ListNode> nodes;

    private ListNode head, tail;

    private int cap;

    // We need a doubly-linked list to serve as the cache

    // In order to make get/put O(1) we need hashmap to keep track of the nodes in the list

    private void addFirst(ListNode node) {

        // head -> head.next

        // head -> node -> head.next

        ListNode nextNode = head.next;

        head.next = node;

        node.prev = head;

        node.next = nextNode;

        nextNode.prev = node;

    }

    

    private ListNode removeLast() {

        // tail.prev.prev -> tail.prev -> tail

        // tail.prev.prev -> tail

        ListNode prevNode = tail.prev;

        if (prevNode == head) {

            return null;

        }

        prevNode.prev.next = tail;

        tail.prev = prevNode.prev;

        return prevNode;

    }

    

    private void removeNode(ListNode node) {

        ListNode prev = node.prev;

        ListNode next = node.next;

        prev.next = next;

        next.prev = prev;

    }

    

    public LRUCache(int capacity) {

        nodes = new HashMap<>();

        head = new ListNode(-1, -1);

        tail = new ListNode(-1, -1);

        head.next = tail;

        tail.prev = head;

        cap = capacity;

    }

    

    public int get(int key) {

        if (!nodes.containsKey(key)) {

            return -1;

        }

        ListNode node = nodes.get(key);

        if (node.prev != head) {

            removeNode(node);

            addFirst(node);

        }

        return node.val;

    }

    

    public void put(int key, int value) {

        if (nodes.containsKey(key)) {

            ListNode node = nodes.get(key);

            node.val = value;

            if (node.prev != null) {

                removeNode(node);

                addFirst(node);

            }

            return;

        }

        ListNode node = new ListNode(key, value);

        nodes.put(key, node);

        addFirst(node);

        if (nodes.size() > cap) {

            ListNode last = removeLast();

            nodes.remove(last.key);

        }

    }

}

/**

 * 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);

 */

四刷
这次做的有点不一样，一开始没有考虑remove的时候需要把key从map里面移除
写到最后的时候不得不加了一个反向的keyMap把ListNode和key联系在一起
看了以前的写法，可以直接在ListNode里面加一个key的field
anyway这次只写了20分钟，还是挺快的

 45.21 %
class LRUCache {
    class ListNode {
        ListNode prev, next;
        int val;
        public ListNode(int val) {
            this.val = val;
        }
    }
    // doubly linked list

    private Map<Integer, ListNode> map;
    private Map<ListNode, Integer> keyMap;
    private ListNode head, tail;
    private int capacity;
    private int size;
    public LRUCache(int capacity) {
        map = new HashMap<>();
        keyMap = new HashMap<>();
        this.capacity = capacity;
        this.size = 0;
        head = new ListNode(0);
        tail = new ListNode(0);
        head.next = tail;
        tail.prev = head;
    }
   
    public int get(int key) {
        // check if key exist -> remove list node from original node, intsert at tail
        if (!map.containsKey(key)) {
            return -1;
        }
        ListNode curr = map.get(key);
        if (curr.next != tail) {
            removeNode(curr);
            appendNode(curr);
        }
        return curr.val;
    }
   
    public void put(int key, int value) {
        // check if key exist -> remove
        // insert at tail
        // check size -> check if we need to remove the 1st node or not
        ListNode curr = null;
        if (map.containsKey(key)) {
            curr = map.get(key);
            if (curr.next != tail) {
                removeNode(curr);
                appendNode(curr);
            }
            curr.val = value;
        } else {
            curr = new ListNode(value);
            map.put(key, curr);
            keyMap.put(curr, key);
            appendNode(curr);
            size++;
            if (size > capacity) {
                ListNode outdatedNode = head.next;
                removeNode(head.next);
                map.remove(keyMap.get(outdatedNode));
                keyMap.remove(outdatedNode);
            }
        }
    }
   
    private void removeNode(ListNode node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }
   
    private void appendNode(ListNode node) {
        ListNode prev = tail.prev;
        prev.next = node;
        node.prev = prev;
        node.next = tail;
        tail.prev = node;
    }
}

[3RD TRY]
Think about thread safety...
I just added synchronized key word to get and put
Should try ReentrantLock in the future

 60.20 %
import java.util.concurrent.ConcurrentHashMap;

public class LRUCache {
private LinkedHashMap linkedHashMap;
public LRUCache(int capacity) {
this.linkedHashMap = new LinkedHashMap(capacity);
}

class LinkedHashMap {
class Node {
private Node prev;
private Node next;
private int key;
private int value;

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

private int capacity;
private Map<Integer, Node> map;
private Node head;
private Node tail;

private int size;

public LinkedHashMap(int capacity) {
this.capacity = capacity;
map = new ConcurrentHashMap<>();
head = new Node(0, 0);
tail = new Node(0, 0);
head.next = tail;
tail.prev = head;
size = 0;
}

public synchronized int get(int key) {
if (!map.containsKey(key)) {
return -1;
}
Node curr = map.get(key);
// remove node
remove(curr);
// insert after head
insertHead(curr);
return curr.value;
}

private void remove(Node node) {
node.prev.next = node.next;
node.next.prev = node.prev;
}

private void insertHead(Node node) {
Node nextNode = head.next;
head.next = node;
node.prev = head;
node.next = nextNode;
nextNode.prev = node;
}

public synchronized void put(int key, int value) {
Node curr = null;
if (map.containsKey(key)) {
// update value & position
curr = map.get(key);
curr.value = value;
remove(curr);
} else {
curr = new Node(key, value);
map.put(key, curr);
size++;
}
if (size > capacity) {
Node lastNode = tail.prev;
map.remove(lastNode.key);
remove(lastNode);
size--;
}
insertHead(curr);
}
}

public int get(int key) {
return linkedHashMap.get(key);
}

public void put(int key, int value) {
linkedHashMap.put(key, value);
}
}

[1ST TRY]
LintCode
不是很难 关键是doubly linked list在head 和tail 都应该加dummy node
会比不加简洁一万倍
一个是get之后也要update位置
一个是尽管set到同样key的值，value也有可能被改变， 所以也要update位置

public class Solution {

    private class Node {
        public Node prev, next;
        public int key, value;
        public Node(int key, int value) {
            this.key = key;
            this.value = value;
            this.prev = null;
            this.next = null;
        }
    }
    private Node head, tail;
    private Map<Integer, Node> hash;
    private int cap;
    // @param capacity, an integer
    public Solution(int capacity) {
        // write your code here
        this.head = new Node(0, 0);
        this.tail = new Node(0, 0);
        head.next = tail;
        tail.prev = head;
        this.hash = new HashMap<Integer, Node>();
        this.cap = capacity;
    }

    // @return an integer
    public int get(int key) {
        // write your code here
        if (!hash.containsKey(key)) return -1;
        Node curr = hash.get(key);
        moveToTail(curr);
        return curr.value;
    }
    private void moveToTail(Node node) {
        //delete node from the current position
        node.prev.next = node.next;
        node.next.prev = node.prev;
        //insert node before tail
        tail.prev.next = node;
        node.prev = tail.prev;
        tail.prev = node;
        node.next = tail;
    }

    // @param key, an integer
    // @param value, an integer
    // @return nothing
    public void set(int key, int value) {
   
        // write your code here
        if (hash.containsKey(key)) {
            Node curr = hash.get(key);
            curr.value = value;
            moveToTail(curr);
            return;
        }
        if (hash.size() >= cap) {
            hash.remove(head.next.key);
            head.next = head.next.next;
            head.next.prev = head;
        }
        Node newNode = new Node(key, value);
        hash.put(key, newNode);
        tail.prev.next = newNode;
        newNode.prev = tail.prev;
        tail.prev = newNode;
        newNode.next = tail;
    }
}


二刷 LeetCode
35.23 %

对doublyLinkedList的处理完全用函数了 感觉还是比较简洁的
写了1个typo Initialize时候tail.prev = head
2个bug 问题出在 每一个node不光要记住它的value 同时也要记住它的key 因为从head remove的时候，需要根据head.next找到hashmap里面的key并删除 所以node要有key和value


class doublyListNode {
    public doublyListNode prev, next;
    public int key, val;
    public doublyListNode(int key, int val) {
        this.key = key;
        this.val = val;
        prev = null;
        next = null;
    }
}
public class LRUCache {
    private doublyListNode head;
    private doublyListNode tail;
    private int capacity;
    private Map<Integer, doublyListNode> map;

    public LRUCache(int capacity) {
        head = new doublyListNode(-1, -1);
        tail = new doublyListNode(-1, -1);
        this.capacity = capacity;
        map = new HashMap<Integer, doublyListNode>();
        head.next = tail;
        tail.prev = head;
    }

    public int get(int key) {
        if (!map.containsKey(key)) return -1;
        doublyListNode curr = map.get(key);
        moveToTail(curr);
        return curr.val;
    }

    public void put(int key, int value) {
        doublyListNode curr;
        if (map.containsKey(key)) {
            curr = map.get(key);
            curr.val = value;
            moveToTail(curr);
        } else {
            if (capacity == 0) {
                //System.out.println(head.next.key);
                map.remove(head.next.key);
                deleteFromHead();
                capacity++;
            }
            curr = new doublyListNode(key, value);
            map.put(key, curr);
            addToTail(curr);
            capacity--;
        }
    }
    private void addToTail(doublyListNode node) {
        tail.prev.next = node;
        node.prev = tail.prev;
        node.next = tail;
        tail.prev = node;
    }

    private void deleteFromHead() {
        //Empty list
        if (head == tail) return;
        //Otherwise there are at least 3 nodes
        head.next.next.prev = head;
        head.next = head.next.next;
    }
    private void moveToTail(doublyListNode node) {
        //delete from list
        node.prev.next = node.next;
        node.next.prev = node.prev;
        //addToTail
        addToTail(node);
    }
}

/**
 * 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);
 */

28. Implement strStr() / strStr II

Version #2 Rabin Karp

O(m + n)
28.58 %
class Solution {
    public int BASE = 1000000;
    public int strStr(String haystack, String needle) {
        if (haystack == null || needle == null) return -1;
        if (needle.length() == 0) return 0;
     
        int target = 0;
        int power = 1; // weight of the highest bit
        int len = needle.length();
        for (int i = 0; i < len; i++) {
            target = (target * 31 + Character.getNumericValue(needle.charAt(i))) % BASE;
            power = power * 31 % BASE;
        }
        int hashCode = 0;
        for (int j = 0; j < haystack.length(); j++) {
            //       j = 3, len = 3
            // abc + d
            hashCode = (hashCode * 31 + Character.getNumericValue(haystack.charAt(j))) % BASE;
            // delete (j - len)
            if (j >= len) {
                hashCode = (hashCode - Character.getNumericValue(haystack.charAt(j - len)) * power) % BASE;
                if (hashCode < 0) hashCode += BASE;
            }
         
         
            if (hashCode == target) {
                // double check to ensure correctness
                //haystack index [j - len + 1, j]
                if (haystack.substring(j - len + 1, j + 1).equals(needle)) return j - len + 1;
            }
        }
        return -1;
    }
}


Version #1 KMP
看了普林斯顿老爷爷的讲解感觉理解的比较深刻了，但是自己写还是不熟练
LeetCode上面有一个人dfa只用了一维数组，没懂为何
https://discuss.leetcode.com/topic/3576/accepted-kmp-solution-in-java-for-reference

网上另一个讲解

暂时先这样吧以后有空再看看

public class Solution {
    /**
     * @param source a source string
     * @param target a target string
     * @return an integer as index
     */
    public int strStr2(String source, String target) {
        // Write your code here
        if (source == null || target == null || source.length() < target.length()) return -1;
        if (target.length() == 0) return 0;
        int i, j, N = source.length(), M = target.length();
        int[][] dfa = dfaBuilder(target);
        for (i = 0, j = 0; i < N && j < M; i++) {
            j = dfa[source.charAt(i) - 'a'][j];
        }
        if (j == M) return i - M;
        return -1;
    }
 
    public int[][] dfaBuilder(String target) {
        int M = target.length();
        int R = 26; //ASCII
        int[][] dfa = new int[R][M];
        dfa[target.charAt(0) - 'a'][0] = 1; //The 1st match state
        for (int x = 0, j = 1; j < M; j++) {
            for (int c = 0; c < R; c++) {
                dfa[c][j] = dfa[c][x]; //copy mismatch cases
                dfa[target.charAt(j) - 'a'][j] = j + 1; //set the match case
                x = dfa[target.charAt(j) - 'a'][x];
            }
        }
        return dfa;
    }
}

二刷

Version #1 Brute Force

Runtime: 0 ms, faster than 100.00% of Java online submissions for Implement strStr().

Memory Usage: 40.3 MB, less than 90.37% of Java online submissions for Implement strStr().

Time O(mn)

class Solution {

    public int strStr(String haystack, String needle) {

        if (haystack == null || needle == null || needle.equals("")) {

            return 0;

        }

        

        int needleLen = needle.length();

        int haystackLen = haystack.length();

        for (int start = 0; start + needleLen <= haystackLen; start++) {

            if (matches(haystack, start, needle)) {

                return start;

            }

        }

        return -1;

    }

    

    // abcde

    // qqqqabcde

    private boolean matches(String source, int start, String target) {

        for (int i = 0; i < target.length(); i++) {

            if (start + i >= source.length()) {

                return false;

            }

            if (source.charAt(start + i) != target.charAt(i)) {

                return false;

            }

        }

        return true;

    }

}

15. 3Sum

四刷 06/2022

Version #1 Two Pointers

一个可以优化但是没写出来的点就是因为array是sorted，所以如果outer loop的nums[i] > 0就可以break了，因为三个 >0 的数是没法加成0的

这里犯了一个错误就是

Arrays.asList(new int[]{a, b})这样创造出来的ArrayList是immutable的，如果想让它mutable就要先赋值给一个 new ArrayList<>(Arrays.asList(a, b))

同时看了之前的写法，也可以直接把result list的reference传进去，然后2sum找到结果以后直接加到结果里面

Time O(N^2)

Space O(logN) to O(N) used by the sorting algorithm

Runtime: 37 ms, faster than 46.23% of Java online submissions for 3Sum.

Memory Usage: 59.8 MB, less than 32.09% of Java online submissions for 3Sum.

class Solution {

    public List<List<Integer>> threeSum(int[] nums) {

        Arrays.sort(nums);

        List<List<Integer>> result = new ArrayList<>();

        for (int i = 0; i < nums.length; i++) {

            if (i != 0 && nums[i] == nums[i - 1]) {

                continue;

            }

            List<List<Integer>> pairs = twoSum(nums, i + 1, nums.length - 1, -nums[i]);

            for (List<Integer> pair : pairs) {

                pair.add(nums[i]);

                result.add(pair);

            }

        }

        return result;

    }

    

    // Find distinct pair that add up to target from nums[start, end]

    private List<List<Integer>> twoSum(int[] nums, int start, int end, int target) {

        List<List<Integer>> result = new ArrayList<>();

        while (start < end) {

            int sum = nums[start] + nums[end];

            if (sum == target) {

               result.add(new ArrayList<>(Arrays.asList(nums[start], nums[end])));

                start++;

                while (start < end && nums[start] == nums[start - 1]) {

                    start++;

                }

            } else if (sum < target) {

                start++;

            } else {

                end--;

            }      

        }

        return result;

    }

}

Version #2 HashSet - no sorting

Time O(N^2)

Space O(N)

Runtime: 684 ms, faster than 14.39% of Java online submissions for 3Sum.

Memory Usage: 150.5 MB, less than 6.74% of Java online submissions for 3Sum.

class Solution {

    public List<List<Integer>> threeSum(int[] nums) {

        Set<List<Integer>> result = new HashSet<>();

        Set<Integer> visited = new HashSet<>();

        for (int i = 0; i < nums.length; i++) {

            if (visited.contains(nums[i])) {

                continue;

            }

            visited.add(nums[i]);

            Set<Integer> seen = new HashSet<>();

            for (int j = i + 1; j < nums.length; j++) {

                if (seen.contains(-nums[i] - nums[j])) {

                    List<Integer> tuple = Arrays.asList(nums[i], nums[j], -nums[i] - nums[j]);

                    Collections.sort(tuple);

                    result.add(tuple);

                }

                seen.add(nums[j]);

            }

        }

        return new ArrayList<>(result);

    }

}

Input:[0,0,0,0]

Output:[[0,0,0],[0,0,0]]

Expected:[[0,0,0]]

三刷 05/2022

一遍bug free过了，开心

重点是要通过sorted array 来deduplicate

这里稍微陷入了一个错误，就是以为如果 i, j, k在sorted array里面，那一定只能是两个小的值加起来得到一个大的值。其实这是不对的

nums[i] + nums[j] + nums[k] = 0，无论把哪个数放到右边都成立

所以outer loop不一定是i = nums.length - 1, i--，如果用i = 0, i < nums.length也是正确的

Runtime: 25 ms, faster than 82.71% of Java online submissions for 3Sum.

Memory Usage: 58.7 MB, less than 59.10% of Java online submissions for 3Sum.

class Solution {

    public List<List<Integer>> threeSum(int[] nums) {

        // Make it a two sum question

        // nums[i] + nums[j] == nums[k]

        // Since we want to deduplicate the solution set, we need to sort the array first and skip numbers when index != 0 && nums[index] == nums[index - 1]

        if (nums == null || nums.length < 2) {

            return new ArrayList<>();

        }

        Arrays.sort(nums);

        List<List<Integer>> result = new ArrayList<>();

        for (int i = nums.length - 1; i >= 0; i--) {

            if (i != nums.length - 1 && nums[i] == nums[i + 1]) {

                continue;

            }

            twoSum(nums, i, result);

        }

        return result;

    }

    // Given nums[startIndex], find all pairs of numbers on its left that sum up to its value

    private void twoSum(int[] nums, int endIndex, List<List<Integer>> result) {

        int target = -nums[endIndex];

        int left = 0, right = endIndex - 1;

        while (left < right) {

            if (nums[left] + nums[right] < target) {

                left++;

                continue;

            }

            if (nums[left]  + nums[right] > target) {

                right--;

                continue;

            }

            result.add(Arrays.asList(nums[left], nums[right], nums[endIndex]));

            left++;

            right--;

            while (left < right && nums[left] == nums[left - 1]) {

                left++;

            }

            while (left < right && nums[right] == nums[right + 1]) {

                right--;

            }

        }

    }

}

二刷
还是写的很艰难
对于一样的数的处理是跳过，left不能和left+1一样，right不能和right-1一样，但是left是可以和right一样的
有空还是再写写吧
result.add(Arrays.asList(nums[targetIndex], nums[left], nums[right]));
这种写法也要熟悉

79.71 %

public class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        if (nums == null || nums.length <= 2) return result;
        Arrays.sort(nums);
        //TODO
        for (int i = 0; i < nums.length - 2; i++) {
            if (i == 0 || nums[i] != nums[i - 1]) {
                twoSum(nums, i, result);
            }
        }
        return result;
    }
    private void twoSum(int[] nums, int targetIndex, List<List<Integer>> result) {
     
        int target = 0 - nums[targetIndex];
        int left = targetIndex + 1, right = nums.length - 1;
        while (left < right) {
            if (nums[left] + nums[right] == target) {
                result.add(Arrays.asList(nums[targetIndex], nums[left], nums[right]));
                while (left < right && nums[left] == nums[left + 1]) left++;
                while (left < right && nums[right] == nums[right - 1]) right--;
                left++;
                right--;
            } else if (nums[left] + nums[right] > target) {
                right--;
            } else {
                left++;
            }
        }
    }
}

Version #1 Two Pointers
Time O(n^2)
三刷
三个数当遇到duplicate的时候都要跳

36.43 %
class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        if (nums == null || nums.length < 3) {
            return result;
        }
        Arrays.sort(nums);
        int len = nums.length;
        for (int i = 0; i < len; i++) {
            if (i != 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            int left = i + 1;
            int right = len - 1;
            while (left < right) {
                int sum = nums[i] + nums[left] + nums[right];
                if (sum == 0) {
                    result.add(Arrays.asList(nums[i], nums[left], nums[right]));
                    left++;
                    right--;
                    while (left < right && nums[left] == nums[left - 1]) {
                        left++;
                    }
                    while (left < right && nums[right] == nums[right + 1]) {
                        right--;
                    }
                } else if (sum < 0) {
                    left++;
                    while (left < right && nums[left] == nums[left - 1]) {
                        left++;
                    }
                } else {
                    right--;
                    while (left < right && nums[right] == nums[right + 1]) {
                        right--;
                    }
                }
            }
        }
        return result;
    }
}


一刷

Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

 Notice

Elements in a triplet (a,b,c) must be in non-descending order. (ie, a ≤ b ≤ c)

The solution set must not contain duplicate triplets.

53.69%
做这道题出现了很多小bug，主要问题是在用pointer的时候，while loop是不能无脑加的
每一次都要判断pointer是否出界
判断依据譬如left < right, index > 0, index < numbers.length等等
TwoSum可以单独写成一个method
Time Complexity O(n^2) Space Complexity O(1)
public class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        if (nums == null || nums.length == 0) return result;
        Arrays.sort(nums);
        int left, right;
        int index = 0;
        while (index < nums.length - 2) {
            if (index > 0 && nums[index] == nums[index - 1]) {
                index++;
                continue;
            }
            int target = nums[index];
            left = index + 1;
            right = nums.length - 1;
            while (left < right) {
                if (nums[left] + nums[right] + target == 0) {
                    List<Integer> temp = new ArrayList<>();
                    temp.add(target);
                    temp.add(nums[left]);
                    temp.add(nums[right]);
                    result.add(temp);
                    left++;
                    right--;
                    while (left < right && nums[left] == nums[left - 1]) left++;
                    while (left < right && nums[right] == nums[right + 1]) right--;
                } else if (nums[left] + nums[right] + target < 0) {
                    left++;
                } else {
                    right--;
                }
            }
            index++;
        }
        return result;
    }
}