刷题记录

美好的一天,从解题开始。


写在前面

这里主要存放刷题的记录,同一个题的不同方法甚至相同方法都会出现在这里,比如时隔数周再复习某个方法解某个题。

题目前面的[xx]表示第几次做这个题。

保证每天要做至少一道从未做过的新题。当天做的新题用就用[00]标注。如果mock的限制时间内没做出来或感觉需要强化复习的再加个;

格式:### [[00]-]()


2022年

1-22

[00]-LC: 778. swim-in-rising-water

  • 能力检测二分+BFS:二分用来快速缩小边界找到符合条件的t,BFS用来判断时间为t时是否能到达右下角。二分复杂度\(O(\log n)\),DFS最坏情况\(O(n^2)\),总复杂度\(O(n^2\log n)\)
  • 能力检测二分+DFS:思路类似,因为只用找一条路径,所以DFS更快,复杂度同上
  • 最短路径(堆):类似Dijstra算法,每次从堆里取出所需t最小的点,然后向堆里添加该点可达的所有点(以及所需的t)。最多需要向堆里添加\(n^2\)个点,所以复杂度为\(O(n^2 \log n)\)

[01]-LC: 1456. maximum-number-of-vowels-in-a-substring-of-given-length

  • 滑动窗口:优化小tips:滑动时,只在cur增加时判断是否为最大值,以减少判断次数

1-21

先补昨天的题,再整点小题加强信心,明天早上早起补今天的题!

[00]-LC: 34. find-first-and-last-position-of-element-in-sorted-array

  • built-in:bisect还算好用
  • 二分法:手写更快

;[00]-BS: 817. Kth-Pair-Distance.py

这个题目的关键在于绝对不能\(O(n^2)\)遍历数组来找到所有对的差的绝对值,只要\(O(n^2)\)就一定TLE。

  • 暴力法+排序:简单但超时TLE
  • 堆:同样超时
  • 双指针+计数二分:可以用双指针来在\(O(n)\)时间知道差值在diff以内对有多少个;再用二分法在\(O(\log n)\)时间找出正确的符合要求的diff
    • 双指针计数:ij构造窗口,窗口内的即为nums[j]-nums[i]<=diff,计数就是j-1-i\(O(n)\)的遍历就能知道有多少个数小于等于diff
    • 计数二分:diff上下限分别为0max(nums)-min(nums),因为上面的函数包含了等于diff的情况,所以即使传入了正确的diff返回结果也一定大于k,右边界缩小为mid(否则会错过正确的diff)。
  • 双指针改进+计数二分:如果遍历左指针i,那么j在向前试探的时候需要判断是否越界;换成遍历右指针ji一定在j左边,不用判断越界,在BS: binary search上速度快了300ms。

1-20

消极怠工还熬夜,颓废的人生啊

1-19

;[00]-LC: 475. heaters

  • 排序+能力检测二分:复杂度\(O(\log{(max(m,n))}*m*\log n+m\log m+n\log n)\)
    • 排序

;[00]-BS: 791. Minimum-Light-Radius

这个题要先想到:在给定半径的情况下,验证三个灯是否能cover所有点。这个点没想到就很难展开思路。验证三个灯是否能覆盖所有点显然可以使用二分法。同样,确定半径也可以使用二分法。

  • 排序+能力检测二分:复杂度\(O((n+\log{[max(nums)-min(nums)]})*\log n)\)
    • 先排序,复杂度\(O(n\log n)\)
    • 能力检测二分:用二分法确定在给定半径r的情况下,三个灯是否能覆盖所有点,第一个灯light一定在nums[0]+r的位置,第二个灯则在light+r的位置,但这是具体值,需要在nums中找到light+r元素(二分要素察觉),以此类推摆满3个灯并返回bool值。需要进行三次二分查找,复杂度为\(O(\log n)\)
    • 半径r的取值范围为\([0,(nums[-1]-nums[0])/2]\),而nums中的元素均为整数,所以半径的步进大小为0.5,枚举r判断是否能cover所有点即可。枚举可以直接循环,但二分显然更加快,复杂度为\(O(\log{(max(nums)-min(nums))})\)

1-18

[00]-LC: 153. find-minimum-in-rotated-sorted-array

  • built-in:\(O(n)\)大法好,不符合题意
  • 二分法:\(O(\log n)\),写的复杂了一点(条件判断部分)
  • 二分法:\(O(\log n)\),改进,直接和右端点/左端点比较并根据情况缩放范围

[00]-LC: 154. find-minimum-in-rotated-sorted-array-ii

和上面类似的题目,但是是困难题,因为出现了重复数字

  • built-in:\(O(n)\)大法好,不符合题意
  • 伪二分法:\(O(n)\),重复数字在相等的时候不能二分缩小返回,只能把右边一步一步的挪

;[00]-LC: 1901. find-a-peak-element-ii

昨天做的162的后续

  • 二分法:将二维数组脑补成一维数组,按昨天"有坡必有顶"的思路同理,去比较它右边/左边的元素,区别在于昨天的一个元素变成了今天的一列元素,为保证能找到peak,就必须选这一列元素的最大值(可以认为最大值一定是纵向的peak),这样保证了纵向是peak,再用二分法横向去找坡来爬即可。复杂度\(O(m\log n)\)

[00]-BS: 757. Triple-Inversion

