春季四个月刷题

3.19 做题

388. Longest Absolute File Path. 这个题目的思路是这样，首先要把文件/文件夹的名字从给定字符串中提取出来，这时就需要使用“\n”来分割给定字符串、生成一个String Array；然后发现即使这么做以后，Array中的每一个String仍然有“\t”，那么这个“\t”就代表了当前文件/文件夹的级别，没有\t就说明是dir，有几个\t就说明这处在第几层；那么这里实际上是需要进行定位，对于每一个文件/文件夹都要定位它的父文件夹、父父文件夹这样，那这当然不是在这个Array中单纯往前找就可以找到的，因此这里使用了一个Stack作为辅助；Stack存储的，就是当前这个文件/文件夹所存在的目录路径的从一开始的整体长度，而stack的每一个元素都是一个文件/文件夹的绝对路径长度；维护stack的方法就是（stack有一个0元素作为最下面的元素），每一次遍历到一个array中的string后，先检查它拥有的tab个数，然后算出它的层级，如果这个string的层级比stack的size要小，那就说明现在这个string代表的文件/文件夹相对于stack存储的最上面的那个数字代表的文件/文件夹后退了，那么stack就应该持续地poll，也就是相当于后退的操作，知道stack的size和当前string的层级相同，这就意味着stack顶的数字代表的文件夹，就是当前string代表的文件/文件夹的父文件夹；那么这时只需要获取到当前string的长度，加上stack顶的长度，再减去当前string的tab数量，再加1（表示中间的/分隔符），就表示当前string代表的文件/文件夹的绝对路径长度了；那么如果当前string拥有"."的话，就说明这是个文件，那就可以和全局最大进行比较更新了

394. Decode String. 这是一个String的解码题，给定一个编码好的String，编码的方式就是这样k[encoded_string]，也就是比如可能给定的String是这样“3 [ 2 a b [ a b 3 [ a b c 4 [ a b ] ] 2 [ a ] a b c d ] 5 [ a b ] e f ] g h”，意思就是说，k代表后面的括号内圈定的字符串的重复次数，很容易理解；那么具体在做的时候，肯定是需要从左到右遍历给定字符串的每一个字符的，那么就会遇到四种情况，也就是数字、左括号、字符、右括号；当遇到数字时，就进行统计这个数字到底数值为多少即可，比如现在是325[ab]的话，扫描到了3，那么统计方式就应该是k = k * 10 + c - ‘0’；如果遇到的是字母的话，那当然就应该有一个StringBuilder去append这一串字母；问题在于左括号和右括号分别代表什么；左括号就代表，当前统计完毕了一个数字，而这个数字之前可能还会有已经构建完毕的StringBuilder，因为括号可能是一层套一层，从左到右并不一定是左右括号交替出现的，就比如这种情况“3 [ a b c 4 [ a b ] ] ”，从左到右的话，先是构建abc，然后计数了4，然后紧接着又出现了一个左括号；而左括号的后面，就需要开始构建新的StringBuilder，当染也有可能需要重新开始计数，这就比如这种情况“2 a b [ a b 3 [ a b c 4 [ a b ] ] 2 [ a ] a b c d ]”，第一个左括号后面首先要构建ab，然后计数3；那么遇到左括号的话，既然前后都可能会有构建StringBuilder的需求和计数的需求，那就应该把左括号之前构建好的StringBuilder和计数完毕的数字，各自放到一个Stack当中先保存下来，然后把全局的StringBuilder和全局的计数归零，用来构建左括号后面的需求；而如果遇到右括号的时候，简单来看就意味着一个StringBuilder构建完毕了，但同样也意味着，这组括号结束了而它前面的k应该生效了，也就是说decode string的过程中，现在应该根据k去重复构建这个String了；那么就比如对于这种情况来说“2 a b [ a b 3 [ a b c 4 [ a b ] ] 2 [ a ] a b c d ]”，当遇到的是4 [ a b ]的这个右括号，现在全局计数是0，而全局StringBuilder则是ab，而这组括号的左括号之前的4和abc都已经被放到各自的stack当中了，因此就应该从stack中把4和abc拿出来，首先根据4重复ab，然后再把重复获取到的string给append到abc的后面；也就是说遇到右括号，就说明现在应该完成一组构建了，也就是decode的过程；在这个题目中，需要维护的是一个全局的计数和全局的StringBuilder，全局计数其实无所谓，因此计数完毕以后，往后走肯定是直接左括号（否则就失去了计数的意义），因此计数完毕后肯定就直接加到stack当中了；但是对于全局StringBuilder来说，当构建完毕一个以后，它后面可能遇到的是数字，也可能遇到的是右括号；如果遇到数字的话，意味着马上要遇到左括号，那么也会驾到stack中；而如果遇到的是右括号，就意味着这个StringBuilder需要重复然后加到从stack中取出的StringBuilder后面，这时，当加完以后，这个全局的StringBuilder应该保存的就是这个加完的结果，那么这时再往后的话，对于一个右括号来说，后面可能是数字、可能是字母、也可能仍然是右括号；如果是数字的话，这个全局的StringBuilder也就不要动了，直接等着数字后面的左括号、然后一起加到stack中即可；如果是字母，那这组字母肯定不需要重复，那直接加到这个全局SB后面就可以；如果仍然是右括号的话，就说明有一组括号结束了，那么这个全局的StringBuilder就又要重复k次，然后加到stack中当前的最顶的StringBuilder后面；也就是说这个题目，遇到左括号加到stack中，遇到右括号从stack中拿出，就像是recursion的往下走和往上返的过程，因为括号都是完美对称的，所以一个全局的StringBuilder，按照上面的方式，肯定会最终存储所有decode后的String的

