286. Walls and Gates

-1 - A wall or an obstacle.
0 - A gate.
INF - Infinity means an empty room.
For example, given the 2D grid:
INF -1 0 INF
INF INF INF -1
INF -1 INF -1
0 -1 INF INF
After running your function, the 2D grid should be:
3 -1 0 1
2 2 1 -1
1 -1 2 -1
0 -1 3 4

DFS BFS都可以做，需要注意的是以门为起点去向下延伸，而不是以房间开始

public void wallsAndGates(int[][] rooms) {
    for (int i = 0; i < rooms.length; i++)
        for (int j = 0; j < rooms[0].length; j++)
            if (rooms[i][j] == 0) dfs(rooms, i, j, 0);
}

private void dfs(int[][] rooms, int i, int j, int d) {
  // 注意rooms[i][j] < d
    if (i < 0 || i >= rooms.length || j < 0 || j >= rooms[0].length || rooms[i][j] < d) return;
    rooms[i][j] = d;
    dfs(rooms, i - 1, j, d + 1);
    dfs(rooms, i + 1, j, d + 1);
    dfs(rooms, i, j - 1, d + 1);
    dfs(rooms, i, j + 1, d + 1);
}

class Solution {
    public void wallsAndGates(int[][] rooms) {
        Queue<int[]> queue = new LinkedList<>();
        for (int i = 0; i < rooms.length; i++) {
            // find gate
            for (int j = 0; j < rooms[i].length; j++) {
                if (rooms[i][j] == 0) {
                    queue.offer(new int[]{i, j});
                }
            }
        }
        int[] dx = {0, 0, -1, 1};
        int[] dy = {1, -1, 0, 0};
        while (!queue.isEmpty()) {
            int[] cor = queue.poll();
            int i = cor[0], j = cor[1];
            for (int idx = 0; idx < 4; idx++) {
                if (i + dx[idx] >= 0 && i + dx[idx] <= rooms.length - 1 && j + dy[idx] >= 0 && j +                                                  dy[idx] <= rooms[0].length - 1 && rooms[i + dx[idx]][j + dy[idx]] == Integer.MAX_VALUE) {
                    rooms[i + dx[idx]][j + dy[idx]] = rooms[i][j] + 1;
                    queue.offer(new int[]{i + dx[idx], j + dy[idx]});
                }
            }
        }
    }
}

DFS & BFS

516. Longest Palindromic Subsequence

subsequence和substring不一样 比如 bbbab 最长的sub sequency是bbbb，所以返回4

memo search比较好理解，helper函数传入头尾指针，如果头尾的字符相同，那么该字符串的最长回文长度就是2+中间部分的最长回文长度，进行递归。如果头尾的字符不同，那么头指针+1尾指针不动，或尾-1头不动。查过的substring用memo记录。helper函数传入头尾指针和memo二维数组。memo[i][j]表示以i, j分割出的substring的最长回文长度
Palindromic常用套路dp[i][j]
Palindromic还有一种方法叫做extend，定义中心pivot然后向两边扩展，pivot可以是a，也可以是aa这种

class Solution {
    public int longestPalindromeSubseq(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        return helper(s, 0, s.length() - 1, new Integer[s.length()][s.length()]);
    }
    public int helper(String s, int start, int end, Integer[][] memo) {
        if (memo[start][end] != null) {
            return memo[start][end];
        }
        if (start > end) {
            return 0;
        }
        if (start == end) {
            return 1;
        }
        if (s.charAt(start) == s.charAt(end)) {
            memo[start][end] = 2 + helper(s, start + 1, end - 1, memo);
        } else {
            memo[start][end] = Math.max(helper(s, start + 1, end, memo), helper(s, start, end - 1, memo));
        }
        return memo[start][end];
    }
}

DFS + Memo Search

380. Insert Delete GetRandom O(1)

设计一个数据结构支持O(1)的插入删除返回随机数

hash支持O1的insert和delete但无法返回随机数，list可以通过index支持O1的删除和插入
所以用hashmap保存value-index信息，同时也维护一个arraylist
答案只删除array list的最后位置，如果不是要swap

Random rand = new Random();
rand.nextInt(n) //不包括n

DATA STRUCTURE

673. Number of Longest Increasing Subsequence

Input: [1,3,5,4,7]
Output: 2
Explanation: The two longest increasing subsequence are [1, 3, 4, 7] and [1, 3, 5, 7].
找到最长递增子序列的个数

思路来自于找最长连续递增子序列的长度，一个DP数组记录截止到当前位置最长的递增子序列长度，另一个DP数组记录到当前位置的子序列，有几种可能构造出最长长度。何时更新第二个DP数组是复杂的地方。
DP写法需要学习

• DP数组在哪初始化
• 全局变量在何处更新