看了hint才做出来的,一开始根本没想到归并排序,归并排序YYDS。

  • 朴素暴力法:\(O(n^2)\),直接双重循环就行,TLE
  • 二分法:\(O(n^2)\),朴素暴力法改进得到,如果内层循环的查找是在一个有序列表中进行,就并不需要\(O(n)\)才能找到,而是可以用二分法做到\(O(\log n)\),所以在外层遍历的同时构建一个有序列表。但这里构建有序列表要涉及到移动数组,插入的复杂度仍然为\(O(n)\),所以总复杂度依然是\(O(n*(n+\log n))=O(n^2)\),但是BS上勉强能过(py黑魔法出现了)。
  • 二分法+平衡二叉树:\(O(n\log n)\),继续优化上面的方案,结合平衡二叉树来保证有序列表的插入复杂度能降低到\(O(\log n)\),总复杂度为\(O(n*(\log n+\log n))=O(n\log n)\)
  • 归并排序:\(O(n\log n)\),这个题目出题人的意图解法,将数组分为前后两部分,对这两部分递归调用自己排序(可以理解为已经有序了),合并的时候因为两部分已经有序了,可以在\(O(n)\)时间内算出满足条件的个数。

1-17

;[00]-LC: 162. find-peak-element

  • 遍历: O(n)思路,不符合要求
  • 二分法: 关键点:有坡必有顶。只要有坡,顺着坡走一定能找到顶

[00]-LC: 278. first-bad-version

  • 二分法:没什么好说的,简单题,4分钟秒了,直接套bisect那套二分模板

1-16

[00]-LC: 33. search-in-rotated-sorted-array

  • 二分法:强行把nums还原成旋转前的样子再二分。
  • 二分法:改进,不再还原数组,直接再二分的left和right上加上旋转的偏差,数组越界问题直接取余即可。

;[00]-LC: 375. guess-number-higher-or-lower-ii

  • 回溯+记忆化

[00]-LC: 374. guess-number-higher-or-lower

  • 二分法
  • 二分法

[00]-LC: 69. sqrtx

  • built-in:直接returnint(x**0.5)或者int(math.sqrt(x))
  • 二分法:参见我1-6号总结的python built-in 二分法api bisect的模块。[00]-LC: 35. search-insert-position,同时这次另总结出了一条新规律:因为bisect将数组分为了[left,mid]和[mid+1,right]两个部分,我们在灵活运用时可以这么分,也可以分为[left,mid-1]和[mid,right],比如这个题就得这么分(当真值在右边也就是x>mid*mid的时候,因为题目要求开根号的整数部分,left取mid+1就有可能丢弃掉真实结果,所以left必须取mid,那为了避免死循环就必须取right=mid-1,也就是第二种分法):
    • 如果是left=mid+1,说明即使left等于mid了也是左边界在缩小,那么为了避免死循环,mid的值应当相对偏左,即mid=(left+right)//2
    • 如果是right=mid-1,说明即使right等于mid了也是右边界在缩小,那么为了避免死循环,mid的值应当相对偏右,即mid=(left+right+1)//2

1-15

[00]-LC: 148. sort-list

深夜想起来今天没做新题,凌晨3点补上。基本上15分钟搞定归并,剩下15分钟写了写计数排序。然后花了1个半小时写快排,debug半天还踏马超时。看来快排在没有random以及填坑法partition这类trick的加持下还是很慢的,有个题解说快排的话c++提交要看运气,有时候会超时。难怪python的built-in排序是写的归并,归并排序YYDS

  • 计数排序:不符合题目要求
  • 快排:能用但是超时(debug很麻烦,且没法用填坑法做partition)
  • 归并排序:yyds

[01]-LC: 912. sort-an-array

归并比较熟练了,15分钟搞定,快排还是花了快30分钟,partition不是很熟悉,可能还得再练,以后就填坑法了

  • 归并排序
  • 快排+填坑法
  • 计数排序法(哈希表)
  • 计数排序法(列表,又快又好)

1-14

;[00]-LC: 1737. change-minimum-characters-to-satisfy-one-of-three-conditions

  • 朴素枚举+哈希:核心点是枚举字母a-z,令其为x,计算使字符串a完全小于x并使字符串b完全大于等于x所需要的操作数就能找到满足条件1的最小操作数,条件2完全对称,条件3直接统计可得。
  • 朴素枚举:将哈希替换成了列表,企图加快速度,然而在LC上速度更慢
  • 枚举+动规:朴素枚举的问题在于重复计算,拿满足条件1的情况举例,枚举字母xa的结果,与xb的结果之间是存在联系的,x=a的结果只需要再-A[i]+B[i](i为x=b时的下标),就能得到x为b的结果。本质和上面的朴素枚举是同理的。

1-13

;[00]-LC: 1904. the-number-of-full-rounds-you-have-played

这个题轻微超时了(3分钟),有点菜,一开始把开始时间和结束时间都提前取整了,导致整个代码又臭又长,条件判断还错中复杂。说起来现在越来越怠惰了,昨天上一天课啥都不想干

  • 朴素思路:把开始时间和结束时间分别提取出来,对于分钟进行取整处理(开始时间向后取整,结束时间向前取整),然后根据小时的不同情况去判断,算总分钟数(可以看作时间戳),最后返回结果。
  • 朴素思路优化:既然本来都要算总分钟数,那就不要提前取整,直接获得总分钟数,然后调整开始时间(向后取整),最后除15即可

