思路总结

数组：

数组内顺序：

• 是否有序？
• 如果排序，是否会有额外的性质？
• 递增、递减在该题内的含义？

• prefix sum（前缀数组）在该题内是否有特殊含义？
• 如果是 continuous subarray 的问题
  1. dp 是否有用？
  2. 滑动窗口 + hash map 是否有用？
  3. 考虑 prefix sum + hash map 是否有用？
  4. 双指针相向而行是否有用？其实滑动窗口也是双指针类型的。因此2，4可以合并为：双指针解法。

二维数组：

• 是否和图有关系？如果有关系，则使用图的思路来思考。

如果需要涉及单调栈（monotonic stack)，思考是否能够用一个变量代替。

树：

• 遍历方式？DFS (pre order, in order, post order)，BFS (level order)。
• 如果是 DFS，是否有必要使用 stack 代替 recursion？一般在 in order 的使用。

String：

• 如果涉及的两个字符串之间的转换，可以思考是否能够使用二维 dp，一个字符串当行，另一个当列。
• 涉及 String 的 拆分，可以考虑 dp。例题：139 word break。
• 如果需要使用 Map 记录每个字符的信息，可以考虑是否能够使用 数组 代替。

dfs：

• 首先先确定 dfs 的物理意义，并在每一层都严格维护。
• 如果发现过程可以使用 buffer，并且 buffer 的 key 是整数，则可以考虑使用 dp。
• 如果题目需要给出 “所有” 的可能情况，考虑 dfs。考虑剪枝的情况。

bfs：

• 如果需要记录 最短距离，那么遍历首选 bfs。

Union find

• 是否需要把数据进行分组？例如 分邮件、large island 问题，都需要进行分组。

算法需要回看历史数据

• 如果算法中需要回看之前的数据（尤其是前一个访问过的数据），可以考虑使用 Stack。
• 使用 HashMap 记录遍历过的数据，查找方便。例如 two sum，continuous subarray sum。

国版

31. Next Permutation

tag：递增、递减序列在题目中的特殊意义
寻找数组中递增、递减序列的含义。和之前“无序数组找任意peek”那道题一样，需要找到递增、递减序列在其中具有的特殊意义才能解决问题。

426. Convert Binary Search Tree to Sorted Doubly Linked List

tag：经典 dfs，将dfs函数物理意义定义清楚
非常经典的dfs。只要把dfs的物理意义给定义好，实现dfs的过程严格按照物理意义来，那么解题就很简单。注意其中关于 null 的判断与处理。

1762. Buildings With an Ocean View

tag：使用不断更新的变量来代替单调栈dp数组 (Monotonic stack)
使用单独的变量来代替单调栈数组（也即使用dp求得每个位置的最大值）。这个技巧使用在了“最大的雨水积累”、“除了自己之外的数字乘积”等需要使用单调栈的地方。单调栈英文：monotonic stack。

50. Pow(x, n)

tag：Integer.MIN_VALUE在取反时会超过 int 的取值范围
注意需要先将 int n 转化为 long n进行计算，因为n有可能是-2^31，它取反是超过int范围的。这是一个坑，需要注意。

139. Word Break (Mark)

tag：带 buffer 的 dfs，可以使用 dp 解决
带buffer的dfs，可以转化为动态规划。这种String类型的题目大多可以使用动态规划来解决。该题需要注意边界条件的判断。

美版

238. Product of Array Except Self

tag：使用变量代替单调栈dp数组
同国版1762。

199. Binary Tree Right Side View

tag：bfs进行level order traversal
经典的 bfs level order traversal。

301. Remove Invalid Parentheses

tag：带有剪枝的 dfs
由于题目中要求求出所有可能的情况，因此算法上选择 dfs。首先定义好 dfs 的物理意义。对于本题，可以发现能够剪枝的情况，即左括号 <= 右括号时，如果再遇到一个右括号就可以直接丢弃。同时需要记住 dfs 里吃了吐的原则，一定要保证这点。

这道题和另一题很像，但那道题只要求返回最小removal中的任意一个就可以了，因此不用dfs，而用StringBuilder + Linear Scan 即可。题目之差几个字，但是算法截然不同。

528. Random Pick with Weight

tag：随机数，可以使用前缀和 prefixSum 解决
新的题型，根据数字大小按权重选择数字。使用 prefixSum + binary search 来代替选择过程。

827. Making A Large Island (Mark)

tag：dfs；union find；最多可以将一个1转换成0
经典的题目，组合了dfs + union find + 面对可转换0->1时的解题思路。

1. 在进行dfs的时候，如果是在一个二维数组上进行dfs，那么可以直接使用一个boolean matrix 作为 visited，没有必要使用Set<String>。

