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

9.8 做题

721. Accounts Merge. 图+DFS；先构建好图，构建图的方法就是用Map，key是当前节点，value是当前节点的相邻节点Set；然后对于所有节点分别进行dfs，dfs的流程就是，对于当前节点首先添加到list当中，然后对它所有的相邻节点都进行dfs，也都是相同的recursion操作；如果对于一个节点的dfs成功的话，就说明完成了一个account的merge，接下来就可以去其他节点进行dfs了；当然这里需要一个visited Set，避免dfs到已经被merge过的节点

543. Diameter of Binary Tree. 这个题目就是一个基本的tree的recursion题目，要求一个节点到另一个节点的路径长度的最大值，这个路径可以是经过root也可以不经过；那么首先maintain一个全局最大，然后进行recursion；recursion的方法，首先想left和right两个子树进行recursion操作，获得left和right子树返回上来的值，这个值就应该是left子树的包括left节点（子树的root节点）在内的最大路径的长度，right也一样；那么有了这两个值，他们相加实际上就是当前包括当前root在内的最大路径长度，把这个长度和全局最优进行比较更新；然后recursion往上的return就应该是，包括当前节点在内的，left和right取一条路就可以了（这个题目和之前的一个题目很类似，也是和全局最大比较更新的时候取left+right，而往上返的时候取left or right）

636. Exclusive Time of Functions. 这个题目应该关注一下如何讲给定的数组中的字符串进行一些转换；这里把每个字符串转换成了一个Log对象，分别有三个field：function_id, isStart, time；然后遍历给定数组，根据每个string建立一个Log对象，然后如果这个log是start，那么就push到stack里面；如果是end，那么就从stack中poll出来最上面的那个，然后在结果数组当中寻找到对应的记录时间的位置，加上当前遍历到的log和poll出来的这个log的时间差（注意要加1，这是因为就算start和end的time一样，也相当于是有了1个时间）；然后这个处理好之后，由于这是单线程cpu，这个处理好的function在运行时前一个start的肯定在休息，那么就需要在结果数组中对应记录前一个start的log的时间，减去刚刚处理好的log的时间，这是显然的；这个题目用stack的方法，start就push，end就poll，然后进行各种对应相关操作

896. Monotonic Array. 这个题目就是遍历array，然后按照情况进行讨论就可以了；记录下来previous的那个元素，然后和当前遍历的进行比较即可

986. Interval List Intersections. 这个题目是给了两个array的集合，让找他们的交集（同一集合中的array互不相交）；那么方法就是挨个遍历两个集合里的array，按照顺序一个一个遍历；每次遍历到a集合中的第i个array和b集合中的第j个array，然后对于这两个array看看怎么找到交集：如果这两个array的左端点的最大，要小于等于两个array的右端点的最小，那么就说明这两个array有重合，重合的部分就是从最大左端点到最小右端点的范围；然后比较完以后，i或者j需要往后移，去讨论下一对array，当然这里不能都移动：因为可能出现当前的某个array太大了，即使跟这个算完了intersection后，后面还有一大段；所以就是，如果这两个array的哪一个的右端点正好是最小右端点，那么这个对应的index就应该往后移

9.9 做题

825. Friends Of Appropriate Ages. 建立HashMap，key是age，value是该age在给定数组中出现的次数；然后遍历所有单个的age，找出每个age的pair（即对map的keySet进行双重遍历），然后根据题目要求看看第一个age能不能给第二个age发送朋友请求；如果可以的话，那么结果就需要加上这两个age的出现次数的乘积，这就相当于是所有第一个age的人都可以向第二个age的人发送朋友请求，所以两个都要乘起来（如果这两个age相同，那么实际上就是这个age的人互相乘，也就是a * (a - 1)）

415. Add Strings. 这个题就是对两个String进行从后往前的遍历的基本操作；要求implement一个加法，给了两个数据的话，肯定都是两个要求从后往前进行，这样比较方便计算carry；这里的两个指针分别从后往前同步走，每次循环，获取到两个String的当前位置上的数，两个加起来再和carry相加取个位数给append到res中，然后取十位加到carry里面；但是如果两个String不够长的话，那么如果指针同步走肯定会出现负数，那么如果指针式负数位置的话，就意味着不需要从该String获取数了，直接去0即可；最后把res给reverse过来就好了