class Solution {
    public int findNumberOfLIS(int[] nums) {
        int N = nums.length;
        if (N <= 1) return N;
        int[] lengths = new int[N]; //lengths[i] = length of longest ending in nums[i]
        int[] counts = new int[N]; //count[i] = number of longest ending in nums[i]
        Arrays.fill(counts, 1);

        for (int j = 0; j < N; ++j) {
            for (int i = 0; i < j; ++i) if (nums[i] < nums[j]) {
                if (lengths[i] >= lengths[j]) {
                    lengths[j] = lengths[i] + 1;
                    counts[j] = counts[i];
                } else if (lengths[i] + 1 == lengths[j]) {
                    counts[j] += counts[i];
                }
            }
        }

        int longest = 0, ans = 0;
        for (int length: lengths) {
            longest = Math.max(longest, length);
        }
        for (int i = 0; i < N; ++i) {
            if (lengths[i] == longest) {
                ans += counts[i];
            }
        }
        return ans;
    }
}

DP

208. Implement Trie (Prefix Tree)

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

212. Word Search II

给一个char的矩阵和单词list，找出list中在矩阵中的单词

Trie + backtracking (典型题）

20. Valid Parentheses

22. Generate Parentheses

给一个n是左右括号有几对，返回所有的左右括号组合

dfs做，找出所有可能性，搞清什么时候可以加左括号，什么时候可以加右括号
helper(int left, int right, int n, String temp, List<String> res)
// base case
temp.legnth() == n * 2

241. Different Ways to Add Parentheses

2 * 3 - 4 * 5 可以在各处加括号，返回所有可能的结果

每个运算符分成左右两个部分，两部分再递归调用自己，分治！
如何判断进来的是只有数字的字符串比较重要：res的size是0

23.Merge K sorted array

Merge K个排好序的链表
Divide&Conquer

57. Insert Interval

Given intervals [1,3],[6,9], insert and merge [2,5] in as [1,5],[6,9]

分析出三种情况很重要，
1 有交集（交集的子情况也比较多，但两种不相交比较好找），就把待merge数组的start end，再继续去merge
2 interval在待merge数组的前面，把interval加进result
3 interval在待merge数组的后面，把两个数组都加进result，并把merge数组改成null，之后都不管了
最后别忘了如果merge数组不是null的话 将其加入result

// 如果没有排过序
Collections.sort(list, new Comparator<Interval> {
@override
public int compare(Interval i1, Intervali2) {
 return i1.start -i2.start;
}
});

253. Meeting Rooms II

同类型题

283. Move Zeroes

Given nums = [0, 1, 0, 3, 12], after calling your function, nums should be [1, 3, 12, 0, 0].

两个指针做，用for循环比用while更好理清思路，不是说非得上来就声明两根指针，一根指针声明，另一根在for循环里
Two pointer

621. Task Scheduler

Input: tasks = ["A","A","A","B","B","B"], n = 2
Output: 8
Explanation: A -> B -> idle -> A -> B -> idle -> A -> B.

算个数和给出真正的顺序是有差别的，不必纠结于先A还是先B，开始想复杂了。实际上n+1个坑，从频率高到低从pq里poll出来填进坑里，再放进tempList，所以在这个size是n+1的slot里，每个任务出现一次，如果pq里没任务了但计数器还没到n+1，就说明需要加idle，统计个数即可。把tempList的task如果freq大于1，再丢回pq

Comparator<Task> comp = (t1, t2) -> t2.count - t1.count

PriorityQueue

325. Maximum Size Subarray Sum Equals k

Given nums = [1, -1, 5, -2, 3], k = 3,
return 4. (because the subarray [1, -1, 5, -2] sums to 3 and is the longest)

Subarray类题目需要想到前缀和数组，优化➕Hashmap
sum(i~j) = PrefixSum(j+1) - PrefixSum(i) PrefixSum[0] = 0
** Subarray + Hashmap**

class Solution {
    public int maxSubArrayLen(int[] nums, int k) {
            if(nums == null || nums.length == 0) return 0;
            int length = nums.length, sum = 0, maxSubLen = 0;
            //Using a hash map to store the sum of all the values before and include nums[i]
            Map<Integer, Integer> map = new HashMap();
            for(int i = 0; i < length; i++) {
                sum += nums[i];
                if(sum == k) {
                    maxSubLen = Math.max(maxSubLen, i + 1);
                } else if(map.containsKey(sum - k)) {
                    maxSubLen = Math.max(maxSubLen, i - map.get(sum - k));
                }
                if(!map.containsKey(sum)) {
                    map.put(sum, i);
                }
            }
            return maxSubLen;
        }
}

523. Continuous Subarray Sum

Input: [23, 2, 4, 6, 7], k=6
Output: True
Explanation: Because [2, 4] is a continuous subarray of size 2 and sums up to 6.

思路好想，但是乘除法有点绕， 把余树放进map里

    public boolean checkSubarraySum(int[] nums, int k) {
        if (nums == null || nums.length == 0) {
            return false;
        }
        Map<Integer, Integer> map = new HashMap<>();
        int sum = 0;
        // hold the position
        map.put(0, -1);
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            if (k != 0) {
                sum = sum % k;
            }
            if (map.containsKey(sum)) {
                // make sure at least subarray has more than 2 elements
                if (i - map.get(sum) > 1) {
                    return true;
                }
            } else {
                map.put(sum, i);
            }
        }
        return false;
    }