2. 解决这种“可以转换内容”的题目时，可以考虑先将转换的机会用掉，然后在一个确定的情景下解题，这样更容易。比如本题，最多允许将1个1转换为0，那么可以直接扫描所有的0，对于扫描的0将其作为1看待，这样就成为一个确定情景了。

3. Union find 是解决这类面积类为题的思路之一。使用 dfs 求得。

1650. Lowest Common Ancestor of a Binary Tree III (Mark)

tag：LCA变种，容易踩坑，从一个node一直往上道null后，需要从另一个node再重新开始
这道题和传统的LCA不同，这道题的 Node 给了 parent 指针，并且 root 不再作为函数参数传递进来了。

这道题需要注意一点的是，给的两个 Node 可能不在同一层，因此不能无脑的取 parent 判断相不相等。

636. Exclusive Time of Functions

tag：linear scan + stack
对于这类linear scan过程需要会看之前内容的题目，可以考虑使用 stack。加入 stack 之后算法的核心思想就是如何利用、维护 stack 以及里面的内容。

721. Accounts Merge (Mark)

tag：Union Find
对于需要“合并”类的题目，可以使用 Union-Find 算法。

Union Find 算法的大致思路是，给每个节点都设置一个 parent，这个 parent 也表示当前节点和parent节点属于同一个 union。每一个union都有一个自己的特殊标识，这个标识可以是自己另外指定的（例如指定额外的index作为标识），也可以将union中的某个节点作为标识（对于该节点来说，parent就是它自己）。在扫描所有节点的过程中，不断更新维护 parent，最后就可以将整个集合分成若干 union。

Union Find 算法的核心函数是 find() 和 union()。find函数是找到给定节点所属的 union，union()可以合并两个union()。需要额外注意的是，当前节点的 parent 并不是当前节点的 union标识，我们需要使用 find() 来找到 当前节点的 union 标识。

236. Lowest Common Ancestor of a Binary Tree

tag：recursion；传统LCA
对于recursion，最重要的就是定义recursion函数的物理意义。对于传统LCA，recursion函数的物理意义是：返回 LCA 或者 p,q 节点自己。

523. Continuous Subarray Sum

tag：prefix sum；two sum变种 (hash map)
首先看到 “continuous”，“subarray”，可以想到使用 prefix sum。但使用 prefix sum 会发现仍然需要求出每一个 subarray 的值，单独的 prefix sum无法降低时间复杂度。

这时候发现关键点：这种求组合为target的题目，都可以考虑使用 two sum 的逻辑，使用一个 hash map 记录下遍历过的值，在访问到新值的时候先从 map 中找找有没有符合条件的已访问过的元素。这可以有效降低时间复杂度。

另对于本题，由于题目需要subarry至少有两个元素，因此还需要额外的逻辑确保这个。

124. Binary Tree Maximum Path Sum

tag：recursion，人字形结果，一字形定义
树的题目除了 level order traversal 时需要使用 bfs，其他绝大部分都使用 recursion。

recursion 的题目最重要的步骤就是定义 recursion 的物理意义。一般情况下，recursion 的物理意义和题目的问题应该是相同的。

但是这道题的难点就是在于 recursion 物理意义和题目所求的是不一样的。题目要求求出最长的“人字形”路径，但是这样的 recursion 是非常难以维护的，因此将 recursion 定义为求最长的“一字形”路径，而之字形路径的维护在每一层 recursion 内部进行。

269. Alien Dictionary (Mark)

tag：graph problem；topological sort + bfs/dfs
本题是图论的一道好题，涉及到了 topological sort，是一个之前没有接触过的思想。通过维护节点的入度 (in-degree) 来对节点进行排序。每次选出入度为0的节点，加入结果集，删除该节点，同时更新邻居节点的入度，重复直到没有入度为0的节点。这个描述很适合使用bfs来实现，也即 while(!queue.isEmpty()){...}。实现 topological sort 的方法有 bfs 和 dfs，本题使用了 bfs，dfs还没搞懂。

这道题除了学到了新的图论算法，另外给我的启示是，算法过程中维护的数据结构越少越好，尽量能让数据结构复用。

65. Valid Number (Not complete)

tag：dfa（deterministic finite automation 有限状态机）

273. Integer to English Words

tag：recursion + corner cases
由于这道题每个部分的转换规则是有规律的，因此可以使用 recursion 来完成。

本题的难点有三个：1. 转换过程中 num 的更新；2. parse 过程中 corner case 的考虑；3. 输出字符串的空格问题。

56. Merge Intervals