468. Validate IP Address. 这个题目完全就是体力活，完全按照题目要求把代码写出来就好了，其他没那么复杂，看这个https://leetcode.com/problems/va ... ava-Simple-Solution；把每一个步骤要做的都做好即可

708. Insert into a Cyclic Sorted List. 这个是一个linkedlist的操作题目；从给定的head出发，遍历整个list，找到合适target插入的位置：1. target的值正好等于当前node；2. target的值在当前node和后一个node之前；3. 当前node是最大node并且target更大；4. 当前node是最小node并且target更小；这些都是可以插入的位置，插入就可以了；如果没有找到插入位置的话，就干脆在给定的head后面进行插入即可

463. Island Perimeter. 这个题目就是一个矩阵遍历的题；对于每一个island点，首先周长加4；然后对它的上下左右四个方向进行检查，如果发现某个方向有邻居island，那么周长减1；这样遍历完就好了

9.10 做题

674. Longest Continuous Increasing Subsequence. 这个题目当然本质上还是DP，不过可以用这样一种方法去想；就是说，遍历给定数组，如果当前的元素比它前一个大，那么就需要计数+1；否则的话，当前元素比它前一个小，那就可能需要另起炉灶，因为就比如这样：[6, 7, 9, 1, 2, 3, 4, 5, 11, 13]，这种的话，扫描到了1要比前一个9小，而从6到9已经积累了长度为三的递增序列，那么从1到5的话长度为5，肯定需要重新开始；这时就可以，maintain一个全局最大的max，让max去记录当前积累下来的最大，比如现在就是3；然后计数器归1，可以计数“以当前元素为最大元素的递增子序列的长度”，这就是计数器的物理意义，也就是dp数组的dp[i]的物理意义

958. Check Completeness of a Binary Tree. 这个题目有两种做法，一种是recursion的方法：基本思路是，在recursion的过程中记录计数当前tree的总共Node数量，同时检查更新当前tree的最后节点的index，因为如果这个tree是完全二叉树的话，那么每一个点在整个tree的index都应该遵循，如果root为i，那么left就应该是i*2，right就应该是i*2+1；如果那么每次recursion的时候都应该往下传递下面这个节点根据当前节点的index而应该是的index，并且每次recursion时全局最大的index也应该和当前节点index检查更新，并且记录总节点个数，recursion结束时两者比较看是否相同；另一种是BFS层级遍历，逻辑就是，如果这是一个完全二叉树，那么层级遍历的过程中，不能出现这样的情况，即如果已经发现一个节点是空节点，那么继续层级遍历的话，要么以后的节点都是空的，要么如果出现了一个非空的节点，那就说明这是错的，因为这就相当于中间出现了气泡一样

824. Goat Latin. 这个题目就是单纯的操作，把给定String给split成String数组然后一个部分一个部分按照要求，该怎么操作就怎么操作，判断条件等等

528. Random Pick with Weight. 这个题目的就是要求，给一个数组要随机选出index，当然不是随便选，而是把index对应的value当作权重，然后再随机选index；由于value是权重，比如[1, 3, 2, 4]这个数组，0这个index就有十分之一的可能，1这个index就有十分之三的可能，2这个index就有十分之二的可能，4这个index就有十分之四的可能；这样的话，首先要用Random的对象去generate出来一个随机数，随机数的范围应该是从1到所有权重的总和，也就是数组所有value的和，也就是1到10；那么现在generate出来了一个随机数，比如是5，怎么根据这个随机数去判断应该选择哪一个index呢？那么这里的做法是这样，算出数组的prefix和，也就是[1, 4, 6, 10]这个数组，那么generate出来了5的话，正好落在4到6这个区间，那么取后面的那个权值和的index也就是2；这是因为，prefix数组相当于把整个权重分成了0～1，1～4，4～6，6～10这几个区间，每个区间的长度对应给定数组的value也就是权重；random出来的随机数是随机的，落在这几个区间的概率正好对应了权重，这样就可以实现要求了；有了随机数以后，就去prefix数组里面找它所属的区间即可，可以挨个找，也可以用binary search找

