Skip to content

Latest commit

 

History

History
83 lines (69 loc) · 5.16 KB

File metadata and controls

83 lines (69 loc) · 5.16 KB

Leetcode刷题笔记

动归

5.回文子串 动归解法,将问题视作两个串的公共子串,有二维和一维的解法,两个子串的位置对应上了才是回文串。

单调栈

单调栈问题,正序遍历和倒序遍历 正序遍历时,栈内保留的是待更新元素 倒序遍历时,栈内保留的是可能会用于更新别人的元素

贪心

  • 分糖果(10.05) 明白正序倒序遍历的含义(尝试都在正序一次完成,发现无法完成。错误的想法是因为,只注意到向左向右看,没注意到不管向哪看,都依赖前方数值,要求已完成更新),且最后为什么是取较大值

  • 11.盛水最多的容器(11.11) 双指针,理解的关键在于——为什么移动较短的一侧,为什么较短的一侧不需要再和其他水柱考虑高度。 一样高时,不管往前移是得到一个更高的柱子还是得到一个更矮的柱子,盛水量都是减少。(?但)

二分法

  • 222.Count Complete Tree Nodes(10.26) 位运算,二分法(解法启发对mid值上下取整的思考) mid取上整可用 mid = (l+r+1)/2mid = l + (r-l+1)/2 ,取下整则为 mid = (l+r)/2mid = 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个数字的。

DFS 和 BFS

是否需要使用 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次