224. Basic Calculator. 这个题目和之前的decode string一样，要理解遍历给定String过程中，遇到什么样的字符需要做什么样的事情，同时要搞清楚全局维护的都应该是哪些变量；这里全局维护了一个sign、一个res、一个num、以及一个stack，res是全局结果，num是每一次统计到的数字、sign是当前应该计算的是+还是-；如果遇到数字，那么就更新num；如果遇到+或-的运算符号，那么就说明前面的数字扫描完了，扫描完了就要加到结果当中去，而当前的sign（注意不是现在扫描到的符号）正好就一定是扫描完的数字的前面的符号，因此用这个sign乘扫描完的数字，就可以加到结果中去了，然后再根据现在扫描到的符号更新sign，同时num归零；如果遇到括号的话就应该注意；如果是左括号，那么左括号前面一定是符号，也就是说现在的num已经归零，而sign存储着这个符号，res则存储着现在已经获取到的结果；而左括号后面一定是一个独立的表达式，也就是先是数字然后又是符号，那么sign现在存储的符号肯定不能直接作用于这个左括号后面的数字，而是作用于这组括号整体的，res也是，不能直接用sign和这个数字相乘；因此出现左括号就意味着要另起炉灶，重新开始计数num、获取sign、加和res了，那么现在已经有的sign和res就要放到stack当中进行存储，先放res再放sign，然后进行重制；那么左括号后面的数字和符号处理方式和之前的一样，接下来就会遇到右括号；遇到右括号就意味着这一组括号内部的表达式扫描完毕了，而右括号前面的一定是数字，因此这个num就应该乘它前面的sign然后加到res当中去，这样这组括号内部的表达式的值就处理完毕了，然后要做的就是把这个值也就是当前的res和这组括号之前的加起来，也就是说，要重新获取到这组括号之前的符号和res，也就是已经存储到stack当中的，因此先poll出来之前的sign，再poll出来之前的res，用prev_sign乘当前的res，再加到prev_res上即可；那么最后结束循环时，可能还是会遇到一个扫描的数字，因此在最后获取到num，再乘sign加到res即可，最后返回res

227. Basic Calculator II. 这个题目是给定一个表示四则运算的表达式String，没有括号；注意的就是calculator的符号滞后性，即每当扫描到一个符号的时候，当前的sign变量总是存储着前一个符号、而num变量总是存储着当前扫描到符号的前一个数字，滞后性就是说，每当扫描到一个符号，应该运算的总是前一个符号和前一个数字，运算完毕后，再把num归零、用sign记录当前符号；另外calculator的stack，这里应该存储的就是每次运算完毕的数字，也就是每次遇到符号时进行计算前一个数字和符号的结果需要offer到stack当中；具体来说，每当扫描到数字时，那就加到num里面去；每当扫描到符号时，就说明前面扫描的num已经构建完毕，同时当前的sign变量存储的是构建完毕的num之前的那个符号，那么如果是+或-的话，直接把当前构建的num乘1或-1，添加到stack中；而如果是*或/的话，考虑到运算优先级，这里就不仅仅需要当前的num和当前的sign了，还需要这个sign更前面的那个数字，也就是之前被offer到stack中的那个prev_num，因此就要把这个prev_num给poll出来，和当前的num进行*或/运算，获取到结果之后再offer进stack中；注意如果当前扫描到最后一个的时候，最后一个一定是num，而且前面还有一个符号sign，因此如果扫描的是最后一位，就需要和遇到符号的情况一起处理；因此如果遇到符号或者扫描到最后一位，就需要进行总结计算，把num和sign的结果放到stack当中；扫描完毕后，从stack中一个一个取出结果，相加即可，因为在之前遇到符号的时候，总是乘1或-1，或者如果有*或/的情况就会已经运算完毕，因此最后简单相加即可

385. Mini Parser. 这个题目本质上讲还是扫描String然后对不同情况下的字符进行分类讨论，而如果遇到括号一类的特殊字符，就需要往下走或向上返，并用一个stack来进行模拟；需要维护一个stack来存储往下走时上一层的NestedInteger，维护一个cur来保存当前层的NestedInteger，每当一层扫描完毕之后，当前的cur就应该加入到上一层的NestedInteger、也就是需要从stack中poll出来，并且返回上一层、也就是需要更新cur回上一层，因此这个题目和decode string以及basic calculator带括号的很相似；当遇到左括号的时候，说明要往下走一层，因此表示当前层的cur就需要被添加到stack当中去，然后cur归零准备下一层；当遇到右括号的时候，说明当前层的一个integer扫描完毕，需要被添加到当前层的cur当中，当谈也意味着这整个一层都扫描完毕了，要回归上一层，因此就从stack中poll出上一层的NestedInteger，然后把这一层的cur整体添加到上一层的NestedInteger当中，然后由于往上返了回到了上一层，cur记录的也就应该是变成上一层的了；当遇到逗号的时候，前面要么是右括号要么是数字，右括号的情况刚刚已经讨论过了，如果是数字的话，就简单给当前层的cur添加一个数字即可；这里注意如何扫描数字，使用的不再是num = num * 10 + c - '0'了，而是限定了一个left，left只是指向特殊符号的后面，然后和遍历的right进行圈定字符串而已，是另一种方式

5.4 做题

84. Largest Rectangle in Histogram. 这个题目要向左向右看，对于一个数组元素来说，它能够组成的面积最大矩形，肯定是从它开始往左走到最远处的不比它数值要小的位置，和从它开始往右走到最远处的不比它数值要小的位置，确定这两个位置以后乘该元素本身的数值，就可以通过长乘宽算出；最简单的方法就是遍历每一个数组元素，对每一个元素都向左向右进行循环遍历，找到最左最右位置，但是这样就很花费时间，因为出现了重复计算的问题：当某一个数组元素的最左位置计算出来以后，对于数组中这个元素右边的其他元素，如果这些其他元素能够往左走走到这个元素的位置，那么接下来就可以直接取该元素的最左位置即可，并不需要重复计算；因此这里采用的方式就是，进行两次遍历分别去寻找数组中每一个元素的最左位置和每一个元素的最右位置；第一次遍历寻找最左位置时，从左往右找，这样左边的元素就可以被先算出来，从而右边的元素计算时，就可以利用到左边已经算好的结果，即当index为left_most的数组元素比当前index为i的数组元素要大或等于的话，left_most = left[left_most]；对于第二次遍历寻找最有位置时也是如此

