秋季新学期计划 - 刷题|补基础|准备面试

给你点个赞吧！

给你点个赞吧！给你点个赞吧！给你点个赞吧！

10.6 复习

****HashMap和字符串类型题目的结合，有种类型的题目就是Group类型，也就是需要把一些元素分类开来，每个类别有个代表元素作为key，这类元素的集合作为value

242. Valid Anagram. 复习；这个题目我就单纯用了HashMap来做；具体的操作就是，遍历s字符串，然后把所有字符都送进去，key是char，value是出现的次数；然后遍历t字符串，对所有字符都在map中进行检验，如果是key的话，检查一下value也就是计数是否大于0，如果是的话，更新计数减一；对于其他任何情况，都要返回false；通过检查的话就是true

249. Group Shifted Strings. 复习；这个题目是比较典型的group的题目，group就是把类似的元素group到一起，那么要点就是，什么才是类似的元素？怎么group到一起？对于第二点，实际上就是要找一个key，也就是它们的代表，如果对于任意一个元素，可以找到它的代表，那么这个代表就是key，就可以放到map当中；那么key怎么找呢？要确定什么是类似的元素才可以；这个题目里面的话，其实就是对于字符串的相邻字符的距离的问题，如果两个String，比如adc和gji，a到d的距离是3，d到c的距离是25，而g到j的距离是3，j到i的距离是25；那么就可以说，adc的key是325，gji的key也是325，key相等，group；所以这个题目的话找key的思路很重要

336. Palindrome Pairs. 复习；这个题目就要明确四种情况就可以了，也就是那些，对于两个String来说，可能可以组成Palindrome的四种情况：1. 如果一个String是“”空的，另一个String是Palindrome，那么就肯定可以组成；2. 如果一个String是另一个String的reverse，那么同样肯定可以；3. 如果一个String的其中一半的substring是Palindrome，而这个String的另一半的substring的reverse正好是另一个String，那么这两个就可以；（第4种情况和第三种相似）；然后这里需要的判断Palindrome和获取reverse的helper function可以自行完成；其他的就是如何把上面的逻辑转化成代码判断了

356. Line Reflection. 这个题目就是找一个和y轴平行的线，看看对于所有的点来说能不能使得它们各自关于这个线对称于另外某个存在的点；方法就是，首先找到这个线，由于是和y轴平行，所以只需要考虑点的x坐标就好了；那么这条线，肯定就是最左的点和最右的点之间连线的中垂线（如果这个线存在的话）；那么遍历所有的点，加入到Set里面，然后记录max和min，也就是最左最右的点；然后再遍历这些点，对于所有的点，都去set里面找，有没有一个对应的点，x坐标是当前点的x坐标关于这个中垂线的对称，y坐标和当前点y坐标一样；如果都有的话就是true

205. Isomorphic Strings. 复习；这个题目，就是挨个检查看看是不是当前检查到的字母正好和原来检查的匹配，如果不匹配返回false；如果第一次检查就加入到map中；那么最后还需要再来一遍，因为第一次用s做key，第二次应该用t做key

10.6 复习

****这里是和2Sum类似的问题，对于一个target来说，当前遍历的元素，需要从Map中找对应的互补，使得当前元素和互补元素可以组合成为target

560. Subarray Sum Equals K. 复习；这个题目和2sum类似，需要用HashMap进行记录；那么对于2sum来说，给定一个target，只有两个元素相加，那么遍历的时候就是key等于value，value等于index；那么对于任何一个新遍历到的元素，首先去HashMap中寻找有没有已经包含target减去当前元素的value的key，也就是实际上是对每一个新遍历到的元素，都去Map中寻找对于target来说的这个新元素的互补；那么这个题目也是类似的思路，都是去Map中寻找对于target来说新遍历到的元素的互补；只不过，这里的“互补”不再是相加的关系，并且新遍历到的“元素”不是单纯的这个元素本身；实际上就是，这里存储在HashMap中的key，是prefix sum，前i项的和；而value则是这个前i项的index也就是i；这里每新遍历到一个元素，都把从起始位置到这个元素为止的subarray的sum记录在map当中；而检查的内容，也就是去Map中找“互补”；那么既然存储的是prefix sum，那么互补就不应该是当前的key和Map中的其他key加起来等于target了；因为这里的target是subarray的sum，那么对于prefix sum来说，不同prefix sum的相减才是subarray的sum；因此就要去map中寻找，是否存在另一个prefix sum，使得当前的prefix sum减去它，正好等于target