1-12

[00]-LC: 1834. single-threaded-cpu

模拟题,动态极值,基本就是堆了。

  • 双堆(小顶堆):把所有task全部入堆(记得要先带index)。然后pop出所有在current_time之前的task并push到另一个堆,根据processing_time在另一个堆顺序出堆(并修改current_time)
  • 小顶堆+排序:不再用堆排处理tasks,直接把它带index进行built-in排序,其余一样
  • 小顶堆+排序优化:带着index排序tasks还是比较慢(因为是tuple),可以直接排序下标(sorted(list(range(n)),key=lambda x:tasks[x][0])),其余一样

1-11

[01]-LC: 657. robot-return-to-origin

  • 模拟:根据指令变化x和y的值
  • built-in:虽然蠢但是速度却最快
  • 哈希:一遍统计后看上下与左右的数量是否相等,和方法一思路相同

;[00]-LC: 467. unique-substrings-in-wraparound-string

  • 前缀和+动规:需要前缀和前备知识1。如果p[i]p[i-1]只差1或者差-25,那就符合条件。计算从开头到i为结尾的字符串的符合条件的子数组个数即可。但结果不能直接把动规数组相加(也就是前缀和数组求和),而是要记录i作为字符串结尾的符合条件的子数组的最多的结果,需要哈希表。

1-10

;[00]-LC: 1203. sort-items-by-groups-respecting-dependencies

  • 不会做呜呜呜,按照正确的思路写出来就是TLE我tcl…

1-9

;[00]-LC: 886. possible-bipartition

今天的题被自己菜到了,没看出来是染色问题,光在想怎么去DFS了,没有想到用colors/visited数组/哈希表来表示分组的结果,光在那愣愣的想创建俩集合了。

  • DFS:染色问题,深搜最适合解决了
  • DFS+all函数:试着用python的all函数简化代码,好用是好用就是慢了不少
  • BFS:用辅助空间(队列)处理,在LC上速度比DFS更快

[00]-LC: 785. is-graph-bipartite

和上面思路完全一样的题,二分图。纯属练习做,30分钟搞定了下面两种方法哈哈。

  • DFS:和LC. 886一样的思路
  • BFS:和LC. 886一样的思路

1-8

[00]-LC: 997. find-the-town-judge

  • 朴素哈希:一开始没反应过来这题是图,变量命名用trustedtrusted_by_me太稀碎了
  • 哈希:用哈希表标记节点的入度数和出度数,返回出度为0且入度为n-1的节点即可

1-7

;[00]-LC: 239. sliding-window-maximum

学习了一下单调队列,发现这玩意儿和堆在pushpop这些操作上挺相似的,难怪堆又叫优先队列。

这个题目有两个关键点:1. 动态取极值;2. 移除无效值。第一点可以很容易想到堆,但是第二点堆却很难做到,这里可以通过检查堆顶是否已经无效了来移除无效值。但更好的思路是维护一个单调队列。

  • 朴素暴力法:复杂度\(O(n*k)\),直接TLE
  • 暴力法剪枝:同样TLE,复杂度\(O(n*k)\)
  • 堆:维护一个大顶堆,每次滑动完成后,将堆顶元素作为结果保留。复杂度\(O(n\log n)\)
    • 移动滑动窗口时将新元素入堆
    • 检查堆顶元素是否已经不在滑动窗口范围内,如果不在,出堆,直到最新的堆顶在范围内
  • 单调队列:维护一个单调队列,滑动窗口移动后,将单调队列的队首作为结果保留。nums中每个元素恰好被入列一次并出列一次,复杂度为\(O(n)\)
    • 每次将新元素从队列末尾入列,入列时移除所有比它小的元素
    • 检查队首元素是否在滑动窗口范围内,如果不在就出列,直到队首在范围内

1-6

[00]-LC: 35. search-insert-position

我也没想到我从小到大居然没在LC上做过二分查找的题,今天正好借机会研究了下python里bisect的源码,分析了一波

  • 朴素二分查找
  • 二分查找:更标准的板子(分为[left,mid]和[mid+1,right],更合理),和bisect包的源码类似。
    • bisect_left的时候,
      • 去考虑target插到右边的情况,也就是target>nums[mid]: 现在要缩左边界,target最终的结果一定不会为mid(因为是bisect_left,且已经比nums[mid]大),所以缩小左边界不用考虑midleft=mid+1
      • target插左边的时候: 要缩右边界,即使target小于nums[mid],但由于插的位置是bisect_left,有可能target还是除了mid以外的值都大,那最终结果依然有可能是mid,所以缩小右边界的时候不能忽略midright=mid
    • 类似的,bisect_right的时候,
      • 去考虑target插左边的情况,也就是target<nums[mid]: 现在要缩右边界,target的最终结果一定要考虑mid (因为是bisect_right,哪怕是比nums[mid]小,下标也要往右挪)。所以缩小右边界一定要考虑mid,right=mid
      • target插右边的情况: 要缩左边界,就算target是等于(或 \(\geq\) )nums[mid]了,但由于插的位置是bisect_right,下标必然要往右挪,所以缩小左边界不用考虑mid的情况,left=mid+1123
  • bisect:直接调api(源码和上面的类似)

