Leetcode/各大家--146. LRU Cache(HashMap + Doubly LinkedList)

146. LRU Cache(HashMap + Doubly LinkedList)
hard
https://leetcode.com/problems/lru-cache/

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

get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
put(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

Follow up:
Could you do both operations in O(1) time complexity?

Example:

LRUCache cache = new LRUCache( 2 /* capacity */ );

cache.put(1, 1);
cache.put(2, 2);
cache.get(1);       // returns 1
cache.put(3, 3);    // evicts key 2
cache.get(2);       // returns -1 (not found)
cache.put(4, 4);    // evicts key 1
cache.get(1);       // returns -1 (not found)
cache.get(3);       // returns 3
cache.get(4);       // returns 4

  Google Uber Facebook Twitter Zenefits Amazon Microsoft Snapchat Yahoo Bloomberg Palantir

思路： use a hashmap + doubly linked List: (head)..(pre)<—>(cur)<—>(next)..(end)
           Always set the head for the most recent accessed node.
           watch edge case like 1 node in list. Deleting head/tail, we need to set head/tail simultaneously.
Complexity: Time O(1) Space O(N)

public class LRUCache {
    class Node{
        Node pre;
        Node next;
        int val;
        int key;//need key fields for look back to delete in Map
        public Node(int key,int value){
            this.val = value;
            this.key = key;
        }
    }
    private void removeNode(Node n){
        Node preN = n.pre;
        Node nextN = n.next;
        if(n == head)head = nextN;//watch case of deleting head & end
        if(n == end)end = preN;//
        if(preN != null)preN.next = nextN;
        if(nextN != null)nextN.pre = preN;
    }
    public void setHead(Node n){//head is most recent val
        n.next = head;
        n.pre = null;
        if(head != null) head.pre = n;
        head = n;
        if(end == null)end = head;//actually when only head in list
    }
    //instance variable
    Node head = null;
    Node end = null;
    HashMap<Integer,Node> map = new HashMap<>(); //<val, node in list>
    int capacity;
    public LRUCache(int capacity) {
        this.capacity = capacity;
    }
    
    public int get(int key) {
        if(!map.containsKey(key))return -1;
        Node cur = map.get(key);
        removeNode(cur);
        setHead(cur);
        return cur.val;
    }
    
    public void put(int key, int value) {
        if(!map.containsKey(key)){
            if(map.size() >= capacity){
                map.remove(end.key);
                removeNode(end);
            }
            Node cur = new Node(key, value);
            map.put(key, cur);
            setHead(cur);
        }else{//update value
            Node cur = map.get(key);
            cur.val = value;
            removeNode(cur);
            setHead(cur);
        }
    }
}

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

Leetcode/G家F家 -- 341. Flatten Nested List Iterator (Design + Recur)

341. Flatten Nested List Iterator(Design + Recur)
medium
https://leetcode.com/problems/flatten-nested-list-iterator/
相关题： 同样用recursion traverse list 来计算
http://rainykat.blogspot.com/2017/01/leetcodelinkedin-339364-nested-list.html 

Given a nested list of integers, implement an iterator to flatten it.

Each element is either an integer, or a list -- whose elements may also be integers or other lists.

Example 1:
Given the list [[1,1],2,[1,1]],

By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,1,2,1,1].

Example 2:
Given the list [1,[4,[6]]],

By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,4,6].

 Google Facebook Twitter

思路： traverse the nested list using recursion and store element to arraylist.

/**
 * // This is the interface that allows for creating nested lists.
 * // You should not implement it, or speculate about its implementation
 * public interface NestedInteger {
 *
 *     // @return true if this NestedInteger holds a single integer, rather than a nested list.
 *     public boolean isInteger();
 *
 *     // @return the single integer that this NestedInteger holds, if it holds a single integer
 *     // Return null if this NestedInteger holds a nested list
 *     public Integer getInteger();
 *
 *     // @return the nested list that this NestedInteger holds, if it holds a nested list
 *     // Return null if this NestedInteger holds a single integer
 *     public List<NestedInteger> getList();
 * }
 */
