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

9.18 复习

今天复习了四个区间类型的问题，都是很基本的题目，基本上都是和sort相关，要用comparator去比较区间的左端点然后排序，进而对整个排好序的区间序列进行遍历然后有进一步的比较

56. Merge Intervals. 复习；这个题目要求给了一些作为区间的pair，让你去把这些区间看看有没有overlapping然后去merge起来；那么merge intervals的话，其实首先要做的就是根据它们的start端点进行排序，然后遍历这些排好序的区间，首先把前一个区间的end端点，和当前区间的start端点进行比较，如果end端点大于等于当前区间的start端点，就说明有overlapping的情况，需要去merge；那么要merge的话，就是要把前一个区间的end端点和当前区间的end端点进行比较，取最大的那个end然后和前一个区间的start端点暂时组成新的区间；然后这个新的区间再作为“前一个区间”进行下一次比较；如果发现end端点小雨当前区间的start端点，说明没有overlapping，那么也说明前一个区间merge完毕，加入到res中，然后把当前区间作为“前一个区间”进行下一次比较

57. Insert Interval. 复习；这个题目和上一题差不多，都是去merge interval，那么merge的话很容易，就是对于要去merge的两个区间，比较它们的左端点取最小的那个，比较它们的右端点取最大的那个，这样组成了新interval；那么怎么确定两个区间需要被merge呢？首先，如果一个区间的右端点小于目标区间的左端点，那么肯定不需要merge；然后如果一个区间的左端点大于目标区间的右端点，同样不需要merge；问题就是，如果一个区间的右端点大于目标区间的左端点，要不要merge？答案是不确定，因为一个区间的右端点大于目标区间的左端点的话，并不能确定这个区间的左端点和目标区间右端点的关系；所以应该用一个区间的左端点和目标区间的右端点进行判断，如果一个区间的左端点小于目标区间的右端点的话，肯定需要merge；那么这个题目里就这样依次进行比较就好了，该merge的时候先merge再放进去，不该merge的时候直接放进去

252. Meeting Rooms. 复习；这个题目就是首先按照左端点把所有区间进行排列，然后遍历排好序的区间，看看每一个区间的右端点，是否小于下一个区间的左端点

253. Meeting Rooms II. 复习；同样是本质上是对interval的操作；interval类的问题首先一般都需要对区间左端点进行排序，然后再顺次遍历排好序的区间检查右端点；这个题目就是，按左端点排好序以后进行遍历；同时maintain一个能够对区间右端点进行Compare的Heap，这是因为要把右端点较小的区间能够优先选出来，因为右端点代表结束时间，越小的话就越可能不需要额外的房间；初始化的时候把左端点最小的区间offer进Heap中；然后遍历排好序的序列，对于每一个区间来说，都首先从heap中poll出当前结束时间、也就是右端点最小的区间，然后和当前区间比较：如果当前区间的左端点比从heap中poll出来的区间的右端点要大，就说明不需要一个新房间，那么就merge一下这两个区间（这里不是出现overlap才merge，而是不出现就merge），把当前区间的右端点作为poll出来的区间的右端点；如果当前区间左端点比poll出来区间的右端点小的话，就说明需要新房间，那么直接把这个当前区间offer进heap中就好；最后每次循环时，都把这个poll出来的区间，无论是否重新merge了，都重新offer进heap，使得heap中始终拥有当前右端点最大的那个区间；最后算heap的size就好了，size就代表着需要的房间数量，因为每次有新的区间offer进heap的时候，都是两个区间有重叠的时候

9.19 复习

今天首先复习了类似区间的题目，仍然是遍历、排序、比较端点等等

352. Data Stream as Disjoint Intervals. 复习；注意看清题目，题目要求的是合并，而并不是把所有可能的区间都罗列出来；因此，再根据value获取到lowerKey和higherKey之后，既然Key是作为区间的右端点的话，lowerKey所对应的interval是很有可能把value包含在内的，就比如<4, [4, 8]>这个key和interval，那么如果插入一个7的话，实际上不对现有区间序列造成影响的，因此这种情况，也就是lowerKey在可能可以和value合并的话要注意一下，当lowerKey对应区间的右端点 + 1大于等于value的时候需要进行合并，但是合并后的新区间的右端点究竟是什么这个还需要额外注意；另外对于higherKey来说，如果需要合并的话，higherKey应该删除才对，也是同样的原因