1-5

[00]-BS: 801. Quadratic-Application

  • built-in排序法:线性变化之后直接sort,又快又好,\(TC: O(nlogn)\)
  • 队列+双指针:因为线性变化是抛物线,所以适合双指针从两端出发,根据抛物线开口方向,取两端线性变化后的值的较小者/较大者2,进行入列/入栈操作。如果a==0则直接列表解析搞定,\(TC: O(n)\)
  • 队列+双指针:上述方法的改进,a==0的情况依旧可以用队列解决,删掉分类讨论。\(TC: O(n)\)

[01]-LC: 26. remove-duplicates-from-sorted-array

  • 双指针:一个cnt留在原地,一个快指针依次遍历,cnt仅在发现不同时移动并赋值

1-4

[00]-LC: 974. subarray-sums-divisible-by-k

  • 前缀和+同余定理+哈希集合嵌套:和 BS: 924是换皮怪关系,不过我一开始看错题意了,以为要把所有符合条件的子串都输出出来,所以在哈希表中用set保留了所有下标。
  • 前缀和+同余定理:上述方法的改进,哈希表里只存数量即可。又是写出了官方题解类似的代码2333。

[00]-LC: 523. continuous-subarray-sum

  • 前缀和+同余定理:和 BS: 924是换皮怪关系,居然写出了和官方题解几乎一样的代码,笑死

[01]-LC: 876. middle-of-the-linked-list

  • 快慢指针:一个一次动两下,一个一次动一下,快的到头了慢的就到中间了。

[01]-BS: 924. Delete-Sublist-to-Make-Sum-Divisible-By-K

  • 前缀和+同余定理:同下,对昨天的题进行一个总结和复习,改日再做一遍。

1-3

;[00]-BS: 924. Delete-Sublist-to-Make-Sum-Divisible-By-K

这个题要找出一个子列表,使原列表和在除掉子列表后能被k整除

  • 废物思路:强行搞了个\(O(m*n^3)\)复杂度,\(n^2\)找子串,n求和,再包个m以适配不同的target,完美诠释了什么叫废物

  • 循环:\(O(n^3)\)循环,把targets放在set里,找到需要的子串和之后直接对set验证即可

  • 朴素循环:\(O(n^2)\)循环找需要去除的子串,\(O(n)\)子串求和,直接对k取余验证即可(所以上面两个方法连naive都不如)

  • 前缀和:\(O(n^2)\)去循环找要去除的子串,子串求和通过前缀和在\(O(1)\)搞定,复杂度\(O(n^2)\)

  • 前缀和+同余定理3:通过两者的结合复杂度能实现\(O(n)\) \[ \begin{align} (total-delete)\% k&=0\\ total\%k&=delete\%k\\ &=(pre[j]-pre[i-1])\%k\\ (pre[j]-total)\%k&=pre[i-1]\%k (i\leq j) \end{align} \] 有了以上推论,对于任意\(j\),我们只用去找所有小于等于\(j\)\(i\)对应的pre[i-1]%k,是否等于(pre[j]-total)%k即可。但显然这依旧是\(O(n^2)\)的复杂度,该如何降到\(O(n)\)呢?用哈希表即可:原先对于每个j,我们都要向前找一遍所有i,看i是否满足条件,但如果我们把"满足条件"的计算结果作为哈希表的key储存起来呢?

    具体的,在遍历j的时候:

    • 要先看等式左边的(pre[j]-total)%k是否存在于当前的哈希表中,如果存在,保留j-i,这里的i指哈希表的value。
    • pre[j]%k的结果作为key,j作为哈希表的value存起来,至于key相同的问题看这里的上标4

1-2

今天这个题是真的恐怖如斯恐怖如斯。

;[00]-LC: 30. substring-with-concatenation-of-all-words

设n为字符串长度,m为words个数,k为单个单词的长度

  • naive思路:缝缝补补拼凑而成,最后成功但TLE的方案;其实正确思路就在这里面了,就不考虑复杂度了(很乱)

  • 遍历+哈希:符合要求的子串长度一定是len(words[0])*len(words),直接遍历s,取出这些子串,再对这些子串判断其是否符合要求即可。(对words建哈希统计,看子串能否符合要求即可)。有n个子串,每个子串要在哈希表中访问m次来确定子串是否符合要求,复杂度为\(O(n*m)\)

  • 遍历+哈希+条件优化:上述方法的改进,不再一个字符一个字符的跳,而是一个单词一个单词的跳跃,且根据不同情况优化跳跃,以达到剪枝的效果5

    • 找到了不在哈希表里的词:直接将i跳到这个词后面,ji开始,当前哈希表重置
    • 完全匹配的情况:记录i,将i向后跳一个单词的长度,同时调整当前哈希表(删除跳过的单词),j从当前位置继续
    • 找到的词重复次数过多的情况:让i开始向右跳并调整当前哈希表(删掉跳过的词),直到重复次数等于当前结果。j从当前位置继续

    其实这个方法依然有n个子串要考虑,但是由于对哈希表的维护已经不同的跳跃规则,所以每个子串中对哈希表的访问变少了。具体的:

    • 如果单词不在哈希表中,那就放弃这种情况;
    • 如果完全匹配,只会移除上一个单词,中间的信息保留了;
    • 如果重复次数过多,则从前向后调整哈希表,没有完全清零;

    平均每个子串只访问了一次哈希表,所以复杂度为\(O(n)\)