tag：sort + linear scan
对于merge类的题目，除了 union find 之外，也可以考虑先将给定的数组进行排序，然后再找规律。往往排序后的数组有很多特殊的性质可以使用。注意输入数组的有序性。

140. Word Break II

tag：dfs + limitation（剪枝）
由于题目需要求出所有的可能情况，因此首先考虑使用 dfs，同时发现有很多可以剪枝的地方。

这道题的一个坑是在于 StringBuilder 在吃完吐的时候，delete 的函数是删除字符，而不是字符串的，因此在吐时需要从 sb.length() - word.length() 开始删，而不是单纯的减一。

987. Vertical Order Traversal of a Binary Tree

tag：dfs/bfs + Comparator
树的问题首先想到 dfs 和 bfs。dfs：in order, pre order, post order。bfs：level order。

这道题主要是要读懂题目，选用合适的数据结构，算法层面的技巧不强。对于需要排序的题目，数据结构可以考虑：PriorityQueue，TreeMap，TreeSet。方法：Arrays.sort()，Collections.sort()。

560. Subarray Sum Equals K

tag：prefix sum + hash map
看到 subarray，需要想到 prefix sum 与 dp。再看到 subarray sum，可以考虑使用 prefix sum。这道题是找组合和等于k，和 two sum 是很类似的，因此考虑使用 HashMap 来记录下便利过的元素。由于题目要求求个数，而不要求index，因此 HashMap 里只需记录某个 prefix sum 值出现了多少次即可。

1249. Minimum Remove to Make Valid Parentheses

tag：StringBuilder + linear scan
这道题在scan原String时，使用StringBuilder来存放字符。这道题更多是算法层面的思想，也即如何处理多出来的左括号和右括号。对于多出来的右括号，可以不append进 StringBuilder 里；对于多出来的左括号，可以遍历完后从右往左删除多余的。

139. Word Break

tag：dp + String，带 buffer 的 dfs 转 dp
这道题没有一开始就想到用 dp，但是梳理一下思考过程，还是能有启发。

首先想到的是暴力 dfs，但由于这道题只用找到一种 segmentation 情况就行，因此可以在 dfs 里加上 buffer 来存中间结果。我对 dfs 函数的设计是：dfs(String s, int index, int[] buffer, List<String> wordDict)，带 buffer 的单变量 dfs 可以很自然的变成 dp。对于 dfs(String s, int index, int[] buffer, List<String> wordDict) 这个函数，我的定义是：对于s，从index到最后一个字符所组成的字符串是否能够被wordDict segment。

对于字符串的 dp 来说，dp[i] 一般定义为“以 s[i-1] 结尾的字符串 ...”，因此这里 dp[i] 定义为以 [0, i) 左闭右开区间的substring 是否能被 segment。

227. Basic Calculator II

tag：将字符串转化为整数的巧妙方法
一个由数字组成的字符串，除了使用 Integer.valueOf() 之外，还可以这样：

int num = 0;
for(char c : s.toCharArray()) {
  num += 10 * num + c - '0';
}
return num;

347. Top K Frequent Elements (Mark)

tag：counting sort / bucket sort，给数组的 index 赋予意义，利用 index 的值本身来存信息
这道题使用到了新的排序算法: counting sort 或 bucket sort。注意这道题需要返回 Top K 的所有元素，而不是找到第 K 个元素。

这道题的思路比较简单，就是遍历整个数组，得到每个element出现的次数，然后根据次数从大到小选择前K个返回。问题在于时间复杂度需要是O(n)，但基于比较的排序至少是 O(nlogn)，因此使用到 counting sort / bucket sort。

bucket sort 的适用场景是，所给的数字在一定范围内均匀分布，这种情况下 bucket sort 的性能是最好的。无论是 bucket sort 还是 counting sort，它们都有一个共同点：都用到了数组的 index 作为信息。

对于这道题来说，可以新建一个 List<Integer>[]，其中 List[i] 里面存的是出现次数为 i 的所有元素。这里就将 index 赋予了有用的信息，如果我们从后往前遍历这个 List[]，那么自然是从次数最多向次数最少遍历的。遍历新数组的时间复杂度是 O(n)；生成这个新数组时，由于题目不要求相同frequency的元素的排序，因此时间复杂度也是 O(n)（如果返回的结果里相同的frequency也需要排序的话，那么时间复杂度会更高）。因此这道题的时间复杂度是 O(n)。

953. Verifying an Alien Dictionary

tag：提早对 corner case 进行判断；善于使用提供的API
这道题是 easy 的题目，思路比较简单，代码量也不多。

