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

9.23 复习

****两道longest common的题目，其实也没有特别大的关系

14. Longest Common Prefix. 复习；这个题目最简单的方法就是，对给定的String数组进行排序，然后找第一个和最后一个，然后一个一个比，如果字符相同，那就append到结果里面去，否则就返回结果

1143. Longest Common Subsequence. 二维DP题目，一个一个去进行比较，如果当前两个位置对应的字符相同，那么dp[i + 1][j + 1]应该等于dp[i][j] + 1，如果不同的话，就等于上面的或左边的的最大的那个；注意dp数组的size一定要比给定String的size更大就好

9.23 复习

****四个binary search的题目，binary search主要就是确定，每次排除掉的那一半都必须是不包括结果在内的就可以了，基于此应对各种变种

35. Search Insert Position. 复习；这个题目要求，如果taget存在就返回target，如果target不存在，就找到插入的位置，而插入的位置实际上是要插在比target小的元素的右边位置，实际上也就是最小的那个比target大的元素的位置（因为target这时不存在）；所以翻译一下，这个题目实际上就是在nums中找到，大于等于target的元素的最小的那个；所以在binary search的过程当中，循环条件如果是最一般的left < right的话，那么nums[mid] == target的情况直接返回就可以了；如果nums[mid]比target小，那肯定不是要找的（因为这里要找到大于等于target的），所以left = mid + 1；如果nums[mid]比target大，那么可能是要找的但是不一定（因为要找到最小的大于等于target的，现在找到了一个大于target的，还是有可能是结果的），所以right = mid；也就是说binary tree每次排除的，都应该是绝对不可能成为目标结果的那部分；那么最后要考虑一个corner case，也就是如果nums里面所有元素都比target小的话，最后right指针指向的肯定是nums的最后一个位置，这个时候返回right + 1就可以了

278. First Bad Version. 复习；这个题目很有意思，要找到第一个bad version，其实就是如果把整个版本从左往右排开的话，左边早右边晚，那么就是找最左边的bad的版本，序列就应该是这样的g g g g g b b b b b b；那么这个题目用binary search的话，循环条件是最一般的left < right的话，如果mid定位到bad的了，可以确定的是这里是bad version，可能是最早的一个也可能不是，所以right = mid；而如果mid没有定位到bad，说明这里肯定不是要找的，因此left = mid + 1

33. Search in Rotated Sorted Array. 复习；这个题目再次说明了binary search的本质其实还是在每次binary partition的时候，都必须要排除target绝对绝对绝对不可能存在的那一部分，并不一定是二分的，但是排除的一定是不可能存在的那一部分；这个是rotated的sorted array，并不能说从头到尾都是单调增的；那么仍然有一个mid，如果mid直接指向了target那么直接返回；否则的话，考虑一下究竟应该往哪里继续搜索，而不再考虑哪个部分；由于binary search必须要求单调增，那么首先可以考虑的就是，现在有三个指针，left、mid、right，如果从left到mid是单调增，那么就可以先考虑这部分，否则就去考虑mid到right，总之肯定至少有一个范围是单调增的；那么对于单调增的left到mid来说，如果target正好在left到mid这个范围内（可以通过nums[left] <= target < nums[mid]来验证），那么直接让right = mid - 1过来就可以了，接下来left到right就是单调增、进行最一般的binary search就好；否则，说明target不在这个left到mid的单调增范围之内，那也不要紧，让left = mid + 1，然后排除掉这个肯定不可能存在的部分，接下来继续在这个有rotated pivot的部分进行查找就可以了，总会查到一个范围是单调增且target在其中的

81. Search in Rotated Sorted Array II. 复习；这个题目和前面的题目唯一不同的地方就是，nums中间可能有重复的元素出现；那么对于重复的元素可能造成的影响就是，left和mid定位到了同样的数字上面，而target不被mid所指向，那么这时的left到mid这部分就没有了继续search下去的意义；为了breaking这种情况，简单的left++就可以了，实际上这个left++就是通过在局部进行效率低的逐次搜索，去break这个tie

9.24 复习

****今天又是几个binary search的题目，明天争取做完

153. Find Minimum in Rotated Sorted Array. 复习；binary search变种题目，需要找pivot，那么对于pivot来说，从left到pivot，和从pivot到right都是单调增的，那么也就是说，比如nums[mid] > nums[right]的话，pivot肯定在这个范围之内，那么binary search就可以往这边找，找的话就right = mid就可以了，因为并不能确定这时的mid是不是target；否则的话，如果只是找到了一个单调增的区间，那么pivot肯定不在这个范围之内，left = mid + 1；