1-1

新年好!这是1-2补写的,因为元旦在朋友家聚餐吃饭,勉强写了点题,没时间写总结了。而且题目其实也没写的很好,计算器这类题没有总结出一个通解,日后再补。

[01]-LC: 227. basic-calculator-ii

计算器最好想最简单的题

  • 栈:把+/-当成一元运算符考虑,默认表达式一开始有+号,然后运算符则是保留上一个运算符,每次遇到新的运算符就去处理上一个运算符。个人不是很喜欢这种思路,之后再找更好的方法

;[00]-LC: 224. basic-calculator

  • 栈+dfs:这个题目比上面的稍难一点,因为加入了括号的运算。题目提到的一元表达式倒是因为直接把+/-当成一元表达式提前解决了。括号是直接用dfs解决的。

;[00]-LC: 772. basic-calculator-iii

224多了乘法和除法,本质上就是224227的结合体,在224的基础上加上乘法除法即可。

  • 栈+dfs

[00]-LC: 3. longest-substring-without-repeating-characters

  • 哈希:naive想法,每次遇到重复的字符,从重复字符的起点开始重置字典重新统计,这样worst case复杂度就是\(O(n^2)\)
  • 哈希+滑动窗口:上面方法的改进,不需要重置字典,因为除了那个重复的字符以外其它的字符都是没重复的, 所以可以应用滑动窗口,当右指针扫到和set重复的情况,左指针向右滑直到找到这个重复的字符, 滑动的同时从set中删掉。复杂度\(O(n)\)

2021年

12-31

[00]-LC: 447. number-of-boomerangs

这个题教会了我:千万不要在提交之前删掉print,我本来mock-interview已经做完了,而且思路也是最优解了,结果忘了删print疯狂TLE,硬生生在那想nlogn的思路(并不存在)。

  • 哈希:朴素思想是\(O(n^3)\)6,但可以用哈希保存某一个点到其他点的距离的个数,{distance: counter},把每个点的哈希表存下来,最后进行排列计算:\((n-1)*n\),累加得到答案。\(O(n^2)\)
  • 哈希:上述方法已经是最优解了,进行亿点点优化,从1500ms降到500ms
    • 哈希表并不用存起来,得到一个点的哈希表后保留其排列计算的结果即可。
    • 算距离的部分,python中**要比*慢的多
    • 计算距离是算平方,并不需要abs(我是啥b)

12-30

[00]-LC: 697. degree-of-an-array

  • 哈希+循环重复:naive思路,通过哈希表找到nums的degree,将能得到最大degree的candidate都列出来, 依次判断这些candidate能构成的答案,(关键点:subarray必须要包含所有candidate), 在这些答案中找到最小值,尽管在LC里跑赢了100%的submit,但是很显然worst case复杂度O(n^2)。 比如[1,2,3,4,5,6,7,1,2,3,4,5,6,7]这样的用例,可以自己提交一个[0-24999]*2的例子,会超时
  • 哈希:LC上的思路,在哈希表里额外存放同一个数的起点和终点下标,方便之后计算长度,复杂度O(n)

[01]-LC: 347. top-k-frequent-elements

  • 哈希+排序:先统计频率,然后对其排序。设字典长度为m,则复杂度为(n+mlogm)
  • 哈希+堆:调Counter自带的most_common库,底层其实还是heapq的nlargest,复杂度O(n+mlogk)
  • 哈希+堆:自己维护了一个小顶堆,和方法3底层的nlargest同理。复杂度O(n+mlogk)

12-29

[00]-LC: 589. n-ary-tree-preorder-traversal

  • 简单题,和树的遍历一个东西

[00]-LC: 590. n-ary-tree-postorder-traversal

  • 简单题,和树的遍历一个东西

[02]-LC: 1. two-sum

老经典题目了,哈希表yyds

  • 用哈希表构建value到index的映射,遍历列表时先看target-num是否在哈希表中,不在就将num添加到哈希表中

12-28

现在怠惰的真就只做每日一题了吗,太菜了

[00]-LC: 987. vertical-order-traversal-of-a-binary-tree

  • dfs+排序:用哈希表{col: list}的形式储存节点坐标,其中list的元素为(row,val),以方便排序

12-27

笑死,根本早不起

[00]-297. serialize-and-deserialize-binary-tree

  • 朴素BFS思路:第一次写的有些青涩,基本思路就是队列作为辅助空间,层序遍历(并且把null带上)。反序列化类似操作。

  • BFS:和上述方法类似,略微改进调整,反序列化前删掉了多余的null,比前者思路更清晰

  • DFS:递归,YYDS。不得不说这个思路太妙了,其实复杂度和BFS一样,只是递归代码量少很多,运行起来无比玄妙,具体来说就是:

    • 序列化:先序遍历,用,隔开

    • 反序列化:data=data.split(','),然后整个nonlocal变量i,递归过程中data[i]就是根节点(先序遍历),i+=1,然后左子树右子树分别递归调用即可。

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      def deserialize(self, data):
      i = 0
      data = data.split(',')

      def dfs():
      nonlocal i
      if data[i] == 'null':
      i += 1
      return None
      root = TreeNode(data[i])
      i += 1
      root.left = dfs()
      root.right = dfs()
      return root

      return dfs()