325. Maximum Size Subarray Sum Equals k. 复习；这个题目和上一题一样，Map中的key同样存储着前i项和，value则是这个i也就是index；那么这里要求的是最大长度的subarray使得它的和是target；那么对于每一个遍历的新元素就要开始进行寻找：如果这个新元素的index所对应的prefix sum正好等于target；那么比较更新res和当前的元素（实际上这里直接更新使得res = i + 1就好了，因为这是从左到右的遍历，肯定越来越长）；否则的话，去map里面进行查找，查找是否map包含另一个prefix sum，使得当前prefix sum减去这另一个prefix sum正好等于target，如果相等的话，取出和这个prefix sum所对应的元素的index，然后用当前元素的index去减它，就得到了当前这个subarray的长度了，那么这个长度就要和res进行比较更新；然后对于当前的prefix sum来说，只有在它不在map中存在的时候才能put进map中去，因为希望map中存储长度尽量小的index，这样相减以后才会变大

10.6 复习

****这里是滑动窗口的问题，滑动窗口就是确定好左端点右端点的范围，然后用一个HashMap来记录当前范围内部的一些信息，然后右指针往前走，走到一定程度满足一些条件后，左指针再继续走

3. Longest Substring Without Repeating Characters. 复习；找到最长的不包括重复字符的substring，这是典型的双指针圈定滑动窗口使用HashMap的题目；窗口的右端点不断往前走，每遇到一个字符，都包含到窗口中，也就是记录到Map中；Map的key是字符，value是出现的累计次数；如果右端点检查到一个字符，包括这个在内它在窗口中已经出现了多于1次，那么窗口的左端点就要往前走，一个字符一个字符的吐出来，直到把当前检查的右端点对应的字符的次数减为1；而如果不多于1次的话，右端点每向前走一步，都需要比较更新当前最大的substring长度

395. Longest Substring with At Least K Repeating Characters. 复习；这个题目要找到一个最长的substring，使得里面的所有字符在这个substring的出现次数，都不小于k次；那么首先遍历这个String，对于每个字符做统计，结果放到Map里面；那么对Map的每一个key-value pair做遍历，如果发现所有的key对应的次数都大于k，那么给定String本身就是一个满足条件的，自然最长；否则，使用滑动窗口；首先右端点向前走，如果现在右端点对应的字符在Map中的value也就是出现次数小于k的话，说明这个字符肯定不能被包含在目标substring之内，那么对从左端点开始到当前右端点之间的这段substring做recursion处理，注意这里使用recursion是求这段substring里面最长的所有字符出现次数都大于k的substring长度，然后和res进行比较更新；之后左端点要跳到右端点的后面一位，因为右端点这时指向的字符肯定没用了；然后右端点每次都前进

159. Longest Substring with At Most Two Distinct Characters. 复习；这个题目我在自己做的时候使用了一个非常不适合推广的方法；那么正确的通用方法就是，用map去记录滑动窗口的重要信息；然后滑动窗口，右端点每次往前进，每遇到一个新的字符都要往map里面检查更新，如果遇到一个新的字符，那么记录当前distinct字符的counter要++，否则的话单纯更新map；如果现在的counter大于2的话，说明当前的滑动窗口当中已经包含了多于两个独特字符；这时左端点就要往前走，每往前走一个都实际上是吐出来一个字符，那么被吐出来的字符对应在map中出现的次数对应减1；那么如果减1完以后发现这个字符对应的次数已经是0了，那么counter就要--；减到小于等于2的时候，右端点才能继续走

340. Longest Substring with At Most K Distinct Characters. 复习；这个题目跟上一个two的题目完全一样，就是把2换成给定的k就好了；这里要额外注意，在代码中什么时候移动右指针什么时候移动左指针，什么时候进行比较更新

76. Minimum Window Substring. 复习；这里是要找出，最小的substring，使得这个substring能够包括所有的给定targetString的字符；那么做法就是maintain一个hashmap，这个hashmap中的key是给定字符，value是给定字符的出现次数；那么又一个滑动窗口，右端点往前走，如果右端点指向的字符是给定字符的话，也就是在hashmap中检查是否contains，那么就要hashmap的对应key的value进行减1，并且计数器--；那么当计数器为0的时候（这个计数器实际上就是记录给定targetString的size的，还有多少个char没有被包含在窗口当中），就是可以要移动左端点的时候，去缩减窗口的长度，同时比较更新当前长度即可