154. Find Minimum in Rotated Sorted Array II. 复习；这个题目和上一个题目一样，区别就是这里有duplicated的元素；另外，这个题目要找最小，要找pivot，那么只有left = mid + 1而right则是等于mid；这样的话，如果right = mid且正好是duplicated的话，就可能进入循环永远不结束的情况；这时就需要break tie；那么break ite的话，这里就不能left ++了而要right--；因为上面的这个过程都是对right进行讨论的；在nums[mid] == nums[right]的情况下，如果left++，很可能就会遗漏left指向的这个数，因为这时并不能确定left是不是指向pivot

374. Guess Number Higher or Lower. 复习；这个就是最基本的binary search；最基本的流程就是循环条件是left < right，循环最后的状态就是left == right，那么返回left就好了

162. Find Peak Element. 复习；这个题目更加典型，告诉我在定位到mid以后，应该用mid和什么位置去比较，这里是和mid + 1去进行比较，如果mid比mid + 1小，说明mid不包括mid的右边肯定有一个peak，那么left = mid + 1；否则right = mid，因为这里并不确定mid是不是peak

34. Find First and Last Position of Element in Sorted Array. 复习；真难……不想做了

9.25 复习

****今天做了两个binary search的题目，不是特别好

274. H-Index. 复习；这个题目的思路是这样，首先对每个元素的出现次数进行统计，就给一个bucket数组，数组每个bucket的index代表当前元素的值，也就是引用次数；而bucket的value则代表引用次数的index的论文出现了多少次；那么如果有一篇论文引用次数太多的话，那么bucket统一留出最后一个位置用来统计这些引用次数过多的论文的出现次数；因此bucket的物理意义就是，包括它在内的所有右边的bucket的value的和，就意味着引用次数至少是当前bucket的index代表的数值的论文的数量；而H-index的意义正好就是，引用次数至少是n的论文的数量为n；那么这样就把这两个给联系了起来，也就是说从右往左去加bucket，累加到某个位置时，使得比当前bucket的index（假设为n）要大，也就是引用次数至少是n的论文数量大于等于n了，那么这个index n就是结果

275. H-Index II. 这个题目真是不太懂啊不太懂

9.26 复习

****今天做了两个比较麻烦的包裹着binary search的题目

315. Count of Smaller Numbers After Self. 复习；这个题目这一次用的binary search的方法做的，方法就是，从后往前遍历这个给定数组，然后都需要maintain一个，当前遍历到元素的右边的所有元素组成的有序list；然后从后往前遍历的过程中，就对当前这个元素去查找，这个当前元素对于它右边的所有元素组成的有序list，应该能够的插入的位置；那么找到了这个插入的位置以后，这个位置的index就是对于当前遍历到的这个元素在给定数组里面，在它右边的且比它小的元素的个数；这个很好理解，因为现在有一个当前元素的右边所有元素组成的有序数列，如果找到了这个元素应该插入的位置的话，实际上它的位置、它的index就代表着它应该排在它右边元素组成的有序数列的第几个，也就是意味着它右边有多少个元素小于它；那么这就变成了一个，遍历所有给定数组元素，然后一边建立有序数组，一边在有序数组上进行元素插入的问题

300. Longest Increasing Subsequence. 复习；有点想明白了，就是说，遍历给定数组，然后有一个结果的list；首先遍历的时候，先把第一个元素放进去；如果后面遍历到的元素比这个元素小，那么replace掉；如果后面遍历的元素比这个元素大，那么就扩大结果list，然后把后面的元素放进去；但是如果又遇到了一个小的该怎么办？这里就出现了binary search；也就是说，对于每一个新遍历到的元素，都把它作为target，在结果list里面做binary search；如果发现这个target应该插入的位置是这个结果list的中间，那么好，就把这个位置的元素和它做替换；如果发现的这个target应该插入的位置是这个结果list的最末尾，那么就说明当前这个target，正好可以作为这个increasing subsequence的最后一个元素加入进来，从而增加这个递增子序列的size

9.29 复习

****这一次是linkedlist的简单题目

206. Reverse Linked List. 复习；我用recursion做的