本题给我的启发是，在逻辑处理过程中，如果有corner case，尽量先单独列出来提前解决，能够省去后面很多的麻烦。比如本题，有一个 corner case 是，如果 word2 是 word1 的一个子串 (substring(0,x))，那么直接返回 false。把这个 case 单独拿出来处理，后续的逻辑就不用担心这种情况了。

71. Simplify Path

tag：stack + 字符串处理 + corner cases
本题的数据结构选用的是 stack，原因是存在 “.." 这种情况，能够回到上一级目录。

在参考答案和discussion里，都使用了 s.split("/") 函数来对字符串进行预处理。这样虽然代码量会减少很多，但感觉避开了本题想考察的一个重点，就是如何处理字符串。因此在刷题的时候使用这样的函数无可厚非，但是面试时需要经过面试官的同意才行。

173. Binary Search Tree Iterator (Mark)

tag：使用 stack 模拟 recursion，可在 recursion 过程中暂停
本题的目标是实现空间复杂度 O(h) 的算法，因此传统递归实现 in-order traversal 存放所有节点顺序的方法并不适用。

对于 recursion 的题目，可以考虑使用 stack 来模拟递归的过程。本题是经典的利用 stack 模拟递归的题目。利用 stack 模拟递归的好处在于，可以自己控制递归的过程。本题中，可以先将所有的左节点放入 stack 中，而不放右节点。随着 next() 的调用，再将 pop 出来的节点的右节点的所有左节点放入 stack 中。这样相当于控制了递归的过程，空间复杂度是 O(h)，h 是树的高度。

stack 模拟 recursion 需要注意的是 push stack 的顺序。stack 是后进先出，而对于当前节点来说，节点的左孩子应该是先出的，因此左孩子需要后放入 stack，先将自己 push stack。

1047. Remove All Adjacent Duplicates In String

tag：stack；利用 StringBuilder 代替 Deque
很多题目我们需要用到 stack 的思想，但并不每道题都需要使用 Deque 来实现 stack，也可以考虑 int[]，StringBuilder 之类的数据结构。本题利用 StringBuilder 来模拟 stack，代码更加简洁。

339. Nested List Weight Sum

tag：读懂题意 + dfs
这道题的难点之一在于读懂题意以及对新给 API 作用的理解，在这两方面必须花时间了解清楚题意。

由于题目中涉及到了“层”的概念，因此使用经典的 dfs 来完成，注意定义清楚 dfs 的物理意义。

314. Binary Tree Vertical Order Traversal (Mark)

tag：树的遍历 + bfs + TreeMap
关于树的题目，十有八九是离不开树的遍历的，因此确定按照什么样的顺序遍历树是至关重要的。常用的遍历有 dfs (pre order, in order, post order) 与 bfs (level order)，这两种遍历方式的特点是不同的。

对于 dfs 来说，由于可以使用 recursion，因此适用于对每个节点都进行类似操作的题目，是更常见的遍历方法。

对于 bfs 来说，level order traversal 能够保证遍历过程中 树的深度的有序性（深度+1）、同深度间节点的有序性（从左向右或从右向左）。

对于本题，由于题目中需要节点从左到右的顺序，因此选用 bfs 来完成。由于需要按照 col 来排序，因此使用 TreeMap。

670. Maximum Swap

tag：monotonic stack + String API
一个题目是由 算法+数据结构 组合而成的，有时候数据结构可以为算法提供思路，有时候算法能为数据结构的选择进行指导。这道题是需要先想清楚算法的细节，再选择合适的数据结构。

最开始做这道题时，算法是错误的，以为是要找单调的递增的序列，然后将peek和左侧bottom交换。

正确的算法应该是，找到自己右边最大且离的最远的数，然后进行交换。提到找自己右边最大，就想到了单调栈 monotonic stack。

317. Shortest Distance from All Buildings (Mark)

tag：bfs
本题为 Hard，选择合适的算法很关键。

遍历算法的选择：由于需要记录到每个点的最短 steps，因此选择 bfs 来实现（bfs 天生自带最短路径属性，这是 dfs 不具备的）。对于遍历，有两种选择：1. 从 0 开始遍历，寻找到每个 1 的 steps；2. 从 1 开始遍历，寻找到每个 0 的 steps。这两种方式都是可行的，但是当 0 更多的时候，从 1 开始效率更高；1 更多的时候，从 0 开始效率更高。这点可以在面试时提出。

数据结构。如何判断一个0是否能够到达所有的1？可以针对每个位置设置一个counter，每bfs遍历到一次该点，该点的 counter 就加一，最后看 counter 是否等于 grid 中 1 的总个数即可。

1382. Balance a Binary Search Tree

tag：in order traversal + dfs
对于 BST 的题目，首先想到 in order traversal。