10.7 复习

****这里是一些TopK的问题，使用PriorityQueue

912. Sort an Array. 这个题目是单纯的数组排序，当然就有多种方法，quick sort需要掌握，其他的选择排序、插入排序、冒泡排序、合并排序、堆排序都需要掌握

347. Top K Frequent Elements. 复习；这个TopK的问题实际上普遍用PriorityQueue来做，也就是首先遍历给定Array，统计一下对应元素和频率，放到Map当中；然后建立一个可以存储Map的PriorityQueue，并且建立一个可以比较Map.Entry的Comparator，优先级就按照每一个entry的value大小来确定；然后就是把每一个Map中的entry都给offer到Heap当中；由于这是一个minHeap，因此每当offer到minHeap的size大于k的时候，就poll掉，而poll掉的肯定是比较小的那个；因此minHeap就总是可以maintain最大的top K个；最后把剩下的top K个从minHeap中poll到res里面即可

692. Top K Frequent Words. 这个题目同样是Top K，和之前的Top K element是同样的思路；那么变动的地方在于，当词频一致的时候，需要用字母进行排序，实际上就是多种判断priority的规则；这些都需在Comparator内部进行实现；那么首先如果词频不相等的话，就非常简单的去return就好了；那么如果词频相等的话，不能简单返回0，而是需要去找entry的key（词频是value，词本身是key），然后把key转化成charArray，然后两个charArray进行逐个字母的比较（String不能直接比较但是字母可以），如果发现哪个字母更小，实际上就可以进行return了

252. Meeting Rooms. 复习；这个题目严格来说考察的是Comparator，是利用Comparator去对一个长度为2的array进行排序；排序就是按照第一个元素为标准；排好之后，遍历排好的array，对于每一个pair来说，如果右端点大于后面的左端点，就说明有重合，因此不能出席所有meeting

253. Meeting Rooms II. 复习；这个题目之前做过，总之就是首先按照左端点进行排序，然后按照右端点确定优先级建立一个minHeap；这样遍历排好左端点顺序的intervals以后，每次都从minHeap中提取出现在右端点最小的区间，看看和当前遍历的元素是否重合，如果不重合，说明不需要新开教室，所以merge这两个区间，也就是物理意义就是当前的room可以开这两个会；否则把遍历到的interval给offer到heap当中

370. Range Addition. 复习；这个题目也好说，建立一个map，key是index，value是从当前key对应的index开始，后面所有所累计需要进行的加减增量；同时对于起始位置开始是+，而终止位置后面的那一位需要减，这样进行抵消；那么最后构建res数组的时候，从初始位置开始，用一个sum去记录增量，然后去map里面去get到，因为即使是map当中也不会说每一个key都对应着全部的增量，所以需要进行再次累计；然后sum随这i的增加进行累计，越初始的i影响越少、累计越少，res[i]就存储当前累计的sum即可

楼主真的很勤奋   从你的秋季计划我也学到了很多  祝楼主早日找到工作！

10.8 复习

****这里做了一些非常基础的Binary Tree的遍历的题目，也就是preorder、inorder、postorder、levelorder

144. Binary Tree Preorder Traversal. 复习；Binary Tree的preorder遍历，recursion的方法当然容易，但是iteration的方法比较麻烦一些；首先preorder就是见到root马上打印，然后往左走，那么对左子树的root也同样马上打印；所以iteration的做法就是，首先维护一个stack，offer进来一个root，然后马上poll出来；poll出来就是打印，并且对于这个poll出来的root，先offer进它的右子节点，再offer进它的左子节点；这样下一次poll的时候，优先出来的就是左子节点了；然后对于左子节点进行同样的操作：poll、打印、offer右子节点、offer左子节点

94. Binary Tree Inorder Traversal. 复习；这个题目是Binary Tree的中序遍历，recursion同样简单；iteration的话，除了维护一个stack，还需要有一个helper node，也就是next；next所记录的，就是下一步应该进行遍历的节点；那么首先，对于一个root来说，下一步应该遍历的节点总是它的left node，那么next就始终指向root.left一直往左走；那么直到next为空的时候，就可以知道当前root是没有left node了，那么也就是说需要打印当前的root了；而打印完毕、add进res中以后，下一步需要打印的肯定就是当前这个root的right子节点了，那么next指向root.right；接下来还是按照同样的方式继续循环即可；那么循环条件应该是next不为空以及stack不为空，满足一个即可