341. Flatten Nested List Iterator. 这个题目的意思是，给了一个List，这个List里面的元素可能是Integer也可能是List，而每个List内部仍然也可能是Integer也可能是List；这个特殊的List要实现的功能就是iterator，实现hasNext和next；next要获取的只能是Integer，因此hasNext就应该进行各种操作，从而把List进行剥皮、把内部的Integer找到，从而next能够进行获取；这里使用了stack，将给定的List从后往前放到stack当中，使用stack的原因就是对于当前取出来的元素，如果是List的话需要剥皮抽取出内部的Integer和内部List，然后再放入stack中去的话，就仍然可以保证相对的顺序；实现hasNext方法，首先判断当前stack是否为空，如果为空就false，如果不为空的话，再判断当前stack顶部是Integer还是List，如果是Integer就直接true，如果是List的话，就从stack顶取出这个List元素，从后往前进行遍历，将获取到的元素（可能是Integer也可能是List）放入stack中，这其实就完成了剥皮，但只是剥了一层皮；剥完一层皮以后，一个List当中可能只包含List而不直接包含Integer，那么就不能马上提供给next方法进行元素获取，因此就需要继续剥皮，直到有Integer出现才行；所以接下来的步骤就是调用recursion方法，再进行一次hasNext，实际上也就是对当前取出的第一个List剥完一层皮之后的stack进行的重复操作；那么对于这第一个List会一直进行剥皮，直到把这个List范围中的Integer剥出来，或者把这个List剥完发现什么都没有，然后再去剥下一个List；这个题目一定要注意顺序，由于是一个stack，那么从stack中拿出的List一定要倒序循环，才能保证相对位置

263. Ugly Number. 验证一个数字是否只有2、3、5这三个因数，方法就是：由于每一个数字都是可以进行因子分解的，而乘法又是满足交换律的，因此如果一个数字只有2、3、5这三个因数，那么进行因子分解以后一定是2 * 2 * 2 * ... * 3 * 3 * ... * 5 * 5 * ...，所以只需要对这个数字进行一直除2、一直除3、一直除5，然后看看最后剩下的是不是1就可以了

264. Ugly Number II. 这个题目的问题在于，每一个ugly都不是和它前一个ugly有直接联系的，所以不好使用recursion的方法；从1开始，可以乘2、乘3、乘5，但2、3、5中间还有一个4，其因子为2 * 2也是一个ugly；不过不管怎样，ugly总是由另一个ugly通过乘2、3、5来实现的，那么反过来从第一个ugly也就是1开始，1乘2、3、5得到了三个ugly，然后这三个ugly也都要分别乘2、3、5再得到9个ugly；但是如果需要按照顺序的话，每次就只能得到一个ugly，比如从1开始，乘2得到下一个ugly，那么接下来第三个ugly，就可以从1乘3、1乘5、2乘2、2乘3、2乘5当中进行挑选，不过这样随着ugly数量的增加每一次循环都要比较非常多个潜在的解；那么进一步简化的方法就是，每次只去比较一部分结果，比如1乘3、1乘5、2乘2这三个，这是因为对于2、3、5这三个数，每一个ugly都总是要去乘一下，所以就可以使用3个index，分别表示现在要去乘2、3、5的ugly的index，因为最小值总是从这三个ugly里面挑选；比如对于1乘3、1乘5、2乘2这三个，index3和index5都是0，而index2已经是1了；就这样去构建数组，直到n为止

313. Super Ugly Number. 这个题目和ugly number II完全一样，只不过这里对ugly的因子进行了拓展，不再只是2、3、5而是有一个数组的数，那么使用相同的思路，对数组提供的每一个因子都维护一个index，然后进行循环找到最小并把对应的index++即可

5.5 做题

138. Copy List with Random Pointer. 这个题目要去复制一个链表，而这个链表不仅有next指针，还有一个random指针，这就意味着不能用单纯的顺序遍历的方式，要换一种思路；对于每一个原链表的节点，都创建一个值相同的新节点与其对应起来，而它们的对应关系就要使用一个Map表示，key为原节点，value为新节点，只不过建立map的时候新节点并没有对next和random指针进行赋值；在map建立完毕、新旧节点对应好以后，就需要进行新节点的next和random指派了，这个操作其实很简单，把key和value取出来，value的next就是key的next的value，同理value的random就是key的random的value；这个过程完毕后获取head对应在map当中的value即可

373. Find K Pairs with Smallest Sums. 这个题目要使用PriorityQueue，要找到k个最小的pairs，最一般的方法就是全部都offer到PQ当中然后往外面poll出k个；这样做的缺点就是无视了给定数据已经排序好的事实，因为利用给定数据的部分排序，可以简化往PQ中offer和poll的操作；首先往PQ中offer一些初始值，然后poll出来一个再offer进来一个，这里要注意的是，poll出来的肯定会是当前的最小值，但是offer进去的一定不能是随机的，因为每次poll出来的都应该不仅是当前PQ中的最小值，还应该是所有可能结果的全局最小值；那么就选择两个数组的各自第一个元素的组合作为第一个要poll出来的，因此这个最小元素就一定要作为初始值放到PQ中；那么剩下的PQ初始值，当然不能要求是全局最小的，否则就没必要使用PQ了，但也要要求是局部最小的，所以就应该offer第一个数组的第一个元素、和第二个数组的所有元素的组合；在准备好以后就可以正式进行offer和poll了，poll出来的第一个组合一定是全局最小，但是接下来要保证的就是如何offer下一个、才能保证下一次poll出来的一定也是全局最小的；由于当前PQ中已经有了第一个数组的第一个元素、和第二个数组的所有元素的组合，因此肯定也就有了第一个数组的第一个元素、和第二个数组的第二个元素，当然这个第二个数组的第二个元素可能本身就会很大使得它和第一个数组的第一个元素的组合不是最小值；在这种情况下，最小值的可能就要从第一个数组的元素中寻找了，寻找第一个数组的剩下的元素和第二个数组的第一个元素的组合，而这就是应该offer到PQ当中去的；所以应该被offer的下一个组合，就应该是第一个数组的第二个元素、和第二个数组的第一个元素的组合；推广一下就是，每一次被offer进去的组合，都应该是这一次被poll出来的组合、其第一个数组元素往后推、而第二个数组元素不变的组合，这样的话就至少可以保证offer进去的组合、和已经存在于PQ中的组合，可以涵盖全局最小了；因此这个题目对于两个数组来说，第一个数组往后走是因为主动offer的原因，而第二个数组往后走则是被动poll的原因