这道题最开始的时候想复杂了，一直在想如何直接在原来的树上 dfs/ bfs 从而生成新的 BST。最后没想到。

正确做法是，先用 dfs 按照 in order 顺序将每个节点放入一个 list 中，然后基于这个 sorted list 使用 dfs 来生成 BST。这里需要注意的是，在 in order traverse 原树时，把节点放入 list 中之后需要将当前节点的左右孩子置为 null，避免生成新树时出现环。

list 生成 BST 的过程可以参考题目：108. Convert Sorted Array to Binary Search Tree。

1263. Minimum Moves to Move a Box to Their Target Location

tag：bfs
看到题目：Minimum Moves，再加上图的题目，因此需要首先想到 bfs。

这道题的难点在于，在 bfs 遍历的过程中，邻居位置遍历的合法性。除了没有越界、不能是 ‘#’ 外，还需要保证推箱人能够能够到达对应的推箱位置。同时，在 bfs 遍历过程中，如何定义 “已经访问过的情况” 也是难点之一。平时的题目更多是单一变量的，即该位置是否有被访问过。但是这道题 “已经访问过” 有两个变量，一是箱子的位置，二是人的位置，只有这两个情况都曾经遍历过时，才算是“访问过”，可以剪枝。

249. Group Shifted Strings

tag：HashMap + String convert
本题更偏算法。思路是，将所有的String都转化为以 a 开头的 shifted string，如果属于同一组的话，那么 a 开头的 shifted string 会是相同的。

791. Custom Sort String

tag：int[] 代替 HashMap
这题的思路很有意思。先遍历 待order 的数组，记录每个字符出现了几次，然后遍历给定的 order 数组，根据记录的字符次数加入到 StringBuilder 中。由于遍历 order 数组已经保证了顺序，因此这个方法适用。剩余的字符再加入到 StringBuilder 后面就可以了。

记录字符出现次数可以使用 int[] 来记录，而不用HashMap，其中 index 即为 char c - 'a'。

863. All Nodes Distance K in Binary Tree （Mark）

tag：dfs + 思路
这道题的难点在于，如何得到 target 节点上方节点的 distance 信息，以及上方节点的其他孩子节点的信息。

1. 不要吝啬使用数据结构来存储不要的信息。能够使用一个 HashMap 来储存 target 上方节点的 distance，这个 HashMap 能够使用 dfs 来获得。

2. 获得 distance map 之后，可以使用 dfs 来遍历这棵树了。在定义 dfs 物理意义的时候，一定要找到规律，不要把 dfs 每一层的逻辑设计的过于复杂。这一步的 dfs 的难点在于，如何更新“与 target 之间的 distance” 这个信息。可以想像现在遍历到了某个节点，这个节点的左孩子如果和 target 不在一边，那么左孩子 distance 就是当前节点 distance + 1，因为 target 想抵达当前节点的左孩子，需要先经过当前节点。同理右节点的 distance 也一样。但问题在于，如果自己的某个孩子与 target 在一侧，并且在 target 上方，那么孩子的 distance 应该 -1 了，因为离 target 近了一步。如果按照这个逻辑来想，每层的 dfs 逻辑会很复杂，既要判断孩子在不在 target 的同一边、在不在 target 上方，还会有不同的 distance 计算方式，这样的设计就是不好的。

我们之前已经得到了一个 HashMap 用来储存 target 同一边的所有上方节点离 target 的 distance。这个数据结构是至关重要的，它的出现能够简化 2 中 dfs 的设计。到达某个节点时，我们先看自己在不在存 distance 的 Map 中（简称 disMap），如果在的话，就把 Map 里的 distance 来作为自己的 distance。在 dfs 左右孩子时，也可以直接粗暴的将孩子的 distance 设置为 自己的 distance + 1，因为如果孩子在target 正上方，则孩子也会在 disMap 里，它那一层的 dfs 中会自己更新 distance；如果孩子不在 target 正上方，那么孩子的 distance 的确等于 当前 distance + 1。这样既保证了正确性，也极大简化了每层 dfs 的逻辑。

766. Toeplitz Matrix

tag：转化题意，复杂问题简单化
这道题是道 easy 的题目，但是我看了答案才写出来，而答案也是的确是 easy 的。

这道题需要判断一个二维数组的各个对角线上的元素是否相等。我的思路是一次遍历数组的每个对角线，查看同一对角线里的元素是否相同。但最后由于坐标转换没有想清楚而失败。

但这道题完全等价于：对于每个元素，判断它和自己右下一格的元素是否相同。这个算法只需要两个普通的 for 循环就完成了。但是我没有想到这样对题意进行转化。

1570. Dot Product of Two Sparse Vectors (Mark)