536. Construct Binary Tree from String. 这个题很有意思，是给定一个按照一定规律的String，让重新建立一个Binary Tree；那么这个就需要根据String的规律，判断遇到什么字符的时候去创建TreeNode，遇到什么字符的时候去建立左右子节点，遇到什么字符的时候往上返回值；maintian一个全局的index；在recursion的时候，比如给了一个String如下：4(2(3)(1))(6(5))，用recursion的方式去改变全局的index来遍历这个String；如果遇到了数字，解析出来准备new一个TreeNode，这里注意数字可能是两位数三位数，这样就要用while循环把当前这部分的数字都取完，然后解析成数字，也就是new一个TreeNode以解析出来的数字为值；如果遇到了左括号，就说明左括号后面的数字肯定是当前recursion层对应的root的子节点；如果是紧接着的遇到了左括号的话，那么肯定是左子节点，用recursion的方法做；如果做完了这个左子节点，随着index的往后，又发现了一个左括号，那就说明这就是右节点，也用recursion方法完成；那么如果遇到的不是左括号，或者index遍历到头了，就说明要往上返回当前的root了；这里我用recursion做，当然这种一幕肯定也可以用iterative的方法，用stack或者bfs类似的方法都可以做

9.11 做题

416. Partition Equal Subset Sum. LC的discussion看这个：01-knapsack-detailed-explanation. 这个题目是0/1背包问题，用DP去做，问题的本质就是，给了一个集合，看看这个集合中是否能够挑出来一些数字，使得这几个数字的和正好等于给定的target；对于这个题目来说，那就是给的这个数组，找出是否存在其中的几个元素，使他们的和，正好等于数组全部元素的总和的一半；那么用DP的方法处理0/1背包问题的话，是需要一个二维的dp：dp[j]，i就表示给定数组的index，j则表示从0到target的累加和，那么dp[j]的物理意义就是，看看数组的前i个数字中，是否能找到若干个，使他们的和加起来等于j；那么最后要找到的就是，看看数组的所有数字中，是否能找到若干个，使他们加起来的和等于target；那么induction rule就是，对于当前的这个数组元素，如果不取的话，dp[j]就应该等于dp[i - 1][j]，如果取的话dp[j]就应该等于dp[i -1][j - nums]；因为不取的话其实就相当于没有这个数组元素一样，如果取的话，那么暂时的目标和j就应该减去取到的这个nums；因此就是dp[j] = dp[i - 1][j] || dp[i - 1][j - nums]

622. Design Circular Queue. 要求实现一个Queue但不是普通的queue，而是首尾相连的；那么就是说，FIFO的时候，比如现在有1，2，3，4这几个在queue中，如果pop的话就是从1开始，offer的话则是从4的后面；那么就希望是这样，pop一次变成了2，3，4这种，如果再offer5进去的话就变成这样5，2，3，4；那么如果再pop的话，或者单纯检查Queue最前面的元素的话，仍然是2；这就相当于一个Queue的数据结构，只不过有一个头指针和尾指针，如果在尾部offer完了，尾指针会自动跑到前面空余的地方去；因此maintain一个array，一个front指针和一个rear指针，同时记录当前Queue中的元素；如果offer的话，那就是在rear部分offer，rear要加1，然后array[rear]等于要被offer的数；当然由于需要首尾相连，因此rear不能单纯的加1，比如现在rear在3的位置，而0的位置被pop出去了，那么rear+1就会out of bound，因此rear再往后应该等于0才对，所以就是说，应该是rear = (rear + 1) % array.length，这样就可以循环进行了；那么对于pop的操作也是一样，只是对front操作就可以了；其他的API都很容易实现，利用count就好了，count就是offer的时候加1，pop的时候减1，验证是否为空为满就是count是否等于数组长度，或者是等于0