986. Interval List Intersections. 复习；题目要求的就是，去merge两个Interval的序列，这样的话就一个一个遍历就好了，对于两个interval来说，看看他们的start和end端点有没有重合，也就是最大的start是否小于最小的end，有的话加进去，然后看看这是不是这两个都讨论完了可以遍历下一个

436. Find Right Interval. 这个题目用的是TreeMap，首先把所有的interval都放进TreeMap当中，key是每个interval的左端点，value则是这些interval在整个intervals序列中的index；放进TreeMap是为了能够更好的根据给定数值找到比它更大或比它更小的key（这里是找到大于等于它的）；而题目是要求，对于一个interval来说，找到它的right interval，就是找到一个interval使得它的左端点能够大于等于当前的整个interval的右端点；因此这里在第二次遍历intervals序列的时候，对于每一个interval找right interval的话，都取到这个当前interval的右端点，然后把右端点去TreeMap当中去查找，是否存在一个key大于等于它并且找到这些key的最小的那个；因为TreeMap的key正好是所有interval的左端点；如果找到的话，那么结果数组的这个位置就是这个key所在的interval所对应的给定intervals序列的index，否则就是-1

9.19 复习

今天还做了五个题目，也算是复习但是实际上没有什么可以总结归纳的，练练熟练度就好了只能

161. One Edit Distance. 复习；这个题目给了两个String，给了一次编辑的机会，让看看能不能通过这一次编辑，使得两个String变得相同；那么遍历这两个数组，如果遇到了不同的字符，那么可能是S要掠过去，也可能是T要掠过去，也可能两个要一起掠过去；那么如果掠过去以后又发生了不相同的话，那就是false了

88. Merge Sorted Array. 复习；这个题目就是从后往前merge，既然是从后面开始，那肯定就是哪个大先放哪个；然后最后如果短的那个数组还没有移完的话，就最后全都移那个就好了

392. Is Subsequence. 复习；这个题就是顺次往下走就好了，维护一个s的index和t的index，t的index每次都走，s的index只有在s和t当前对应的字符相同的时候才会往下走，完成了以后要注意检查s的index是否等于s的length如果等于就说民是subsequence

844. Backspace String Compare. 这个题目用不用stack都可以，用stack肯定是最简单的，就是遇到非#字符就offer进去，遇到#字符的话，就把栈顶元素poll出来即可，然后获得了所有的剩下应该有的字符，最后把它转化成String然后进行比较即可；题目不用stack的话，对于一个String的话，就应该从后往前扫描，即如果从后往前看到了一个#的话，那么说明#前面的char肯定要删除掉的，那么扫描的时候就应该统计一下#的数量，从而决定需要删除的char个数；如果当前字符为#，计数；如果当前字符不为#，那么减去计数器，如果计数器为0的话，那么才说明这个字符应该保留

686. Repeated String Match. 这个题目其实就是不断的进行append就好了，也就是不断对A进行复制1然后append到后面，直到这个新建的String中能够找到B；那么一直加的话，会不会一定能够加出来一个String使得B是子串呢？不能的，这个情况下应该这样判断：如果新建String的长度已经比B的长度多了一个A的长度了，那么就说明再往后加也没有用，因为pattern已经确定了，这里不是长度不够的问题，再往后加的话，B能够匹配的仍然是之前能够匹配的

9.19 复习

这里是几个双指针相向而行的问题，就一个一个检验就好了

11. Container With Most Water. 复习；双指针相向而行，每次移动之后，都要检查当前的全局最优，然后判断哪个指针应该往中间移动

345. Reverse Vowels of a String. 复习；同样是双指针相向而行，左边一直走直到遇到元音字母，右边一直走直到遇到元音字母，然后swap，然后左右++

