5.回文子串 动归解法,将问题视作两个串的公共子串,有二维和一维的解法,两个子串的位置对应上了才是回文串。
单调栈问题,正序遍历和倒序遍历 正序遍历时,栈内保留的是待更新元素 倒序遍历时,栈内保留的是可能会用于更新别人的元素
-
分糖果(10.05) 明白正序倒序遍历的含义(尝试都在正序一次完成,发现无法完成。错误的想法是因为,只注意到向左向右看,没注意到不管向哪看,都依赖前方数值,要求已完成更新),且最后为什么是取较大值
-
11.盛水最多的容器(11.11) 双指针,理解的关键在于——为什么移动较短的一侧,为什么较短的一侧不需要再和其他水柱考虑高度。 一样高时,不管往前移是得到一个更高的柱子还是得到一个更矮的柱子,盛水量都是减少。(?但)
-
222.Count Complete Tree Nodes(10.26) 位运算,二分法(解法启发对mid值上下取整的思考) mid取上整可用
mid = (l+r+1)/2或mid = l + (r-l+1)/2,取下整则为mid = (l+r)/2或mid = l + (r-l)/2。默认/符号表示向下取整,JS中使用取整函数。 -
74.Search a 2D Matrix(10.27)
二分法取整出现死循环问题(该问题出现于while的进入条件为
while(l<r),即不取等号;取等号的写法能避免上下取整导致的死循环问题)low=mid(即if的判断条件是mid>target)mid应该向上取整;high=mid(即判断条件mid<target)应该向下取整。 另一种while循环的写法可以避开对mid的上下取整问题,如下。但是对于LC74这样的问题,目标值不会出现,而是要找到所有小于target的最大数,则使用while(l<r)比较直观方便,退出循环时l===r,此时l指向的就是要找的值,或者这个数不存在,指向边界。
while(l<=r){
if(nums[mid] < target){
l = mid+1;
}
else if(nums[mid] > target){
r = mid-1;
}
else{
return mid;
}
}
//或有重复元素时,查找第一个出现(或最后一个出现)的目标元素
while(l<=r){
if(nums[mid] < target){
l = mid+1;
}
else if(nums[mid] >= target){
r = mid-1;//第一个出现
}
}-
240.Search a 2D Matrix II(10.28)
二维查找问题的二分法。 确定一个完全有序的部分,选定可以在这个部分查找,或排除一个部分的判定条件。 -
81.搜索旋转排序数组II (10.30)
首先遍历部分数组找到中断点的方法时间复杂度O(n),已经不属于二分查找的可能
本题正确二分法的思路是:找到局部完全有序的部分,因为在完全有序的局部判断是否能存在target是容易的,所以可以有着一点写分支,缩小查找范围。
需要注意的是,这一判断条件需要足够充分,并且注意重复元素造成的影响 -
33.搜索旋转排序数组 (10.31)
将nums[l]===nums[mid]的情况单独写出,更便于理解,因为nums[mid]和target比较过了,所以如果有一样的值直接跳过就可以,故l++。 -
4.寻找两个正序数组的中位数(11.10) 使用二分法实现
O(log(m+n))时间复杂度的解决方案,首先 是切入点,不是对两个数组二分,而是针对K的中值,将K减半。第二点关键的是,如果某个数组没有第K/2个数字,那么我们就淘汰另一个数字的前K/2个数字即可。 有没有可能两个数组都不存在第K/2个数字呢,这道题里是不可能的,因为我们的K不是任意给的,而是给的m+n的中间值,所以必定至少会有一个数组是存在第K/2个数字的。
是否需要使用 visited辅助数组的问题,访问过的元素如何标记,才能更方便于整个任务的完成
- 130.被围绕的区域(11.03) 区分开被围绕的区域和没有被围绕的区域,本题从边界出发作为切入点可以省去很多麻烦
- 200.岛屿数量(11.04)
- 207.课程表 (11.08) 只用 入度数组 记录入度的变化即可实现“前驱已完成”的效果,而不需要建立前驱数组,对其中的元素进行删改
- 208.课程表Ⅱ (11.08) 类似上题,返回拓扑排序数组,只需要每次出队后再保存即可。
- Largest Number(10.06) 字典序排列字符串的应用,自定义排序函数的使用。证明未完成
- 16.最接近的三数之和(11.17)
虽然是求绝对值,但是以下双指针的移动方法,不管是大于
target还是小于,都是在往靠近target的方向移动,因此不会遗漏。
- 80.删除有序数组中的重复元素Ⅱ
每个元素最多出现两次,所以只需要当前元素和
nums[left-2]比较即可,已有元素的前两个都不相等,就可以加入当前元素。不用保留原数组前两个元素,再看看是否出现了3次