public class NestedIterator implements Iterator<Integer> {
    List<Integer> list = new ArrayList<>();
    int pos = 0;//current position
    public NestedIterator(List<NestedInteger> nestedList) {
        //use arrayList to store nestedList
        traverse(nestedList);
    }
    public void traverse(List<NestedInteger> nestedList){
        if(nestedList == null) return;
        for(NestedInteger e: nestedList){
            if(e.isInteger()){
                list.add(e.getInteger());
            }else{
                traverse(e.getList());//do recursion when meeting list element
            }
        }
    }
    @Override
    public Integer next() {
        return list.get(pos++);
    }

    @Override
    public boolean hasNext() {
        return pos < list.size();
    }
}

/**
 * Your NestedIterator object will be instantiated and called as such:
 * NestedIterator i = new NestedIterator(nestedList);
 * while (i.hasNext()) v[f()] = i.next();
 */

Leetcode/F家 -- 398. Random Pick Index(Desgin + Random)

398. Random Pick Index(Design + Random)
Medium
https://leetcode.com/problems/random-pick-index/ 

Given an array of integers with possible duplicates, randomly output the index of a given target number. You can assume that the given target number must exist in the array.

Note:
The array size can be very large. Solution that uses too much extra space will not pass the judge.

Example:

int[] nums = new int[] {1,2,3,3,3};
Solution solution = new Solution(nums);

// pick(3) should return either index 2, 3, or 4 randomly. Each index should have equal probability of returning.
solution.pick(3);

// pick(1) should return 0. Since in the array only nums[0] is equal to 1.
solution.pick(1);

思路： use random to ensure equal possibility, key point is save extra space.
解法1: for easier understanding, we create arraylist to store all index of target, and count total,
           Then we use random  from [0,total), to equally pick any element in the array 
Complexity: O(N)time O(m)space - # of target in nums

public class Solution {
    int[] nums;
    Random rand;
    public Solution(int[] nums) {
        this.nums = nums;
        this.rand = new Random();
    }
    public int pick(int target) {
        int total = 0;//total index match target
        int res = -1;
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == target) {
                total++;
                list.add(i);
            }
        }
        res = list.get(rand.nextInt(total)); //int in [0,total)
        return res;
    }
}

解法2: To use no extra space, we pick the index in place.
             (Reservoir Sampling) update by 1/total in the loop
             靠前的index一开始选中的几率高，但是后面loop剩的多被replace的几率也高
             举例有5个元素：
             对于第二个index来说，1/2（pick）*2/3(replace)*3/4(replace)*4/5(replace) = 1/5;
             对于最后一个index来说，就是 1/5(pick) = 1/total.

public class Solution {
    int[] nums;
    Random rand;
    public Solution(int[] nums) {
        this.nums = nums;
        this.rand = new Random();
    }
    public int pick(int target) {
        int total = 0;//total index match target
        int res = -1;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == target) {
                total++;
                int x = rand.nextInt(total);//[0,total)
                if(x == 0){
                    res = i;
                }
            }
        }
        return res;
    }
}
/**
 * Your Solution object will be instantiated and called as such:
 * Solution obj = new Solution(nums);
 * int param_1 = obj.pick(target);
 */

Leetcode/各大家 -- 297. Serialize and Deserialize Binary Tree (Design)

297. Serialize and Deserialize Binary Tree (Design)
Hard
https://leetcode.com/problems/serialize-and-deserialize-binary-tree/

Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.

Design an algorithm to serialize and deserialize a binary tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized to the original tree structure.

For example, you may serialize the following tree

    1
   / \
  2   3
     / \
    4   5

as "[1,2,3,null,null,4,5]", just the same as how LeetCode OJ serializes a binary tree. You do not necessarily need to follow this format, so please be creative and come up with different approaches yourself.

Note: Do not use class member/global/static variables to store states. Your serialize and deserialize algorithms should be stateless.

LinkedIn Google Uber Facebook Amazon Microsoft Yahoo Bloomberg

Serialize: Binary Tree 转成 String
Deserialize: String 转成 Binary Tree

思路： use 2 string marker: "X" for null - empty node, "," for spliter - spliting nodes
          To Serialize, do pre-order traversal. Append node.val(sb可直接append数字) + spliter to StringBuilder recursively.
          To Deserialize, create a queue to add nodes from string(need to 1st split 2nd convert to arraylist) . Then recursively build the tree by pointing left & right children.