141. Linked List Cycle. 复习；就般的快慢指针遍历，如果遍历过程中slow和fast相遇就说明有环

24. Swap Nodes in Pairs. 复习；这个我用了很简单的recursion方法，首先解决后面的pairs，然后留下当前head和当前head.next，这两个去swap操作一下就好了

328. Odd Even Linked List. 复习；这个题目首先理解好题目意思，是要求把位置上的奇偶进行调整，而不是数值上的奇偶；接下来在纸上画图看看就好了，首先初始化odd和even，odd一开始应该指向第一个位置而even指向第二个；然后odd的next指向even的next，odd往next移，然后even再指向odd的next，even往next移；最后实际就相当于划分出了两个List，所以一开始需要维护一个evenHead，最后odd的next应该指向evenHead

92. Reverse Linked List II. 复习；这一题目需要用dummy node，用dummy node的原因就是可以规避一些不必要的corner case检查，比如这里可能会考虑到m和n的位置如果和head有关怎么办，那么head如果也需要进行变动的话，没有对头节点的控制就很麻烦；有了dummy node，fast和slow都从dummy开始遍历，dummy node不变就很容易操作；那么这里的reverse，实际上就是把最先的node一个一个都append到最后一个的后面，每一个都是append到最后一个的后面，那么一开始append的到最后肯定就是排最后了

237. Delete Node in a Linked List. 复习；这个题目就是卸磨杀驴型的题目，首先把当前node的value取后面元素的value，然后用完了以后，当前node的next就指向后面next的next；这里注意，对于当前节点来说，如果只知道它的话，实际上是不能对它进行操作的，拥有的只是它的next而已

9.29 复习

****这一次是LinkedList的稍微复杂一点点的题目

19. Remove Nth Node From End of List. 复习；这个题目仍然需要使用dummy node；使用dummy node的最主要原因就是，相关的操作改动可能会对head节点产生影响；那么对于这一题来说，在确定好要删除的节点的prev之后就可以直接prev.next = prev.next.next了，但是如果增额待删除节点是头节点怎么办？如果待删除节点是最后一个节点怎么办？这些都需要考虑；对于LinkedList的操作，最重要的就是对head节点的控制，以及防止NPE的发生

83. Remove Duplicates from Sorted List. 复习；这个题目要求的是删除重复的元素节点，同时保留重复元素节点的第一个；那么首先慢节点指向可能重复的元素的第一个，然后快指针一开始也指向这个；快指针往后走遍历，当它不等于慢指针的值的时候就停止，然后慢指针next再指向快指针；这里注意，由于快指针一开始指向的是slow，并且在每次fast遍历的时候都是指向slow，所以fast肯定会往后走，因此不会出现slow的next指向自己的情况

203. Remove Linked List Elements. 复习；这个题目也需要用dummy，因为head节点的value可能就是target value；那么每次head往后走，然后记录head如果往后走的话的前一个node；这样，如果head的value等于target的话，它前面的prev的node就可以正好把next指向head的next，这样实际上就完成了删除操作

82. Remove Duplicates from Sorted List II. 复习；这个题目有点麻烦，要删除duplicates并且一个不留；一个不留的话，首先遍历重复节点，确定起始范围；然后根据起始范围，如果范围内只有一个节点，实际上是不重复的，那么prev往后走；如果范围内不只有一个，那么自动忽略；遍历到null的时候，要注意最后这段是不是duplicates

9.30 复习

****这一次复习的是最后四个LinkedList类型的简单操作题目，LinkedList主要就是关注是否有dummy node的标注（如果头节点改变），是否可以使用recursion方法简化操作，另外就是各种指针指向循环的操作

369. Plus One Linked List. 复习；这个题目是用一个由链表表示的数再加1；那么最好的方法就是从后往前进行遍历；但是由于这个是一个单链表，单链表没办法从后往前；所以这里的一个技巧就是，快慢指针从前往后遍历，快指针每次都往后走，而慢指针仅当快指针不指向9的时候才回指向快指针否则就不动；那么最后，快指针指向最后一个元素，而慢指针指向最后一个非9元素，他们之前则都是9（如果有的话）；那么如果快指针不是9，那么光加它自己就好了；否则，慢指针加1（因为慢指针不是9），然后慢指针往后全变成0（因为后面都是9）；最后返回的，如果dummy node仍然是0，说明head不是9，没有进位；否则返回dummy node，因为可能进位；这个题目用dummy node，并且dummy node本身甚至都可能改变

