返回

leetcode

最后还是逃不开

刷刷我的

stash: DP 树 堆/堆排序

https://juejin.cn/post/7170873189482889223/

https://leetcode.cn/circle/discuss/tXLS3i/

贪心算法

605 种花问题 贪心在有坑就占

121 买卖股票的最佳时机 与之前的最小值比较

122 买卖股票的最佳时机 II

561 数组拆分 很容易,排序隔着找就好了

455 分发饼干 排序然后一个一个分配出去就好了

575 分糖果 比较哪个小即可

135 分发糖果 困难题,如果从最小的地方开始向两边分配那么无法覆盖所有解(可能存在多个最小值)但是也算是完成了一部分。实际上问题更复杂或者更简单?实际解法也不复杂

解法一:遍历两遍只需要同时满足两个规则:从左往右是递增序列,从右往左也都是递增序列,要同时满足两种情况,只需要取两个规则的最大值即可。

解法二:把递减视为递增序列,实际上由于要满足两个规则,实际上可以把递减序列视为递增序列从而避免从右往左便利的情况。同时由于糖果分配是递增的,所以可以不用数组来保存,直接扫描一遍即可。但是写出来有难度。

2908. 元素和最小的山形三元组 I 虽然是简单题但是如果数值范围大的话就得靠贪心解决了,和上一题方法基本类似,由于是找**最小值(就是因为这个条件所以可以贪心)**所以只需要从左往右的取最小值和从右往左的取最小值即可,最后在中间不断找到最小值即可,非常微妙。

409 最长回文串 之前做过了,不复杂,统计词频即可

621 任务调度器 并不难想到解法,每次从中挑选频数最多(因此需要多次排序)的n+1个任务组成序列即可。

179 最大数 实际上就是一个排序问题,但是还是有点复杂的。

算法的核心在于搞清楚其实列表的顺序就是拼接的顺序,所以只需要通过某种规则排序即可。对于每个可能拼接的结果,只要保证相邻的两个数的拼接结果是最大的,就可以保证最后的结果是最大的(有严格证明)。

此外可以学习一手python sorted方法的另一种自定义方式:

def do_sort(x, y):
    if x+y > y+x: return -1
    elif x+y < y+x: return 1
    else: return 0
nums = sorted(nums, key=cmp_to_key(do_sort))

56 合并区间 排序然后贪心即可,应该是简单题(看评价好像简单困难不一)

57 插入区间 调用一下前一道题的代码即可,但是题目已经隐含排序了,所以代码中只需要把newinterval放到合适的位置即可,时间复杂度可以达到O(n)

228 汇总区间 跟前两道一样,不难

452 用最少数量的箭引爆气球 反过来求最小交集即可。

435 无重叠区间 贪心妙!找每次最小的不重合右区间即可

646 最长数对链 直接抄上一道题,无重叠区间取反即可。

406 根据身高重建队列

48 旋转图像 顺时针旋转=水平翻转+对角线旋转

169 多数元素 多数元素大于n/2所以无论在任何时刻,遇到该数的频次-遇到其他数的频次>=0

215 数组中的第 K 个最大元素 比较重要的题,下一道题也可以用到这道题的方法,其中有两种解法:大根堆解法快速选择解法,这两个建议都学习一下。

大根堆解法:构建大根堆,则删除的第K个元素之后堆顶就是该元素(heapq.nlargest(k, nums)[-1])

快速选择解法:快排递归求解可知每次会有一个元素到达对应的位置,所以第N-k个位置对应第k大的数,而且每次划分不需要排序,复杂度是O(N)

建议两个都手搓一下。

324 摆动排序 II

75 颜色分类 做出来倒是一点不难,但是得知道如何通过双指针解决问题。双指针也涉及到贪心的相关内容,l从左往右扫描,则1必然在右指针左,2必然在右指针右,以此规则遍历即可。

517 超级洗衣机

649 Dota2 参议院 题目比较复杂,但是可以有多种解法,这里使用的是循环队列的解法(但是停止条件存在问题其实),更加合理的做法是使用两个列表分别表示两个阵容的数量和对应的位置