318. Maximum Product of Word Lengths. 这个题目给了一个字符串数组，要求在没有相同字符的情况下、找出其长度乘积最大的那两个字符串；给定一个数组要找出两个不同元素的数值乘积最大，就肯定要进行一个二重的for循环，找出所有可能的结果然后进行比较，那么在这个题目里两个不同的元素变成了两个字符串的长度，本质上还是一样；那么如何比较两个字符串没有相同的字符，最一般的办法是对两个字符串进行双重循环，对其中一个字符串的每一个字符都去比较另一个字符串的所有字符，检查是否有一样的，那么如果这个题目也采用这个办法就相当于二重循环内部又来了一层二重循环，很麻烦；在此基础上的优化方案就可以是，对于其中一个字符串建立一个Set，让这个Set里存储这个字符串的所有字符，那么对于另一个字符串的每一个字符，都可以用O(1)的时间检查到它到底存不存在于这个Set内部，这样就相当于用O(n)一重循环即可；那么有没有一个方法可以用O(1)的时间来比较两个字符串的是否没有相同字符，以上O(n)是把一个字符串变成了Set而另一个不变，那么可不可以把两个字符串都变成Set，然后Set和Set之间有没有直接比较的方法；其实是没有的，因此就要考虑用一些特殊的方法，就是使用bit；bit可以在一定程度上起到Set的作用，比如每一个字符串本质上都是26个字母的排列，那么使用bit的话就可以把字符串内出现的26个字母都表示在一个二进制上面，对于字符串出现的每一个字母都根据和'a'字符的距离标明1，比如如果出现了a那么二进制的右边第一位就是1，如果出现了d那么二进制的右边第4位就是1；通过这种方式去表示一个字符串，也就是对于每一个二进制bit[i]，都有bit[i] = bit[i] | 1 << (s.charAt(j) - 'a')，j就是对当前字符串的所有字符位置遍历，而i则是对当前字符串数组的所有字符串进行操作，减去a表示偏移量，而1<<则表示对于二进制的1进行对应偏移量的左移，而|的逻辑或操作则表示将当前这一位二进制变成1；在拥有则个bit数组后，如果希望比较任意两个字符串是否有公共字符的话，只需要bit[i] & bit[j]即可，因为&的逻辑与操作就表示只有两个位置都是1结果才会是1，那么如果bit[i] & bit[j]是0的话，就说明没有任何两个位置同时为1，也就是说没有任何两个位置是相同的，也就是说这两个字符串没有公共字符；所以这个题目，只需要在一开始建立好这个bit数组，然后就可以在二重循环内用O(1)的时间比较出两个字符串是否有公共字符了

133. Clone Graph. 这个题目需要copy一个图，实际上就是图的遍历，在遍历的过程中进行图的copy；既然是copy，那么就和之前的clone list with random node一样，需要建立起来一个Map来维护原有node和复制node之间一一对应的关系，而图的遍历则应该使用BFS和DFS两种方式；BFS的方式就是，对于这个图的起始node，首先放到Queue当中，同时在Map中建立一个当前起始node为key、新创建的复制node为value的关系；接下来通过使用Queue来进行图的遍历，在遍历的过程中完成node的复制；遍历的过程很简单，只要Queue不为空，那么首先把Queue最前面的node给poll出来，然后对这个node的可能generate出来的所有相邻node都重新offer到Queue里面去；然后就是复制，复制要注意，并不是说每当generate出来一个新的相邻node就仅仅在Map中put进去并new一个复制的新node就足够了，因为每一个被新复制的node，它除了原有node的值以外还要继承原有node的邻接node的关系；这里对邻接node关系的复制和clone list with random node的题目就很类似，就当前的这个被poll出来的原始node来说，它所对应的复制node，其邻接关系的继承就应该在该原始node去generate邻接node时去实现：对于每一个原始node的邻接node，复制node都应该去Map当中寻找，该邻接node所对应的复制node，而这个过程就应该在每一个被generate出来的邻接node、在Map中建立复制关系之后完成（否则在Map中找不到邻接node的复制node）；也就是原始的复制的邻接，等于原始的邻接的复制：map.get(origin).neighbors.add(map.get(neighbor))；而DFS的方法就是，同样维护一个上面的Map，而每一次递归过程中，都是对每一个node进行操作：对于当前的原始node，如果在Map当中已经有对应的复制node，那么直接返回，否则的话在Map中创建一个原始node和新的复制node的关系，并且对于这个原始node的每一个邻接node进行循环，那么原始node的复制node的邻接node，就应该等于原始node的邻接node的复制node；这里就要直到当前recursion function的功能了，这个recursion的输入是原始node，而最终返回的则应该是该原始node的复制node，而这个for循环的功能，正是要把原始node的邻接node，复制给复制node的邻接node，当然就应该用到recursion；最后这个recursion要返回当前参数原始node的复制node

399. Evaluate Division. 这个题目本质上是个图的题目，分两个步骤：构建Graph、遍历Graph；这个题目给出的是equations和values，因此对于每一个equations当中的未知数，都有两种关系：和另一个未知数的关系、和数值的关系；根据这两层关系构建两张图，一张图是未知数和未知数的关系图，另一张图是未知数和数值的关系（严格来说这不是图）；对于未知数和未知数的关系图，使用Map来表示，key为等式中的一个未知数，而value则为key未知数所出现的所有等式中的所有另一个未知数的List；对于未知数和数值的关系同样是这样，key是等式中的一个未知数，value是key未知数所出现的所有等式的所有数值的List；构建完毕图之后，就可以进行图的遍历了，思路就是对于每一个query，从其中一个未知数出发到另一个未知数为止，在未知数和未知数的关系图中进行查找，看看能否通过图的遍历从一个未知数找到另一个未知数，具体遍历的方式就是DFS，即从一个未知数start出发，对start在Map中对应的另一个未知数List进行遍历，对于遍历到的每一个未知数都进行recursion，其目标未知数仍然为原始目标未知数，但起始未知数就变成了当前的这个被遍历到的未知数；而在图的遍历过程中要维护一个数值，这个数值在每一次遍历的时候都需要乘上当前起始未知数在数值关系图中所对应的value，也就是在recursion当中，新乘上的value就应该和当前的起始未知数处在同一个给定等式当中，这可以通过在Map中的List取同样的index得到