Complexity: O(N) time travel all nodes

public class Codec {
    private final String nullN = "X";
    private final String spliter = ",";
    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        buildString(root,sb);
        return sb.toString();
    }
    private void buildString(TreeNode node, StringBuilder sb){
        if(node == null){
            sb.append(nullN).append(spliter);
            return;
        }
        sb.append(node.val).append(spliter);
        buildString(node.left,sb);
        buildString(node.right,sb);
    }
    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        Queue<String> nodes = new LinkedList<String>();
        nodes.addAll(Arrays.asList(data.split(spliter)));
        return buildTree(nodes);
    }
    private TreeNode buildTree(Queue<String> nodes){
        String val = nodes.remove();//return null
        if(val.equals(nullN))
            return null;
        TreeNode node = new TreeNode (Integer.valueOf(val));//Integer.parseInt()
        node.left = buildTree(nodes);
        node.right = buildTree(nodes);
        return node;
    }
}

// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.deserialize(codec.serialize(root));

Leetcode/F家 -- 157.158. Read N Characters Given Read4 I/ II - Call multiple times (Design)

157.158 Read N Characters Given Read4  I/ II - Call multiple times (Design)
easy hard
https://leetcode.com/problems/read-n-characters-given-read4/

The API: int read4(char *buf) reads 4 characters at a time from a file.

The return value is the actual number of characters read. For example, it returns 3 if there is only 3 characters left in the file.

By using the read4 API, implement the function int read(char *buf, int n) that reads n characters from the file.

Note:
The read function will only be called once for each test case.

思路： 理解-read4(buf) pass进去一个4格子的Array buff，将其填入file中的内容，返回读了4个还是<4个字。读过就算过了这字，下次从剩余的字读起。我们要把buff里面的值赋给buf
           设计read function从file读取n个char。
           关键点是: 最后不满4个数需要读取时，取(file剩余字符)和(剩余需读字符）中较小的值
Complexity: O(n) time
Ex： "ab" read(1): "a"

public class Solution extends Reader4 {
    /**
     * @param buf Destination buffer
     * @param n   Maximum number of characters to read
     * @return    The number of characters read
     */
    char[] buff = new char[4];
    int count = 0;//count from read4 [0,4]
    public int read(char[] buf, int n) {
        int total = 0;//total bytes have read
        while(n > 0){
            count = read4(buff);
            count = Math.min(n, count);
            for(int i = 0; i < count; i++){
                buf[total++] = buff[i];
            }
            if(count < 4)break;
            n -= 4;
        }
        return total;
    }
}

158. call read multiple times

class instance variable概念，obj的var 是keep住的
eg "abcde" [read(1) ,read(4)] - > ["a","bcde"] buffPrt： 0，1； buffCN： 4,4

思路： 在buff有剩余unread cell时(count > n)会考虑， 需要多2个变量,
           pos记录上次剩余未读的buff cell数量，index是第一个未读数的位置（其实就算count）
           在开始read4()之前，先把上一次left over 的buff assign 给buf。 注意每次loop前依旧和n比较，取小值。
ex: "ab"[read(0),read(1),read(2),read(1)] result["","a","b",""]

public class Solution extends Reader4 {
    /**
     * @param buf Destination buffer
     * @param n   Maximum number of characters to read
     * @return    The number of characters read
     */
    char[] buff = new char[4];
    int count = 0;//count from read4 [0,4]
    int pos = 0;//record left number of unused cell in buff
    int leftcnt = 0;//the index of unsed cell in buff
    int index = 0;//index of unsed cell in buff
    public int read(char[] buf, int n) {
        int total = 0;//total bytes have read
        /*fill the left over in buff first*/
        int pre = Math.min(n, leftcnt);
        for(int i = 0; i < pre; i++){
            buf[total++] = buff[index++];
            n--;
            leftcnt--;
        }
        while(n > 0){
            count = read4(buff);
            if(count > n){
                leftcnt = count - n;//unused cells
                index = n;//the index of unread cells in buff
                count = n;
            }else{
                leftcnt = 0;//all buff cells used
            }
            for(int i = 0; i < count; i++){
                buf[total++] = buff[i];
            }
            if(count < 4)break;
            n -= 4;
        }
        return total;
    }
}