today's mission: 209-198
209: Minimum size subarray sum
这个题目求minimum size, 也是利用的sliding window的思想， 但是是用的变长window. 利用两个指针，left and right 代表一个虚拟的window, 一开始移动right， 如果达到要求， 移动left来求最短的size.
这个题目也有需要特别注意的细节，如果array里面所有元素加起来都没有sum大的话，是需要返回0的，这种特殊情况需要特殊处理。
208:
207: 上一篇总结过，略
206: reverse linked list
iterative 和 recursion的方法都需要掌握，iterative的方法和recursion的方法处理上有一些区别， iterative的方法实质上只进行了一次变换，而recursion每次需要进行两次变换。 虽然简单，但是还是要注意细节。
205： isomorphic string
这个题目要注意
1， 如果只看题目给的列子, 只能看出是s1 到s2的映射一一映射，但是提交后发现也需要s2到s1的映射， 所以最直接方法是用两个map
2. 题目是针对string， 256个字符， map的对象也是char，当map的对象是char的时候，map是可以转化成int array来做的，节省时间和空间。
204：Count prime
这个题目利用的算法在应用密码学里面学过，
1. 需要一个额外的数组，这个数组在这个题目里面必须用heap, 因为可能数字很大， 超过stack的范围；
2. 所需要进行标记的是non prime的数字，而不是prime的数字，所以只能用一个count = n-2，碰到一个非prime就count--，
3. 为了避免重复运算，只有需要碰到一个non-prime的时候才需要进行对后面数字进行判断。
203: remove element in linked list
这个题目需要注意：
1. 可能head要被remove, 所以 需要dummy head来辅助处理corner case
2. pre对于遇到需要remove的element和不需要remove的element处理起来是不同的，因为如果遇到需要remove的element, 删除cur，此处的pre仍然是下一个cur的previous 节点。
202: Happy number
这个题目虽然不难，但是是很有意思的一个题目， 看一个数是否在计算过程中重复出现，可以用set来实现。
201： Bitwise And of Numbers Range
求一个range里面所有数的&的结果， 这个题目分析发现其实就是找这两个数的相同前缀bits, 因为其他不同位&之后是一定会为0的，找到相同前缀bits然后后面所有位补0就是结果。
200 : Number of Island
很典型的二维矩阵 dfs + mark visitI 的题目， 上下左右四个方向进行搜索，不需要额外开辟新的visit的数组，可以以矩阵里面的元素代替，如果visit过了，直接将该元素变成’0‘就代表visit过了。需要对矩阵里面所有非0的元素进行dfs.
199 : Right sight view of a tree
这个题目其实是考察的树的level order traversal, right sight view就是每一层的最后那个元素。
191- 173
No comments:
Post a Comment