5.6 做题

310. Minimum Height Trees. 这个题目的意思是，给出一个本质为树的图，在其中选择一个节点为root，使得这个树拥有最短的高度；这个题目的思路就是，首先构建这个图，同时构建每一个节点node的degree；构建图的方法就是使用HashMap，key为节点，value则为该节点的相邻节点的List；而记录degree的同样使用一个HashMap，key为每个节点，value则为该节点的degree也就是相邻节点个数；构建图的过程是根据给定的edges二维数组进行的；当构建图完毕之后，就应该一步一步寻找root节点，这里注意root节点并不是degree最大的，而应该是“最深”的节点；因此方法就是，对于这个图，每一次去掉叶子节点，也就是在degree的HashMap中value为1的节点，而去掉它们以后，去图的HashMap中找到这些被去掉的节点的相邻节点，对于这些相邻节点来说由于该叶子节点被去掉了，那么这些节点的degree就应该减1，所以在degree的HashMap要进行更新；而这个过程自然就会出现新的叶子节点、即degree为1的节点；这样一次又一次去掉叶子节点、更新degree后，最后一个被去掉的点、也就是最深的点就一定是root节点了；因此使用BFS的方法，Queue的初始就是最初的叶子节点，而每一次从Queue中expand出来的就应该是当前Queue中的叶子节点，而每次generate出来再offer进Queue的就应该是那些因为去掉了叶子节点、degree减1、而变成新的叶子节点的节点

149. Max Points on a Line. 这个题目的思路其实很直观，给定若干点，那么这些点两两相连就是它们可以组成的直线，一般来说可以组成n(n-1)条直线，但是由于有的点可能正好出现在了已经组成的直线上面，这样就会有三个点、四个点都在一条直线上，这就有了本题，找出一条直线上出现最多的点的数量；这里就应该使用一个Map，key就是斜率，而value就是这个斜率上的点的数量；然后对给定的若干个点进行二重循环，对于每一对点，都去算它们的斜率，然后看看HashMap当中是否已经存在了对应斜率，如果有的话那么就说明这条直线上又多了点；那么到底多了几个点，这里就需要进行约分，对于每一对点的坐标之差，都要除以这两个点的最大公约数，然后进行一个字符串的拼接，再作为key，从而使得最后记录在HashMap的斜率是唯一的；并且每一次第一重循环时都要清空map，这样才能够不进行重复的统计；也就是说对于每一个点都进行一次讨论，看看从这个点出发的所有可能的直线能最多经过其他多少个点，然后更新最大值，然后到了另一个点的时候再重新开始

5.7 刷题

86. Partition List. 这个题目要使用DummyNode，使用两个DummyNode分别表示大的链表和小的链表，然后再分别指派一个cur；随着head在原链表上的移动，cur根据当前节点和x的比较去检查是否需要使用next连接上，如果需要就进行next连接并且对应cur和head同时往后走；循环结束后不要忘了把cur进行切断，然后两个分链表要相连，即一个dummy和另一个的cur连接

23. Merge k Sorted Lists. 这个题目用PriorityQueue来做，最朴素的方法当然就是对于给定的这些链表，把这些链表上的每一个节点的值都放进PQ当中，然后再全部从PQ当中poll出来，挨个连接到新的链表的后面，这样做的话肯定能做出来，但是就没有使用到给定的条件，也就是这些链表本身都是排好序的；那么对此对于链表来说，每一个节点除了内部的value以外还有next，所以掌握了头节点就相当于掌握了整个链表；所以在PQ建立完毕以后，首先把所有链表的头节点offer到PQ当中，然后就可以进行poll了，因为这里实际上可以保证，poll出来的肯定就是最小值，因为本身PQ中存在的就一定包含了全局最小，这就利用了sorted List的性质；那么每当poll出来一个以后，要保证下一次poll出来的仍然是全局最小，这就要看offer进哪一个节点了，所以offer进去的就一定是刚刚poll出来的节点的next，才能保证当前PQ中仍然拥有着全局最小值，这是因为PQ中仍然保存了当前所有链表的头节点；当利用了给定链表们的排序性质以后，PQ中的数据就小了，那么每一次poll和offer的时间自然就缩短了

147. Insertion Sort List. 这个题目就是insert sort在LinkedList上面的实现，插入排序的意思就是，对于当前数据结构中未排序部分的第一个元素，都去在已经排序完毕的那部分当中，从前往后进行比较，当发现该元素比前一个元素大、比后一个元素小的时候，就可以进行插入了；当然并不是所有情况下，所有元素都需要进行从前往后的插入，这里就可以进行优化；当插入完毕前一个的时候，对于当前的这个元素，如果它本身就应该在这里（即就算从头到尾遍历比较也还是会插入到已排序部分的最末端），那么就可以不用再重新比较了，通过这种机制进行优化

5.7 刷题

221. Maximal Square. 这个2维DP的题目，需要一个二维DP矩阵；这个二维DP矩阵需要比给定的矩阵大一圈，即多一行多一列，并且在这多出来的第0行和第0列初始值应该是0；该矩阵每一个点dp[i][j]的物理意义应该是，如果给定矩阵的当前位置是1的话，那么这个点和与它相邻的左、上、左上三个点进行组合，能够组成的最大正方形的边长是多少；这里的实质意义是，如果当前的矩阵点是1，那么它本身就肯定是一个边长为1、面积为1的正方形；这时为了检查其他的可能性，即这个点是否可以和其他点构成更大的正方形，就需要检查它在DP中相邻的，也就是左、上、左上这三个点；这里可以这样理解，当dp[i][j] = 1时，如果dp[i][j - 1] = 5，dp[i - 1][j] = 3，dp[i - 1][j - 1] = 7，这就意味着(i, j)这个点，它左边的点可以组成一个边长为5的正方形、上边的点可以组成一个边长为3的正方形、左上方的点可以组成一个边长为7的正方形，那么就需要取最小再加上(i, j)这个点使得可以组成边长为4的正方形，这是显然的因为上边的点是最小的，而左边和左上方都可以满足它；因此(i, j)的物理意义就是，以该点为右下点，向左向上最多可以组成边长为多少的正方形；induction rule就应该是刚刚所描述的那样，而base case也就是第0行和第0列，因为它们本身就是不存在的，它们的意义就在于为了对给定矩阵的最上面一行和最左边一列使用induction rule，才可以使得对于这些点来说，它们本身是1的话那就是1，否则就是0