678 有效的括号字符串 初次涉及到动态规划了,这里的解法是设置了两个变量最小open和最大open,每次遇到左括号时则最小最大均会+1,遇到右括号时最大-1(当最大小于0说明有括号超标了所以返回不有效),同时最小取0和最小-1的最大值(因为需要考虑到*的存在)。当遇到*时最小取最小-1和0的最大+1。在这种实现中最小表示最少可能的未匹配左括号数量而最大表示最多~。

420 强密码检验器 是困难题,应该有前置题目可以先做

上述的题目是数组贪心相关的,整体来说难度参差不齐。由于这方面的题目较多所以其实并没有简单的通解能够解决所有问题,通常需要分析贪心的条件(感觉可以贪就贪,咱就不证明了)。通常的解决方案有flag、双指针、双向检测最大值(对于多个条件的需要多遍遍历,寻找同时满足条件的情况即可)

53 最大子数组和 妙妙妙

134 加油站 同样妙妙妙,关键在于题目条件和合适的推理,如果gas-cost的和小于0则必然不存在对应的出发点。同时由于解唯一,所以只需要从前往后遍历,如果走不通就设置为下一个点即可,遇到的可以走到尽头的一定是可以走通的点。

581 最短无序连续子数组 首先能想到前后遍历一下,从前往后找最大,从后往前找最小即可。(虽然有思路但是写不出来的飞舞呜呜呜)

152 乘积最大子数组 最开始想着从前往后遍历,值是不断增加的所以扫描就好了,显然是错误的:[1,-2,-5,-4,3]所以还是得用正经方法(所以说这题并不是贪心可恶)。正经方法就是从前往后维护一个最大值和最小值(负数)数组,遇正继续,遇负交换,问题划分成两个子问题即可。

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        maxv, imax, imin = -inf, 1, 1
        ln = len(nums)
        for i in range(ln):
            if nums[i] < 0:
                imax, imin = imin, imax
            imax = max(imax*nums[i], nums[i])
            imin = min(imin*nums[i], nums[i])
            maxv = max(maxv, imax)
        return maxv
     

子序列与贪心算法

334 递增的三元子序列 直觉上感觉好像并不能直接m1, m2 做出来,感觉得谨慎一点,但是确实可以。

376 摆动序列 这个倒是不难想,毕竟是必然递增的,所以得到差值数组即可

659 分割数组为连续子序列虽然是中等但是个人感觉已经很难了,一个有趣的点在于,由于是贪心的题目,所以正常来说的话会每次尽可能分3个或者分尽可能多(但是都不对,这两个都可以通过题目给出的例子直接反例枪毙)

题解非常简单的说明了**,如果x-1存在就接上去因为延长一个序列好于新加一个序列**,但是理解起来比较复杂,不如看这个例子:

https://leetcode.cn/problems/split-array-into-consecutive-subsequences/solutions/376129/zui-jian-dan-de-pythonban-ben-by-semirondo/

还是贪心算法,从头扫描,如果能接着上一个序列,就在上个序列后添加当前值,如果不行,前插一行继续下一个数字。 例如 2, 3, 4, 4, 5, 5, 6 顺序如下 [[2]] [[2, 3]] [[2, 3, 4]] 4不能后接,前插一行 [[4], [2, 3, 4]] [[4, 5], [2, 3, 4]] [[4, 5], [2, 3, 4, 5]] [[4, 5, 6], [2, 3, 4, 5]] 最后比较是否所有序列长度大于等于3

虽然思想类似,但不是根据大小序一个一个递增延长的,而是遍历列表(因为列表存在重叠元素,可以依次按序往之前已经有的子序列添加了)

但是像上述例子做的话复杂度就太高了O(n^2)使用哈希表即可。剩下的就不用说了。

数字与贪心

343 整数拆分 dp划分子问题:mv = max(mv, l*what[r], r*what[l], r*l)

单调栈法

因为之前没有做过单调栈的相关问题,所以首先解释一下,单调栈是指只有当值大于当前栈顶元素时才能进栈的栈

