leetcode题目分类

字典树(Trie树、前缀树)

模板题

208. 实现 Trie (前缀树)

209. 单词替换

210. 添加与搜索单词 - 数据结构设计

211. 键值映射

212. 实现一个魔法字典

213. 前缀和后缀搜索

214. 字符串的前缀分数和

进阶：01字典树

环检测 & 拓扑排序

207. 课程表
208. 课程表 II
     剑指 Offer II 115. 重建序列

回溯

698. 划分为k个相等的子集
699. 火柴拼正方形
700. 公平分发饼干

思路：
1.回溯前的准备
2.要回溯什么
回溯函数内
3.终止条件
4.进入和退出怎么搞

递推

递归

使用递归树的方法来判断问题

回溯-》记忆化搜索-》动态规划

动态规划

思路：

1. 确定dp数组以及下标的含义
2. 确定递推公式
3. dp数组如何初始化
4. 确定遍历顺序
   5. 举例推导dp数组

写代码顺序：

0. 边界条件（最后考虑）

1. 初始化

2. 遍历

3. 递推公式

4. 返回

5. 记忆化搜索

   1. Leetcode 140 单词拆分 II
   2. Leetcode 472 连接词
   3. 10题正则表达式匹配
   4. 第37题解数独

6. 区间dp

   1. 当问题可以分解为若干个子区间，并且子区间之间有一定的联系或者约束时，可以考虑用区间dp来求解
   2. 合并、匹配、划分
   3. 石子合并、括号匹配、回文串、邮局建设
   4. 1000. 合并石头的最低成本
   5. 而状态转移方程一般是枚举区间内的一个分割点
      1. 如dp [i] [j] = min {dp [i] [k]+dp [k+1] [j]+cost}

能解决的问题：

1.求最大值/最小值

1014. 最佳观光组合
1015. 买卖股票的最佳时机
1016. 买卖股票的最佳时机 II
      剑指 Offer 47. 礼物的最大价值
      剑指 Offer 42. 连续子数组的最大和
1017. 下降路径最小和
1018. 三角形最小路径和

2.求是否可以完成组合

139. 单词拆分

3.求子数组 个数/最大值/长度

413. 等差数列划分

4.组合总数

剑指 Offer 10- II. 青蛙跳台阶问题
剑指 Offer 46. 把数字翻译成字符串

5.最少操作数

72. 编辑距离

贪心

55. 跳跃游戏
56. 跳跃游戏 II

测试用例的设计

边界条件的测试

0
最大值

功能测试

前缀和

一维前缀和

二维前缀和

第一题就是基本的读入字符串排序，忘记细节了。

第二题是读入一01串，对应的下标为士兵的能力，0代表攻击士兵，1代表防守士兵，找到一个分割点，使得左侧攻击士兵和右侧防御士兵差的绝对值最小。这题直接用一个求和数组记录遍历就能过。

第三题是给定一个数组，删掉下标不为质数的值，然后合并起来循环操作，求最后一个数。这题是能找到规律，在某个区间的答案会是一个定值。直接暴力解了。

第四题是给多个环形链表的部分（可以重叠），把他们串起来然后切开形成最小字典序。这题主要是记录一下链表顺序，正逆比较一下就可以

第五题买股票进阶版，给定本金，每天都可以买入卖出1笔，而且可以手里留存多笔股票，求最大利润。这题不太会做，暴力DFS做的只过了50，蹲个大佬

做了4个半，最近一个月才开始补算法，难点的题就做不出来了，以及我是用python写的，可能时间复杂度要求和C++比会有些差别

参考资料

[详解前缀树「TrieTree 汇总级别整理 🔥🔥🔥」]https://leetcode.cn/problems/sum-of-prefix-scores-of-strings/solution/by-lfool-w82u/
前缀和
前缀异或
Codeforces游玩攻略
Codeforces快速精通
ACM-高精度模板(综合篇)
C++ lambda表达式与函数对象
https://codeforces.com/blog/entry/66715
https://codeforces.com/blog/entry/66909

区间dp

(区间dp) 力扣区间dp 题集记录
[力扣] DP问题分类汇总
区间dp入门——总结+习题+解析
OI Wiki

记忆化搜索

LeetCode刷题总结 — 记忆化搜索框架