125. Valid Palindrome. 复习；这个题目也是，双指针相向而行，对于字符串的所有valid的字符都进行相向而行的， 一个一个检验就好了

9.20 复习

****这一次复习的三个题目，分别是shortest distance的1、2、3题目，基本上都是通过遍历给定数组然后得到两个word的index的sorted list，然后再通过逐次比较谁小移谁的方法找到答案；另一种方法就是维持两个指针时刻指向最新的两个target在给定数组的index

243. Shortest Word Distance. 复习；这次复习题发现了一个新方法，之前做的时候就是用两个指针在遍历数组的时候去挨个更新，然后再去更新全局；而这里的方法更容易推广一些，也就是首先遍历整个words数组，对于每一个word1出现的index，都顺次加到list1中，而每一个人word2出现的index，都顺次加到list2中；那么这次循环结束后得到的两个list，就可以去顺次进行各自遍历，各自遍历到的值也就是word1和word2出现的index，作差然后和全局最有比较，比较完以后，“谁小移谁”，也就是哪个的index小就移谁，这样就避免了不必要的检查

244. Shortest Word Distance II. 复习；这个题目的思路和上一题完全一样，只不过拆开成为了一个Design问题，也就是输入words数组，和求去两个目标word的distance是分开的；那么就可以在输入words数组的时候做一些动作，使得求取两个word的distance的时候不需要重新按照第一题的方法重新从words数组中读取下标形成list了；因此，输入数组的时候，就可以建立一个map，key是每一个word，而value则是这个word在输入words数组中的index的list；那么在求取两个word的distance的时候，直接去map中以它们作key，然后拿出list，再用第一个题目的做法就可以了

245. Shortest Word Distance III. 复习；这个题目就不能用遍历给定数组然后取出所有两个target的index然后逐次比较了，当然也可以这么做就是很麻烦；这个题目用的是两个指针然后遍历word的时候，顺次记录出现的两个target的当前最新的位置，那么如果这两个word不一样的话，其实就跟第一题一样；如果一样的话，那么在要给第二个指针更新的时候，同时还要给第一个指针更新，这就相当于是两个指针同步进行更新，指向的则是每一个相邻的两个同样word的pair，这样肯定能够想找到最小的距离

9.20 复习

这里的两个题是求两个数组的交集的，这种题有三种做法，首先就是用HashMap/HashSet，这种就很简单；然后就是，对于数组进行排序，然后一个一个比较就好，这种很直观；另外就是，对一个数组进行排序，然后对另一个数组的每一个元素，都在排好序的数组中进行binary search，找到了就算交集

349. Intersection of Two Arrays. 复习；这个题目用Set去做，首先把第一个数组的所有元素add进set中，set可以去重；然后再弄一个Set，遍历第二个数组，如果第二个数组中的一个元素被set所包含，那么就直接add到新的Set中；最后这个新的set就是结果了

350. Intersection of Two Arrays II. 复习；这个题目和上一题相比，对于重复出现的element也要包含进去，那么如果还用这个思路的话，就可以直接maintain一个HashMap，其中key就起到记录元素的功能，而value则是计数重复的次数；对于第一个数组去初始化这个HashMap，然后第二个数组的每一个数都去HashMap中检查，只有在存在这个key并且value > 0的情况下，才能算作结果；而这个时候应该去对value进行更新，每次减1

9.22 复习

****这里是所有关于N Sum的题目，基本上的方法就是双指针相向而行进行各种遍历

1. Two Sum. 复习；最经典的题目了，用HashMap即可，注意各种假设

15. 3Sum. 复习；这个题目用双指针相向而行；因为本来就是O(n^2)，排序的话不超出时间

18. 4Sum. 复习；跟前面一个题一样，外面再套一层即可

16. 3Sum Closest. 复习；这个题目就是3sum的变种，每次有了新结果和全局进行比较就可以了，方法还是通过双指针相向而行来减少复杂度