85. Maximal Rectangle. 这个题目的思路借用了之前的一个求直方图内最大矩形的题目；对于给定的一个矩阵来说，要进行一行一行的扫描，扫描完毕每一行之后，都要建立其一个height数组，该数组的含义是将当前扫描行作为直方图的最底部，往上看看能够组成怎样的直方图，当然由于给定的是一个0、1相间的矩形，而直方图不能把0算进去，因此每当扫描一行的时候，如果遇到1就说明这个最底部可以构成直方图，那么就把height数组的对应位置+1表示增高了，如果遇到0就说明这里空了，那么height数组之前加过的就要全部放弃了；在对这一行进行完毕扫描后，就构建起了以这一行为底部、往上连续的直方图了，那么对于这个直方图能够组成的最大矩形面积，当然就直接调用上一题目的方法就可以了；那么给定矩阵的每一行其实都可以组成这样的直方图，那么只需要取最大结果的那一行就可以了；因此总结一下，这个题目就是扫描、构建height、求height的最大、对于所有行取最大

363. Max Sum of Rectangle No Larger Than K. 这个题目本质上来说可以归结为1维的形式：如何在一个给定数组中找到一个subarray，使得该subarray的sum是不大于给定target的最大值；因为这个题目我已经按照一个二重循环的方式将其归结为以上问题，如果以上问题能够凭借O(n)的时间做出来的话整体就是O(n^3)的时间，效果应该会很不错；归结的方法就是，首先求出来给定矩阵的prefix，这里我选择了按行prefix，然后任意选择两行即可求出这两行之前的元素和，按照每一列的方式可以组成一个sum数组，而sum数组就正是1维形式的输入

198. House Robber. 这个题目就是对于每一个房子来说，如果偷这个房子的话，那就不能偷前一个，因此就算再前一个的结果加上这个房子的钱；如果不偷的话就还是前一个房子的结果

213. House Robber II. 这个题目和上一个唯一不同的就是首位连接了，因此如果第一个偷，那么最后一个就不偷；如果最后一个偷，那么第一个就不偷；这实际上就相当于两种情况，一个是从第一个到倒数第二个，另一个是从第二个到倒数第一个，对这两个subArray进行分别求解然后比较最大即可

5.8 做题

91. Decode Ways. 这个题目使用DP来做；给定了一个数字字符串，从1到26每一个都可以对应一个英文字母，看看这个数组能够有多少种组成英文字母的方式；这个问题就在于，一位数能够组成应为字母，两位数也能组成英文字母，所以对于任意一个位置的数字，都可能有两种方式：它本身作为一个数字组成一个字母，它和它前一个字母这两个数字组成一个字母；比如"49020513"这个字符串，对于最后一位的3来说，它本身代表着英文字母C，因此这个字符串就相当于是"4902051C"，当然3和前面的1组成的13代表了英文字母M，因此这个字符串就相当于是"490205M"；因此"49020513"这个字符串的组成方式，就相当于"4902051"子串的组成方式加上"490205"子串的组成方式，因为后面的C或M已经确定了；所以对于每一个位置来说，首先检查当前位置本身代表的数字是否在1到9之间，如果是就相当于有了第一种方式，在检查当前位置和前一个位置代表的数字是否在10到26之间，如果是就相当于有了第二种方式；对于这两种方式加起来就是当前位置上的结果，从而能够组成DP数组

10. Regular Expression Matching. 这是字符串匹配的二维DP题目，题目所给出的一个是原始字符串s，一个是pattern字符串p，p除了正常字母以外还包括星号和点号；基本的思路就是使用DP，用二维DP的dp[j]去表示，s字符串的前i个字符，是否能够和p字符串的前j个字符进行匹配；初始化DP的时候，由于对s的前0个字符，p的前0个字符一定也能匹配，但是p的前j个字符，如果通过星号的辅助，比如这种：a*r*v*q*f*，每隔一个字母加一个星号的，那么星号就可以作为0，这样和前面的字母都抵消掉，当然就可以和s的前0个字符进行匹配；具体来说就是，如果p的第j个字符是星号，而且如果p的前j-2个字符可以和s的前0个字符匹配的话，那么不管p的第j-1个字符是啥，都可以被星号抵消，当然就可以完成匹配；初始化完毕以后就可以进行DP二维数组的构建了，对于s的前i个字符和j的前j个字符dp[j]，如果s的i和p的j本身就相同，那么当然在这个位置上可以进行匹配，所以dp[j]就取决于s的前i-1和p的前j-1能够匹配；如果p的j本身就是点符号，那么由于点符号可以和任意字符进行匹配，当然就可以和s的i匹配，因此这时和上面一样，dp[j]取决于s的前i-1和p的前j-1能够匹配；如果p的j是一个星号，那么就要进行讨论；如果s的第i个和p的第j-1个本身是同样的字符，或者p的第j-1个本身是点号可以任意匹配，那么当然p在第j个位置上的星号就可以进行任意的取值，而星号取值的不同也决定了dp[j]取决于什么样的情况：如果这时星号取0，就说明尽管s的第i个和p的第j-1个可以匹配，由于星号取0那么就也干脆不匹配了，所以dp[j]就取决于s的前i个和p的前j-2个是否能够匹配；如果星号取1，那么就说明既然s的第i个和p的第j-1个可以匹配，那么星号就不做任何操作，dp[j]就取决于s的前i-1个和p的前j-2个是否能够匹配；如果星号取任意值，就说明这时p的前j个不仅可以和s的前i个匹配，还可以进一步表示更多的该字符，所以dp[j]就取决于s的前i-1个和p的前j个能够匹配；另一方面，如果如果s的第i个和p的第j-1个不是同样的字符，并且p的第j-1个本身是点号可以任意匹配，那么p在第j个位置上的星号，就只能是0，从而可以抵消掉p在第j-1上的字符的不同，这样dp[j]就取决于s的前i个和p的前j-2个是否能够匹配