885. Spiral Matrix III. 这个题目可以算是矩阵操作题目，只要搞清楚从起始位置开始，到底一步一步是怎么走的，走多长、哪个方向就好了；这个题目就是，从起始位置开始，转着圈走，也就是先往左、再往下、再往右、再往上走，但是如果每次走的步长一样的话，那就一直原地不动了，所以每次走的步长有所不同：每当要往左走的时候，走的步长应该是上一次走的步长加1；每当要往右走的时候，步长也应该是上一步加1；只有这样才能不断扩大自己走的范围，最终完全覆盖住给定的矩阵；那么这种问题一般都是实现给一个二维固定数组，作为direction{{0, 1}, {1, 0}, {0, -1}, {-1, 0}}；然后从当前点开始，一开始是往左走，走当前的步长，然后往下走；然后往右走的时候，当前步长加1，再接着往上走；就一直这么走，步长根据方向去看看是不是要改变，然后每次走到新的位置，都看看是不是在矩阵范围之内，如果是的话，把坐标添加进结果里面就好了

678. Valid Parenthesis String. 这个题目看上去有多种方法，iteraitve就可以做，不过代码很复杂，这里我先用recursion/DFS的方法做的；就是说现在的字符串有左括号、右括号、星星，星星可以作为左右括号用，也可以作为空；那么检查的方法就是，maintain一个count；如果遇到左括号，count++，表示现在有很多可以匹配的左括号；如果遇到右括号，count--，表示现在有一个右括号跟左括号匹配了；如果count在某一个步骤小于0的话，就说明左括号不够用了，肯定错；如果遇到星星，分三种情况讨论，也就是上面的三种；体现在recursion当中就是，下一步的recursion里面要么count增加了说明星星作为左括号，要么count减少了说明星星作为右括号，要么count不变说明星星为空，但是当前的index肯定要往前走的

489. Robot Room Cleaner. 这个题目是非常好的题，其实思路很直观，但是很难想像出这个代码应该是什么样子；就是给一个机器人，有四个API分别是向左转、向右转、前进、打扫；那么现在假设机器人在0-0位置上，首先0-0位置需要打扫，然后在一个Set里记录下来这个0-0；之后因为有四个方向，那么就做四次循环，每次循环指向一个方向，那么当然还是需要一个方向矩阵{{0, 1}, {1, 0}, {0, -1}, {-1, 0}}；那么每次循环取一个方向，首先根据当前位置算出接下来要去的位置，也就是当前坐标加上当前的方向矩阵的pair；然后取Set里面看看，这个位置是不是已经visited过了，并且调用move走一下，如果走成功了说明没有障碍，并且robot实际已经到了前一个点了；到了新的点以后，在recursion调用当前的这个函数进行处理；处理好之后，robot在新的点要返回原来的位置，也就是转一百八十度，然后走，然后转一百八十度（这里是为返回原来的方向）；接下来在这次循环的最后，turnRight一下，因为需要改变方向；这里注意，并不是说，四次循环调用方向矩阵的pair就能自动改变方向了，只是用方向矩阵的四次循环，能够帮助提前算出来下一次的方向，从而方便去Set里面提前验证而已；真正改变方向的还是循环最后的turnRight；然后curDir也需要作为参数传入，因为并不是每一次都得是先向左，如果这个robot本来现在是想下的，那么这个方向也应该向下走才对

9.13 做题

477. Total Hamming Distance. 这个题目是让求给定一个数组，把里面元素都变成二进制表达，然后看看相互的二进制表达有多少位数不一样，然后把所有不一样的都给算出来；那么最一般的肯定就是两两进行比较，用两个for循环，然后每一对的二进制表达的不同的数量都累加起来，这样当然就比较麻烦；这里用的方法就是，因为二进制表示其实就是32位数，那么首先对32进行循环；那么在循环内部，再对数组进行循环；对于数组里的每一个元素，都让它右移当前位数（从0到31位的外循环），然后和1进行取&操作，这样正好能获取当前右移后的数的最后一位，如果是1就是1，是0就是0；那么通过这两层循环，实际上就把这些数组里的数字的全部32位数都给过了一遍；那么每次取到当前最后一位数字以后，就都加起来（其实就是加1或者加0）；那么内循环结束后，这些加起来的数字，就是这些数组元素在当前位置上为1的个数，那么用数组长度减去这些个数就是当前位置上位0的个数，而1的个数和0的个数相乘，就是这所有元素在这个位置上的不同的数量；然后对32循环就可以了