tag：hash map -> list of key-value pairs + two pointers -> binary search
这道题的首先反应是，使用数据结构储存非零的 index 与 值，在相乘的时候能够减少不必要的遍历时间。

方法一是使用 HashMap 来储存 index、value。这种方法可行，但是在 FB 面试过程中，面试官并不欣赏这个做法，原因是因为数组大了之后，给每个 index 进行哈希运算也需要花时间。

方法二是使用 List<int[]> 来存储 [index, value] 对，在计算 dot product 的时候使用 two pointers 的方法，分别遍历两个数组的 List<int[]>。由于生成 List 时是顺序遍历输入数组的，因此 List 内部是有序的。

这道题还有个 follow up：如果只有一个是 sparse，另一个不是怎么办？解决方案是，在进行 dot product 的时候，使用 binary search 来找到非 sparse 数组的 List 的 非零值。

658. Find K Closest Elements

tag：continuous subarray + two pointers
这道题并没有显示的说明时 subarray 的题目，但是可以通过题意分析出必须是 subarray 的题。

作为 subarray 的题目，可以考虑的解法有：双指针、dp。其中双指针也分为同向而行（滑动窗口）、相向而行。本题在尝试同向而行失败后，发现相向而行才是正确的解法，因为这道题隐含的意思是从数组两端逐个剔除不正确元素。

本题不选择滑动窗口的另一个原因是，我只对窗口的边界值感兴趣，而对窗口内部的元素不感兴趣，这样其实就从滑动窗口退化成了双指针问题。在选择双指针方向的时候，注意到比较的是两端的极值，于是选择相向而行。

581. Shortest Unsorted Continuous Subarray

tag：continuous subarray + motonic stack -> 单指针代替
// TODO:

162. Find Peak Element

tag：binary search 的意义：尝试可能的部分
这道题要求使用 logn 的解法，因此想到 binary search。binary search 的核心在于：淘汰不可能的部分。也可以换个理解：尝试可能部分。

这道题初一看和 binary search 没啥关系，但是分析：如果 mid 左小右小，则自己是 peek，返回；mid 左小右大，那么右边一定有peek，则找右边；mid 左大右小，左边一定有 peek，找左边；左大右大，两边都有peek，任意一边就行。

1329. Sort the Matrix Diagonally (Mark)

tag：合理表达 diagonal 元素 + heap 用于排序
这道题的难点有两个，一个是如何按照下标获取对角线元素，二是如何排序对角线元素。

对于第一个问题，同一对角线的坐标 (i, j) 有 i-j 的值是相等的。可以通过 i-j 相等在遍历整个 matrix 时将不同对角线的元素分开。

对于第二个问题，无论是sort API 还是 sort 算法，我们一般是在一维数组里进行排序，没有来排序过对角线。但实际上，我们可以用 heap 来进行排序。不能只记住 heap 在 kth closest 类题目中的使用方法，它最原始的功能还是排序。

1008. Construct Binary Search Tree from Preorder Traversal (Mark)

tag：dfs 物理意义
本题是通过 preorder traversal 来构建 BST，对于构建 tree，首先想到的是 dfs，现在的问题在于如何定义 dfs 的物理意义，以及如何规定 base case。

可以回忆如何判断BST是否合法的题目，解法dfs里加入了 low、high 信息用于判断当前节点是否合法。在本题中，也可以在 dfs 的里加入 low、high 的信息，用于判断 preorder 的元素在当前层的 recursion 中是否合法。通过 low、high 的信息来规定 base case。

1305. All Elements in Two Binary Search Trees

tag：使用 stack 代替 recursion 对 BST 进行 in-order traversal
这道题的核心就是 tag 中的内容，能用 stack 代替 recursion 之后，就可以做谁小移谁了。当然也可以先用 dfs 把两个 Tree 都遍历一遍，然后再谁小移谁。

260. Single Number III

tag：bitmask + 位运算
// TODO

1095. Find in Mountain Array

tag：binary search
本题是单纯的 binary search。首先用binary search 找到 peek，其次在peek左侧进行 binary search，最后在 peek 右侧 进行 binary search。

唯一需要注意的是，由于这题对 API 的调用有要求，因此在每一轮 binary search 的时候，先把值存在下来，而不要在 if 语句中调用 API。

105. Construct Binary Tree from Preorder and Inorder Traversal (Mark)

tag：dfs + map
典型的 dfs，使用 map 来加速查找 preorder 某个元素 在 inorder 数组中的 index。

763. Partition Labels

tag：greedy algorithm
找出每个元素最后出现的下标，然后从头到尾 scan。

419. Battleships in a Board