44. Wildcard Matching. 这个题目和上一个题一样，用二维DP数组来构建，看看s的前i个和p的前j个能否进行匹配；当然这两个题目都要注意的一点是，二维DP数组应该比s和p的长度大一圈，来表示s的前0个和p的前0个；初始化情况就是，p的前j个是否能够和s的前0个进行匹配，那么肯定p这时只能取星号，星号可以匹配空字符串和任意长度的字符串，而？只能匹配单个字符，所以在s的前0个匹配，p的星号只能取连续0，并且不能像前一个题目一样进行抵消，只要有一个不是星号，那么就一定不能匹配；构建DP时，如果s的第i和个p的第j个字符相同，或者p的第j个是问号，那么在这个位置上肯定能够匹配，因此这时dp[j]取决于s的前i个和p的前j个；否则，如果p的第j个是星号的话，由于星号可以表示空、单个字符、多个字符，那么对于这三种情况，如果星号为空，那么就只能靠p的前j-1个字符去对s的前i个进行匹配了，如果星号为单个，那么这时星号的作用就和问好的作用一样了，如果星号为多个，那么这个星号不仅可以在这里起作用，还可以接着用，因此还可以匹配s的前i-1个；如果p不属于以上的任何一种情况的话，由于这里的问号和星号都没有抵消的作用，那么显然s的前i个和p的前j个就不能进行匹配

45. Jump Game II. 这个题目主要是BFS，但是可以使用Greedy的方法进行简化；BFS就是，初始在第0个index位置，每次都把Queue当前保存的index给poll出来；对于每一个poll出来的index，首先检查从它开始跳它对应的value的步数能不能到底，如果能的话直接返回步数，否则进行generate；generate的就是从这个index开始最远能够跳到的位置的index，从远到近offer到Queue当中，为了保证效率，不重复offer到Queue中，还应该加一层Set去dedup；另一个方法是Greedy，从数组的头部开始遍历，每次检查当前能够跳到的最远位置以及当前的最远位置，每次基于当前的index和value来检查是否要更新能够跳到的最远位置；而一旦遍历到了当前的最远位置时，就说明完成了一次跳跃，那么jump计数并且将当前的最远位置更新为当前能够跳到的最远位置

199. Binary Tree Right Side View. 这个题目这次使用的是recursion的方法，右侧优先的preorder，preorder要做的就是验证，如果当前结果集的size正好等于当前树高的话（从0开始），那么就添加；这是因为，右侧优先的preorder，总是可以保证只要树高增加一层，那么第一个遍历到的就一定是最右的节点；这时由于树高增加，结果集的size就正好和树高相同，而当添加完毕以后，结果集的size+1，这一层的其他节点树高不变，自然就不会加到结果集了
[i][i][i][i][i][i][i][/i][/i][/i][/i][/i][/i][/i]

5.13 做题

230. Kth Smallest Element in a BST. 题目要求找出BST中第k小的元素，由于是BST并且要找最小，所以就需要对其进行inorder顺序的打印，然后找到第k次遍历到的节点即可；inorder遍历一个树有iteration和recursion两种方式，iteration的方式就是使用一个stack和helper节点，helper节点存储下一次要被遍历的节点，首先一路往左走并且将每次helper经过的节点都offer到stack当中，直到helper为空说明扎到底了，然后从stack当中poll出来一个节点就算是当前遍历的节点，对于本题来说每次遍历一个节点都应该进行计数，如果当前计数正好等于k说明该节点就是第k小的节点；recursion的方式就是在对left和对right进行recursion之间进行计数，如果计数恰好等于k，也就说明当前节点是第k小的，那么记录下来该节点，在recursion结束后返回即可

98. Validate Binary Search Tree. 这个题目给出一个Tree的root，需要验证这是否是一个BST；BST的性质就是对于每一个节点来说，它都要大于它的左子节点并且小于它的右子节点，从root出发，首先root本身是没有大小限制的，然后对于root的左子节点，其值可以尽量小，但不能超过root本身的值，对于root的右子节点来说，其值可以尽量大，但不能小于root本身的值；另一方面，对于一个root来说，不仅它的左子节点要小于它、右子节点要大于它，它的整个左子树都应该小于它、整个右子树都应该大于它，因此在recursion中应该传递上下边界：对于一个节点的左子节点，其下边界应该传递，上边界应该是当前节点的值；对于一个节点的右子节点，其上边界应该传递，下边界应该是当前节点的值；另一方面对于传递过来的上下边界的值，应该使用Integer数据类型而非int，这是为了避免临界值的情况；如果使用iteration的方法，需要考虑的问题就比较简单：每一次都记录着上一次被遍历到（被stack给poll出来的节点），然后每次poll出来当前节点时，都使用上一次poll出来的prev节点进行值的比较，看看是否违反了规则，这是因为BST的inorder遍历，总是从小到大的

235. Lowest Common Ancestor of a Binary Search Tree. 这个题目要利用BST的性质：如果当前root节点的值正好大于p节点的值并且小于q节点的值，就说明root是p、q节点的LCA；这是因为对于p和q节点来说，root的值要么同时小于它们、要么同时大于它们、要么位于它们之间，对于前面的两种情况，在BST中只能寿命p、前两节点同时在root节点的右子树或者左子树，那么root在这种情况下肯定不会是LCA，因此在第三种情况下root就应该是LCA了：因为从最底部的root开始找，第一个出现p小于root小于q的情况一定是LCA，这时p出现在root的左子树、q出现在root的右子树，如果再往深处找，无论root去哪一个子树，都一定不是另一个节点的Ancestor了

