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/各大家-- 380. Insert Delete GetRandom O(1) (Random + Design)

380. Insert Delete GetRandom O(1)
medium
https://leetcode.com/problems/insert-delete-getrandom-o1/

Design a data structure that supports all following operations in average O(1) time.

1. insert(val): Inserts an item val to the set if not already present.
2. remove(val): Removes an item val from the set if present.
3. getRandom: Returns a random element from current set of elements. Each element must have the same probability of being returned.

Example:

// Init an empty set.
RandomizedSet randomSet = new RandomizedSet();

// Inserts 1 to the set. Returns true as 1 was inserted successfully.
randomSet.insert(1);

// Returns false as 2 does not exist in the set.
randomSet.remove(2);

// Inserts 2 to the set, returns true. Set now contains [1,2].
randomSet.insert(2);

// getRandom should return either 1 or 2 randomly.
randomSet.getRandom();

// Removes 1 from the set, returns true. Set now contains [2].
randomSet.remove(1);

// 2 was already in the set, so return false.
randomSet.insert(2);

// Since 2 is the only number in the set, getRandom always return 2.
randomSet.getRandom();

 Google Uber Twitter Amazon Yelp Pocket Gems Facebook

思路：Use HashMap + ArrayList to build the data structure.
          Map store pairs of <val, index in list> and List is store the val existed.
          They are same size. Add and remove together
          When removal, list: replace the removed element with last added element.
                                    map: replace the index(val) of last added element, and remove val(key)

Complexity: Space: O(N)

ublic class RandomizedSet {
    Map<Integer, Integer> map;//<val, index in arrlist>
    List<Integer> list;//keep a record of value for get random 
    int size;//map and list are the same size
    Random rand;
    /** Initialize your data structure here. */
    public RandomizedSet() {
        this.map = new HashMap<>();
        this.list = new ArrayList<>();
        this.size = 0;
        this.rand = new Random();
    }
    
    /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
    public boolean insert(int val) {
        if(map.containsKey(val)) return false;
        map.put(val, size);
        list.add(val);
        size++;
        return true;
    }
    
    /** Removes a value from the set. Returns true if the set contained the specified element. */
    public boolean remove(int val) {
        if(map.containsKey(val)){
            int last = list.get(size - 1);
            list.set(map.get(val), last);//use last added ele to fill the element to be removed 
            map.put(last, map.get(val));//update last added ele's index in list
            map.remove(val);
            list.remove(size - 1);//remove at end is constant
            size--;
            return true;
        }
        return false;
    }
    
    /** Get a random element from the set. */
    public int getRandom() {
        return list.get(rand.nextInt(size));
    }
}

/**
 * Your RandomizedSet object will be instantiated and called as such:
 * RandomizedSet obj = new RandomizedSet();
 * boolean param_1 = obj.insert(val);
 * boolean param_2 = obj.remove(val);
 * int param_3 = obj.getRandom();
 */

Leetcode/亚麻 -- 199. Binary Tree Right Side View (BFS + DFS)

199. Binary Tree Right Side View (BFS + DFS)
medium
https://leetcode.com/problems/binary-tree-right-side-view/

Given a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.

For example:
Given the following binary tree,

   1            <---
 /   \
2     3         <---
 \     \
  5     4       <---

You should return [1, 3, 4].

思路1： BFS, use level order traverlsal. key is to track each level size, and add the 1ast one to list.

public List<Integer> rightSideView(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Queue<TreeNode> qu = new LinkedList<>();
        if(root == null) return res;
        qu.offer(root);
        while(!qu.isEmpty()){
            int size = qu.size();
            for(int i = 0; i < size; i++){//traveling current level
                TreeNode curr = qu.remove();
                if(i == size - 1)res.add(curr.val);
                if(curr.left != null) qu.offer(curr.left);
                if(curr.right != null) qu.offer(curr.right);
            }
        }
        return res;
    }

思路2: DFS， preorder改一下顺序，从右走的左边. To ensure rightmost node of depth,
            Key is we ensure we only add the first node of the specific depth by check depth == list size.
for ex, if we add node at depth 1 from right subtree, we won't add it again when travel the left subtree