tag：局部代替整体
例如枚举矩形的时候，我们将最左上的点作为锚点来遍历举行。这道题里，在计算个数时，也可以只数符合条件的最左上的点。

442. Find All Duplicates in an Array

tag：使用数组的 index 来存储必要的信息
本题的目标是使用 O(1) 的空间解决，因此不能使用额外的数据结构，只能使用 input 数组，此时需要巧妙的使用数组的 index 来存储信息。

由于题目的限制，数组中数的范围是 1～n，刚好能够使用 input 数组来存储信息。每当遍历到 num 时，执行 nums[Math.abs(num)-1] *= -1 ，将对应位置的数置为负数。当另一个num查看该位置为负数时，就知道之前已经遍历过了，自己出现了两次。这里的关键是 Math.abs()。

1026. Maximum Difference Between Node and Ancestor

tag：recursion 从上到下传递信息
做多了从下往上传递信息的 recursion，突然遇到从上到下传递信息的题目还是不习惯。

这题的思想是，把当前层的最大值和最小值传递给下一层，那么递归到 null 时，此时就维护着从根到该 null 节点路径上的最大值和最小值，然后在 null 节点计算结果。

979. Distribute Coins in Binary Tree

tag：dfs物理意义
dfs 物理意义是 tree 类型题目最核心的要点。正确合理的物理意义能让代码简洁、思路清晰。

本题 dfs 的物理意义是：返回该节点多余的coin。每一层为了维护这个物理意义，需要先得到 left 多余的coin，再得到 right 多余的coin，那么本层多余的coin就是 root.val + right + left - 1。问题在于 movement 如何计算？当前层的movement = Math.abs(left) + Math.abs(right)。因为返回值为正数时，表示子树有多余的 coin 需要上移；如果返回值为负数时，表示子树需要相应的 coin。两者绝对值相加即为经过当前节点的 movement。

695. Max Area of Island (Mark)

tag: dfs
这道题是经典的图遍历题，之前一直都是用 bfs 写，今天看了答案里 dfs 的写法，被 dfs 的简洁所震撼。

dfs 中，所有的不合法情况全部在 base case 中处理了，recursion rule 就只需对四个方向进行新的 dfs 而不用管是否合法。

451. Sort Characters By Frequency

tag：根据出现频率排序 + bucket sort
与“出现频率”有关的题目，首先想到 bucket sort（准确的说是 counting sort），因为出现的频率是有上限的，即为输入数据的长度。在待排序数有上边界的情况下，很适合使用 bucket sort。如果要求的输出对相同 bucket 内的顺序不关心，那使用 List[] 即可；如果对 bucket 内部顺序关心，可以考虑使用 PriorityQueue[]。

865. Smallest Subtree with all the Deepest Nodes

tag：lca 变种
本题是 lca 的变种，在 lca 的基础上加上 depth 的元素。在 lca 中，dfs 的返回值是两个 tree node 中任意一个的 lca；在本题中，由于加入了 depth 的元素，因此每一层 dfs 的返回值中，不仅需要返回 tree node，也要返回 depth，因此返回值是一个 Pair<Integer, TreeNode>。

739. Daily Temperatures (Mark)

tag：approach1: monotonic stack 的正确用法 / approach2: dp
本题有两种做法：1. monotonic stack，2. dp。虽然用 dp 的做法从空间复杂度上会更优秀 (O(1))，但是 monotonic stack 的方法也值得学习。

本题 dp 的本质是，使用 dp 数组减少回看的次数。如果不用 dp，那么在位置 i 时，只能 linear scan 后面已经遍历过的元素。但如果维护 dp 数组，在回看时可以很快跳到可能符合条件的位置，避免了linear scan。

本题 monotonic stack 的做法是：从左向右遍历数组，读到位置 i 的数时，将 monotonic stack 中所有小于的值的 index pop 出来，并更新对应 index 的 ans，然后将 i 放进去。遍历完成后将 monotonic stack 中剩余的 index 对应的 ans 置为 0。这样维护了一个单调递减（准确的说是单调不递增）的单调栈。

1554. Strings Differ by One Character

tag：set + all possible combination that substitue a character with '*'
这道题的思路很巧妙，使用通配符代替原字符串当中的一个字符，将一个字符串所有可能的通配符情况存储在一个 set 中。比如 "abcd" 的所有通配符情况是：“*bcd”, "a*cd", "ab*d", "abc*"。在遍历 input 时，如果发现当前字符串的某种通配符情况在 set 中出现过，则表示这两者只差了一个字符，直接返回 true。如果遍历到最后都没有匹配的，返回 false。