2. Add Two Numbers. 复习；这个题目是给的两个倒序的LinkedList，所以可以从后往前加；每次相加以后，当前位上的数一定是相加后除以10的余数，进位的就是相加后除以10的进位；然后如果有一个链表结束的话，检查另一个链表需不需要继续，因为进位的数应该持续相加；如果最后进位进到头了，也就是说最后一位仍然是9，那么需要在末尾增加一个node

160. Intersection of Two Linked Lists. 复习；这个讨论还是很重要的https://leetcode.com/problems/in ... -difference-in-len!；首先就是说，这里给定的两个list不管是不是一样长，都可以分为他们各自的部分和他们共同的部分；对于长度来说，他们共享共同的部分，而其中一个list加上另一个list的自己的部分的话，实际上他们的长度就相等了；那么首先就是，他们各自往后遍历；如果某一个list的遍历到头了的话，这个指针就应该指向另一个list的头，然后继续往后；这样，他们两个肯定会汇合在intersection的位置；这是因为，lenA = selfA + share，lenB = selfB + share；那么在某一个走到尽头后往另一个走，实际上就是selfA + share + selfB，那么两个都这么走，最后汇合的点肯定是intersection

21. Merge Two Sorted Lists. 复习；这个题目用recursion方法真的是非常的方便；思路就是，对于两个list来说，从头节点开始，如果l1的值小于l2的值，那么就说明l1的头节点应该保留，继续讨论的就应该是l1.next和l2，那么这个继续讨论的部分就让recursion function来完成就可以了；而这个继续讨论的部分，肯定是在l1的头节点后面的，所以了l1的next就应该指向recursion返回的子list的结果，这样就完成了构建；对l2的情况也是如此

9.30 复习

****这里十几个LinkedList的稍微提高一些的题目，主要麻烦的地方就是，很多思路是需要分几步做，比如先找中点，然后切断，然后排序，然后merge这些过程，那么过程和过程之间需要有很好的联系，要思考是不是有些corner case需要进行处理的，这些要注意

234. Palindrome Linked List. 复习；三步走：找中点，reverse后半段，挨个挨个往后查

143. Reorder List. 复习；这个题目就是几步走，找中点，切断，反转，merge；注意切断的后半段，一定长度要比前半段低，这是为了希望能够方便操作避免NPE或者避免遗漏

142. Linked List Cycle II. 复习；假设A是初始段长度，B是slow在cycle以后走的长度，那么A + B是slow走的长度，2A + 2B是fast走的长度；现在知道fast比slow多走了一个cycle，可知cycle长度为A + B；而slow在cycle中已经走了B的长度，剩下还有A的长度就可以到达cycle入口，而A正好也是起始段长度；所以只需要让slow继续走，然后起点再来一个指针往前同步走，相遇的话就是cycle的起点；那么如果slow走到了null的话，说明没有环

148. Sort List. 复习；这个题目就单纯是考察，merge sort在LinkedList上面的实现的；由于merge sort是分治法做，那么就要找中点，然后recursion两段；对于linkedlist来说，首先找中点，然后recursion，然后merge即可

9.30 复习

****最后几个ListNode的题目了

25. Reverse Nodes in k-Group. 复习；这个题目主要就考察最基本的操作类问题，怎么样去按规定长度进行reverse，reverse完了以后怎么继续遍历，reverse开始的时候各个辅助节点状态怎么样，reverse结束以后各个节点状态又应该怎么样

86. Partition List. 复习；这个题目也是用dummy node来去做，两个list，去遍历给定的list，大的就append到大list后，小的就append到小list后；那么最后两个list连接起来就好了

61. Rotate List. 复习；这个题目就是找到最后的点，同时找到长度，然后根据list的长度对k取余，然后找到要切断的点，然后就好操作了

23. Merge k Sorted Lists. 复习；这个题目就用PriorityQueue来完成就好了，因为PQ规定了大小关系，把所有list的所有node的值offer进PQ中，然后一个一个offer出来就正好排好序了

147. Insertion Sort List. 复习；这里要注意，每一次insertion的过程中，都应该是从最开头开始的，然后dunmy一开始不要连接head；然后就是从头开始遍历，发现等待插入当前节点的话，就用ListNode的操作插入，然后prev从头开始，head往后走一个