public List<Integer> rightSideView(TreeNode root) {
        List<Integer> result = new ArrayList<Integer>();
        traverse(root, result, 0);
        return result;
    }
    public void traverse(TreeNode root, List<Integer> result, int depth){
        if(root == null)return;
        if(depth == result.size()){
            result.add(root.val);
        }
        traverse(root.right, result, depth + 1);
        traverse(root.left, result, depth + 1);
    }

Leetcode/亚麻 -- 438. Find All Anagrams in a String (window2ptr)

438. Find All Anagrams in a String(window 2ptr)
easy
https://leetcode.com/problems/find-all-anagrams-in-a-string/

Given a string s and a non-empty string p, find all the start indices of p's anagrams in s.

Strings consists of lowercase English letters only and the length of both strings s and p will not be larger than 20,100.

The order of output does not matter.

Example 1:

Input:
s: "cbaebabacd" p: "abc"

Output:
[0, 6]

Explanation:
The substring with start index = 0 is "cba", which is an anagram of "abc".
The substring with start index = 6 is "bac", which is an anagram of "abc".

Example 2:

Input:
s: "abab" p: "ab"

Output:
[0, 1, 2]

Explanation:
The substring with start index = 0 is "ab", which is an anagram of "ab".
The substring with start index = 1 is "ba", which is an anagram of "ab".
The substring with start index = 2 is "ab", which is an anagram of "ab".

思路： string window套路 using 2 pointer, key is to check 'end - start + 1 == t.length()' to find valid anagram.
Complexity: O(N) time - loop, O(N) space - map

public class Solution {
    public List<Integer> findAnagrams(String s, String t) {
        List<Integer> res = new ArrayList<Integer>();
        Map<Character, Integer> map = new HashMap<Character, Integer>();//<all char, freq in t>
        for(char c : s.toCharArray()) map.put(c, 0);
        for(char c : t.toCharArray()){
            if(map.containsKey(c))
                map.put(c, map.get(c) + 1);
            else 
                return res;
        }
        int start = 0, end = 0;
        int counter = t.length();
        while(end < s.length()){
            char cur = s.charAt(end);
            if(map.get(cur) > 0) counter--;
            map.put(cur, map.get(cur) - 1);
            while (counter == 0){
                if(end - start + 1 == t.length()) res.add(start);
                char c2 = s.charAt(start);
                map.put(c2, map.get(c2) + 1);
                if(map.get(c2) > 0) counter++;
                start++;
            }
            end++;
        }
        return res;
    }
}

Leetcode/各大家 -- 127. Word Ladder(BFS)

127. Word Ladder（BFS）
Medium
https://leetcode.com/problems/word-ladder/

Given two words (beginWord and endWord), and a dictionary's word list, find the length of shortest transformation sequence from beginWord to endWord, such that:

1. Only one letter can be changed at a time.
2. Each transformed word must exist in the word list. Note that beginWord is not a transformed word.

For example,

Given:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log","cog"]

As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
return its length 5.

Note:

• Return 0 if there is no such transformation sequence.
• All words have the same length.
• All words contain only lowercase alphabetic characters.

 Amazon LinkedIn Snapchat Facebook Yelp

思路： Use BFS to traverse dictionary. The level is composed of the words that are 1 char diff from curWord. If find such newWord, first check if is end word so we return min length, else check if in dict & remove it to avoid repeat.
4 loops in total: 1st queue.isEmpty(); 2nd queue.size() -- current level
                          3rd curword.length() - chose every char; 4th 'a' to 'z' - replace each char

 Note: if use DFS, we need to travel all path to decide the shortest one. If using BFS, we stop once we found since we start from short to find the path.解释

public class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        if(beginWord.equals(endWord)) return 1;
        Set<String> set = new HashSet<>(wordList);
        Queue<String> q = new LinkedList<>();
        int len = 2;
        q.offer(beginWord);
        while(!q.isEmpty()){
            int size = q.size();
            for(int i = 0; i < size; i++){
                String cur = q.poll();
                for(int j = 0; j < cur.length(); j++){
                    StringBuilder sb = new StringBuilder(cur);
                    for(char c = 'a'; c <= 'z'; c++){
                        sb.setCharAt(j, c);
                        String tmp = sb.toString();
                        if(set.contains(tmp)){
                            if(tmp.equals(endWord)) return len;//endword need to be in dict
                            q.offer(tmp);
                            set.remove(tmp);
                        }
                    }
                }
            }
            len++;
        }
        return 0;
    }
}

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