496 下一个更大元素 I 第一眼看题目和数量空间,感觉可以O(l1*l2)秒掉,但是还是得尽可能地达到进阶的要求。单调栈的解法十分巧妙,首先由于单调栈的性质,每次进栈的时候都会把比其小的取出放入,所以不难想到,一个数下一个更大元素正好是能取出的最后一个元素,因此遍历数组得到所有数的下一个最大元素,之后查询即可。当然,题解也是非常妙的。

class Solution:
    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
        res = {}
        stack = []
        for n in reversed(nums2):
            while stack and n >= stack[-1]:
                stack.pop()
            res[n] = stack[-1] if stack else -1
            stack.append(n)
        return [res[n] for n in nums1]

503 下一个更大元素 II

456. 132 模式

316 去除重复字母

402 移掉 K 位数字

321 拼接最大数

84 柱状图中最大的矩形

85 最大矩形

数组中的动态规划

before do it, 动态和贪心虽然学习并了解了很多遍,但是时至今日仍然是对我而言极度困难的一类题目。要想更好的理解动态规划,首先需要理解动态规划和递归的区别,显然,一个是自顶向下进行求解,而DP则是自底向上求解(实际上都可以理解成一个个分支的图后者树形),在进行求解的过程中,如果上一点的选择不会影响到之后的状态,那么这类题型就是贪心,每次选择最优解即可(虽然有时候需要严格证明),如果会影响到之后的状态,那么这类题型就是DP。也因此一般做到DP会有两种思路:拿一个数组记录所有的状态或者使用递归解法解决。但是两者都会面临状态过多的情况,因此需要使用一些手段来筛选需要的状态(感觉DP的核心就是筛选,当然,严格的证明过程也是不需要的)

虽然各种题有各种讨巧的做法,但是DP总归是两步组成的:状态转移、筛选状态。剩下的就要靠练习了感觉。

509 斐波那契数 没想到吧,我也是dp

198 打家劫舍 第一个题解确实详细也几乎是DP的启蒙,建议全文背诵(至于精简版写法,暂且无所谓了)

70 爬楼梯 挺简单的但是刷不出来,可以正推推导式。动态规划多少跟递归有点关系,但是使用常规递归会导致计算量超标和栈深度过高,所以还是使用dp合理一点

338 比特位计数 O(nlogn)是不需要使用dp的,O(n)是需要使用dp算法的。O(n)方案中的的最高位方法挺妙的,使用 i&(i-1)==0来判断是否是正好2的幂数,如果是的话为1,否则就是最高位的数字加上去即可,挺妙的。

55 跳跃游戏 取能走的最远和之前预期的能走的最远的最大值即可。

45 跳跃游戏 II 和之前的题相差倒是不大,首先从一个点出发可以到达的所有点都是下一个起跳点,比较这些起跳点中可以跳的最远的即可。从一个起跳点开始到达之前的边界之前的最大值。之后继续跳到下一点。

213 打家劫舍 II 两轮打家劫舍

650 只有两个键的键盘 就是利用最小公倍数的思路即可,可以化简为递归子问题:找n的最小公倍数$f(n) = f(n/k) + 2$

91 解码方法 想法是对的,就是没有写出来呜呜呜。思路有点像爬楼梯,保存一下之前的状态并求和即可。当然同样可以用两个变量来减少时间复杂度。

639 解码方法 II

552 学生出勤记录 II

123 买卖股票的最佳时机 III

188 买卖股票的最佳时机 IV

309 最佳买卖股票时机含冷冻期

32 最长有效括号

复杂的dp还是算了

264 丑数 II 实际上就是每次找三个因数中最小的不断递增即可。

313 超级丑数

403 青蛙过河

子数组、子序列中的动态规划

689 三个无重叠子数组的最大和

413 等差数列划分

446 等差数列划分 II - 子序列

368 最大整除子集

416 分割等和子集

279 完全平方数

背包问题

322 零钱兑换

518 零钱兑换 II

474 一和零

494 目标和

377 组合总和 Ⅳ

矩阵中的动态规划

62 不同路径

63 不同路径 II

64 最小路径和

120 三角形最小路径和

576 出界的路径数

688 骑士在棋盘上的概率

221 最大正方形

629 K 个逆序对数组

174 地下城游戏

96 不同的二叉搜索树

329 矩阵中的最长递增路径

动态规划与字符串匹配

583 两个字符串的删除操作