145. Binary Tree Postorder Traversal. 复习；postorder的遍历同样recursion是非常简单的；但是iteration的方法，麻烦的就在于除了要maintain一个stack之外，还需要一个helper node去记录当前访问到的节点的上一个访问的节点；那么由于是postorder，也就是当前root必须等它的左子节点和右子节点都遍历完毕以后才能进行遍历打印；也就是说，对于当前的current node来说，也就是当前从stack中peek出来的节点，如果previous node是null或者是它的parent节点，说明这个current node是刚刚从上往下过来的，它的左右子节点仍然没有遍历，因此首先检查它的左子节点，如果存在的话就offer进stack当中，然后检查它的右子节点，如果存在的话就offer进stack当中，如果两个都不存在，也就是没有必要进行访问了，直接打印当前节点、add进res中；如果previous node是它的左子节点，说明现在要访问右子节点了，那就检查它的右子节点，如果存在的话就offer进stack当中，否则打印当前节点；如果previous node是它的右子节点，说明所有访问完毕，那么直接打印即可

102. Binary Tree Level Order Traversal. 复习；这个题目也很简单，直接BFS打印就可以了

429. N-ary Tree Level Order Traversal. 这个题目和二叉树的打印区别就在于这是一个n叉树，所以每次BFS过程去generate的就不是左右子节点进Queue了，而是generate它的children list中的所有节点进Queue，其他过程和一般的一样

107. Binary Tree Level Order Traversal II. 复习；这个题目把每次打印的level list都往前面add就可以了

10.10 复习；

****几个DFS的基本入门题目

78. Subsets. 复习；最基本的DFS题目，recursion tree画出来，对于给定array中的任意一个元素来说，都是取或者不取，判断完以后进入下一步recursion，然后紧接着判断下一个元素；所以recursion tree是个二叉树

90. Subsets II. 复习；这个题目不同就在于给定的array里面有重复元素，要求的是不能有重复的subset，而每一个subset里面可以重复；那么和前面的不同就是，当要recursion去考虑添加下一个元素的时候，先看看下一个元素和这次考虑的元素一不一样；如果一样的话，那么还去考虑，就可能造成，比如这次的这个元素没加，但是下次同样的元素又加了；而另一个recursion的route就是，这次的这个元素加了，而下次同样的元素没加；所以就会造成很大的困扰

77. Combinations. 复习；这个题目和上一个subset的一样，区别就是这里需要保证conbination的长度，把长度作为base case的依据

46. Permutations. 复习；这个就是用swap的方法，而且每次recursion里面需要进行遍历，而不是二叉树

47. Permutations II. 复习；这个和之前的排列题目一样都是swap，但是因为出现了重复的情况，所以有的时候swap了当前这个，要swap后面一个的时候会发现两个一样，那么swap就失去了意义，从而造成重复；解决方法是每次recursion都maintain一个set就可以了

10.11 复习

****DP的入门题目

70. Climbing Stairs. 复习；这时最简单的dp问题，当前i长度的台阶，可以由i-1长度的台阶走一步到达，也可以由i-2长度的台阶走两步到达；因此i的步数，实际上由i-1和i-2的步数决定；这样就可以得到dp的induction rule了

62. Unique Paths. 复习；这个题目和上一个爬楼梯的很像，同样对于当前点来说，可以由他上面的点走到，也可以由他左边的点走到；这样，这个点可以走到的次数，实际上就等于他上面和他前面的点能够走到他的次数的两者之和；当然对于一些边节点来说，没有上面的点或者没有左边的点或者两个都没有，这些都应该考虑到

63. Unique Paths II. 复习；这个题目就是多做一些判断，然后和上面的问题大致类似的

120. Triangle. 复习；这个题目实际上就是从底部往上遍历一下即可，对于三角形的底部进行遍历，倒数第二层开始，每一个的和都是往下一层的相邻两个的最小的，加上它自己；所以这种形式的话，dp矩阵里每一个值都能保证是最小的

279. Perfect Squares. 复习；dp存储的就是，当前的i减去一个square以后，找到这个前面的dp就好了