Daily Leetcode

每日一题

DP

• 24.7.21 1186删除一次得到子数组最大和 枚举数组右端点讨论
• 24.7.23 3098求出所有子序列的能量和 子序列枚举，很难想到dfs的定义
• 24.8.11 1035不相交的线 类似最长公共子序列
• 24.8.15 3148矩阵中的最大得分 寻找最大最小值，记录到当前位置的最小值
• 24.8.19 552学生出勤记录II 把 dfs写在外面，多个测试用例可共享记忆化搜索结果，效率更高。
• 24.8.20 3154到达第K级台阶的方案数 灵神的组合数学秀麻了
• 24.8.28 3144分割字符频率相等的最少子字符串 满足条件：字符串长度=最大频率*字典长度

技巧类DP

• 24.7.9 3202找出有效子序列的最大长度II 灵神模运算整理

数位DP

• 24.8.21 3007价值和小于等于K的最大数字 好难啊

DFS

• 24.7.15 721账户合并 计算联通块，将相同value的key索引存入列表
• 24.7.22 2101引爆最多的炸弹 建有向图+枚举起点
• 24.8.12 676实现一个魔法字典 字典树，child设为dict()

图

• 24.7.17 2959关闭分部的可行集合数目 Floyd算法，二进制枚举，两点之间有多个边用二维矩阵建图
• 24.7.18 3112访问消失节点的最少时间 Dijkstra算法

贪心

• 24.7.26 2740找出分值区
• 24.7.27 3106满足距离约束且字典序最小的字符串
• 24.9.3 2708一个小组的最大实力值 记录最大最小值

位运算

• 24.8.22 3133数组最后一个元素的最小值

二分

• 24.8.3 3143正方形中的最多点数 答案有单调性，可二分

前缀和

• 24.8.14 3152特殊数组II 二分不如前缀和优雅

双指针

• 24.7.10/11 2972统计移除递增子数组的数目I/II 枚举后缀，分类讨论
• 24.8.9 3132找出与数组相加的整数II 灵神的双指针太优雅了，我写的是💩
• 24.9.2 2024. 考试的最大困扰度 用defaultdict记录

数据结构

• 24.7.13 3011判断一个数组是否可以变为有序 数组，分组循环
• 24.7.14 807保持城市天际线 数组，求行列最大值
• 24.7.19 3096得到更多分数的最少关卡数目
• 24.7.24 2766重新放置石块 哈希集合模拟
• 24.7.25 2844生成特殊数字的最少操作 字符串
• 24.7.29 682棒球比赛 用数组模拟
• 24.9.5 3174清除数字 stack

数学

• 24.7.9 3102最小化曼哈顿距离
  曼哈顿距离与切比雪夫距离(max(|x2-x1|,|y2-y1|))转换：
  • 将一个点 (x,y) 的坐标变为 (x+y,x−y)后，原坐标系中的曼哈顿距离等于新坐标系中的切比雪夫距离。
  • 将一个点 (x,y) 的坐标变为 ((x+y)/2,(x−y)/2)后，原坐标系中的切比雪夫距离等于新坐标系中的曼哈顿距离。
• 24.7.20 2850将石头分散到网格图的最少移动次数 全排列，调包
• 24.7.28 699掉落的方块 暴力枚举，线段树不会！
• 24.7.30 2961双模幂运算 快速幂

一眼题

• 24.7.12 2974最小数字游戏
• 24.7.16 2956找到两个数组中的公共元素
• 24.7.31 3111覆盖所有点的最小矩形数目
• 24.8.13 3151特殊数组I
• 24.8.18 551学生出勤记录I
• 24.8.29 3142判断矩阵是否满足条件
• 24.9.1 1450在既定时间做作业的人数
• 24.9.4 2860让所有学生保持开心的分组方法数

刷题技巧

巧用内置库

• 计算前缀和：list(itertools.accumulate(l, initial=0))
• 获取连续重叠对 for a, b in itertools.pairwise(nums):
• 从nums中选2个元素组合/排列 for i in itertools.combinations/permutations(nums, 2):
• check函数二分：bisect_left(range(1_000_000_001), True, key=check)

巧用数据结构

• 有序数组 from sortedcontainers import SortedList

其他技巧

• 死循环，同时记录当前轮数 for i in count(1):
• 数组每行最大值：mx_row = list(map(max, nums))
• 数组每列最大值：mx_col = list(map(max, zip(*nums)))
• 1_000_000_001表示10**9+1
• 设置dict的value默认值为ind：defaultdict(lambda: inf)
• enumerate(nums, start=1)