72 编辑距离

97 交错字符串

115 不同的子序列

516 最长回文子序列

132 分割回文串 II

131 分割回文串

139 单词拆分

140 单词拆分 II

514 自由之路

10 正则表达式匹配

44 通配符匹配

状态压缩动态规划

464 我能赢吗

691 贴纸拼词

698 划分为 k 个相等的子集

638 大礼包

473 火柴拼正方形

区间中的动态规划

486 预测赢家

664 奇怪的打印机

375 猜数字大小 II

312 戳气球

546 移除盒子

树形 dp

337 打家劫舍 III

124 二叉树中的最大路径和

数位 dp

233 数字 1 的个数

600 不含连续 1 的非负整数

数组

485 最大连续 1 的个数

495 提莫攻击

414 第三大的数

628 三个数的最大乘积

上面的题目都是简单的,显然排序一下会简单很多,但是复杂度就会到达O(nlogn)所以一般尽可能的还是会考虑O(n)的算法。由于复杂度不看系数所以多遍历几次也是可以的(多用几次max,min也没啥问题)

645 错误的集合 虽然有常规思路但是如果用数学方法求解还是有意思的

697 数组的度 存一下就好

448 找到所有数组中消失的数字 中等但是很简单

442 数组中重复的数据O(n)的空间很简单,但是O(1)就很讨巧了

41 缺失的第一个正数 原地哈希,和上一道题一样的方案

274 H 指数 如果不使用O(n)做的话也不难

80. 删除有序数组中的重复项 II双指针轻松拿下(也可以考虑使用哈希表来保存,但是这样就需要额外的时间复杂度了)

上面的题目涉及到频数,出现的计算,因此大概率是需要使用数组桶的方式进行求解,对于python来说可以使用一些简单的方法来统计频率或者统计位置

# frequency
from collections import Counter
busket = Counter(list)
# posistion
for i,j in enumerage(list):
    if lpos.get(j, None) if None:
        lpos[j] = [i]
    else:
        lpos[j].append(i)

453 最小操作次数使数组元素相等对立事件

665 非递减数列 不难也还行

283 移动零 不难

上面的涉及到简单的数组移动,但是一般会有原地狡猾的呢限制来提高难度,所以可以使用诸如双指针等方法进行交换来实现原地置换

118 杨辉三角 确实不难

119 杨辉三角 II 是前面的升级版,要求找到规律了

661 图片平滑器 手写滤波器,但是没有特殊的地方,复杂度会比较高

598 范围求和 II 小贪心!

419 甲板上的战舰 是图论部分的问题,如果不考虑挑战的话其实并不复杂(毕竟不能修改棋盘),可以先浅浅解决一下

上述题目为二维数组相关问题,目前来看难度还不大,主要还是熟练二维数组操作技巧。但是同时二维数组也会比较频繁的和图论等问题结合,因此后续还会出现很多类似题目。(比如419题)

189 轮转数组 用python可太容易了

396 旋转函数

栈和递归 (暂时完成?)

用栈访问最后若干元素

682 棒球比赛

71 简化路径 中等题但是比上一道还简单

388 文件的最长绝对路径 可以不用栈做的其实

栈与计算器

150 逆波兰表达式求值 很基础的栈应用了已经

227 基本计算器 II 稍微有点繁琐了已经

224 基本计算器 已经繁琐到没必要做了

栈与括号匹配

20 有效的括号 ez

636 函数的独占时间 在入栈的时候顺便多处理一下就好了,也挺好的题目

32 最长有效括号 栈+DP,有点难了属于是,自己的方法考虑不到嵌套的情况,建议参考题解二进行快乐的理解记忆

递归

递归在dfs的时候还会好好学习的,但是核心在于入栈和出栈之前进行一手判断操作

385 迷你语法分析器 核心其实是解析器

341 扁平化嵌套列表迭代器 妙妙妙

394 字符串解码 递归就好了,但是写不出来

树与递归

100 相同的树

222 完全二叉树的节点个数

101 对称二叉树

226 翻转二叉树

差点难到哥们

437 路径总和 III

563 二叉树的坡度 天才题解,同时也提供了一种很舒服的递归条件:

