看了discussion加了个queue，不过感觉没什么必要加q，反正保存的都一样，只是set.iterator().next()的时间大于O(1)，用q可以保证O(1)。看了题目条件是get可以随便返回一个值，但是test case不让这么做。很无语啊

图的题，和course schedule差不多。bfs来解，每次放入只有一个edge的node（现在的leaf）。然后直到只剩最上面一层。注意考虑单独的node（和别的node不相连）。比如: [[1,2], [2,3]], n = 6这种情况，就有[0, 4, 5]三个点都不和别的node相连。还有[], n = 2的时候就要返回[0, 1]。

Kth Smallest Element in a BST 题目链接：[链接] inorder traverse： {代码...} 二分找结果，按左边nodes数来分： {代码...} 如果改下node，加入number of left的field，那就可以在O(h)时间内找到结果了： {代码...}

这道题dfs做，关键是注意对称性，减少dfs次数。同时注意第3个条件 No jumps through non selected key is allowed. 这种情况发生在两个值的x和y差值没有1的时候，也就是abs(nx-x) == 2或者abs(nx - x) == 0，y也是同理。

Maximum Product of Word Lengths 题目链接：[链接] {代码...} 除了用bit先处理之外，还可以用set保存所有不含某个字母的word，python这么写。参考这个博客：[链接]

H-Index 题目链接：[链接] sort： {代码...} calculate suffix sum: {代码...} H-Index II 题目链接：[链接] {代码...}

Ones and Zeroes 题目链接：[链接] knapsack problem，这里是最基本的01背包，把cost变成了二维的。参考背包九讲：[链接] {代码...}

dp，可以brute force，不过这题可以memory，所以可以iteration用dp table做或者recursion：dfs+suffix array来做，还是得用二维数组保存算过的结果。这题的subproblem是到第i个数时，能够得到sum为j的ways数量，由于sum可能是负数，所以要做一个shift，使其从0开始。滚动数组优化空间。

Max Consecutive Ones 题目链接：[链接] {代码...} Max Consecutive Ones II 题目链接：[链接] {代码...}

看到discussion还有一种用入度出度的方法，比较厉害，不用额外空间：除了根节点和叶子节点之外，每个节点都有2个出度（left，right）和1个入度，根节点非空有2个出度0个入度，叶子节点有1个入度。令diff = outdegree - indegree，那么从累加diff会一直保持正，最后为0。从左往右比较好理解，因为preorder总是总root到左...

Inorder Binary Tree Inorder Traversal lc题目链接：[链接] recursion： {代码...} iteration: {代码...} morris: 参考这篇文章[链接] {代码...} Inorder Successor in BST 链接：[链接] recursion: {代码...} iteration: {代码...} 173. Binary Search Tree Iterator 题目链接：[链接]还是一样的，iteration用stack，...

dp：用dp table，就是每次找出nums[i]为结尾的最长的increasing串的长度就好了。所以分解成subproblem就是: dp[i] = max(dp[j]) + 1，这个复杂度是O(N^2)。

Is Subsequence 题目链接：[链接] greedy, 只要s里面当前的字符可以和t里的字符匹配，s的index就+1 {代码...} follow up: string很长，用字典存起来dict很大，用trie

首先确定上下的边界，左右线段按照横坐标排序。然后从左往右，如果碰到left的边，就加到集合里，碰到right的边，就从remove掉。检查重合面积：每次加left的边之前，检查一下集合里面的边是否有和当前left重合的情况，这里集合可以用heap。这里如果横坐标相同先remove right的边，再加left。检查填充满：上图的情况就组成...

Binary Tree Maximum Path Sum 题目链接：[链接] dfs对每个node，查一下包含这个node的最大路径值。 {代码...}

Diagonal traverse 题目链接：[链接] 就是找index的规律。。 {代码...}

greedy的题感觉思路好难写啊。首先肯定是要排序，首先想到的思路是先按h再按k排序，h从低到高，k从高到低，原因是第一步想先把是0的yi 个一个放进结果里，然后把前面的k都--，第二遍还是找k = 0的。一直重复到结束。

Decode String 题目链接：[链接] stack的题，感觉还是分析下stack什么时候pop，什么时候push，思路会比较快。loop里面不加while循环的写法。 {代码...}

Summary Ranges 题目链接：[链接] loop两种写法： {代码...} {代码...}

Valid Word Abbreviation 链接：[链接] 注意第一个数字是0的情况，["a", "01"]这种也是不合法的。 {代码...} {代码...} Minimum Unique Word Abbreviation 题目链接：[链接] 又是一道backtracking的题。看了这个博客的解法：[链接] 现在是穷举可能的结果，注意prune，然后check是否有和dict相同的。还有一个注意的就是要...

后两个数字，用2 points来找，从j = i + 1, k = len() - 1开始： if n[j] + n[k] < target - n[i]: count += (k-i), j++ 因为所有(j+1, k)之间的数和n[j]组合都< target - n[i]

这个题要求O(1)的复杂度。首先要做到get(key)是O(1)，能想到的数据结构只有两三种，一个是HashMap<key, value>，一个是List<value>，key是index，还有一个Array[value]， key是index。array不太可能，因为长度要initial而且不可变，题目也没说长度固定。list也不行，因为有put操作，list的insert操作是O(N)...

这道题用deque，注意一下存的是index，因为要判断是否到最大的window值，是通过现在的index和deque第一个index的差来判断的。

dfs + 记忆化搜索，用一个二维dp记录找到的最长路径的长度，如果发现dpi != 0,证明这个点被找过，不用重复。Number of Islands和这题一个思路。

把一个单词分为两个部分：left, right。right部分是回文的，在words里面找是否有reverse的left。这里的left范围是(0, len(word))，最小是0，因为要保证是两个单词，最大是len(word)，这时候要找出另一个和他相反的串。根据题目的意思，一个单词只能用一次，而且words里面单词都是unqiue的。现在的问题就在于如果判断righ...

这种找一个词由多个词组成的题，是拿dp或者dfs来解，dp本质上其实也是dfs。这道题要判断输入的词能否由字典里的单词组成，那么可以用个boolean的dp数组。

可以用trie tree来做。把所有num放进tree，之后对每一个num从最高位找是否存在和当前bit不同的path。把build tree单独写一个函数，结果TLE了，所以放一起了。。

图用topological sort，和course schedule题类似。要找到所有字母的indegree，之后用q存下入度为0的字母，然后输出。要记录下每个字母对应的所有parent字母，防止重复。求indegree的过程可以用dfs，从所有单词的index = 0开始，对不同的字母存入度，相同的去下一层。

Wiggle Sort 题目链接：[链接] 这道题允许等号，相对简单，有两种方法：1. sort然后交换奇数位和它下一位的元素，2. 不满足条件的时候直接交换 可以用递推来说明一下这么做的正确性： 假设到第i位之前都满足题目要求的关系 现在比较第i位和第i+1位 if i == odd: nums[i] >= nums[i+1]，到i+1位都满足条件 nums[i] &lt...

Encode String with Shortest Length 题目链接：[链接]