236. Lowest Common Ancestor of a Binary Tree. 在一个一般的Binary Tree中寻找LCA，需要进行分类讨论：首先对左子树和右子树进行recursion，获取到的要么是p、q两节点，要么是已经找到的LCA节点，要么是空节点；如果获取到的同时为p、q两节点，那么当前root就是LCA；如果只有一个获取到了p、q节点而另一个为空（肯定为空），那么检查当前root本身是否为p、q节点，如果是就说明档期root就是LCA，否则返回找到的这个p、q节点；如果两者都没有获取到p、q节点但两者中有一个不为空，就说明这个不为空的就是LCA；最后检查当前root是否为p、q节点，如果是则返回，否则返回空

108. Convert Sorted Array to Binary Search Tree. 这个题目需要使用recursion进行构建，因为是根据有序数组构建BST，所以只需要考虑到每次recursion所需要构建的对应数组范围即可；对于每一个recursion来说，都使用数组的mid位置元素构建当前子树的root节点，并且使用数组左半边进行recursion构建左子树、数组右半边进行recursion构建右子树，然后让左右子树拼接到root节点并返回即可

5.20 做题

109. Convert Sorted List to Binary Search Tree. 这个题目同样是根据一个有序序列创建BST，但是因为该有序序列不是数组而是LinkedList，因此不能立刻找到中点、因此不能立刻创建root节点；recursion的方法仍然一样，给定一个start和一个end的位置，recursion的作用就是将这个范围内的有序序列进行创建成BST；那么首先在有了start和end以后，就应该找到这个范围的中点，LinkedList的中点方法就是快慢双指针，直到fast或者fast的next为空为止，但是这里注意终止条件不总是为空，因为这里找的是确定范围的LinkedList的中点，那么终止条件就应该是fast或者fast的next到达这个范围的end；当用slow指针找到中点之后，就可以首先构建起root节点，然后对于root之前的部分、即start到slow，和root之后的部分、即slow的next到end，分别进行recursion操作，形成了root节点的left节点和right节点，最终构建起了一整棵BST

173. Binary Search Tree Iterator. 这个题目本质上仍然是对一个BST进行inoorder顺序的iteration方法，只不过把一段完成的可以进行完全部遍历打印的BST、分解成了hasNext和next这种方法，从而可以控制打印的判断和只打印下一个，这就相当于要在完全理解如何进行BST的inorder的iteration方法的基础上，看看完整的代码到底哪一个部分是负责哪一个功能的；hasNext就是判断是否当前BST还有下一个元素可以打印，对应到BST的inorder遍历，其实就是while循环的终止条件；next就是获取到下一个元素，其实就是while循环的循环体；而构造方法实际上就是while循环之前的那些、初始化Stack和next节点的这些步骤

297. Serialize and Deserialize Binary Tree. 这个题目的先将一棵树序列化成String，然后在对序列化后的String进行反序列化回到原来的这棵树上；首先对于一棵树来说，序列化其实就是打印成为一个String，因此有三种方式可以进行遍历打印；这里采用的是preorder的方式，因为这种方式打印出来的String，最靠前的永远是root的打印结果；对于打印完毕后的String，首先获取到第一个元素，由于这是preorder所以第一个元素就是root，接下来直接对剩下的元素进行recursion的调用，分别建立起root的left和right子节点就可以了；而对于preorder建立起来的String不需要确定left的范围和right的范围，因为preorder的性质是首先一路扎到底并且顺次打印；另外要注意使用一个Stack作为辅助，每构建一个树节点都要向stack当中去poll出来一个元素，如果poll出来的是代表NULL的string那就返回null，否则建立root

5.21 做题

121. Best Time to Buy and Sell Stock. 这个题目给定了一个时期的价格数组，每一个时期可以买入也可以卖出，看看什么时候买入什么时候卖出的利润最高；因此就可以设置一个当前买入价和当前利润，对于买入价来说，如果当前买入价大于当前价格，就说明可以用更少的钱进行买入，所以对当前买入价进行更新；而如果当前价格大于当前买入价的话，就说明在这个时间卖出的话一定可以赚取利润，因此就要和当前利润进行比较，看看是否在这个时间卖出的利润更大；这里注意有一个时间的过程，同一个时间只能干一件事情，所以对于同一个时间的价格来说，要么在这个时间买入、要么在这个时间卖出，而买入只可能发生在当前价格比当前买入价更低的情况，卖出则只可能发生在当前买入价比当前价格更高的情况；本质上是一个DP的题目，dp[i]表示当前利润，dp[0]一定为0，就和初始的最大利润一样，dp[i]的induction rule就是，如果当前价格高于当前买入价的话，就应该和dp[i - 1]即当前最大利润进行比较

122. Best Time to Buy and Sell Stock II. 这个题目使用的方法就是，遍历整个prices数组，如果发现当前的prices比前一次的prices高，就可以将这个价格的差值加上，就相当于前面一次买入、后面一次卖出；当然事实上可能出现这种情况，即当前的price比前一次的高、而前一次的price又比更前一次的高，这当然不可能出现两次买入和卖出，而且如果用上面的这种方法，就相当于前前一次买入、前一次卖出同时买入、当前次卖出，不符合要求；但是使用这种方法，本质上相当于是前前一次买入，当前次卖出，前一次只相当于是个中间项

123. Best Time to Buy and Sell Stock III. 对于给定次数的多次买入和多次卖出，并且买一定在卖之前；方法就是确定，每一次卖出都一定发生在每一次买入之后，而下一次买入则一定发生在当前次卖出之后；因此本次卖出后的利润，一定等于本次买入后的利润加上当前价格（因为是在本次进行卖出，卖出的价格就是当前的价格，进行了售卖）；而本次买入后的利润，一定等于上一次卖出后的利润减去当前价格（因为是在本次进行买入，买入的价格就是当前的价格，进行了消费）；首次买入，由于不存在前一次卖出，因此没有利润，所以首次买入后的利润就等于负的当前价格

188. Best Time to Buy and Sell Stock IV. 这个题目和上一个一模一样，当前的买入利润，等于上一次的卖出利润减去当前价格；当前的卖出利润，等于当前的买入利润加上当前价格

309. Best Time to Buy and Sell Stock with Cooldown. 完全参考这个discussion，按照dp的的思路，对于buy、sell、rest这三个状态分别进行dp的推导，然后将rest用buy和sell表示，形成只包含buy和sell的dp推导，最后化简这两个dp数组即可https://leetcode.com/problems/be ... my-thinking-process