238. Product of Array Except Self

For example, given [1,2,3,4], return [24,12,8,6]. 要求O(n)

Two passes，第一趟用一个变量记录index左边的乘积，第二趟记录右边的成积，再乘起来

554. Brick Wall

Input:
[[1,2,2,1],
[3,1,2],
[1,3,2],
[2,4],
[3,1,2],
[1,3,1,1]]
Output: 2

用hashmap存每个边出现的频率不难想，在于一遍就能得出结论，而不是再遍历map一遍去找最大值，每次往map里放完东西，都更新一遍最大值

class Solution {
    public int leastBricks(List<List<Integer>> wall) {
        Map<Integer, Integer> map = new HashMap<>();
        // 主要是这个count
        int count = 0;
        for(int i = 0; i < wall.size(); i++) {
            int sum = 0;
            for(int j = 0; j < wall.get(i).size() - 1; j++) {
                sum = sum + wall.get(i).get(j);
                map.put(sum, map.getOrDefault(sum, 0) + 1);
                count = Math.max(count, map.get(sum));
            }
        }
        return wall.size() - count;
    }
}

*Hashmap

209. Minimum Size Subarray Sum

For example, given the array [2,3,1,2,4,3] and s = 7,
the subarray [4,3] has the minimal length under the problem constraint.

解法比较高级，1+3+1+3=8>7，所以让8减第一个元素尝试去缩小window，更新最小值，然后减第二个直到不能缩小，指针停下。
while循环三步走，先update最值，删开头尝试新可能性，最后挪start

    public int minSubArrayLen(int s, int[] nums) {
        int sum = 0, start = 0, res = Integer.MAX_VALUE;
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            while (sum >= s) {
                res = Math.min(res, (i - start + 1));
                sum -= nums[start];
                start++;
            }
        }
        return (res == Integer.MAX_VALUE) ? 0 : res;
    }

Sliding Window

76. Minimum Window Substring
    S = "ADOBECODEBANC"
    T = "ABC"
    Minimum window is "BANC".

思路和上题一样，找最小的窗口
Sliding Window

class Solution {
    public String minWindow(String s, String t) {
        Map<Character, Integer> map = new HashMap<>();
        for (char c : t.toCharArray()) {
            map.put(c, map.getOrDefault(c, 0) + 1);
        }
        int start = 0, minSize = Integer.MAX_VALUE, minStart = 0, count = 0;
        for (int i = 0; i < s.length(); i++) {
            
            char c = s.charAt(i);
            if (map.containsKey(c)) {
                
                map.put(c, map.get(c) - 1);
                if (map.get(c) >= 0) {
                    count++;
                }
            }
            // A -1, B 0， 存在负数的可能
            while (count == t.length()) {
                // update
                if (i - start + 1 < minSize) {
                    minSize = i - start + 1;
                    minStart = start;
                }
                // delete first
                char r = s.charAt(start);
                if (map.containsKey(r)) {
                    map.put(r, map.get(r) + 1);
                    // 注意是 > 0, 过剩了再减 AAB
                    if (map.get(r) > 0) {
                        count--;
                    }
                }
                start++;
            }

        }
        return (minSize == Integer.MAX_VALUE) ? "" : s.substring(minStart, minStart + minSize);
    }
}

239. Sliding Window Maximum

** Deque **
Given nums = [1,3,-1,-3,5,3,6,7], and k = 3.
Therefore, return the max sliding window as [3,3,5,5,6,7].
Find max value of each sliding window

用双端队列，LinkedList实现
队列里存index，不存值，
每进来一个新值，1）看是不是要poll出最老的元素 2）进来的新值如果比之前的值大，pollLast，因为用不到他们

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        if (n == 0) {
            return nums;
        }
        int[] result = new int[n - k + 1];
        LinkedList<Integer> dq = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            // peek, poll针对队头（最早进入的元素）
            if (!dq.isEmpty() && dq.peek() < i - k + 1) {
                dq.poll();
            }
            while (!dq.isEmpty() && nums[i] >= nums[dq.peekLast()]) {
                dq.pollLast();
            }
            dq.offer(i);
            if (i - k + 1 >= 0) {
                result[i - k + 1] = nums[dq.peek()];
            }
        }
        return result;
    }
}

140. Word Break II