本题的关键点在于 input 数组中所有的字符串都是不同的（unique），因此只要两个字符串存在相同的通配符情况，则两者必定差一个字符。如果 input 数组中有重复字符串，那么通配符相同时也可能是原字符串相同，遇到这种情况可以先用一个 set 过滤掉 input 数组中相同的字符串，然后再操作。

518. Coin Change 2

tag：dp，完全想不到的 induction rule
这道题的第一想法是用 dfs 做，后来发现会超时，于是加上 buffer。buffer 本身便是一个 int[][]，因此很自然能想到改写为 dp，不过是一个二维 dp。

然而这道题并不需要二维 dp，只需要一维 dp 就能够搞定。而一维 dp 的induction rule 确实难想，看了答案后又觉得理所应当。一维 dp 的物理意义是：dp[i] 表示组成 i money 有多少种方法。base case很简单想，dp[0] = 1。问题在于 induction rule。对于任意一个 coin，dp[i] += dp[i-coin]，因此 induction rule 如下：

int[] dp = new int[amount + 1];
for(int coin : coins) {
  for(int i = coin; i < dp.length; i++) {
    dp[i] += dp[i - coin];
  }
}
return dp[amount];

这个 induction rule 真是太妙了。

311. Sparse Matrix Multiplication (Mark)

tag：sparse matrix compression
本题的核心有两个：一是如何压缩 sparse matrix，二是压缩后如何计算。

压缩 sparse matrix 的方式为，将每个非零值用一个 int[] 表示，其中 int[0]: row, int[1]: col, int[2]: val。使用一个 List 存放每个 int[]。由于遍历过程的特殊性，能够保证 int[] 之间是有序的。

基于压缩 List 如何进行乘法？可以发现，对于 matrix1 中的任意元素 m1，如果 matrix2 中的元素 m2 有 m1.col == m2.row，则需要相乘并更新 res[m1.row][m2.col]。使用双指针 scan 两个压缩 List。

946. Validate Stack Sequences

tag：greedy algorithm
本题的思路是：每插入一个元素，都将所有符合 popped 的元素都 pop 出去，用一个指针记录 pop 的index。最后看 popped 数组是否被全部 pop 掉。

1233. Remove Sub-Folders from the Filesystem

tag：sort input array！！
对于数组类的题目，没有头绪时试试 sort 一下，看看会有什么新发现。

这道题的做法是，先sort input array，sort 完之后相邻的两个字符串就会有相同的前缀。只需要判断当前字符串的开头是否是上一个字符串 + “/”，即可判断当前目录是否是 directory。

这题还是对 String 的 sort 不敏感。

48. Rotate Image

tag：如何rotate + 如何对折
这道题的核心是分析出rotate 90度等价于 先上下对折，然后对角线对折。

有了这个思路之后，难点在于如何对折对角线。这需要遍历主对角线右上方的元素即可，并将 (i,j) 和 (j,i) 位置的元素交换。代码如下：

// 2. swap diagonal
for(int i = 0; i < m; i++) {
    for(int j = i; j < n; j++) {  // 注意这里是 j = i
        swap(matrix, new int[]{i, j}, new int[]{j, i});
    }
}

647. Palindromic Substrings (Mark)

tag：palindrome string + dp
本题是关于 palindrome 的题，我对 palindrome 依旧不太感冒。

这道题可以使用二维 dp 来完成，dp[i][j] 的意思是 s[i...j] (inclusive) 是否是 palindrome。base case 分为两部分，第一部分是 i == j，此时 dp[i][j] = true；第二部分是 i == j-1，此时 dp[i][j] = (s[i] == s[j])。induction rule 为：if s[i] == s[j], then dp[i][j] = dp[i+1][j-1]。根据 induction rule 可以推断出填补 dp matrix 的顺序，应该是从下往上 (i--)、从左往右 (j++)。

1011. Capacity To Ship Packages Within D Days (Mark)

tag：binary search
这道题怎么都没想到能用 binary search 来写，但是明白原理之后又确实能用 binary search 写。

这道题根据题目意思可以换一种描述方式：给定最小的 capacity 和 最大的 capacity，求出符合要求的最小的capacity。这样，最小的 capacity 就是 left，最大的 capacity 就是 right，任务是找到 left，right 之间符合要求的最小值。

对于本题来说，最小的 capacity 是所有weights 中的最大值，因为capacity 至少能够装下最重的货物。最大的capacity 是所有weights 的总和。

那么binary search 的过程在干什么？首先选取一个 mid，假设它为 capacity，然后按照要求按顺序装货物，最后看需要多少天。如果 dayUsed > days，说明 capacity 太小，left = mid+1；如果 dayUsed <= days，说明 capacity 合理，但有可能有更优解，right = mid。while 条件是 left < right，因为 left == right 时就不需要继续走了。