本文共 2579 字，大约阅读时间需要 8 分钟。
数组、链表、跳表：
一般暴力可解决，优化思想一般有双指针、升维
1、数组
283 移动零
11 盛最多水的容器
70 爬楼梯
15 三数之和
2、链表
206 反转链表
24 两两交换链表中的节点
141 环形链表
142 环形链表II
25 K个一组翻转链表
3、其他
26 删除排序数组中的重复项
27 旋转数组
28 合并两个有序链表
30 两数之和
31 加一
栈：
具有最近相关性的问题，使用栈
队列：
具有先来后到特点的问题，使用队列
滑动窗口都使用队列
20 有效的括号
155 最小栈
84 柱状图中最大的矩形
239 滑动窗口最大值
641 设计循环双端队列
42 接雨水
哈希表、映射、集合
242 有效的字母异位词
49 字母异位词分组
1 两数之和
树、二叉树、二叉搜索树
树问题的解法都是递归
树的题目解法比较固定，要么深搜要么广搜
94 二叉树的中序遍历
144 二叉树的前序遍历
590 N叉树的后序遍历
589 N叉树的前序遍历
429 N叉树的层序遍历
递归
递归的基本思想为：1、找最近重复子问题；2、数学归纳法
递归的步骤为：1、递归终止条件；2、处理当层逻辑；3、跳到下一层；4、清理当前层
递归的代码模板：
public void recur(int level, int param) { //1、递归出口 if (level > MAX_LEVEL) { //处理结果 return; } //2、处理当前逻辑（参数发生变化） param = process(level, param); //3、进入下一层（缩小问题规模：子问题） recur(level+1, param); //4、逆处理（将参数回退到之前的状态） param = inverseProcess(level, param);} 相关题目：
70 爬楼梯
22 括号生成
226 翻转二叉树
98 验证二叉搜索树
104 二叉树的最大深度
其他：
111 二叉树的最小深度
297 二叉树的序列化与反序列化
236 二叉树的最近公共祖先
105 从前序与中序遍历序列构造二叉树
77 组合
46 全排列
47 全排列II
分治、回溯
将一个规模为N的问题分解为K个规模较小的子问题，这些子问题相互独立且与原问题性质相同
求出子问题的解，即可得到原问题的解。
简单问题可用二分法解决
50 Pow(x, n)
78 子集
169 多数元素
17 电话号码的字母组合
51 N皇后
深搜、广搜
1、深搜
1）递归写法
def dfs(node, visited): #终止 if node in visited: return visited.add(node) ... for next_node in node.children(): if not next_node in visited: dfs(next_node, visited)
2）可以用栈
2、广搜
BFS代码结构
def BFS(graph, start, end): queue = [] queue.append([start]) visited.add(start) while queue: node = queue.pop() visited.add(node) process(node) nodes = generate_related_nodes(node) queue.push(nodes)
102 二叉树的层序遍历
433 最小基因变化
22 括号生成
515 在每个树行中找最大值
其他：
127 单词接龙
126 单词接龙II
200 岛屿数量
529 扫雷游戏
贪心算法
贪心算法是一种在每一步选择中都采取在当前状态下最好或最优的选择，不能回退
动态规划会保存以前的运算结果，并根据以前的结果对当前进行选择，有回退功能
322 零钱兑换
860 柠檬水找零
122 买卖股票的最佳时机
455 分发饼干
874 模拟行走机器人
55 跳跃游戏
45 跳跃游戏II
二分查找
1、二分查找的前提
1）目标函数单调性
2）存在上下界
3）能够通过索引访问
2、代码模板
left, right = 0, len(array)-1while left <= right: mid = (left + right) / 2 if array[mid] == target: # find the target break or return result elif array[mid] < target: left = mid + 1 else: right = mid - 1
3、相关题目
69 x的平方根
367 有效的完全平方数
33 搜索旋转排序数组
74 搜索二维矩阵
153 妱旋转排序数组中的最小值
动态规划
1、关键点
动态规划和递归或者分治没有根本上的区别（关键看有无最优子结构）
共性：找到重复子问题
差异性：最优子结构、中途可以淘汰次优解
2、解题思路
1）最优子结构 opt[n] = best_of(opt[n-1], opt[n-2], ...);
2）存储中间状态opt[i]
3）递推公式（状态转移方程或DP方程）
Fib：opt[n-1] + opt[n-2]
4）二维路径：opt[i, j] = opt[i+1, j] + opt[i][j+1]（判断opt[i, j]是否空地）
3、相关题目
62 不同路径
63 不同路径II
1143 最长公共子序列
70 爬楼梯
120 三角形最小路径和
53 最大子序和
152 乘积最大子数组
63 不同路径II
322 零钱兑换
排序算法
其余不常见的
字典树、并查集、高级搜索、红黑树、AVL树、位运算、布隆过滤器、LRU缓存
转载地址：http://mynii.baihongyu.com/