12-26

md作息还没调过来,明天早上等人收快递,必早起,今天必早睡!

[00]-LC: 513. find-bottom-left-tree-value

用BFS直观,DFS稍微想想也能搞定

  • BFS:层序遍历,思路清晰
  • DFS:naive思路,先求最大深度,再找节点
  • 上述DFS改进:DFS过程中维护一个最大深度和ans(当前答案),同样仅需一次遍历

12-25

圣诞快乐!这几天作息有点颠倒,要调过来!

[00]-LC: 129. sum-root-to-leaf-numbers

  • naive dfs思路:模拟测试写出来的。每次深搜的时候把目前的结果传递下去即可
  • dfs思路:上面方法的优化。主要是代码更简洁了。
  • bfs思路:经典层序遍历。把node和当前结果作为tuple放在队列里,到子节点再计入ans即可。

12-24

圣诞节和朋友聚餐,今天就做2题3个法就结束!

[01]-LC: 100. same-tree

  • 递归:一行我秒了,有什么好说的 return p.val == q.val and self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right) if p and q else p == q
  • 非递归:用两个队列维护,pop出来的如果p和q都不是None就比较,然后leftright继续入队;如果有一个none那就直接看p!=q

;[00]-LC: 227. basic-calculator-ii

  • navie思路:写的不是很好,而且有限时间内也没写出来,计算器这个专题明天好好看了攻略再动手!逆波兰冲!

12-23

今天做计算器非常失败,4道题,明天就淦它了!

[00]-LC: 946. validate-stack-sequences

这是个大一考试里出现过的题,不过那会不要求写程序,而是自己模拟。

  • 栈模拟:设一个栈s,现在对pop的数组遍历,设为pop_numpop_num那一定得是push数组里来的,有且只有两种方法:
    • 本来就在当前的栈顶,那就把它pop走
    • push 的时候找到了

[00]-LC: 150. evaluate-reverse-polish-notation

  • 栈写法:逆波兰表达式计算,经典题目了,遇到数字就入栈,遇到计算符就pop两下计算结果再入栈

[01]-LC: 104. maximum-depth-of-binary-tree

  • 队列:非递归写法,用队列作为辅助栈模拟层序遍历的过程
  • 递归:一行搞定,每次返回当前节点的深度,+1比较大小

12-22

今天早上起晚了,下午人生第一次在美帝看了电影(一个人),两场连看,晚上也摸鱼了好久,凌晨1点才写了每日一题,写了俩个方法。就这样吧,早点睡,明天早起把今天的量补一补!

;[00]-LC: 146. lru-cache

  • 双向链表+哈希表:操作比较基本,双向链表用来维护队尾的元素,哈希表构建key到链表节点的映射
  • OrderedDict:python built-in数据结构,真香。

12-21

;[00]-LC: 859. buddy-strings

这个题我18分钟才在浏览器上过,edge case巨多

  • naive模拟
  • 改进上述思路:理清楚所有edge case:
    1. s和goal长度不等
    2. s和goal中出现了3个及以上不同的字符
    3. 只出现了1个不同的字符
    4. 没有不同的字符:需要set来判断是否有两个以上的重复字符

[00]-LC: 59. spiral-matrix-ii

  • 模拟:难点主要是edge case要在不提交前就能想清楚并bug free

;[00]-LC: 142. linked-list-cycle-ii

  • 快慢指针navie思路,只领会了快慢指针的表皮,没有深入理解题目第二个难点同样可以快慢指针解决
  • 快慢指针:上述方法改进。假设环形链表公共部分是a,要求的点是ans,快慢指针第一次相遇点是meet,那么起点到ans的路程是a,ans到meet是b,meet到ans是c,而快指针走的路程是慢指针的两倍 则有2(a+b)=a+n(b+c)+b,化简得到a+b=n(b+c),a=n(b+c)-b。如果从起点走到ans (路程为a)就等于从meet点走n圈再回退b步。两个人可以相遇到ans点

[01]-LC: 141. linked-list-cycle

发现lc上竟然记录了我4.5年前用C提交的记录。

  • 快慢指针法:slow指针一次一跳,fast指针一次两跳,有环则二者一定相遇

12-20

愉快的放假第三天,也只刷了一个新题。明天开始加大题量,把讲义里的题也刷上去。反手来一个痛定思痛,学了一个下午,4道新题+12个方法,我太强了😂

;[00]-LC: 41. first-missing-positive

这是个困难题,他难就难在他非要你用O(1)的空间复杂度+O(n)的时间复杂度,然后搞笑的是比起hastset,虽然理论上都是O(n),但是和hashset的O(n)比起来还还是要慢不少(一个80ms左右,一个170+ms)。

  • naive思路:集合,得到数组中正数的个数cnt,则答案一定在1~cnt之间。 把num变成集合(违反题目SC要求),判断1~cnt是否出现在集合中,未出现的就是答案
  • 上面方法的改进版:集合。去掉了没用的smallest,答案一定在1~len(nums)+1之间,遍历即可。
  • LC题解:标记法(哈希),关键点:答案一定在1~n+1之间,所以用num和下标进行映射并标记 规则是num->index-1,比如[3,4,1,1],3的话就在下标2处标记,4就在下标3处标记, 遍历的时候返回第一个没有标记的下标+1就是结果。标记可以用负号表示 第一次遍历需要把原有非正数变成n+1(即不再考虑),第二次遍历进行映射,第三次遍历返回答案
  • LC题解:标记法(哈希),思路类似上面,区别在于这个方法是直接通过调整元素, 使数组尽变成num[i]=i+1的样子,比如[3,4,1,-1]就是通过交换变成[1,-1,3,4] 那么第一个num[i]!=i+1的下标+1,就是缺失的第一个正数