567. Permutation in String. 乍一看，可以用dfs加上strstr的方法，当然这个太麻烦；最好就是用滑动窗口+HashMap；首先建立一个HashMap，里面的key对应给定的s1的字母，value则是该字母在s1中出现的次数；同时maintain一个滑动窗口，什么时候滑动窗口中圈出了所有s1中出现的字母，并且滑动窗口的size正好和s1的length相等，那么就说明找到了结果，否则的话滑动窗口继续滑动；具体来说，这里首先是快指针往前走，然后如果遇到s1中字符的话，那就对应map中的value减1；如果map中的某个key因为快指针的移动而变成了0的话，那就说明有一个字母完全被发现了，那么就需要count--（这个count就是key的数量）；当count为0的时候，就说明当前滑动窗口已经完全包括了s1的全部字母，那么验证是否窗口长度和s1相同，如果相同就是true，不同的话，慢指针往前走，如果略过了s1中字符，那么count和map中的value也要相应改变

449. Serialize and Deserialize BST. 这个题目就是非常典型的Serialize和Deserialize的题目，给一颗树，让用某种方法以String的形式记录下来，同时这个记录的String以后还能够再用某种方法变回Tree去；那么对于这个Tree，想把它变成String的方法很简单，就用某种方法遍历一遍比如preorder，遍历的时候把每一个节点的值都记录下来，这里就成了一个String；然后再Deserialize回去的时候，对于这个String，想要搞清楚取什么才是root取什么才是left这种，那么光打印还不行，在变成String的时候得进行分割，比如打印下来一个节点的值，后面就要跟着一个regex比如逗号作为分割符，这样在以后比较方便；那么变回去的时候就可以根据regex进行分割，然后把分割好的一个一个数都放进一个Queue里面；对于这个Queue来说，在当前recursion层，poll出来的那个，如果不为空，那么就new一个root的TreeNode，然后对于root的left和right都可以recursion做，因为queue已经poll出来了一个；那么如果位空的话，打印的时候应该打印#，这样变成Tree的时候就可以在poll的时候，如果是poll出来了一个#，那直接return null就好了

921. Minimum Add to Make Parentheses Valid. 这个题就是遍历整个String，遇到左括号的话，说明可能需要添加右括号，那么right先++；那么如果遇到了右括号，先看看有没有等待添加的右括号，如果有，说明这里就可少添加一个了，所以right--；否则的话，说明右括号现在多了，那么left++；那么这里的顺序不能颠倒，不能先处理左括号，因为左括号可以暂时多，但是右括号不行

480. Sliding Window Median. 这个题目其实和求流数据的median差不多，这个滑动窗口在数组上移动的过程，其实就是数据流的过程；那么依然是maintain两个heap，一个minheap一个maxheap，分别放置比median大的数方便取最小，和比median小的数方便取最大；具体过程还是和那个流数据的median差不多的，但是区别就是，如何把滑动窗口转化成流数据的创造；具体看一下代码就好了，遍历数组的时候，如果往前走到一个新位置，那么重新求一下median，然后把窗口末尾的元素remove掉，然后新加上新遇到的元素即可

9.14 做题

1027. Longest Arithmetic Sequence. 动态规划题目加上遍历和HashMap；这个题目的思路就是，用HashMap去存储，以index为i对应的array元素为终点，间距step为d的最长序列的长度；所以要有一个DParray，DParray的每一个元素都是一个HashMap，对应给定的array的元素，每一个HashMap都是以对应元素为终点的，key是step，value是最长序列长度；那么遍历给定array，对于每一个元素x，都回过头来遍历它前面的array的元素y；对于当前的x和y，x-y等于d，那么现在就要验证以x为终点，step为d的子序列有多长，那么这里最小肯定就是2；然后如果以y为终点、step同样为d的子序列是之前求过的（即dp[j]中有d这个key），那么现在加上了一个后面的x，就相当于是原来的长度加1；而如果之前已经求出来了以x为终点step为d的子序列的话，同样把这个值拿出来；那么两者进行比较，哪个大就把哪个放在当前的x对应的HashMap中，最后和全局最大比较更新即可