class Solution:
    def findTilt(self, root: Optional[TreeNode]) -> int:
        def dfs(node):
            if not node:
                return 0, 0
            l_sum, l_diff = dfs(node.left)
            r_sum, r_diff = dfs(node.right)
            return l_sum + r_sum + node.val, l_diff + r_diff + abs(r_sum - l_sum)
        return dfs(root)[1]

617 合并二叉树

508 出现次数最多的子树元素和

572 另一棵树的子树

543 二叉树的直径

654 最大二叉树

687 最长同值路径

87 扰乱字符串

树的层次遍历

102 二叉树的层序遍历

429 undefined

690 员工的重要性

559 undefined

662 二叉树最大宽度

671 二叉树中第二小的节点

513 找树左下角的值

515 在每个树行中找最大值

637 二叉树的层平均值

103 二叉树的锯齿形层序遍历

107 二叉树的层序遍历 II

257 二叉树的所有路径

623 在二叉树中增加一行

653 两数之和 IV - 输入二叉搜索树

104 二叉树的最大深度

111 二叉树的最小深度

112 路径总和

113 路径总和 II

129 求根节点到叶节点数字之和

404 左叶子之和

199 二叉树的右视图

655 输出二叉树

116 填充每个节点的下一个右侧节点指针

117 填充每个节点的下一个右侧节点指针 II

树的前序遍历

144 二叉树的前序遍历

589 undefined

树的前序序列化

606 根据二叉树创建字符串

331 验证二叉树的前序序列化

652 寻找重复的子树

297 二叉树的序列化与反序列化

449 序列化和反序列化二叉搜索树

树的后序遍历

145 二叉树的后序遍历

590 undefined

树的中序遍历与二叉搜索树

94 二叉树的中序遍历

700 undefined

530 二叉搜索树的最小绝对差

538 把二叉搜索树转换为累加树

230 二叉搜索树中第 K 小的元素

98 验证二叉搜索树

173 二叉搜索树迭代器

669 修剪二叉搜索树

450 删除二叉搜索树中的节点

110 平衡二叉树

95 不同的二叉搜索树 II

108 将有序数组转换为二叉搜索树

109 有序链表转换二叉搜索树

重构二叉树

105 从前序与中序遍历序列构造二叉树

106 从中序与后序遍历序列构造二叉树

二叉树的展开

114 二叉树展开为链表

最近公共祖先

235 二叉搜索树的最近公共祖先

236 二叉树的最近公共祖先

Morris 中序遍历

501 二叉搜索树中的众数

99 恢复二叉搜索树

四叉树

558 undefined

427 undefined

What’s more

28. 找出字符串中第一个匹配项的下标 妙啊,虽然能想到使用递归加$(a)b$方式添加有效字符串,但是确实写不出来。

class Solution:
    @lru_cache(None)
    def generateParenthesis(self, n: int) -> List[str]:
        if n == 0:
            return [""]
        res = []
        for i in range(n):
            for l in self.generateParenthesis(i):
                for r in self.generateParenthesis(n-1-i):
                    res.append("({}){}".format(l, r))
                        
        return res

这里还涉及到了一个装饰器:lru_cache(None)

Strategy Eviction policy Use case
First-In/First-Out (FIFO) Evicts the oldest of the entries Newer entries are most likely to be reused
Last-In/First-Out (LIFO) Evicts the latest of the entries Older entries are most likely to be reused
Least Recently Used (LRU) Evicts the least recently used entry Recently used entries are most likely to be reused
Most Recently Used (MRU) Evicts the most recently used entry Least recently used entries are most likely to be reused
Least Frequently Used (LFU) Evicts the least often accessed entry Entries with a lot of hits are more likely to be reused

如上表显示不同情况下需要使用的情况

42. 接雨水 非常经典的题,左右各扫一遍找最小即可。(本来以为很难结果秒了)

478. 在圆内随机生成点 拒绝采样,这个很微妙!细节在于完全随机(所以是均匀的),考虑到随机选择极坐标是不均匀的(点会集中在圆心),合格的做法应该是随机选择半径的平方!(因为圆内的面积和半径的平方成正比)

Licensed under CC BY-NC-SA 4.0