201. bitwise-and-of-numbers-range
- 给两个数字，求这两个数字之间（含他俩）所有数的And的结果。
- ME：从1开始左移，找到恰好不大于下界的2的幂，然后看看上界是否超过了这个幂的两倍，因为一旦这两个数字包含2的倍数，就直接是0了，想想
111 & 1000。如果不包含，那么这个幂对应的位置就一定是1了，那么用这个幂与原本的下界和上界取个异或，就得到了后续的部分，递归下去找数字，结果再加上当前这个幂即可。[详情见这里]。 - TA：这个方法看似暴力，其实有个trick是每次都约减掉了最高位的1.这个方法的核心则是『寻找m和n的左侧最长的公共部分』，最后用上界与这个公共部分（公共部分以左全为1，不过无所谓）再做个与即为结果。这个也是类似，不过是『右移m和n来找公共部分』，同时用一个factor记录从哪一位开始往左都是相同的了。
202. happy-number
- 给一个正整数，判断它是否Happy。所谓happy指的是求各位的数字的平方和，得到的是1则是happy，不是1就继续这样算平方和。不是happy的数会陷入循环。
- ME：递归加Set标记是否轮回搞定。
- TA：这个是Iterative版的set，利用set.add判断是否出现重复。这个借助Floyd Cycle Detection的答案更加妙，来源于快慢指针检测链表中是否有环，这里也是这样，fast是每次往后算两步，slow是一步。当fast到达了1说明是happy，如果fast追上了slow说明成环了。
203. remove-linked-list-elements
- 给一个链表和一个val，将链表中与val相等的节点删除。
- ME：用一个伪头部O( n )搞定。一开始偷懒没有搞双指针，结果没法处理连续删除的问题，例如
[1,1]删除1. - TA：挖去，原来单指针足够了，关键是你逮到一个与val相等的节点后，当前节点的next重新赋值，但不能往后挪，这样才能保证后续的那个节点也被check到。还有这个recursive的方法，既然函数会返回节点，那么就一路往后直到null，若当前节点需要被删除，就返回后续的节点即可。
204. count-primes
- 给一个正整数n，求n之前有多少素数。
- ME：衣洗题还没搞出来，丢人。一开始就想到用HashSet把非素数给放进去，结果爆内存。后来又想着用暴力方法吧一个个调用isPrime判断一下，果断超时。
- TA：没想到竟然可以直接new数组，都不会爆内存，难道测试用例这么弱的吗？这里还有个更subtle的方法，既然偶数都不可能是素数，那一开始就把所有偶数排除掉，count初始化为
n/2。利用composite数组记录是否为合数，从3开始遍历，不是合数则进入内层循环，将i * i + a*i对应索引的composite置为true，同时count--。速度炒鸡快。
205. isomorphic-strings
- 给两个字符串，看能否建立一一映射关系，使得字符串s能转换成t。一一映射要求各个key映射到不同的value，不能多对一，更不可能一对多。
- ME：HashMap搞定，利用containsKey判断是否定义过映射，利用containsValue防止多对一。
- TA：这个告诉你，由于都是ASCII字符，那么可以用数组代替HashMap嘛，这样会快很多。果然很快。
- 我去，当年谷歌实习面试的原题，明明做过竟然没搞出来。。。follow-up说如果这些test字符串是million级别的，要怎么优化。不能再给每一组维护a pair of maps，需要找出某种pattern，那么可以根据secret字符串总结出一个pattern，然后后面的字符串都调用相同的算法生成pattern，直接比较pattern字符串即可。123456789101112131415161718192021public boolean isIsomorphic(String s, String t) {if (s == null && t == null) {return true;}if (s == null || t == null) {return false;}return getPattern(s).equals(getPattern(t));}private String getPattern(String str) {int index = 0;StringBuilder sb = new StringBuilder();Map<Character, Integer> map = new HashMap<>();for (int i = 0; i < str.length(); i++) {if (!map.containsKey(str.charAt(i))) {map.put(str.charAt(i), index++);}sb.append(map.get(str.charAt(i))).append('#');}return sb.toString();}
206. reverse-linked-list
- 给一个链表，反转它，返回反转后的链表头。要求iterative和recursive分别实现。
- ME：iterative的很好办，一个prev从null开始，一个curr从head开始，改变curr.next指向prev即可。recursive没想出来。。。
- TA：偷看了别人的，写出了recursive的方法。我当时搞不懂怎么写是因为不知道应该返回head还是tail，其实每次递归还是应该返回新的头部，因为tail完全可以用当前元素的next访问到。
207. course-schedule
- 很典型的图论题，判断根据所给的prerequisite列表能否规划出修完全部课程的方案。术语叫作topological sort，托普排序。
- ME：真的抓狂，明明很基础的一个题，想半天搞不出来。回头翻了大二上的数据结构Lecture 13果然找到了托普排序。利用『入度为零』判断哪个点可以作为起始点，将这些点全部入队，然后从队首的点出发，将它相邻的点的入度都减1，相当于『修了这门课』。这样一直循环直到队列为空，看看遍历了多少课程。
- TA：课上讲的其实就是这个BFS的方法，此外还有DFS的方法。DFS需要借助visited数组，标记哪些课程已经上过了，如果在后续DFS中回到了上过的课程索引，说明成环了，这样的课程依赖关系永远没有办法满足，直接返回false。如果全部课程都走过一遍了，也没有成环，那就说明可以。注意DFS如果使用数组会超时，因为需要遍历才能知道后续课程索引，而使用ArrayList就直接往后get就好了。
208. implement-trie-prefix-tree
- Trie树来源于单词『retrieve』，主要用于字典查找、输入法联想，因为可以提供prefix查找。这个就是实现一波。
- ME：这个题促使我翻看了大二上的『数据结构与算法』的PPT，理解了相关内容后实现起来非常容易。
- TA：因为search和startsWith非常类似，只是search要求在该节点处isWord为真，这个答案告诉你，可以将公共部分提取出来调用这个find函数，返回找到的该字符串对应的最后一个节点。
209. minimum-size-subarray-sum
- 给一个目标s和一个int数组，求最短长度的连续子串使其元素和大于等于s。
- ME：想到了双指针做法，就是fast指针一直往后加知道超过s，然后slow指针再跟进同时减掉slow指针对应的值，一旦小于s就又开始挪fast。这是个O( N )的做法，但是follow up要求想到O( NlogN )的。
- TA：这个大神的Two pointer就比你的简单很多咧。此外就是这个O( NlogN )的做法，很容易想到二分查找，但是二分要求数组是有序的，但在这里原数组的顺序matters，不能动，怎么破？我就是不知道这个。其实题目说了都是正数，那么它对应的累积和数组cumultive就是有序的了，在搜索目标s的时候加上之前的和就可以了。这里的二分查找和通常的不太一样，因为通常是找到了就直接输出索引，最后如果没找到就输出-1，在这里就不能这样，因为没找到就要返回『最小的大于目标的索引』，因此需要在princeton版本二分中删除相等即输出的判断，同时最后返回的是left而不是-1，写出来是这样。
210. course-schedule-ii
- 与207相比需要记录路径了。
- ME：BFS很好办，也是利用入度为0筛选出起始点，然后逐步放到Queue里。但DFS就不好理解了，因为前面的那个『成环』的判定，在这里需要记录路径的情况下，似乎不管用了。
- TA：DFS的方法我参考了这个，原来需要维护两种状态，一个是完全visited，一个是在DFS过程中经过了这个点onpath，在DFS结束之前恢复的是onpath，表示当前这个recursive path已经退出、不再占用这个点，但visited就不能恢复了。
211. add-and-search-word-data-structure-design
- 类似于Trie数，但是在search的时候引入了通配字符
.，可以任意替代一个字母。 - ME：参考前面的Trie题，写出来了这个，需要用一波DFS来处理通配符。
- TA：没啥了。
212. word-search-ii
- 给一个棋盘，再给一个String数组，求在棋盘中出现了哪些字符串。字符串沿四个走位七歪八扭形成的都算出现。
- ME：作死，看了一下tag，发现要用Trie，稍微修改一下就OK了。修改在于把search函数拆分成了单步的nextNodeWithChar函数，给一个字符就返回对应的TrieNode，在DFS的时候一旦碰到对应的TrieNode为空就停止继续搜索了。同时TrieNode中存放的不是boolean，而是一个String，这样就不用重新拼接起来获得字符串了。
- TA：这个超强答案总结了所有可能的优化。去重这里HashSet可以用TrieNode中增加count，或者干脆每当DFS到了这个word的时候就把这个TrieNode的String给置空，以实现『去重』的目的。此外，onpath这个辅助二维数组也不必要，因为当你已经来到了搜索对应的TrieNode时，当前的节点肯定不会在深入的DFS中用到，因此可以直接修改原board，然后在最终退出DFS之前改回来。
213. house-robber-ii
- 和前面198的区别在于，要把数组看作一个首尾相连的住宅区，因此第一个和最后一个不能同时选。
- ME：这题在上次写得很漂亮，但是这里多了一个条件就纠结死了，WA了嗨多次才过。我维护了一个first的布尔数组表示是否选择了第一户人家，这样到达最后一户的时候，如果是真，那么就减掉第一间，在和前一个结果做比较。但是这样无法通过
2,2,4,3,2,5，因为这里就需要在完全不理会第一户的情况下取到最大值10。于是我不得不加入了以第二户为起点的一波比较和赋值，勉强通过，但这个逻辑非常乱，不能提倡。 - TA：这个直接来了两波，想法很直接，但我总觉得略low。他们把这个叫作『two pass』，好吧，这不失为一种方法。关键是不容易出错啊哥！
214. shortest-palindrome
- 给一个字符串，在它的前面增加尽量短的字符串拼接而成的新字符串自对称。
- ME：想到这个方法，自我感觉良好，但中间还是出了很多WA。从中间开始往两边拓展，判断是否对称，让这个『中间』的指针从正中间逐步往字符串头部挪，这样就能找到靠近头部的已经自对称的片段，然后把剩余不对称的拼上去就好了。
- TA：这个的前半部分找自对称的子字符串的那段代码实在太强！从后往前，如果前后指针对应字符相等则前指针++，后指针则不论什么时候都一直–，循环重点是后指针到达起点。此时前指针j所在的位置就是不对称部分的开端，那么这一部分就是需要反转并拼在最前面的部分了。但是这还没完，此时（0，j）这一部分还不能断言就是对称的，例如例子
"abacfghcabakmnchgfcabaiuytrcfghcnmkabachgfcaba"，因此需要递归地处理( 0,j )这一部分。此外还有一个KMP的方法，这个真是一头雾水，有个博客可以看看，不过先放一放吧。。。 - KMP是找common prefix和suffix，自对称是看字符串正读、反渎一摸一样，因此考虑将字符串翻转后拼接到原字符串上，就可以用KMP找prefix和suffix，前半部分是prefix、后半部分是suffix，相等则说明那一段从前往后和从后往前是一样的。12345678910111213141516171819202122class Solution {public String shortestPalindrome(String s) {if (s == null || s.length() == 0) {return s;}String rev = new StringBuilder(s).reverse().toString();String mirrored = s + "$" + rev;int len = mirrored.length();int[] dp = new int[len];for (int i = 1; i < len; i++) {int j = dp[i - 1];while (j > 0 && mirrored.charAt(i) != mirrored.charAt(j)) {j = dp[j - 1];}if (mirrored.charAt(i) == mirrored.charAt(j)) {j++;}dp[i] = j;}return rev.substring(0, s.length() - dp[len - 1]) + s;}}
215. kth-largest-element-in-an-array
- 求一个无序的int数组，经过排序后的第k个大的元素。
- ME：立刻想到了quickSort的应用，写出来是这样。我在这里用的是『以首元素为pivot』，而不是之前一直写的『以中间元素为pivot』的快排，不太熟悉，参考了princeton课件。
- TA：这个是一个总结，可以使用Java内置的priorityQueue（其实就是大根堆），将原数组的每个元素插入进去，始终维持规模为K，最后剩下的队首就是了。
216. combination-sum-iii
- 给整数k和n，要求不重复地从1~9中选k个数出来使得它们的和为n。
- ME：递归解决。数组索引越界了若干次，没有仔细设置循环/判断条件。从1开始取，used数组对应标true，然后将当前剩余需要拼凑的和减去当前取的这个值，进入下一步递归。为了防止重复，只能往后取值。
- TA：这个真的简洁，竟然不需要任何辅助的标记数组！因为每次都是往后取的，所以自然不会取到前面的啦。不过我的因为判断条件比较多，可以提前停止递归，所以比他的快嘿嘿。面试的时候当然还是选择好写的这个来写了。
217. contains-duplicate
- 给一个int数组，确认其中是否含有出现超过1次的数字。
- ME：直接HashSet搞定，在add的时候如果返回false就说明重复了。
- TA：这个小总结了一波，可以先sort再前后判断相邻的嘛。
218. the-skyline-problem
- 给一个int[][]，存储的是一系列三元组，三元组定义了摩天大楼的横坐标起点、终点和高度，求这些摩天大楼的侧视图所形成轮廓中所有横线的左端点坐标。
- ME：完全没有头绪！！！感觉这题是仅次于前面那个什么Word Ladder的题，实在是不知怎么抽象出来。。。
- TA：看了很多post，这个感觉最好懂（代码最短= =）。首先你原本想到的TreeSet思路是对的，但是没必要重新构建Block保存三个int的对象，这里直接
List<int[]>用存储每一条竖线，第一个元素为横坐标、第二个元素为高度，左边缘高度为负、右边缘高度为正这样区分开来。List自定义排序方式就根据横坐标越小的越靠前，若相等则左边靠前。PriorityQueue<Integer>存放的就是高度了，维护从大到小的顺序，初始化插入一个0，然后在循环里取List的元素，如果是右边缘直接remove掉，如果是左边缘就add进去，然后用一个curr取出当前的最大元素，与上一步的最大元素prev做比较，如果不一样了，说明上一步的最大元素已经出队或者新插入的元素高度更大，这两种情况对应下行阶梯或上行阶梯的形状，都需要把左节点插入结果，即当前的这个横坐标以及最大高度。观众朋友会问了，如果刚好全部边都出去了，落到地面了怎么办？这就是为什么要在第一步插入一个0，因为当所有边都出去了，当前横坐标对应的高度就落回到0了，照样可以输出到答案中。写出来是这样的。还有人改造成了TreeMap，因为PriorityQueue的remove任意节点需要O(n)，而TreeMap是O(log N)，因此快很多。不过需要注意的是由于是Map，所以key不能重复，这种限制在priorityQueue中不存在，因此需要对TreeMap的value添加一个计数器，以应对多个相同高度的情况。写出来是这样的。
219. contains-duplicate-ii
- 给一个int数组，给一个长度k，要求如果找到重复项，这两项的索引之差不超过k，返回布尔值。
- ME：一开始直接用HashMap保存值与对应索引，当发现重复的key的时候，就减一下索引看看是否小于等于k，每次都直接put进去更新索引。但是超时，我猜测大概是因为当数组规模很大的时候，每次HashMap查找都比较费时。衣洗题也陷入江局了。。。（但是hin奇怪的是我看别人通过的答案，用Map又是可以的啊。。。）
- TA：这个的提速在于尽可能压缩HashTable的规模，当索引超过k的时候，
nums[i-k-1]不会再被用到，可以用set.remove( Object )删掉它，这样每次查找都会快很多。
220. contains-duplicate-iii
- 给一个int数组，给偏移范围t和索引差距k，求是否存在差距在k以内的两个索引i和j，使得对应的元素之差的绝对值小于t。
- ME：还是用HashSet搞定了，自定义了Range类，根据
[mid-t, mid+t]来确定元素之差是否在t以内。但是当t为0时，即退化为前一个问题的时候，会超时，所以就特殊处理了一下，当t == 0时还是跑之前的代码，结果的速度还是挺快的。不记得在哪里看到的，说自定义类作为HashMap的Key是没有意义的，我当时就只是记住了。这次碰到这个问题，不得不考虑自定义Key放入HashSet，参考了这个。HashSet的比较首先是看hashCode，若hashCode相同，再调用equals比较两个对象。 - TA：这个答案避免了自定义对象的麻烦。如何将相差为t的尽量map到同一个索引呢？答主想到的是除法，将所有int都减去最小int转化为非负Long，然后除以
t + 1将其倍数往后的t个元素都映射到同一个索引bucket，然后建立<bucket, value>键值对插入Map。这样但是光有除法还不够，还需要对前、后两个索引进行比较看看差距是否小于等于t，毕竟不是每个数都是t + 1的倍数嘛，写出来是这样。此外，还有一个利用二分查找树的方法，每次求当前元素 + t在树中的floor，如果大于等于当前元素 - t说明就找到了。与原po相比我稍微改了一下判断条件，同时利用lo和hi防止越Integer界，当然改成Long方便多了。 - 自定义类插入HashSet/HashMap，需要重写HashCode和equals函数。但还是比较麻烦，尽量想想如何用内置类型代替。
221. maximal-square
- 给一个只含有0/1的char棋盘，求其中1组成的最大正方形的面积。
- ME：感觉我这用的是暴力法，若当前为1则向右下一格去分别向上和向左判断是否全为1，一直向右下深入。AC后看了一下tag，发现竟然可以用DP。
- TA：这个DP用一个二维table维护正方形的边长，若当前位置为1，则去左、左上、上三者中的最小值加1作为边长，这样一旦其中一个位置的边长为0就相当于重置了。然后答主又进一步优化了两波，最终只用了一维数组来dp，节省了空间但可读性也就下降了，我模仿着写出了这个。对于dp[j]来说，上对应的就是dp[j]（因为还没改动）、左对的就是dp[j-1]（已经改动过了），那么左上怎么办呢？额外用一个pre来记录，每次刚进入循环时存起来，然后结束循环前赋值给pre，这样在下一步再用到pre就是左上的效果了。
222. count-complete-tree-nodes
- 给一个complete binary tree，即除了叶子Level，其余level都是满的，而且叶子都是尽可能靠左存在的。求这个树的节点数。
- ME：还以为很简单，直接用个类似于level traverse的Queue来搞，结果超时。后来干脆改成一个三行的递归，还是超时。陷入江局。。。
- TA：参考了这个眼熟的大神的写出了这个。不过老实说他这个计算height的方法有些诡异，把-1都搞出来了，我后来在提交页面看到了个超快的iterative方法，写出来是这样。这个计算的高度也是只计算最左的高度，符合人眼计算漫漫叠加那样就没有什么-1了。在主函数里先计算根的高度，然后计算右子树的高度，如果右子树高度刚好是根高度减一，说明左子树一定是满的，因此要潜下右子树继续求高度，而左子树那堆满的节点加上根节点，刚好就是
1 << rightH，满的左子树高度就是rootH - 1 == rightH，节点数本来就是1 + 2 + 4 + 8... + 2^( rightH - 1 )，再加个根节点就相当于对应二进制进多了一位1 << rightH。而如果右子树高度不够根高度减一，说明右子树虽然矮但也是满了的，要潜入左子树继续求高度，而满的右子树节点数就是1 + 2 + ... + 2^( rightH - 1 )，再加个根节点又是1 << rightH。之前那个外国小哥大神还介绍了和最naive的递归方法相似的一个方法，思路是先同时向左和向右下潜，若二者同时null了，说明是full，直接利用高度求节点数即可；若右空而左没空，则需要分别对第一个左子树和第一个右子树递归调用，再加个根节点，由于每次这两个recursive call中有一个能get到full的，因此不会持续递归，这是相比naive的优化。写出来是这样的。 - Did not come up with the simple iterative method.123456789101112131415161718192021222324252627class Solution {private int getHeight(TreeNode root) {int h = 0;while (root != null) {h++;root = root.left;}return h;}public int countNodes(TreeNode root) {int rootHeight = getHeight(root);int ans = 0;while (rootHeight != 0) {int rightHeight = getHeight(root.right);// get right sub heightif (rightHeight + 1 == rootHeight) { // means left is fullroot = root.right;} else { // rightHeight == rootheight - 2, right is full, need to go leftroot = root.left;}ans += (1 << rightHeight); // rightHeight == rootHeight -1 or -2, it can make sure// a full sub tree plus root is added into ansrootHeight--;}return ans;}}
223. rectangle-area
224. basic-calculator
- 给一个只含有数字和加、减、小括号的算式字符串，求结果。
- ME：利用两个Stack，一个存数字、一个存运算符和左括号。当遇到数字时，若符号栈顶不是左括号，就直接pop出数字栈顶数字和pop符号、计算一波并将结果入数字栈。当右括号出现则持续计算直到遇到左括号。写出来是这样。
- TA：这个 只用到了一个Stack，因为符号的加减可以通过一个变量来控制而不用存起来，每次直接就运算掉了，而括号也不需要去验证是否匹配，因此也不用存起来，当出现左括号就把前面的运算结果入栈，同时把括号前的符号入栈，当右括号出现，就先取栈顶的符号乘以当前运算结果，再加上栈顶数字就完成了这部分括号的计算。很优雅。这个 也差不多，模仿了一波。
225. implement-stack-using-queues
- 用Queue实现Stack的功能。
- ME：用两个Queue实现了。
- TA：这个告诉你，只用一个就够了，为了维持『后入先出』，队列要在push的时候维持倒序，这个方法的push是O( n )而pop和top都是直接队首就搞定了。
226. invert-binary-tree
- 镜像翻转一个二叉树。传说中有名的一题，因为有一个不会写这个而被谷歌拒的牛人。
- ME：递归搞定。这里是有返回值的版本，如果是void版本呢？也差不多其实。
- TA：这个改成了iterative的方法，其实就是level traverse中途把每个node的两个孩子对调了，就是镜像了。这里解释了为什么iterative更受青睐：递归可能在函数嵌套过程中增加了overhead、递归容易溢出函数栈、最后一个没看懂，大概是说『更容易拆解』？？？
- Need to remember iterative one12345678910111213141516171819202122232425class Solution {public TreeNode invertTree(TreeNode root) {if (root == null) {return null;}if (root.left == null && root.right == null) {return root;}Queue<TreeNode> q = new LinkedList<>();q.add(root);while (!q.isEmpty()) {TreeNode curr = q.poll();TreeNode temp = curr.left; // swap at each nodecurr.left = curr.right;curr.right = temp;if (curr.left != null) { // push into Collectionq.add(curr.left);}if (curr.right != null) {q.add(curr.right);}}return root;}}
227. basic-calculator-ii
- 给一个只含有
+ - * /四则运算的String，求运算结果。 - ME：模仿学到的单Stack做法，处理优先级不同的情况。利用upgrade确认是否需要提升优先级，提升时将前面的运算结果和符号依次Push入栈，把当前数字设为当前结果，然后往后计算结果，直到回到加减运算时，再将当前结果乘以栈顶的符号、加上再前一位的数字，然后继续往后算。写出来是这样，还是复杂了点。
- TA：在提交页面看到一个超叼的不用Stack的方法，模仿了一波写成了这样。对于加减符号，把符号之前的一个数字乘以sign，直接就往结果里加了，然后更新后续的符号；对于乘法，很巧妙的是直接将乘法前的一个数字融到了sign符号里面，因为sign本身也是要乘后续数字的嘛；对于除法稍微复杂一些，碰到除法符号就设置divide标志，然后将除法符号前的数字赋值给一个prev，然后在除法符号之后的那个数字结束时，完成prev / num的除法，赋值给num，然后再后续计算。讨论区里也有一个类似的。
228. summary-ranges
- 给一个排好序的int数组，求其一个个连续的值域，用String表示并添加到List中。
- ME：既然排好序了，那么连续的话就必须有『索引之差等于值之差』，我首先想到的是二分查找，如果索引差小于值差，则向左半部分找，否则到右半部分。查找完成后start~right即为连续的值域，然后把start赋值为right+1，继续，写出来是这样。
- TA：哇去，我还以为自己这个O( NlogN )的想法很妙，美滋滋哩，结果提交页面看到个one-pass O( N )的，讨论区也有个类似的，笋干爆炸。思路是直接判断前后两个是否差值为1，找到差值不为1的时候结束循环，输出到结果，虽然双重循环但是内层循环的索引用的是外层的，所以还是O( N )。默默学习了一波，写出来是这样。
229. majority-element-ii
- 给一个乱序的int数组，求其中出现次数超过三分之一规模的所有数。要求linear time，O( 1 )space。
- ME：想了半天不知道除了HashMap还能怎么搞，回看了169有个morre voting，但是只适用于求超过一半的元素的情况。陷入江局。。。
- TA：玛德，刚看到这个的开头笋干就懂了大概的思路，既然求一半以上的用的是一个数字，那求三分之一以上的，可能有两个数字，那就设两个变量嘛。不过细节还是得参考才能写出来，例如当count1和count2不断归零之后，新产生的num1、num2不一定超过三分之一频数，还需要遍历一波看看是不是真的符合。写出来是这样。后续有推广到k分之一频数的方法，就是把count和num都对应放到数组里。
230. kth-smallest-element-in-a-bst
- 给一个BST，求第k小的元素。
- ME：丢脸，又忘记二叉树的iterative的in-order怎么写，参考了173才写出来了这题，用一个Stack保存节点，每次持续把左节点入栈，取栈顶加入List，同时看这个节点是否存在右节点，有就深入下去，继续持续把左子树入栈。。。
- TA：这个大神给出了三种方法，玛德貌似我的iterative方法是最不preferable的，而且我用了个List其实根本没必要，因为我只关心最后一个元素，可以直接让k减减嘛。先看看recursive版本的，用一个全局变量
count = k不断减减，直到零就说明找到了，遍历也是优先往左子树递归，若当前不是第k个，再往右子树递归。写出来是这样。第一个答主说是最preferable的，但时间复杂度O( N logN )并不低啊，不过还是模仿了一波。思路是利用左节点数判断，若左边子树的节点数恰好是k - 1，那么当前节点就是了。若左子树节点数多于k - 1，则需要递归进入左子树进一步找。若左子树节点数多于k - 1，则需要递归到右子树，但此时就需要更新k为k - 1 - count。 - Need to know more methods… Implementation OK though.12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970class Solution { // counting nodenum of leftTree and decide which way to dig intopublic int kthSmallest(TreeNode root, int k) {if (root == null) {return 0;}int numLeft = getNodeNum(root.left);if (numLeft >= k) { // k-th should be in leftreturn kthSmallest(root.left, k);} else if (numLeft == k - 1) {return root.val;} else {return kthSmallest(root.right, k - numLeft - 1);}}private int getNodeNum(TreeNode root) {if (root == null) {return 0;}return 1 + getNodeNum(root.left) + getNodeNum(root.right);}}class Solution { // recursive pre-order traverse to update global countprivate int count;private int ans;public int kthSmallest(TreeNode root, int k) {count = k;ans = 0;helper(root);return ans;}private void helper(TreeNode root) {if (root == null) {return;}helper(root.left);count--;if (count == 0) {ans = root.val;return;}helper(root.right);}}class Solution { // basic iterative pre-order tarversepublic int kthSmallest(TreeNode root, int k) {if (root == null) {return 0;}Stack<TreeNode> stack = new Stack<>();stack.push(root);while (root.left != null) {stack.push(root.left);root = root.left;}while (!stack.isEmpty()) {TreeNode curr = stack.pop();if (--k == 0) {return curr.val;}if (curr.right != null) {curr = curr.right;while (curr != null) {stack.push(curr);curr = curr.left;}}}return 0;}}
231. power-of-two
- 给一个整数，判断它是不是2的幂。
- ME：用一个pivot从1开始往左移，直到最高位。写出来是这样。
- TA：在提交页面看到个超叼的方法，思路是直接用n和n-1作一个与运算，如果是2的幂直接全是0了，否则就不是2的幂。模仿了一下。
232. implement-queue-using-stacks
- 用Stack模拟Queue的功能。
- ME：印象深刻好吧，一个栈专门输入、另一个栈专门输出，当输出的空了，就把in的全部给导过来，再pop/peek。写出来是这样。
- TA：没啥了。
233. number-of-digit-one
- 给一个整数n，求从0~n这些数字中，一共出现了多少次1.
- ME：纠结了好久自己写出来了个这个，速度神慢。思路是求最高的非0位，从
1000000000开始逐步除以10去找，求商和余数。若余数为0，说明恰好是整的临界数，除非是1000这样的能在最高位提供1，6000这些都无法在最高位提供1，我的做法是递归地直接去找n - 1这个数的1的出现次数。若不是临界数，再看商，若商为1，则说明『最高位能提供的1由后续数字决定，即余数加1个』，否则最高位能提供的就是完整的当前被除数firstOne个1了。然后递归往后找，一部分是由余数决定的，另一部分就是『商』这么多个完整的firstOne - 1中包含的1了。例如1234，最高位能提供的1就有235个，然后余数234递归去求，还有999往前也要递归去求。98765也类似，最高为能提供的1是8766个，然后递归去求8765中含的1，以及9个10000 - 1中含有的1. - TA：又是这个脸熟的大神，看到这个我是震惊的，怎么可以这么短。。。这个大神思路是这样，k作为1、10、100…的一个除数。当k == 1，此时关注的是个位，每10个数就会在个位出现一个1，共有
( n / k ) / 10个『10个数』；当k == 10，此时关注的是十位，每100个数就会在十位出现十个1，共有( n / k ) / 10个『100个数』，对应1的个数为( n / k ) / 10 * k，这就是基本公式了。但是对于特殊的数字1x, 11x...，可以在最高位提供额外的1，有多少个额外的1呢？n % k + 1个，而判断是否特殊的条件是( ( n / k ) % 10 == 1 )；此外，还需要考虑2x，因为按照目前的公式在计算十位出现的1的时候，( 2x / 10 ) / 10 * 10算出来是0，我们需要让1x在计算十位时得到0而后续的2x~9x都为10，一个trick是在公式中加8，( ( 2x / 10 ) + 8 ) / 10 * 10得到的就是10了。综上，最终的公式就是( ( ( n / k ) + 8 ) / 10 * k ) + ( ( n / k ) % 10 == 1? n % k + 1: 0 )。此外还有这个方法，这个情况更加简洁直观，对于数字xyzdabc来说，考虑千位d出现的1的次数，若d == 0则xyz0000往后都不可能有千位的1，只能向前找，也就是0 ~ xyz-1即xyz * 1000个1了；若d == 1，则除了前面的xyz * 1000个，往后还有0 ~ abc即abc + 1个；若d > 1，则xyz1000 ~ xyz1999都可以被取到，所以直接是xyz * 1000 + 1000，更推荐这个方法！
234. palindrome-linked-list
- 判断一个链表是否自对称。
- ME：一开始用了Stack，后来直接把前半部分链表反转了。利用快慢指针找到中间节点，再根据fast指针后续的情况判断出总节点的奇偶，微调一下，然后pop栈比较、或者直接把前面反转后的链表和后续链表比较。
- TA：没啥吧，不过这里有两个大神争论什么叫作『O(1) space』。123456789101112131415161718192021222324252627282930313233343536373839class Solution {public boolean isPalindrome(ListNode head) {if (head == null || head.next == null) {return true;}ListNode slow = head, fast = head, prev = null;while (fast != null && fast.next != null) {prev = slow;slow = slow.next;fast = fast.next.next;}if (fast != null) {prev = slow;slow = slow.next;}ListNode left = head, right = reverse(slow), head2 = right;while (right != null) {if (left.val != right.val) {return false;}left = left.next;right = right.next;}// prev.next = reverse(head2);return true;}private ListNode reverse(ListNode head) {ListNode pre = null, cur = head;while (cur != null) {ListNode next = cur.next;cur.next = pre;pre = cur;cur = next;}return pre;}}
235. lowest-common-ancestor-of-a-binary-search-tree
- 给一个BST的根节点，给其中的两个节点，求二者最低层的共同的祖先。
- ME：BST根、左、右孩子有大小关系，而且不含重复元素，所以直接根据val来判断递归即可。所给的p、q其中一个已经是root了，那root就是共同祖先了。否则就根据p, q, root的val的大小关系，若
p < q < root则往左递归，若root < p < q则往右递归，若p < root < q，则p和q分属两侧，root直接就是共同祖先了。写出来是这样。 - TA：又是这个外国大神小哥总结了Iterative和Recursive的方法，其中iterative方法利用root - p和root - q是否同号来判断大小关系实在是妙哉，当其中一个等于root的时候也可以直接跳出循环了。
- Just make use of the property of binary search tree;1234567891011121314151617class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {if (root == null || p == null || q == null || p == root || q == root) {return root;}if (p == q) {return p;}if (Math.max(p.val, q.val) < root.val) {return lowestCommonAncestor(root.left, p, q);} else if (Math.min(p.val, q.val) > root.val) {return lowestCommonAncestor(root.right, p, q);} else {return root;}}}
236. lowest-common-ancestor-of-a-binary-tree
- 给一个可能带有重复元素且大小关系不确定的二叉树，给两个节点，求他们的最底层的公共祖先。
- ME：一开始以为没有重复元素，直接向两侧递归如果都能找到两个节点其中一个，就返回当前节点了。结果WA看了一下样例才发现可以重复。想了一晚上都不知道怎么破，陷入江局。。。
- TA：看了这个我恍然大悟，我犯了一个严重的错误，用『值』来判定节点是否相等，而事实上就算『值』重复，两个节点对象那就是两个节点对象，是绝对可以分开的。因此你原来的思路算是可行的，如果当前节点是其中一个，直接就可以返回了；否则就递归往两侧找，如果左侧找不到那说明在右侧、如果右侧为空说明在左侧，如果都不空那就是当前节点了。写出来是这样的。还有一个利用HashMap, Stack, HashSet的iterative的方法，你别说，我还真想到过，但没敢动手实现。思路是利用HashMap记录每个节点的父节点，然后用Stack（其实Queue也行）一直往后类似于层级遍历，当Map中记录到了p和q作为key的键值对，就结束记录父亲的工作。然后用Set记录p的所有父亲，一路向上直到root。然后再从q开始往上找Parent，找到的第一个在Set中出现的，就是最low的共同祖先啦。写出来是这样的。
- fail to come up with the recursive method checking node equation.12345678910111213141516171819class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {if (root == null) {return null;}if (root == p || root == q) {return root;}TreeNode left = lowestCommonAncestor(root.left, p, q); // dig leftTreeNode right = lowestCommonAncestor(root.right, p, q); // dig rightif (left != null && right != null) { // both side has return nodereturn root;}if (left == null && right == null) {return null;}return left == null? right: left;}}
237. delete-node-in-a-linked-list
- 给一个单向链表中的节点，删除这个节点。
- ME：单向链表按道理是不能给定节点直接删除的，题目没说不能用赋值的方法『伪删除』，而且强调了不能删除最后一个节点，我就想到是更改节点的val，一直到最后，将倒数第二个节点的next指向null就完成了。这题没啥意思。。。
- TA：玛德，哪里用全部赋值啊，直接把要删除节点之后一个节点的值覆盖过来，然后把next指向下下个就好了啊。
238. product-of-array-except-self
- 给一个数组num[]，求对应长度的数组使得output[i]为所有数的积除了num[i]，要求O( n )且不能用除法。
- ME：不给我用除法我整个人是懵逼的，脑子一下转不过来，陷入江局。。。
- TA：这个给出了如何从辅助数组到O(1)space的思考过程。首先这个辅助数组的方法我怎么就想不出来呢，left数组从左开始每一格存储的是『除了当前数字的前面数字之积』，right数组从右开始存储的是『除了当前数字的后续数字之积』，然后再来一波对应把left和right乘起来就得到了『除了当前数字前面和后面数字之积』。这怎么能想不到呐？？写出来是这样。至于从O( N )到O( 1 )的空间复杂度，知道了之后也没啥了，以后再碰到尽量想起来吧。既然每一个地方都需要哟还能感到它左边所有项之积和右边所有项之积，而如果只维护left和right两个值，无法在循环到第一位的时候就获得右边所有数的积，怎么办？答主的做法是在一步循环里，对两端进行更新，也就是每个位置会被更新两次，一次是随left更新，一次是随right更新，left和right就分别从左和从右向另一端去乘。妙哉！如果把这个one-pass拆开来写，就是这样的.
239. sliding-window-maximum
- 给一个数组，给一个window的size，要求从左到右滑动窗口，输出每滑动一格所能看到的数中的最大值，汇总在数组中输出。
- ME：维护最大值，而且要方便删除，我就想到了PriorityQueue，218摩天大楼那题用到了。不过为了提升效率我用的是TreeMap，这样删除任意一个元素就是O( logN )了。先根据前k个元素初始化TreeMap，然后继续往后遍历，每次取firstKey就是最大值（不过要在构造时传入Collections.reverseOrder才是从大到小），然后删除窗口中的第一个元素、添加后一个元素，一直往后。写出来是这样，看了tag给的也是Heap。
- TA：挖去！！这个真的妙，思路是利用Deque维护索引，左侧头部就是窗口范围内最大值对应的索引，右侧头部就是依次递减的值对应的索引，在Deque内所存储索引对应的值一定是递减的。循环开始时，先确认最左侧的索引是否已经超出了窗口范围，超出了就需要poll掉（答主用了while，其实if足矣）。然后从右侧比较后续元素，如果新加入的元素比前面的大，就直接pollLast，一直比较，直到可以维持递减状态再把新加入元素的索引add进去（最坏情况是新加入元素比前面的都大，就一直清空了原Deque直接留下新的索引了）。最后就直接把Deque左侧索引对应元素存入结果就好。太妙了！！！写出来是这样。还有一个方法也是挺巧妙的不过不太好移植，根据窗口长度划分区域，分别求左边开始的和右边开始的可见最大值，最后综合一下
left[i + k - 1]和right[i]，写出来是这样。在提交页面还看到一个很简单粗暴的想法，维护一个max，如果窗口前的元素是max，就往后再找一波新的max，这个复杂度感觉就不是O( N )了。。。
240. search-a-2d-matrix-ii
- 给一个m*n的二维数组，其中每一行的元素都满足左边小于等于右边、每一列元素都满足上面小于等于下面，给一个target，判断是否在这个矩阵里面。
- ME：马上想到二分查找嘛。取左上和右下的中间元素（横纵分别取中点），若target较小，则递归搜索中点上方的矩形和它左方的矩形，若target较大，则递归搜索中点下方和它右方的矩形。写出来是这样，不过速度好慢。。。我这样的时间复杂度貌似是（M * log( N )）?
- TA：玛德，原来这个线性查找就已经很快了，O( M + N )呢！
241. different-ways-to-add-parentheses
- 给一个只含有数字和加、减、乘的算式，求各种加括号的方式对应的值，不论值是否重复都输出到List中。
- ME：隐约感到要递归，纠结了很久终于还是写出来了，但是神慢啊。思路就是分成两半，前半部分的数字依次乘以后半部分的数字。
- TA：我的方法跟这个很像，在提交页面最快的方法就是基于这个，再加一个HashMap来避免重复计算。这还有一个DP的方法，
dp[i][j]存的是从第i个数字到第j个数字（不是索引！）的算式的所有可能值。首先对字符串做预处理，拆解成一个个独立的String，数字str与运算符str交替。假设整理后有N个数字，让d从0循环到N-1，表示取第i~i+d个整数的结果，即dp[i][i+d]。而当d=0，就只取一个数字，也就是本身了。内层还有两重循环，就是根据拆分成两半分别求的结果来更新了。
242. valid-anagram
- 给两个字符串，判断它们是否是anagram，既一个把字母打乱后重新组合可得到另一个。
- ME：用bucket数组咯，算字符出现的个数，s出现就++，t出现的就–，最后再扫一波看看是否全部都为0.写出来是这样。
- TA：没啥了。
243. shortest-word-distance
- 给一个String数组，给两个其中的String，求它们的最小距离。
方法一：用两个List记录它们出现的所有index，然后用minimum distance between two sorted array的双指针搞法求最短距离。
1234567891011121314151617181920212223242526272829class Solution {public int shortestDistance(String[] words, String word1, String word2) {if (words == null || words.length == 0) {return 0;}List<Integer> index1 = new ArrayList<>();List<Integer> index2 = new ArrayList<>();for (int i = 0; i < words.length; i++) {if (words[i].equals(word1)) {index1.add(i);} else if (words[i].equals(word2)) {index2.add(i);}}int ptr1 = 0, ptr2 = 0, min = words.length;while (ptr1 < index1.size() && ptr2 < index2.size()) {min = Math.min(Math.abs(index1.get(ptr1) - index2.get(ptr2)), min);if (min == 1) {return 1;}if (index1.get(ptr1) < index2.get(ptr2)) {ptr1++;} else {ptr2++;}}return min;}}方法二：不需要记录每一个index，直接在出现的时候就可以比较了。这样就是完美的one-pass.
12345678910111213141516171819class Solution {public int shortestDistance(String[] words, String word1, String word2) {if (words == null || words.length == 0) {return 0;}int ptr1 = -1, ptr2 = -1, min = words.length;for (int i = 0; i < words.length; i++) {if (words[i].equals(word1)) {ptr1 = i;} else if (words[i].equals(word2)) {ptr2 = i;}if (ptr1 != -1 && ptr2 != -1) {min = Math.min(Math.abs(ptr1 - ptr2), min);}}return min;}}
244. shortest-word-distance-ii
- 还是给一个String数组，给两个其中的String，求它们的最小距离。但是现在需要实现一个类，会call很多次求距离的function。
- 将每个word出现的索引存入List，还是用minimum distance between two sorted array的双指针搞法求最短距离。12345678910111213141516171819202122232425262728293031323334353637class WordDistance {Map<String, List<Integer>> map;Map<String, Map<String, Integer>> cache;public WordDistance(String[] words) {map = new HashMap<>();cache = new HashMap<>();for (int i = 0; i < words.length; i++) {map.putIfAbsent(words[i], new ArrayList<>());map.get(words[i]).add(i);}}public int shortest(String word1, String word2) {if (cache.containsKey(word1) && cache.get(word1).containsKey(word2)) {return cache.get(word1).get(word2);}List<Integer> index1 = map.get(word1);List<Integer> index2 = map.get(word2);int ptr1 = 0, ptr2 = 0, min = Integer.MAX_VALUE;while (ptr1 < index1.size() && ptr2 < index2.size()) {min = Math.min(Math.abs(index1.get(ptr1) - index2.get(ptr2)), min);if (min == 1) {break;}if (index1.get(ptr1) < index2.get(ptr2)) {ptr1++;} else {ptr2++;}}cache.putIfAbsent(word1, new HashMap<>());cache.get(word1).put(word2, min);cache.putIfAbsent(word2, new HashMap<>());cache.get(word2).put(word1, min);return min;}}
245. shortest-word-distance-iii
- 还是给一个String数组，给两个其中的String，求它们的最小距离。与i不同的是这两个word可能相同，不能返回0而是要找出两两之间的最短距离。
- 还是双指针法搞定。12345678910111213141516171819202122232425262728293031323334class Solution {public int shortestWordDistance(String[] words, String word1, String word2) {if (words == null || words.length == 0) {return 0;}if (word1.equals(word2)) {int ptr = -1, min = words.length;for (int i = 0; i < words.length; i++) {if (words[i].equals(word1)) {if (ptr == -1) {ptr = i;} else {min = Math.min(i - ptr, min);ptr = i;}}}return min;} else {int ptr1 = -1, ptr2 = -1, min = words.length;for (int i = 0; i < words.length; i++) {if (words[i].equals(word1)) {ptr1 = i;} else if (words[i].equals(word2)) {ptr2 = i;}if (ptr1 != -1 && ptr2 != -1) {min = Math.min(Math.abs(ptr1 - ptr2), min);}}return min;}}}
246. strobogrammatic-number
- 给一个只含有数字的字符串，判断将它180度翻转后是否还是原来的字符串。skip.
250. count-univalue-subtrees
- 给一个二叉树，求其中所有节点的value都相同的子树个数。DFS+全局变量来求即可，当左子树和右子树都为uni-value时，再判断当前跟节点是否和左、右孩子都相等。skip。
252. meeting-rooms
- 给一个Interval的数组，每个Interval含有meeting的开始和结束时间戳，问是否能参加所有会议。
- 贪心算法，根据start排序，然后取前后两个看有没有overlap。1234567891011121314class Solution {public boolean canAttendMeetings(Interval[] intervals) {if (intervals == null || intervals.length == 0) {return true;}Arrays.sort(intervals, (a, b) -> a.start - b.start);for (int i = 1; i < intervals.length; i++) {if (intervals[i].start < intervals[i - 1].end) {return false;}}return true;}}
253. meeting-rooms-ii
- 给一个Interval的数组，每个Interval含有meeting的开始和结束时间戳，求至少需要多少个meeting room.
- 最少的会议室就需要最大可能利用前面的会议室，因此需要记录之前的会议的结束时间，因此想到用PriorityQueue存，每次和最早结束的比较看看能否接上即可，然后把当前会议的结束时间加入PQ即可。最后在PQ中留下的会议个数就是需要的独立会议室个数。12345678910111213141516class Solution {public int minMeetingRooms(Interval[] intervals) {if (intervals == null || intervals.length == 0) {return 0;}Arrays.sort(intervals, (a, b) -> a.start - b.start);PriorityQueue<Integer> endTime = new PriorityQueue<>();for (int i = 0; i < intervals.length; i++) {if (!endTime.isEmpty() && endTime.peek() <= intervals[i].start) {endTime.poll();}endTime.add(intervals[i].end);}return endTime.size();}}
254. factor-combinations
- 给一个整数，求它所有的factors的组合。
- DFS(backtracking)，给定起始factor，循环判断能否整除直到n，能整除则递归下去求n/factor和factor为起始的新因数。递归停止条件是给的n小于等于1，说明没有更多factor了，这时就把这一路经过的因数存入ans。然后回到上一次调用递归的位置，删除path的最后一个factor，继续往后遍历。时间复杂度有点难分析。。。12345678910111213141516171819202122232425class Solution {public List<List<Integer>> getFactors(int n) {List<List<Integer>> ans = new ArrayList<>();if (n < 4) {return ans;}getFactors(n, 2, new ArrayList<Integer>(), ans);return ans;}private void getFactors(int n, int factor, List<Integer> path, List<List<Integer>> ans) {if (n <= 1) { // 已经除尽了，说明没有更多factorif (path.size() > 1) { // 当前path就是一路走过来用过的factorans.add(new ArrayList<Integer>(path));}return;}for (int i = factor; i <= n; i++) {if (n % i == 0) { // 可以整除，说明i是n的一个factorpath.add(i); // 将i加入path，将n除掉i，再递归从i开始继续往后找大于等于i的factorgetFactors(n / i, i, path, ans);path.remove(path.size() - 1);}}}}
255. verify-preorder-sequence-in-binary-search-tree
- 给一个int数组，判断这个是否可能是一个BST经过前序遍历得到的。
方法一：利用stack维护一个单调递减的序列，一旦出现大的值说明需要折到右子树，弹出时需要存入prev用来保证后面的值一定要大于这个prev值。
12345678910111213141516171819class Solution {public boolean verifyPreorder(int[] preorder) {if (preorder == null || preorder.length <= 1) {return true;}Integer prev = null;Deque<Integer> stack = new ArrayDeque<>();for (int num : preorder) {while (!stack.isEmpty() && num > stack.peek()) {prev = stack.pop();}if (prev != null && num <= prev) {return false;}stack.push(num);}return true;}}方法二：如果不允许额外空间，而允许改变输入的数组，则可以将输入数组作为stack使用。
123456789101112131415161718class Solution {public boolean verifyPreorder(int[] preorder) {if (preorder == null || preorder.length <= 1) {return true;}Integer prev = null, index = -1;for (int num : preorder) {if (prev != null && num <= prev) {return false;}while (index >= 0 && num > preorder[index]) {prev = preorder[index--];}preorder[++index] = num;}return true;}}
257. binary-tree-paths
- 给一个二叉树，返回所有从root到叶子节点的路径，用String的形式存入List。
- ME：DFS搞定，但是我的字符串拼接不合理，
"->"的拼接显得很笨。而且由于用了StringBuilder来真的拼接，所以在DFS结束之前还要删除当前的结果，速度还真不一定比String和加号来得快。写出来是这样。 - TA：这个就是String和加号的，实在是太简洁啦！写出来是这样。这个则给出了Queue和Stack的方法，其实就是类似于层级遍历，找到叶子就把对应的String输出就欧了。Stack代码几乎一样，只不过由于每次都是先处理后进来的节点，所以效果是DFS，先获取的是最右边的路径，然后依次往左。还有一个recursive的，但没有辅助函数，每次将当前节点插入到递归返回列表中各字符串的前面，表示『是从我这个节点到这些字符串的』，最终就是完整的Path了。
- need to know more different solutions.123456789101112131415161718192021222324252627282930313233343536373839404142434445class Solution {public List<String> binaryTreePaths(TreeNode root) {List<String> ans = new ArrayList<>();dfs(root, ans, new StringBuilder());return ans;}private void dfs(TreeNode root, List<String> ans, StringBuilder sb) {if (root == null) {return;}String temp = null;if (sb.length() == 0) {temp = String.valueOf(root.val);} else {temp = "->" + String.valueOf(root.val);}sb.append(temp);if (root.left == null && root.right == null) {ans.add(sb.toString());} else {dfs(root.left, ans, sb);dfs(root.right, ans, sb);}sb.delete(sb.length() - temp.length(), sb.length());}}// no auxiliary methodsclass Solution {public List<String> binaryTreePaths(TreeNode root) {List<String> ret = new ArrayList<>();if (root == null) {return ret;}if (root.left == null && root.right == null) {ret.add(String.valueOf(root.val));}for (String path: binaryTreePaths(root.left)) {ret.add(root.val + "->" + path);}for (String path: binaryTreePaths(root.right)) {ret.add(root.val + "->" + path);}return ret;}}
258. add-digits
- 给一个非负数，不断把它各位加起来，求最终得到的一位数。follow-up是不用循环/递归，在O( 1 )时间内求。
- ME：用循环搞啊，这没啥意思。但follow up的规律想了一下没想出来。
- TA：这个在纸上写写，一下就搞出来了，没啥意思。。。
259. 3sum-smaller
- 给一个数组，和一个target，求数组中所有满足
nums[i] + nums[j] + nums[k] < target的组合数，即使数字相同只要index不同也算不同的组合。 - 固定k，双指针搞i和j。12345678910111213141516171819202122class Solution {public int threeSumSmaller(int[] nums, int target) {if (nums == null || nums.length == 0) {return 0;}Arrays.sort(nums);int count = 0;for (int k = 2; k < nums.length; k++) {int t = target - nums[k];int i = 0, j = k - 1; // 双指针while (i < j) {if (nums[i] + nums[j] < t) { // 固定i，取j,j-1, ..., i+1count += (j - i);i++;} else {j--;}}}return count;}}
260. single-number-iii
- 给一个数组，大多数数字都是恰好出现两次，有两个单身狗只出现一次，找出这两个单身狗。follow-up是不能使用额外的空间。
- ME：还是用了hashset才搞定。但这和前面137. single-number-ii不同了，因为在那里面都只有一个单身狗，而这里有俩。
- TA：这个解释得很清楚。既然有两个不同的数，那么全部异或一遍之后，剩下的就是不同的这两个数的XOR结果，其中为1的就是二者不同的bit，随便取其中一位作为划分依据，这样原数组就分成了两派，一派是该bit为1的，一派是该bit为0的，分别去异或，最后剩下的就是两排中各自的单身狗了。代码参考的是这个，找不同的那个bit用的是取原异或结果的负数（等价于减一再取反），然后与原数做一个AND就得到了最右的原异或结果中的1、同时其他位全部为0.写出来是这样。
261. graph-valid-tree
- 给一个整数n和0~n-1的点组成的无向edges，判断这些点和边是否能组成valid1的tree.
方法一：tree的定义是每个点只有一个parent、边数是节点数-1. 并查集用来存放每个点的parent，每次加入无向边的时候先取两个点的root，这样可以随时判断是否成环（两个点已经共享root了）。最后再判断一下点数和边数即可。
123456789101112131415161718192021222324class Solution {public boolean validTree(int n, int[][] edges) {if (edges == null || edges.length == 0 || edges[0].length == 0) {return true;}int[] id = new int[n];Arrays.fill(id, -1); // 初始时每个点都是rootfor (int i = 0; i < edges.length; i++) {int fromRoot = find(id, edges[i][0]);int toRoot = find(id, edges[i][1]);if (fromRoot == toRoot) { // 成环时一定会归到同一root处return false;}id[toRoot] = fromRoot;}return edges.length == n - 1;}private int find(int[] id, int p) {if (id[p] == -1) {return p;}return find(id, id[p]);}}方法二：用图论的办法，先用Map建图，对于每一个node维护相邻点的set，然后DFS／BFS进行labeling。由于是一个tree，所以只能有一个label，因此一旦重复出现就说明两点之间有多于一条路径，成环了。
263. ugly-number
- 给一个int，判断它是否ugly number，即因数只由2、3、5组成。
- ME：三个单独的循环，分别模5、3、2，最后看看是否剩下1.写出来是这样。
- TA：差不多吧，有的大神把我5、3、2这三个循环都放到外层循环里了。
264. ugly-number-ii
- 给一个整数n，求第n个ugly-number。
- ME：暴力法当然知道，就一波循环往后走，每个判断是否ugly-number呗。我又想了一个不太暴力的暴力法，就是用TreeSet，每次取最前的元素，尝试乘以2、乘以3这样往里放，然后每次就直接取首位就是当前的元素。不过为了防止越界，一开始用的是
curr * i > 0后来改成curr * i > curr，最后改成curr * i / i == curr才对。写出来是这样的，略慢。。。tag给的是DP，但我没想出来怎么个DP法。 - TA：这个讲得很棒。既然都是2、3、5的倍数组成的，那我们就可以分成三个独立的部分共同组成ugly-number的数组，每次从2、3、5倍数中选择最小的放到ugly中，然后更新被选中的那个的倍数，即从ugly中一直往后取倍数乘以相应的2/3/5。写出来是这样，注意中间的三个if不可以写成else if，因为可能factor有重复的，例如
2*3和3*2，一旦取了6，factor2和factor3都需要更新。这应该就是题目想要考察的DP了。
266. palindrome-permutation
- 给一个String，判断它的某一个排列是否能形成palindrome。
- 看看是否有多于一个奇数count的字符即可。123456789101112131415161718192021class Solution {public boolean canPermutePalindrome(String s) {if (s == null || s.length() == 0) {return true;}boolean[] isOdd = new boolean[256];for (char c : s.toCharArray()) {isOdd[(int)c] = !isOdd[(int)c];}boolean hasOdd = false;for (int i = 0; i < isOdd.length; i++) {if (isOdd[i]) {if (hasOdd) {return false;}hasOdd = true;}}return true;}}
267. palindrome-permutation-ii
- 给一个字符串，求他不重复的所有自对称的permutation。
- 不重复的permutation参考47，关键是如何将自对称融入里面。自对称就是正着反着读都一样的字符串，那么可以拆分成两半，将前一部分组合出来，直接reverse以下就得到后半部分。不过还需要注意除了
abba，还有aaba也是合法的，因此需要统计每个字符串的出现频数，只允许一个字符出现奇数次放在中间。之后将字母一次装入一个数组/list中作为pool，沿用47题的去重思路，每次取字母前先看看之前的字母是否一样，如果前一位是相同的字母却没有被取，说明这个位置当前这个字母不能取。123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354class Solution {public List<String> generatePalindromes(String s) {List<String> ans = new ArrayList<>();if (s == null || s.length() == 0) {return ans;}// 统计每个字符出现次数，顺便统计奇数个的字符个数Map<Character, Integer> map = new HashMap<>();int oddCount = 0;for (char c : s.toCharArray()) {map.put(c, map.getOrDefault(c, 0) + 1);oddCount += map.get(c) % 2 == 0 ? -1 : 1;}if (oddCount > 1) {return ans;}// 将一半的字符存入listList<Character> charPool = new ArrayList<>();String mid = "";for (Map.Entry<Character, Integer> entry : map.entrySet()) {if (entry.getValue() % 2 != 0) {mid += entry.getKey();}for (int i = 0; i < entry.getValue() / 2; i++) {charPool.add(entry.getKey());}}dfs(ans, charPool, new boolean[charPool.size()], new StringBuilder(), mid);return ans;}private void dfs(List<String> ans, List<Character> charPool, boolean[] used, StringBuilder sb, String mid) {if (sb.length() == charPool.size()) {ans.add(sb.toString() + mid + sb.reverse().toString());sb.reverse();} else {for (int i = 0; i < charPool.size(); i++) {if (i > 0 && charPool.get(i) == charPool.get(i - 1) && !used[i - 1]) {continue;}if (!used[i]) {used[i] = true;sb.append(charPool.get(i));dfs(ans, charPool, used, sb, mid);sb.setLength(sb.length() - 1);used[i] = false;}}}}}
268. missing-number
- 给一个规模为n的数组，里面包含了0~n-1的数字，除了一个，找到缺的这一个。要求linear time complexity.
- ME：很直接地想到了木桶法呀。follow-up要求不用extra space，感觉又是异或，但是没试出来。。。
- TA：这里列举了三种方法，一是求和法，可以用『首项加末项乘以项数除以二』先求出总和，然后逐个去减，最后得到的就是那个Missing Number了。二是位操作，利用
a ^ b ^ b = a，从头到尾一口气异或索引和数字，因为基本上每个索引都会对应到它的数字，0-0, 1-1, ..., nums[index] - index，除了缺的那个数。写出来是这样。三是二分查找，不过还有一步排序并不是O(N)，所以不太合题意。
269. alien-dictionary
- 给一个按照某种外星人字典序排好序的String数组，只包含小写字母，求这些出现过的字母的顺序。若有多种可能（平级）则任意顺序均可。
- topo排序问题，前后两个字符串逐个字符找到第一对不同的字符，确定先后顺序（前->后）构成一条边，两两字符串全部遍历完之后就形成了一个graph。维护一个inDegree，每次BFS时从入度为0的节点出发，将它可达的所有邻接点的入度都减1（删掉这些边），最后如果全部字符都遍历到了即可。如果出现了环，则一定会又入度不为0的点残留。123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960class Solution {public String alienOrder(String[] words) {if (words == null || words.length == 0) {return "";}Map<Character, Set<Character>> graph = new HashMap<>();Map<Character, Integer> inDegree = new HashMap<>();initInDegree(words, inDegree);buildGraph(words, graph, inDegree);Queue<Character> q = new LinkedList<>();for (char c : inDegree.keySet()) {if (inDegree.get(c) == 0) {q.offer(c);}}StringBuilder sb = new StringBuilder();while (!q.isEmpty()) {char c = q.poll();sb.append(c);if (graph.containsKey(c)) {Set<Character> neighbors = graph.get(c);for (char neighbor : neighbors) {inDegree.put(neighbor, inDegree.get(neighbor) - 1);if (inDegree.get(neighbor) == 0) {q.offer(neighbor);}}}}if (sb.length() != inDegree.size()) {return "";}return sb.toString();}private void initInDegree(String[] words, Map<Character, Integer> inDegree) {for (String word : words) {for (char c : word.toCharArray()) {inDegree.put(c, 0);}}}private void buildGraph(String[] words, Map<Character, Set<Character>> graph, Map<Character, Integer> inDegree) {for (int i = 1; i < words.length; i++) {String prev = words[i - 1];String curr = words[i];int len = Math.min(prev.length(), curr.length());for (int j = 0; j < len; j++) {char c1 = prev.charAt(j);char c2 = curr.charAt(j);if (c1 != c2) { // 找到第一个不同的字母graph.putIfAbsent(c1, new HashSet<Character>());if (graph.get(c1).add(c2)) {inDegree.put(c2, inDegree.get(c2) + 1);}break;}}}}}
271. encode-and-decode-strings
- 实现encode和decode函数，将字符串List和单一条字符串互相转换。
- 字符含有哪些？（所有ASCII字符都可能出现）
- 由于每个符号都有可能出现，所以不能想着用某个特殊符号来拼接和拆分。因此需要额外的信息进行标记，这里用的是在
/之前加上所跟字符串的长度的方式，decode时每次从特定位置开始找/，然后取出它前面的长度信息直接截取后面的子字符串。1234567891011121314151617181920212223public class Codec {// Encodes a list of strings to a single string.public String encode(List<String> strs) {StringBuilder sb = new StringBuilder();for (String str : strs) {sb.append(str.length()).append("/").append(str); // 长度 + / + 字符串内容}return sb.toString();}// Decodes a single string to a list of strings.public List<String> decode(String s) {List<String> ans = new ArrayList<>();int i = 0;while (i < s.length()) {int index = s.indexOf("/", i);int len = Integer.valueOf(s.substring(i, index));ans.add(s.substring(index + 1, index + 1 + len));i = index + 1 + len;}return ans;}}
272. closest-binary-search-tree-value-ii
- 给一个BST，求离target最接近的k个数字。
- 注意由于是BST，因此进行
O(N)中序遍历的时候天然地就可以得到有序的数组，在这个有序数组中找到离target最近的k个数字之后，就可以直接忽略剩余数字了。在中序遍历时，先递归进入左孩子，出来后如果List中仍有位置(size < k)，直接加到末尾。计算当前节点与target之差，和目前List中首位做比较。注意由于是从小到大的，因此List的首位就是离target最远的最小值，因此如果当前的delta更小，直接将首位poll掉即可。12345678910111213141516171819202122class Solution {public List<Integer> closestKValues(TreeNode root, double target, int k) {LinkedList<Integer> retVal = new LinkedList<>();inorder(root, target, k, retVal);return retVal;}private void inorder(TreeNode curr, double target, int k, LinkedList<Integer> retVal) {if (curr == null) {return;}inorder(curr.left, target, k, retVal);if (retVal.size() == k) {if (Math.abs(curr.val - target) > Math.abs(retVal.peekFirst() - target)) {return;} else {retVal.pollFirst();}}retVal.addLast(curr.val);inorder(curr.right, target, k, retVal);}}
273. integer-to-english-words
- 给一个非负的整数，返回它对应的英文念法字符串。
- ME：各种判断，然后递归去求每三位的念法，写出来是这样。其实没什么算法上的难度。。。
- TA：这个和我的思路差不多，不过他直接用的是数字，没想到也挺方便的！也是每次取三位来转换，在数字这里就直接是
num % 1000了。而且答主也没有纠结空格加不加，反正统一都在末尾加上空格，最后返回之前就trim一下就行了。
274. h-index
- 给一个数组，存的是某学者的论文的引用数，求这个学者的h-index，既他有h篇论文引用数大于等于h，剩下的N - h篇都小于等于h。
- ME：我原本的想法是，排个序，然后二分查找。但是各种边缘条件搞得我崩溃。。。失败
- TA：挖去，原来二分竟然是比较弱的了，因为你排个序起码就O(NlogN)了。这个O(N)的木桶法非常好懂，思路是声明一个规模恰好比原数组多1的bucket，表示索引为i的论文有bucket[i]篇。然后根据引用数在相应索引处加加，注意有可能引用数超过了规模，那么统一加到最大索引处。然后再一波流从后往前累加，当刚好累加到论文数大于等于索引（引用数）的时候，就可以输出了；若一直都没有，说明全都集中在0，那就输出0吧。写出来是这样.
275. h-index-ii
- 如果原citations数组已经是升序排列了，改进算法。
- ME：这绝笔是二分查找了，之前搞了一晚上没搞出来。。。这次就直接看discuss了，因为我怀疑搞不出来是因为理解有误。
- TA：这个说了，不可能有多个解，所以只要符合条件的h就可以直接输出了。我先参考了这个，一旦找到引用数与右边论文数相等的就直接输出；若引用数略小，说明右边论文数太多，提升左界；若引用数略大，说明应该往左多取一些论文，下降右界；最后输出有不需要那么多乱起八糟的判断，直接输出右边论文数就可以了，即
len - (right + 1) = len - left。回帖里有个大神说她的更标准，因为要求一个边界是可以取的而另一个是不可取的，这个还是第一次听说。。。
277. find-the-celebrity
- 给一个API函数判断i是否认识j，celebrity的定义是在n个人中，n-1个人都认识他、他却完全不认识他们。
- O(n^2)搞定，对于每个人，一旦他认识别人、或者别人不认识他就跳出循环。
此外还有一种更巧妙的办法，从头开始一个pass，判断如果i认识j则把candidate设为j，如果i不认识j则j不可能是candidate；然后再一个pass看这个candidate是不是不认识所有人、且所有人都认识他。
12345678910public int findCelebrity(int n) {int candidate = 0; // 先假设第一个人是名人for (int i = 1; i < n; i++) { // 他认识别人就，把他排除掉了if (knows(candidate, i)) candidate = i;}for (int i = 0; i < n; i++) { // 确认他是否认识某个人或者某个人不认识他，那他也不是名人if (i != candidate && (knows(candidate, i) || !knows(i, candidate))) return -1;}return candidate;}follow-up：如果knows的开销很大怎么优化？call是肯定要call的，就是如何在知道结果的时候存下来？cache。真的需要cache吗？不见得，因为在第二次循环的时候其实是知道一部分结果的，这些部分完全不需要再call一次know。
278. first-bad-version
- 给一个整数n表示最新的版本号，从1到n一旦有一个版本是bad，那么后续全都是bad，找到这第一个bad的版本。判断某版本号是否bad调用题目本身提供的API，不用理。
- ME：必须二分查找啊，写出来是这样。
- TA：看了很多答案都比我的简洁，比如这个.我最后那个判断left是否bad其实没有必要，因为当
right - left = 2的时候，mid刚好比left多1，如果它是bad，那么right就会降到mid；若mid不是bad，left直接飙升到mid + 1 = right，此时right也是bad，因此最后统一返回right就好了。
279. perfect-squares
- 给一个正整数，求至少由多少个平方数相加能得到它。
- ME：这题不会啊。感觉是要DP的，列了个数组，但是没找到前后依赖/转换关系。陷入江局。。。
- TA：看了这个，感觉也不难啊哥，可能今天状态不好吧。第一个DP的思路是，把当前数减去一个平方数，求得索引对应的值加1就是了，遍历当前索引能减的所有平方数（相减后非负）。写出来是这样。第二种DP就是把dp数组声明为static的List，持续add在末尾，这样当重复构造Solutions类对象的时候，可以共用一个，如果之前的结果已经求出来了，后续便可以直接访问了。第三种是用拉格朗日数学定理『Legendre’s three-square theorem』，结果只可能是1、2、3、4四种，写一个
isSquare函数判断是否平方数得到结果1，利用定理知当且仅当n != 4^a (8b + 7)的时候，n由三个完全平方数组成，因此当n == 4^a (8b + 7)时，结果要么为4要么为2。第四种方法是BFS，首先把不大于n的平方数列举出来，入队后对这些平方数进行拓展，逐个加平方数并入队，直到达到n。
280. wiggle-sort
- 给一个int数组，要求重新排序使得
nums[0] <= nums[1] >= nums[2] <= nums[3]...。 - 抽象以下就是需要奇数位大于等于前一位、偶数位小于等于前一位。in-place做法比较tricky，利用swap。假设0~i满足条件，当i是odd，如果nums[i+1]大于nums[i]了，就需要swap一下
i和i+1，因为nums[i]已经大于等于前一位了，比他大的nums[i+1]换过来肯定行。123456789101112131415161718192021public void wiggleSort(int[] nums) {if (nums == null || nums.length == 0) {return;}for (int i = 0; i < nums.length; i++) {if (i % 2 == 1) { // 对于奇数位，必须不小于前一位if (nums[i] < nums[i - 1]) {swap(nums, i, i - 1);}} else { // 对于偶数位，必须不大于前一位if (i > 0 && nums[i] > nums[i - 1]) {swap(nums, i, i - 1);}}}}private void swap(int[] nums, int i, int j) {int temp = nums[i];nums[i] = nums[j];nums[j] = temp;}
281. zigzag-iterator
- 给两个List，实现Iterator交替输出二者的元素。
- 用Queue的思路，如果List还有多的元素就把它的iterator放进去，没有就继续。使用Queue拓展成k个List输入也很方便。12345678910111213141516171819202122232425public class ZigzagIterator {private Queue<Iterator> q;public ZigzagIterator(List<Integer> v1, List<Integer> v2) {q = new LinkedList<>();if (v1 != null && !v1.isEmpty()) {q.offer(v1.iterator());}if (v2 != null && !v2.isEmpty()) {q.offer(v2.iterator());}}public int next() {Iterator it = q.poll();int ret = (Integer) it.next();if (it.hasNext()) {q.offer(it);}return ret;}public boolean hasNext() {return !q.isEmpty();}}
282. expression-add-operators
- 给一个纯数字的字符串和一个int的目标值，求这些数字通过加、减、乘如何能够得到target。数字可以组合成多位数但必须维持原顺序，且需要注意运算优先级。
- ME：题目描述的最后一句话是我按照自己理解码完代码（递归）才发现的漏洞，多位数倒是好解决（递归外加一层循环），但是优先级是真的不知所措。。。
- TA：参考了这个，和我的思路基本一致，处理优先级用的是反向相减，利用一个
multi参数记录『如果接下来的操作符是乘法，应该乘的数』，如果再往前一步是+ x，那碰到+ x*y的时候就要先从当前结果中减去x再加上x * y；如果是- x，就直接当成『加负数』来看待就好了；如果是* x，优先级是相同的，那就是从当前结果中减去multi再加回multi乘以当前的数字。此外，还需要考虑Integer的边缘情况，直接用Long就搞定了。在我原本的版本上改了一下，写出来是这样。还有这个DFS方法，感觉也是大同小异，怎么会那么快？它就是把相加的时机滞后了，这样就可以持续计算相乘的结果，而不往里加，一旦出现优先级变化才会真正加到结果中。
283. move-zeroes
- 给一个数组，要求把所有0挪到非零的右边，并保持原有非零项的相互顺序。要求In-place，并尽可能减少操作。
- ME：从前往后遍历，碰到零就往后找非零元素并swap。写出来是这样，有点慢。
- TA：这个告诉你，根本不需要用到swap，直接覆盖就好了。思路是从前往后找非零元素，然后直接赋值给Index对应位置，一直遍历一波，这样Index就保存了原数组中所有的非零元素了，最后再往后全部赋值为0即可。这个也用到了swap，但比你的简洁太多，用一个
j记录『最前的0的索引』，然后i往后找非零元素跟j交换即可。后面还有一个one line python的，用的是sort的comparator，让非零元素在零前面，也是666。
284. peeking-iterator
- design题，实现一个具有peek功能的iterator，返回的是调用Next时的元素。
- ME：不太懂Iterator有啥用，直接看了discuss。
- TA：一开始看的是这个，其实就是比正常的Iterator多维护了一个变量next，存储peek应当返回的元素。原po判定hasNext是通过next变量是否为Null来判定的，但这个答主认为，Null理论上是可以作为合法的元素放进去的，因此应当额外维护一个done的布尔值判定是否已经全部吐干净了。
286. walls-and-gates
- 给一个mxn的int数组，INF表示空房间、-1表示走不通、0表示可走的gate，更新每个INF为到最近的gate的距离。
- BFS，先一波O(MN)把所有gate入queue，然后从每个gate出发，先到的INF就一定是最短的。123456789101112131415161718192021222324252627282930313233343536373839class Solution {private final int INF = 2147483647;public void wallsAndGates(int[][] rooms) {if (rooms == null || rooms.length == 0 || rooms[0].length == 0) {return;}// BFS，从每个gate出发，先到的INF就一定是最短的Queue<int[]> cells = new LinkedList<>();int rows = rooms.length, cols = rooms[0].length;for (int i = 0; i < rows; i++) {for (int j = 0; j < cols; j++) {if (rooms[i][j] == 0) {cells.offer(new int[] {i, j}); // 所有gate作为起点}}}while (!cells.isEmpty()) {int[] cell = cells.poll();int row = cell[0], col = cell[1];// 上下左右更新，同时入queueif (row > 0 && rooms[row - 1][col] == INF) {rooms[row - 1][col] = rooms[row][col] + 1;cells.offer(new int[] {row - 1, col});}if (row + 1 < rows && rooms[row + 1][col] == INF) {rooms[row + 1][col] = rooms[row][col] + 1;cells.offer(new int[] {row + 1, col});}if (col > 0 && rooms[row][col - 1] == INF) {rooms[row][col - 1] = rooms[row][col] + 1;cells.offer(new int[] {row, col - 1});}if (col + 1 < cols && rooms[row][col + 1] == INF) {rooms[row][col + 1] = rooms[row][col] + 1;cells.offer(new int[] {row, col + 1});}}}}
287. find-the-duplicate-number
- 给一个规模为
n + 1的数组，元素的值域为[1, n]，其中有一个元素是重复的，重复次数未知，求这个重复的数。原数组不可修改，时间复杂度必须小于O(N^2)，O(1)空间。 - ME：对于这种计数的题，一旦不给用extra space比如HashSet之类的，我就懵逼了。之前做的使用异或操作，但这题想了半天似乎找不出异或能怎么解决。陷入江局。。。
- TA：这个真的是逆天了，竟然能把这个找重复元素的问题转化成『找链表环的入口』的问题。答主的解释是，既然所有元素都只出现一次而某一个出现多次，而且元素的值域严格限制在数组规模以内，那就可以利用当前索引对应的值作为下一步访问的索引，一路访问，利用快慢指针（索引），当两个指针相遇后再从头来多一个指针，和慢指针同时继续后移，相遇即为环的入口。模仿出来是这样。当然前面这个方法比较难想到，但是另一个基于Binary Search思想的方法讲道理应该是能想出来的。既然元素值域为
[1, n]，那每次取中值mid，再O(n)扫一遍看看小于等于mid的元素数是否小于等于mid个（小于是因为不要求每个元素都出现），最终下界即为所求。模仿出来是这样。
288. unique-word-abbreviation
- 给一个String数组，对每个string求abbreviation，保留头尾两个字母，中间替换成长度。主要需要clarify什么叫unique，若其中已经存在这个abbr而src不同，则不唯一；但如果是同一个src形成的abbr，则视作唯一的。skip。
289. game-of-life
- 经典的GameOfLife问题，如果细胞周围有超过三个就死，少于两个也死，而死细胞周围恰好有三个的时候就可以复活。
- ME：in-place搞定，活细胞死则保持1、死细胞复活也保持0；活细胞活为2，死细胞死为-1，最后在遍历一波将大于1的值都减1、小于1的都加1。写出来是这样。
- TA：这个和我的也差不多吧，不过答主用的是2-bit的形式来区分状态的，第一位bit是新的状态，第二位bit是原本的状态，最后只要全部右移一位就把旧的状态抹去了。follow-up有个问题是说如果是无线大的棋盘怎么办，这个大神给出了解答.
290. word-pattern
- 给两个String，一个表示pattern，另一个是待匹配的由空格分隔的若干单词组成的字符串，判断是否匹配。
- ME：直接用HashMap搞定。写出来是这样。
- TA：这个略叼，第一次见Map可以不指定type混存的，大神答主同时把char和string作为key、索引作为value存入map。如果其中一个key重复了就会存入失败，这样就检测出不匹配了。
291. word-pattern-ii
- 给两个String，其中一个作为pattern如abab，另一个作为str，判断str是否符合给定的pattern。
- DFS暴力解法。每一个字符可能会映射到一个单词，因此需要一个map维护这种映射关系。从pattern出发，每一个字符可能映射1～整个str这么长，递归判断即可。123456789101112131415161718192021222324252627282930313233343536373839class Solution {public boolean wordPatternMatch(String pattern, String str) {Map<Character, String> char2WordMap = new HashMap<>();Set<String> wordSet = new HashSet<>();return checkMatch(pattern, 0, str, 0, char2WordMap, wordSet);}private boolean checkMatch(String pattern, int patternIndex, String str, int strIndex, Map<Character, String> char2WordMap, Set<String> wordSet) {if (patternIndex == pattern.length() && strIndex == str.length()) { // 同时到末尾，完美return true;}if (patternIndex == pattern.length() || strIndex == str.length()) { // 某一个已经到末尾，ggreturn false;}char c = pattern.charAt(patternIndex);if (char2WordMap.containsKey(c)) { // 该字符已经有映射，则判断在str中是否符合String word = char2WordMap.get(c);if (!str.startsWith(word, strIndex)) { // strIndex标记起始位置return false;}return checkMatch(pattern, patternIndex + 1, str, strIndex + word.length(), char2WordMap, wordSet);}// 若没有这个字符的映射，则需要遍历后续所有可能的情况，逐一判断for (int endIndex = strIndex + 1; endIndex <= str.length(); endIndex++) {String word = str.substring(strIndex, endIndex);if (wordSet.contains(word)) { // 防止a->xxx, b->xxx的情况continue;}char2WordMap.put(c, word);wordSet.add(word);if (checkMatch(pattern, patternIndex + 1, str, endIndex, char2WordMap, wordSet)) {return true;}wordSet.remove(word);char2WordMap.remove(c);}return false;}}
292. nim-game
- 两个人玩取石头的游戏，每次取1/2/3个，最后把石头取完的赢。给一个整数表示石头数，判断先取者是否能稳赢。
- ME：一开始还用了个DP数组，结果爆内存。后来改成模4一行搞定，摊手。
- TA：模4也可以用位操作表示成这样。其实也有人提出了DP的方法。
295. find-median-from-data-stream
- 在一个数字输入流中，随时调用函数返回当前的中位数。
- ME：要维护从小到大顺序，又要方便访问到中间的元素。。。陷入了江局。瞄了一眼讨论版，看见了要用到两个Heap，前一半和后一半，秒懂。不过Heap我一开始用的是TreeSet，但是这就不允许重复元素了。而PriorityQueue就没法自由访问最前和最后的元素了，再次陷入江局。再次偷看discuss，发现了
Collections.reverseOrder，再观察我的代码，对于前半部分我只需要访问最后一个数字，那就直接反过来，就这样过了。 - TA：我最开始看的是这个大神的，答主先直接都变成了Long类型来防止Integer的越界问题。每次直接add到large中，同时把large首位poll出来取个负数直接add到small中。若large元素少于small了，再把small首位（最小的负数即最大的正数）poll出来add到large中。取Medium的时候若large元素多于small，直接就取large的最小元素即可，否则就取large最小元素和small最小元素之负数的平均数。至于我是怎么想到要Collections.reverseOrder，就是看这个了，原po的答案有点绕。但他们的答案真的很简洁呀！第一遍我先不追求简洁，做出来、逻辑清晰就好。
297. serialize-and-deserialize-binary-tree
- LeetCode中对树的表示是通过数组的形式来做的，这题就是实现一下如何在树节点和它对应的字符串表示，空节点就是null。刚好之前东哥问了一个类似的问题，他还是自己想的，相当于他自己搞了一个Hard题出来？
- ME：题目规定了不能在类中用新的变量来记录state。所以就是BFS咯，写出来是这样。用类似于层级遍历的思路，维护两个Queue，一个存放有效的节点、一个存放Null的索引。根据上一层的有效节点数 * 2得到当前层的节点数，然后用for循环从0开始，如果匹配到Null的索引，就在字符串上拼上
,null，否则就正常从节点队列中取队首并拼接到字符串中，同时判断该节点的左右孩子是否为空，为空就把索引add到索引队列中。需要指出的是，for循环的变量和计算孩子索引所用的变量是不同的，每一层的『有效孩子节点数』需要单独用当前层级的『有效节点数』count记录，乘以2就得到了理论的孩子节点数了。 - TA：唔。。。事实上不需要严格按照LeetCode的字符串格式来表示树，所以这个方法就直接用
X代替了Null，没有前后的方括号，也没有处理最末位的逗号，直接用一个队列（原po用了Deque但这里用了Queue）存储经过split的各个字符串数字。递归地访问各个节点并将节点的值拼接到StringBuilder上；在恢复成树的时候，从队首取出字符、转为数字并新建一个节点出来，此时队列已经更改了，再调用buildTree就能构建左右孩子了。这样写简洁很多。
298. binary-tree-longest-consecutive-sequence
- 给一个二叉树，求其中parent-child路径最长的连续increasing的长度。
- 递归+全局变量，初始长度为1表示若以当前节点结束，可以增加长度为1，然后递归潜入下层child，如果发现当前节点和child可以形成increment则将递归返回的长度加1，返回给上层。12345678910111213141516171819202122class Solution {private int max = 0;public int longestConsecutive(TreeNode root) {helper(root);return max;}private int helper(TreeNode root) {if (root == null) {return 0;}int len = 1; // 以当前节点结束，则长度为1int left = helper(root.left), right = helper(root.right);if (root.left != null && root.left.val == root.val + 1) {len = left + 1; // 根据孩子节点val判断长度是否累加}if (root.right != null && root.right.val == root.val + 1) {len = Math.max(len, right + 1); // 取两个孩子长度的max}max = Math.max(max, len);return len;}}
299. bulls-and-cows
- 给两个String，secret表示预先确定的数字串，guess表示猜测的数字串。bull表示数字和位置完美匹配，cow表示数字是对的但是位置不对，二者不能重复计算。最后返回
xAyB的字符串。 - ME：首先判断是否完美匹配（bull），不完美匹配则用bucket记录，若在secret中出现则加加、在guess中出现则减减。cow的判断就是依赖这个bucket，如果在加的时候已经是负数，说明在guess中出现过；反之亦然。写出来是这样。
- TA：没啥了。
300. longest-increasing-subsequence
- 给一个无序数组，求其中最长升序子序列的长度。
- ME：题目基本的要求是时间复杂度在O(N^2)，所以一开始我就直接暴力搞了，固定一个值然后往后取比它大的，递归到最后再换一个值继续循环，结果超时。挠破头皮也没想出来，感觉会不会是DP？一看tag果然。。。
- TA：非常恼火连O(N^2)的方法都搞不出来，看了这个发现真的不难，DP的思路是固定子序列的最后一个元素，然后从最前方往后遍历判断『取当前子序列的最后一个元素』的时候，最长长度是多少。真的不难才对，模仿着写出来是这样。另外还有二分查找的方法，简直是五体投地螺旋服。维护一个数组tail，tail[i]表示当最长升序子序列的长度为i+1的时候，所有可能中最大元素的最小值。在二分查找中左界为0、右界为当前的tail已填充的size，求一个中点。从原数组中取元素x出来，若
tail[mid] < x，说明还能再往后找找，左界往后，否则就压缩右界。当前后两个指针相等时，直接更新当前位置的tail，然后若i已经到达末尾则更新size。真的。。。强！服！