694. Number of Distinct Islands. 这个题目本质来说，其实和Number of Islands一样，区别就是这里需要记录一个Distinct的island的数量，那么有些island可能形状是相同的，只是不同位置，这种island就应该被看作是相同的island而不能重复计数；所以思路就是，如果能够在dfs的时候，每当完成一个island的寻找之后，都能够把这个island用某种方式给表示出来，然后把这个island的某种表示给放到Set里面，这样如果有相同的话就可以用Set来进行去除了；那么这里使用的把island的表示方法就是，用一个String去表示，String包括了在dfs的过程中，上、下、左、右、后退的这种操作；因为这里的dfs过程实际上是从grid点为1的开始，去四个方向进行尝试的，最终能够尝试完成然后再back回来，那么如果两个island是相同的，那么他们尝试的路径也是相同的，也就是上、下、左、右、后退的顺序一定相同；因此可以用这种方式去表示，注意后退操作一定要添加进来https://leetcode.com/.../Java-very-Elegant-and-concise...

670. Maximum Swap. 这个题目用bucket来做，就是实现准备好10个长度的数组，然后每个元素代表从0到9；遍历给定数，让这个bucket的对应index记录下来给定数中数字的位置；然后再遍历给定数，然后从9开始，如果bucket中记录下来的位置，要比当前给定数的当前数字的位置靠后，并且这个位置对应的数字要比当前数字大，那么swap一下就好了，然后题目就结束了，因为只需要swap一次

935. Knight Dialer. 这个题目没怎么懂，不过这里的代码很简单；对于每一个手机键盘的点来说，按照马的跳法，0能跳到4和6，1能跳到6和8……；首先构建出从0到9的所有这种点的二维数组；然后用DP的方法，从1到N进行累计求，这里的N就是最大用马跳完以后可以走的位置数量，比如跳一次实际上就是不跳，跳两次就是从当前位置转到下一位置，跳三次就是从当前位置跳下一位置再跳下一位置；那么对于第几次的位置来说，结果都是依赖于它前一次的结果的；那么就遍历刚刚建立好的所有点的二维数组，然后假设现在所有十个点的这一次的数量都存储在了dp数组里，然后下一次进行的时候，都有一个临时的数组，记录这一次跳的次数；总之这个题我还是不太懂

865. Smallest Subtree with all the Deepest Nodes. 这个题要求找到一个subtree，使得它包含了这整个tree的所有最深的node，找到这类subtree中最小的那个；首先整个tree肯定是一个这种tree，然后就希望往下找，其实就是获取左右子树的深度，如果左边比右边深，说明最深的node肯定在左边子树，那么这个要返回的root就可以暂时放到left node上；如果右边比左边深，同理那肯定就是rightnode暂时；然后再进行recursion对当前节点；那么如果两遍一样深，说明最深的node有的在左右的在右，那么就返回当前root就好了；这里实际上helper function是返回的Pair，代码比较巧妙https://leetcode.com/problems/sm ... uss/146808/One-pass

9.16 做题

最近不太想做太多新题了，因为接下来可能会面临很多面试，我觉得对旧题目经典题的理解和巩固总结更加重要，接下来每天都要复习更多的旧题目，新题每天就做两道好了

632. Smallest Range Covering Elements from K Lists. 这个题目是greedy的思路：就是首先初始取给定的这些数组的最开头的那些元素，然后找到这些元素的最大和最小，算出来range；然后对于最小的那个元素，在它所在的数组里面往后进行移动，移动一个位置（因为每个数组都是sorted，所以往后移的话，肯定最小的就会增大）；那么移动完成以后，由于最小的变化了，那么可能range就要重新改变了，这时就要重新找到这些元素的最大和最小，重新算range，然后重新移动当前最小的元素，在所在的数组里面的往后一个位置；就这样一直走下去，直到走完；通过这种Greedy的思路，就可以规避很多不需要的组合的查找，从而加快速度；那么具体来说，这里需要用一个PriorityQueue来进行实现，这个minHeap存储的是给定二维数组的坐标（也就是处于第几个list的第几个index）；那么一开始往里初始化offer的话，就是每个list的第0个元素，也就是（i，0）；然后每次poll的话，都是poll的当前位置元素在给定二维list里面的值的最小的那个；而每次往里offer的，如果当前poll出来的是第i个list的第j个index的元素的话，offer的就应该是第i个list的第j + 1个index的元素；那么每次offer和poll的同时，都可以对range和min和max进行相应更新即可