;[00]-LC: 380. insert-delete-getrandom-o1

这个题最有意思的就是你以为set就能搞定,但set并不支持随机读取

所以需要list+哈希,list用来随机读取,哈希维护list的下标,保证能在O(1)时间在list里删除

  • naive思路,worst case会让getrandom复杂度为O(n)
  • 列表+哈希,列表来搞定随机取用,哈希来维护列表的index以保证能remove能在O(1)找到并删除

[00]-LC: 88. merge-sorted-array

简单题,没什么好说的,多写几个方法吧

  • naive思路,O(m+n)时间得到一个新的数组,再倒腾回去
  • 最慢思路,插一个数挪一排,O(m*n)复杂度
  • 方法1改进,O(m+n)时间的同时空间复杂度为O(1),省略再倒腾一趟的O(m)

[00]-LC: 160. intersection-of-two-linked-lists

  • 朴素思想,算长度差,对齐
  • 链表互补法,A走完了从B继续走,B走完了从A继续走。两个指针都走了同样的长度
  • 同上,写法更简洁

12-19

愉快的放假第二天,刷了一个题

[00]-LC: 109. convert-sorted-list-to-binary-search-tree

  • naive思路:遍历链表找中点,把链表截断分成左中右,递归构造树,复杂度O(nlogn),慢在每次要遍历链表
  • 参考的思路:链表顺序和树中序遍历结果相同。可以根据链表长度提前把树构造好,直接中序遍历树填空即可。复杂度O(n)
  • 上述优化:不再提前把树建好,而是用left和right来找到边界,边遍历边建树
  • 偷懒思路:把链表变成列表,可以在O(1)找到中点。

12-18

愉快的放假第一天,好好休息了会儿,今天只刷了两个题

[01]-LC: 24. swap-nodes-in-pairs

  • 用一个空节点来作为头,省掉头的edge case。然后两个指针换来换去就行了

[00]-LC剑指Offer: 53-II. que-shi-de-shu-zi-lcof

  • 二分法:左右找呗
  • 遍历:慢,不过可以一行写完

12-17

算法考试要人命了。终于结束了。今天的每日一题还是做过的,得再翻一个没做过的出来做,淦。

[01]-LC: 61. rotate-list

  • 基础链表题,将链表首尾相连,对k取余处理一下再遍历k次,断开链表即可

[00]-LC: 414. third-maximum-number

简单题,5分钟AC了。

  • 维护first,second,third,遍历一趟就行
  • 类似方法但是长的好看一些

12-16

期末考试要人命,今天就只能做一个新题了。不然复习搞不完。还是得规划好复习时间。balance

;[00]-LC: 768. max-chunks-to-make-sorted-ii

这个题单调栈的思路还没完全理清,只是看了个大概,得去复习了,明天再看。

  • naive思路:从右往左一个一个找max_num,找到了且左右指针相同时存栈里,左右指针不同说明仍然是同一个块,要取代而不是append。速度奇慢
  • 单调栈:就遍历就完事,如果当前数比栈顶还大那说明这个可能可以单独成块,入栈,要是发现了一个数比当前栈顶还小,那说明前面的可能泡汤了,这个小的数得和前面的一起成块,一直出栈直到这个数比栈顶大了。再把最大值入栈。

12-15

[01]-LC: 232. implement-queue-using-stacks

用两个栈实现队列,一个in_stack存入列,out_stack放出列,in倒腾到out的时候顺序就变成了FIFO

  • lazy pop方法:只有在out_stack为空的时候才倒腾,可以让pop的均摊TC为O(1)

[01]-LC: 1054. distant-barcodes

统计频率,每次选一个频率最高的放入ans里,再放频率第二高的,交替。要注意频率是动态变化的,用堆很合适

  • 贪心法+堆:统计频率,根据频率建大顶堆。先pop出堆顶,ans放一个答案。随后再pop出一个项,把之前pop出来的频率-1后放回堆顶,重复步骤即可。barcodes长度为n,不同的code数为k,因为要对堆进行n次操作,所以复杂度为O(n+nlogk)

  • 数学法:和上面的思路一致,只是填坑的部分不需要用堆解决。barcode按频率排序后,每隔一个空填充一下即可。例如

    1
    2
    3
    4
    5
    [1122223]
    统计频率后{2:4,1:2,3:1}
    2_2_2_2
    21212_2
    2121232

    统计频率复杂度为n,排序字典为klogk,复杂度为O(n+klogk)

12-14