259. 3Sum Smaller. 复习；这个题目仍然是3Sum的变种，利用双指针相向而行做即可；这么做的话，对于每一个相加的和，如果它小于target的话，那么就可以增加计数；但是这里的计数可以不仅仅增加1，因为对于i、left、right来说，如果这三个index满足，那么对于所有小于right的index，如果作为right的话其实都满足，而这些index可以从left + 1开始一直到right，因此count += right - left就可以了

923. 3Sum With Multiplicity. 这个题目也是3Sum的一个推广，仍然可以用双指针相向而行的方式，先排好序然后这样做就好了；在内层循环里要注意的就是，对于可能重复的情况要进行统计，统计好重复个数后，相乘可以获得所有的组合情况，这里的相乘的部分需要进行额外注意；然后需要mod一下才能返回结果；这个题目可以用其他更简单的方法做，比如用map去做，当然也可以用bucket去做，在discussion里面都有

167. Two Sum II - Input array is sorted. 复习；这个题目既然给了一个sorted的array了，那么找两个相加和为target的数，就直接双指针相向而行就可以了，因为利用sorted的性质，这种遍历方式肯定能够越来越接近目标

170. Two Sum III - Data structure design. 复习；让设计一个data structre来做Two sum；那么就maintain一个list用来放数，一个map用来放数和统计重复出现的次数（其实不需要list，因为map.keySet()就可以起到同样的作用）；然后就完成了添加工作；在给一个target进行检查的话，就直接一个一个遍历keySet里面的所有number，然后用target去减number得到complement，然后去map里面找是否存在complement，如果存在的话就是true；当然这里注意，如果complement和num相等的话，实际上map里面也是肯定存在的，因为complement本身就是num，但是如果num的数量只有1的话，实际上是不能组成target的，所以这种情况下要看统计的个数是不是大于1

653. Two Sum IV - Input is a BST. 这个题目有三种做法，一个是用HashSet做，其实就跟一般的two sum一样；一个使用inorder遍历BST是sorted array做，这个得到了一个sorted array然后双指针做；还有一个方法是用binary search去做的；看这个discussion即可https://leetcode.com/problems/tw ... choose-one-you-like

楼主太强了，学习一下

楼主加油

9.23 复习

****首先是三个和wiggle有关的题目，其实就只是包装个样子，本身的方法还是不一定一样，一个大一个小就是

280. Wiggle Sort. 复习；这个题目是最简单的wiggle sort，只需要不断去检查，对于奇数位置的元素，是否比它前面的大（或等于），对于偶数位置的元素是否比它前面的小（或等于）；如果违反了规则的话，那么把当前元素和它前面的元素给swap一下就可以了，这样就正好满足；另外就是，虽然这里要求需要比两边都大，但实际上只把当前的和前面的额操作即可；因为比如当前数是奇数位，比它前面的小，比它后面的也要小，这样就两边都不满足了；那么这里和它前面的进行swap，实际上现在就相当于是，当前奇数位肯定比它前面的大，但是后面的不确定；那么继续遍历就可以了，因为遍历到后面的时候，如果后面的这个比当前的大，那么继续swap就好了；总之肯定随着往右遍历都会解决到的

324. Wiggle Sort II. 复习；这个地方需要注意一下，方法是对给定数组排序，然后从前往后，index为奇数的位置，从大到小放置元素；从后往前，index为偶数的位置，从小到大放置元素；剩下的地方给mid；要区分的就是，index的奇偶和物理意义上的奇偶实际上是不一样的

376. Wiggle Subsequence. 复习；这个题目本质上当然还是一个DP的问题，套着一个wiggle的外壳；dp的话是比较典型的两个dp数组然后相互作用的；up数组的up[i]表示，从0到i位置，最长的wiggle subsequence并且满足subsequence的最后一个元素比倒数第二个元素大；down数组的down[i]表示，从0到i位置，最长的wiggle subsequence并且满足subsequence的最后一个元素比倒数第二个元素小；那么induction rule就是，up[i] = down[i - 1] + 1和down[i] = up[i - 1] + 1，这是因为，如果这是一个wiggle subsequence的话，且最后一个元素比倒数第二个元素大，那么倒数第二个元素肯定比倒数第三个元素小，所以这就是两个dp数组的induction rule的相互作用