987. Vertical Order Traversal of a Binary Tree. 这个题目和之前的那个314不同的就在于，这里要求输出的list的子list里面的元素需要按照这个Tree的层级以及数值大小来判断，因此高层的node总是有较高的优先级；所以这里就按照HashMap<Integer, TreeMap<Integer, PriorityQueue<>()>()>()来做了；利用TreeMap去排列Tree的层级，然后再去dfs的方式往下进行；这个讨论的非常的好https://leetcode.com/problems/ve ... orityQueue-Solution

1004. Max Consecutive Ones III. 这个题就是滑动窗口，找出最多拥有K个0的最长子数组；那么每次快指针都往前走，如果遇到了0，那么count++；如果count++加到了count大于给定的K的话，那么快指针就要停下来，让慢指针往前走，如果慢指针遇到了0，那么count就要减1；就这么一直做下去知道count不大于K；最后每一次快指针往前走的时候，都需要用快的减慢的进行比较更新

9.16 复习

这一次复习了array的比较基本的指针问题，这里是利用快慢指针去进行remove类问题的四个题目1) Remove Duplicates from Sorted Array I, II, Remove Element, Move Zeroes

26. Remove Duplicates from Sorted Array. 复习；这个就是用快慢指针来去重的题目，块指针是当前的指针，每次都往前走；慢指针是返回结果需要的指针；当块指针的元素和慢指针相同时，说明现在发现了重复的元素，那么快指针一直往前走；而当两个不一样的时候，即说明快指针的元素应该被保留，所以就应该，把它移到慢指针后面的那一个位置上，然后两个指针同时往前走

80. Remove Duplicates from Sorted Array II；复习；这个题目和上衣题有几个地方不同：fast和slow要从2开始，因为这个题肯定至少有两个元素会被返回；slow是不被包括在结果当中了；fast要和slow － 2去进行比较，这个地方其实有点难以理解，不过意思就是说，这样比较的话，实际上就是默认了，会有两个重复的元素，也就是slow － 2和slow － 1会被保留了

27. Remove Element. 复习；这个题目就是要求去除给定的target，同样用快慢指针，fast指针往前走，slow指针保留结果，这里不包括slow指针，所以最后返回的是slow而不是slow +1；如果fast当前指向的不是target，说明这个元素需要被保留，那么就把它复制到slow指针当前的位置，然后slow和fast都往前走；否则就fast往前走就好了；初始的时候这两个指针都在0的位置，因为0位置也可能是target都是不确定的

283. Move Zeroes. 复习；这个题目同样是快慢指针做，块指针遍历，慢指针保存结果；两个都从0开始，因为0位置也可能是target（也就是0）；当遇到非0元素时，需要保留，那么快指针指向的非零元素，就要和慢指针指向的swap一下；这里不包括慢指针，所以可以直接swap，然后两个一起往前走；如果是0，那么fast往前走就可以了

9.17 复习

这部分复习的是，对Array进行扫描，不过比较有难度的实际场景问题，采用的方式都可以是从左边扫过来、从右边扫过来，然后对两次扫描的结果dp数组进行处理并最终得出来的结果

135. Candy. 复习；这个题目的要求是，给一个数组，对于数组元素来说，如果这个元素的值比它相邻的一个元素的值要大，那么这个元素就应该得到更多的candy，否则就是更少的candy；那么就可以想到，对于一个处于bottom位置的元素来说，也就是如果一个元素比他两边的元素都小，那么其实给它的candy是1就可以了；而如果从这个bottom元素开始，一连着好几个连续的元素都是递增的走势，那么它们的candy就应该是1、2、3、4这样一直增加；那么对于一个处于peak位置的元素来说，也就是如果一个元素比他两遍的元素都大的话，那么就可以想象，这是一个peak，两边都是下坡，然后两边的都会有bottom存在，那么都是从bottom从1开始一直往上，因此peak需要给的candy，其实就是两边从bottom上来以后距离最大的那个，就比如说是这样0、3、5、9、8、7、6、5、4、3、1；那么9是peak，而左边从0开始距离是3，右边从1开始距离是7，也就是说1、2、3是左边发的candy，而1、2、3、4、5、6、7是右边发的candy；所以peak就取最大的那个，也就是7再加1就好了；就这样遍历数组即可；当然这样做没有推广价值，就是单纯的遍历，因为最后这个题其实也是一会儿上坡一会儿下坡，那么就可以从左边扫描一遍算是从左边上坡，然后从右边扫描一边算是从右边上坡，然后两个的最后结果取一个最大就好了