[01]-LC: 378. kth-smallest-element-in-a-sorted-matrix

  • 二分法:利用了sorted的特性,仅通过O(n)次比较,就能找到所有小于等于mid的个数

    1
    2
    3
    4
    5
    具体的:从右上角开始遍历i=0,j=n-1,
    如果它比mid还小,说明从这到左边都比mid小,直接下移,i+=1, count+=j+1
    如果它比mid大,那就往左移,j-=1, count不变
    直到i=n为止。注意下移的时候,j是不需要重置为n-1的,
    因为向下移后右边肯定都大于等于当前元素,重置为n-1也会左移到这里

[00]-LC: 240. search-a-2d-matrix-ii

  • 暴力法:用py的语法糖,一行搞定return target in sum(matrix, [])
  • 斜线查找:和378的找法一模一样,舒服。

[00]-LC: 394. decode-string

贼简单的一个题,经典计算栈。30分钟没写出来,我是废物。限时的内容就不应该想着搞花活,切记切记。

  • 我是笨比写法
  • 再写一遍,计算栈,不再使用"#"作为分隔了,可以当以后的板子用
  • 参考题解写的递归法

[02]-LC: 435. non-overlapping-intervals

这题和后面的都是复习区间相关的贪心法,关键点在于要搞清楚区间是按左界/右界排序

  • 贪心法:这题算是我贪心法入门,右界排序,理由是为了让间隔尽可能不重复,右界小的先安排能保证剩余的空间尽可能大。(当然左界排序然后从数组右边开始也是一样的)

[02]-LC: 452. minimum-number-of-arrows-to-burst-balloons

  • 贪心法:右界排序。要尽可能少用箭,且所有气球都要社保。关键就是要用一个排序来帮助我们尽可能让气球重叠起来。 可以想象我先找一个右界最小的气球,气球按右界排序了,那后面的所有气球的右界都比这个气球的右界,所以后面的气球里只要左界比这个右界小,他们就是重叠的。

[02]-LC: 253. meeting-rooms-ii

  • 贪心法+堆:leetcode付费题,没想到我们算法课遇到了这个题。左界排序。和435的区别在于我们不允许存在重叠,且所有间隔都必须安排(不像435搞不定可以直接甩)。 当安排了一个房间后,这个房间的end_time就已经确定下来了,而剩下的所有会议都是必须安排的,所以最优解是尽可能让时间紧密,对于当前已有房间的end_time,我们需要在剩下的间隔中找到左界最小的,才能尽可能保证时间紧密。这里出现了动态最小值,所以还能用堆找到已有房间中的最小end_time。因为已经确定的是右界,所以要按左界排序(让时间尽可能紧凑)。 我个人理解是,因为所有的间隔都是要安排下来的,贪的是尽可能让他们时间短,已经安排的右界是确定的,所以按左界排(小的先来)。而前面的题目比如:
    • 435贪的是尽可能找到多的不重叠间隔,它贪的是间隔的数量,所以要右界排序,让剩的空间尽可能大。
    • 452贪的是尽量少用箭,也就是尽可能让间隔重叠,右界排序,可以快速找到左界在它左边所有的气球(它指某个气球的右界)。

[02]-LC: 252. meeting-rooms

  • 贪心法:上面一题的青春版,直接排序就可以了,左界右界都ok。

12-13

[00]-LC: 451. sort-characters-by-frequency

这题不难,hash存频率,排序再重组字符即可。

  • 直接快排
  • 手撕堆
  • heapq堆

[01]-LC: 378. kth-smallest-element-in-a-sorted-matrix

这个题尝试了4个做法,还没尝试最快的二分,明天试。

  • 直接快排
  • 归并排序
  • 固定堆1: 维护一个大小为k的大顶堆,需要遍历所有元素,heapq,复杂度n^2logk
  • 固定堆2: 类似题目23,维护一个大小为n的小顶堆,heapq,复杂度klogn

[01]-LC: 23. merge-k-sorted-lists

这个题太经典了,今天又尝试了用heapq搞定,不用手撕堆了。但需要改写ListNode,要继承它并让它comparable

  • heapq堆实现

[01]-LC: 1381. design-a-stack-with-increment-operation

笑死,3个月前做过的题再做还是想不起最优解

  • Naive思路,直接模拟实现
  • lazy_increment思路,只在出栈的时候去进行之前的increment操作,以规避对栈内元素过多的操作

  1. 算连续子数组的个数可以分别求以每个元素的下标作为子数组结尾的个数,再求和。比如[1,3,4]可以分别求以1结尾的个数,加以3结尾的个数,加以4结尾的子数组的个数,而他们之间的是+1的关系,即以3结尾的子数组个数为2,那么比它稍长一个元素的话呢?那就要比以3结尾的子数组个数多1,很多动规题的根基就在这里↩︎

  2. 开口朝上则两端都是结果中较大的值,取较大值放入deque,用appendleft(想象成是每次把最大值入列);开口朝下则说明两端都是结果中较小的值,取较小值放入deque,用append(想象成是每次把最小值入栈)↩︎

  3. \((a-b)\mod k=a \mod{k} -b\mod{k}\)​,当然这个公式表达的其实不完全正确↩︎

  4. key相同可以直接存是因为这个j是距离后面要遍历的j最近的一个,哪怕是覆盖了字典中的key也没关系,因为这个j的下标肯定比前面有相同key的更近↩︎

  5. 因为是一个词一个词跳的,所以整个过程还需要重复单词长度遍(即len(words[0])),让i分别从不同的起点开始↩︎

  6. 说实话做题的时候甚至没想到这个思路↩︎