42. Trapping Rain Water. 复习；这里我使用的方法就是左边右边进行分别扫描，每次扫描的时候就相当于DP的思路和写法，每次都记录下来，当前的最大元素，然后从左到右和从右到左，我自己认为这种方法的解释就是，当我从左到右进行扫描的时候，最右边有一个最高最高的bar，肯定能够兜住所有的水，那么这时我只需要考虑左边的bar就可以了，左边的bar有多高就可以兜住多少的水，左边变得越来越高就可以兜住的水越来越高；然后从右边往做扫描的时候也一样；最后把两个bar给撤掉，其实就是取这两个从左到右和从右到左的扫描的dp数组的最小值，然后当然还要减去bar的值，这样就是可以承装水的值了

238. Product of Array Except Self. 复习；这个题目同样使用了左边右边扫描，它要求的就是，对于每个位置的来说，这个位置的元素就应该是给定数组的除这个位置以外的所有元素的乘积；那么想法就是，从左边扫描过来，扫描的就是prefix_product，也就是从位置为0一直乘到末尾位置；而从右边扫描过来的话，就是从末尾位置一直乘到0；也就是说对于dp_left[i]来说，它的值就是包括它在内的，从0一直乘到i的乘积；而对于dp_right[i]来说，它的值就是包括它在内的，从末尾位置一直乘到i的乘积；那么如果想求i的product of array except self的话，那么就是需要从0位置一直乘到i - 1，同时从i + 1位置乘到末尾，实际上也就是dp_left[i - 1] * dp_right[i + 1]，就通过这种方式就可以求出来所有的位置上的结果

9.17 复习

这里复习的三道题目分别是3) Minimum Size Subarray Sum, Summary Ranges, Missing Ranges，它们都是一些同样用快慢指针的要去检验当中的范围的题目，并不是用滑动窗口去做什么，但是用快慢指针去进行一些数的判断，最后把快指针和慢指针两个确定好取出来的这种

209. Minimum Size Subarray Sum. 复习；这个题目用快慢指针做，实际上是个滑动窗口，快指针往前走，然后prefix sum一直加；当prefix sum加到大于sum的时候，滑动窗口就需要往外吐，也就是慢指针所对应的那个元素要从prefix sum当中减出去；每次需要减的时候，都和全局最优进行比较；然后就这样一直扫描结束就好了

228. Summary Ranges. 复习；这个题目是去扫描整个数组，如果相邻的元素正好是一个一个连续的，那么就是summary起来；那么这个用快慢指针去做，慢指针指向的是连续相邻元素的开始，快指针在这些相邻元素是连续的情况下一直往后走就好；如果快指针停下来了，就说明现在快慢指针正好圈定了一个需要被summar用的ranges，那么就是要把这个ranges加到结果当中去；添加完毕以后，重置快慢指针，也就是说这两个都需要放到下一个可能的ranges中去；这里有些corner case需要检查，比如实际上这个ranges只有一个数值，或者快指针到头了等等

163. Missing Ranges. 复习；这个题目同样应该算作是快慢指针滑动窗口，这里的窗口圈定的应该是missing的ranges；这里在code里面虽然没有显式提出来快慢指针；在遍历给定数组的时候，同时maintain一个start指针，start指针是给的upper和lower的范围的；如果当前数组的元素和start相等，就说明这个没有missing；然后start始终在没有missing的情况都是++，考虑紧挨着的下一个；如果发现不相同，那肯定就是nums比start要大了，实际上就是missing了；既然missing了，那么就是start到nums - 1是missing的，这个ranges就要加到结果里；最后不要忘记可能存在的corner case，lower和upper这两头的ranges