来自：leetcode300+题、《剑指offer》100+题、《数据结构与算法之美》、《业务开发算法50讲》
前言
两个误区
1、「算法工程师」里的算法里和「数据结构与算法」里的算法
- 前者重点在于数学建模和调参经验，计算机只是拿来做计算工具，是「数学算法」
- 后者重点在于计算机思维，站在计算机的视角抽象、化简问题，然后用编程的方式去解决问题，是「计算机算法」
本文所说的算法是指「计算机算法」
一般情况下，计算机算法和数学算法没什么关系，很多人对计算机算法的误解可能是以前学数学的时候留下的「后遗症」。数学题一般是通过仔细观察，找几何关系、列方程，然后算出答案，而计算机思维恰好相反：有没有什么数学公式就交给你们人类去推导吧，如果找到一些定理最好，找不到就穷举呗
2、只有算法工程师和大数据工程师需要学习算法，开发不需要
千万不要以为学好数据结构和算法就能去做算法工程师，也不要以为做算法工程师就不要学习算法
一个事实是：大部分技术人员都是基于现成的开发框架做事
另一个事实是：只要你想找技术相关的岗位，数据结构与算法的考察是绕不开的
为什么要学习算法
比较虚的说法：技术人员的内功、扎实的基本功、各种高大上的深入原理。。。
比较实的说法：技术人员的核心竞争力，表现在：
- 对于在岗的技术人员：工具的熟练程度 和 业务的掌握程度
-
算法的本质
在时间和空间的权衡下，找到解决问题的最适方案(而不是最优)
-
分享目录
包含基本的数据结构和基本题型、常见的算法题型套路和模板、计算机世界里用到的一些算法
数据结构
- 数组
- 链表
- 栈
- 普通栈
- 单调栈
- 队列
- 普通队列
- 单调队列
- 优先队列
- 树
- 树的前、中、后遍历
- 树的遍历变形类
- 树的构建类问题
- 二叉搜索树(bst)
- 完全二叉树
- 前缀树
- 图
- 图的存储
- 并查集
- 图的深度和广度遍历
- 图的遍历变形
- 最小生成树
- 最短路径
- 拓扑排序
算法
- 二分
- 双指针与滑动窗口
- dfs
- bfs
- 动态规划
- 位运算
- 归并与快排
- 其他高频技巧类
数据结构
数组
数组
定义：存储元素数量固定且元素类型相同的有序集
一维数组
var arr [5]int
二维数组
var arr [5][5]int切片
通常大家在go里用的是切片，切片是基于数组增加了动态扩容机制的一种有序集合
var arr []int
切片的扩容机制(这里不考虑内存对齐)
If 旧容量<1024，旧容量*2 else 旧容量*1.25
// runtime/slice.go func growslice(et *_type, old slice, cap int) slice { //et 表示slice的一个元素，old 表示旧的slice cap 表示新切片必须的容量 … newcap := old.cap doublecap := newcap + newcap if cap > doublecap { newcap = cap } else { if old.len < 1024 { newcap = doublecap } else { for 0 < newcap && newcap < cap { newcap += newcap / 4 } if newcap <= 0 { newcap = cap } } } … }问题
1、扩容机制后内存还连续吗？
2、为什么几乎所有的语言都按倍数扩容，而不是+1，+c的固定大小扩容呢
复杂度推导
假设要插入n个元素
每次+1的扩容
1+2+3+…+n = n^2，复杂度O(N^2)
- 每次+c的扩容
1c+2c+3c+…+floor(n/c) = n^2，复杂度O(N^2)
- 每次2倍扩容
总拷贝次数，就是从 1 加到 2 的 x 次，其中 x 是 logn 向上取整；这是因为容量每次都在翻番，所以每次触发拷贝的时候，容量分别是 1、2、4、8 … 一直到 logn 向上取整
1+2+4+8+…+2^x=2^(x+1)−1，复杂度O(N)
题型
两数之和 给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。 你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。 你可以按任意顺序返回答案。 示例 1： 输入：nums = [2,7,11,15], target = 9 输出：[0,1] 解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。 示例 2： 输入：nums = [3,2,4], target = 6 输出：[1,2]
其他题型
结合双指针
- 删除有序数组中的重复项
- 移除元素
- 两数之和 II - 输入有序数组
- 优势洗牌(田忌赛马类问题)
二维数组
- 旋转图像
-
链表
type ListNode struct { val int next *listNode }
go里有官方的链表库“container/list”，很少见到有人用到，基本上动态数组完事
但是在算法里链表是常考题型题型
1、反转链表
反转链表 给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。 示例 1： 输入：head = [1,2,3,4,5] 输出：[5,4,3,2,1]
2、回文链表
回文链表 给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。 示例 1： 输入：head = [1,2,2,1] 输出：true 示例 2： 输入：head = [1,2] 输出：false其他题型
反转类
- K 个一组翻转链表
合并类
结合双指针
- 删除排序链表中的重复元素
- 链表中倒数第k个节点
- 环形链表
-
栈
普通栈
模板
var stack []int stack = append(stack, 0)//进栈 stack = stack[:len(stack-1)]//出栈
题型
1、有效的括号
有效的括号 给定一个只包括 ‘(‘，’)’，’{‘，’}’，’[‘，’]’ 的字符串 s ，判断字符串是否有效。 有效字符串需满足： 左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序闭合。 示例 1： 输入：s = “()” 输出：true 示例 2： 输入：s = “()[]{}” 输出：true其他题型
-
单调栈
维持了栈的先进后出的特性，附加了栈中元素单调的特性
使用场景较少，一般用在“Next Greater Element”类问题模板
var stack []int for i := 0; i < n i++ { for len(stack) > 0 && heights[stack[len(stack)-1]] > heights[i] {//出栈：不满足单调性质 top := stack[len(stack)-1] stack = stack[:len(stack)-1] //算法逻辑 … } //算法逻辑 … stack = append(stack, i) }
题型
每日温度 给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指在第 i 天之后，才会有更高的温度。如果气温在这之后都不会升高，请在该位置用 0 来代替。 示例 1: 输入: temperatures = [73,74,75,71,69,72,76,73] 输出: [1,1,4,2,1,1,0,0] 示例 2: 输入: temperatures = [30,40,50,60] 输出: [1,1,1,0]
其他题型
- 柱状图中最大的矩形
- 下一个更大元素 II
去重类型(利用单调栈模板)
- 移掉 K 位数字
- 去除重复字母（去重题型的最高境界）
- 不同字符的最小子序列（跟去除重复字母相同）
拼接最大数(劝退题，慎做，难哭：涉及单调栈、数学、枚举、分治)
队列
普通队列
模板
var queue []int queue = append(queue, 0)//进队 queue = queue[1:]//出队
单调队列
维持了栈的先进先出的特性，附加了队列中元素单调的特性
一种队列结构，既能够维护队列元素「先进先出」的时间顺序，又能够正确维护队列中所有元素的最值
模板
var queue []int for i := k; i < n; i++ { for len(queue) > 0 && nums[queue[len(queue)-1]] < nums[i] {//出队：不满足单调 queue = queue[:len(queue)-1] //算法逻辑 … } queue = append(queue, i) //算法逻辑 … }
题型
1、滑动窗口最大值
滑动窗口最大值 给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。 返回 滑动窗口中的最大值 。 示例 1： 输入：nums = [1,3,-1,-3,5,3,6,7], k = 3 输出：[3,3,5,5,6,7] 解释： 滑动窗口的位置 最大值 ———————- ——- [1 3 -1] -3 5 3 6 7 3 1 [3 -1 -3] 5 3 6 7 3 1 3 [-1 -3 5] 3 6 7 5 1 3 -1 [-3 5 3] 6 7 5 1 3 -1 -3 [5 3 6] 7 6 1 3 -1 -3 5 [3 6 7] 7优先队列
概念是是队列，每个元素被赋予了优先级，队列按优先级出队入队；实现上一般都是用堆来实现
模板
type heapInt []int func (h heapInt) Len() int { return len(h) } func (h heapInt) Less(i, j int) bool { return h[i] > h[j] } func (h heapInt) Swap(i, j int) { h[i], h[j] = h[j], h[i] } func (h heapInt) Push(x interface{}) { h = append(h, x.(int)) } func (h heapInt) Pop() interface{} { x := (h)[len(h)-1] h = (h)[:len(*h)-1] return x }
题型
1、数组中第k个最大元素
数组中的第K个最大元素 给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。 请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。 示例 1: 输入: [3,2,3,1,2,4,5,5,6] 和 k = 4 输出: 4其他题型
- 合并K个升序链表
- 课程表 III
设计推特（数据结构综合设计题）
树
树的题型算是承上启下的一类综合型算法，包含了递归、回溯、分治，往深了还能结合动态规划
树的前、中、后遍历
层次遍历属于bfs范畴，本节不做讨论
b(b+)树、线段树(竞赛范畴)、红黑树这些数据结构不会有面试让你手写，我也没遇到这类算法题，本节也不做讨论
节点
type TreeNode struct { Val int Left TreeNode Right TreeNode }
前中后序遍历模版-递归
func traversal(root TreeNode) []int { var ret []int var helper func(root TreeNode) helper = func(root TreeNode) { if root == nil { return } //前序遍历位置 //ret = append(ret, root.Val) traversal(root.Left) //中序遍历位置 //ret = append(ret, root.Val) traversal(root.Right) //后序遍历位置 //ret = append(ret, root.Val) } helper(root) return ret }
前中后序遍历模版-迭代
我这里没写后序遍历，如果想一套模版搞定前中后序遍历，下面代码应该怎么改？
根 左 右
右 左 根
左 右 根
func Traversal(root TreeNode) []int { if root == nil { return []int{} } var ret []int var stack []*TreeNode for len(stack) > 0 || root != nil { if root != nil { //前序 //ret = append(ret, root.Val) stack = append(stack, root) root = root.Left } else { root = stack[len(stack)-1] stack = stack[:len(stack)-1] //中序 //ret = append(ret, root.Val) root = root.Right } } return ret }树的遍历变形类
树的变形题有两个思考方向
遍历一遍二叉树得出答案
- 先序遍历
- 中序遍历（尤其二叉搜索树）
- 后序遍历
- 层序遍历（尤其按照层来解决问题的时候）
- 序列化与反序列化（结构唯一性问题）
- 通过分解问题计算出答案
- 分治思想
题型
二叉树的最大深度
遍历一遍如何得到答案
func maxDepth(root TreeNode) int { ret, depth := 0, 0 var helper func(root TreeNode) helper = func(root TreeNode) { if root == nil { return } depth += 1 ret = getMax(ret, depth) helper(root.Left) helper(root.Right) depth -= 1 return } helper(root) return ret }
分解子问题如何得到答案
当前节点的高度=？
func maxDepth(root TreeNode) int { if root == nil { return 0 } leftDepth, rightDepth := maxDepth(root.Left), maxDepth(root.Right) return getMax(leftDepth, rightDepth) + 1 }
当然，但是并不是所有问题两种思路都行得通，大部分情况下终有一种方案可行
二叉树的最近公共祖先
func lowestCommonAncestor(root, p, q TreeNode) TreeNode { if root == nil || root == p || root == q { return root } //去root的左右两边找p所属的子树 left, right := lowestCommonAncestor(root.Left, p, q), lowestCommonAncestor(root.Right, p, q) if left != nil && right != nil { //在root左右两边 return root } if left == nil && right != nil { //在root左边 return right } if left != nil && right == nil { //在root左边 return left } return nil }
其他题型
- 翻转二叉树
- 填充每个节点的下一个右侧节点指针
- 二叉树展开为链表
- 最大二叉树
-
业务应用
git rebase
rebase合并得到的是一条直线，他原理是啥呢
树的构建类问题
如何根据已有条件构建二叉树
什么情况下能唯一确定一棵二叉树？
什么情况下不能，为什么题型
其他题型
-
二叉搜索树(bst)
定义：
或者是一棵空树
- 或者是具有下列性质的二叉树：
- 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值
- 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值
- 它的左、右子树也分别为二叉排序树
基于上述性质：二叉搜索树中序遍历有序
如何在一颗二叉搜索树中搜索某个节点呢
模板
func searchBST(root TreeNode, val int) TreeNode { if root == nil { return nil } if root.Val == val { return root } else if val < root.Val { return searchBST(root.Left, val) } else if val > root.Val { return searchBST(root.Right, val) } return nil }
题型
二叉搜索树中第K小的元素
func kthSmallest(root TreeNode, k int) int { var ret int var helper func(root TreeNode) helper = func(root TreeNode) { if root == nil { return } helper(root.Left) k -= 1 if k == 0 { ret = root.Val return } helper(root.Right) return } helper(root) return ret }
删除二叉搜索树中的节点
func deleteNode(root TreeNode, key int) *TreeNode { if root == nil { return nil } if root.Val == key { if root.Left == nil { //情况1 无左子 return root.Right } if root.Right == nil { //情况2 无右子 return root.Left } //情况3 左右都有 寻找左子最大或右子最小 temp := root.Right for temp.Left != nil { temp = temp.Left } temp.Left = root.Left root = root.Right } else if key < root.Val { //去左子树删除 root.Left = deleteNode(root.Left, key) } else if key > root.Val { //去右子树删除 root.Right = deleteNode(root.Right, key) } return root }
其他题型
- 把二叉搜索树转换为累加树
- 从二叉搜索树到更大和树
- 二叉搜索树中的插入操作
- 验证二叉搜索树
- 不同的二叉搜索树
-
完全二叉树
性质：叶子结点只能出现在最下层和次下层，且最下层的叶子结点集中在树的左部
下层节点铺满时就变成了满二叉树题型
完全二叉树的节点个数
最简单的方法就是直接遍历，对每个访问的节点计数，但是这就没用到完全二叉树的性质
假设左子树的高度为 l ，右子树的高度为 r，利用完全二叉树的性质： 当 l =r时，也就是3、4这种情况，左树必定是满的，所以求左树节点数就是 2^l-1，右树节点数依旧用递归的方法去求
- 当 l！=r 时， 也就是1、2这种情况，右树必然是满的，所以求右树节点数就是 2^r-1
func countNodes(root TreeNode) int { if root == nil { return 0 } l, r := getHeight(root.Left), getHeight(root.Right) if l == r { //左满右不满 return 1<<l + countNodes(root.Right) } else { //左不满右满 return 1<<r + countNodes(root.Left) } } //递归求高度 func getHeight(root TreeNode) int { if root == nil { return 0 } return getMax(getHeight(root.Left), getHeight(root.Right)) + 1 }
前缀树
前缀树，又叫字典树， 是一颗非典型的多叉树模型
多叉好理解，即每个结点的分支数量可能为多个
什么是非典型呢，就是它和一般的树节点的结构不太一样
//这是多叉树节点 type MultiTree struct { val int children []MultiTree }
看个例子
有三个单词，”sea”,”sells”,”she”，它的前缀树长这样，那么前缀树的节点如何设计呢？
前缀树的节点
//前缀树 type Trie struct { isEnd bool children [26]Trie }
为什么这么设计？
看看前缀树需要哪些操作
插入
向 Trie 中插入一个单词 word
首先从根结点的子结点开始与 word 第一个字符进行匹配，一直匹配到前缀链上没有对应的字符，这时开始不断开辟新的结点，直到插入完 word 的最后一个字符，同时还要将最后一个结点isEnd = true;，表示它是一个单词的末尾
查找
查找 Trie 中是否存在单词 word
从根结点的子结点开始，一直向下匹配即可，如果出现结点值为空就返回 false，如果匹配到了最后一个字符，那我们只需判断 node->isEnd即可
前缀匹配
判断 Trie 中是或有以 prefix 为前缀的单词
和 search 操作类似，只是不需要判断最后一个字符结点的isEnd，因为既然能匹配到最后一个字符，那后面一定有单词是以它为前缀的
模板
type Trie struct { isEnd bool children [26]Trie } func Constructor() Trie { return Trie{} } //插入 func (this Trie) Insert(word string) { curNode := this for i := 0; i < len(word); i++ { if curNode.children[word[i]-‘a’] == nil { curNode.children[word[i]-‘a’] = &Trie{} } curNode = curNode.children[word[i]-‘a’] } curNode.isEnd = true } //查找 func (this Trie) Search(word string) bool { curNode := this for i := 0; i < len(word); i++ { if curNode.children[word[i]-‘a’] == nil { return false } curNode = curNode.children[word[i]-‘a’] } return curNode.isEnd } //前缀匹配 func (this Trie) StartsWith(prefix string) bool { curNode := this for i := 0; i < len(prefix); i++ { if curNode.children[prefix[i]-‘a’] == nil { return false } curNode = curNode.children[prefix[i]-‘a’] } return true }
题型
-
业务应用
前缀树的应用还挺多的，常见的比如我们的自动补全功能，搜索引擎的搜索下拉等等
图
图在日常开发中的使用场景很少，对于开发老说，除了地图业务，其他类型的业务很少涉及
但是！！！leetcode和大公司面试(尤其是外企)里属于高频题型，因为大家用的少，所以区分度高(卷～)
再加一个但是！！！图的考察点很单一，题型没法多变，辨识度高，所以图的问题也很简单(模板好背)
简单复习下图论的基本知识
图的类型 无向图
- 有向图
- 加权图
顾名思义，就是每天边带了一个权重，这个权重可以是任何一种度量，比如时间，尺寸，距离等，比如下面地点的距离 
图的连通性
图并不是所有节点都是联通的，如下面的图，其实对应着4个连通分量(连通子图)
对于有向图，联通的含义是指每个节点存在到其他任意节点的路径(强连通)
但是连通问题我没遇到过有向图，所以只需要关注无向图
入度和出度
主要是针对有向图，入度是指指向某个节点的边的数量，出度是指某个节点指出去的边的数量
图的存储
比较常见的就两种
- 邻接矩阵
二维数组存储 
- 邻接表
模板
邻接矩阵使用起来比较简单，所以刷题的时候直接用邻接矩阵就行
代码表示用二维数组或map数组都可以(我个人喜欢用map数组)
//map数组表存储 graph := make([]map[int]bool, numCourses) for i := 0; i < numCourses; i++ { graph[i] = make(map[int]bool, 0) } for i := 0; i < len(prerequisites); i++ { graph[prerequisites[i][1]][prerequisites[i][0]] = true }
图的遍历
图就是就是树的延伸，所以对图的遍历可以参考多叉树的遍历
多叉树的遍历模板
func traversal(root Node) []int { if root == nil { return nil } for _,child := range root.Children { traversal(child) } }
图是可能存在环的，所以如果直接复用树的遍历，会产生死循环
这就需要引入一个visited数组对已经访问过的顶点进行标记
*图的遍历模板
func dfsGraph(i int, graph []map[int]int, visited []bool) { if visited[i]{ return } visited[i] = true //标记访问 for k, _ := range graph[i] { dfsGraph(k, graph, visited) } return }
题型
其他题型
在bfs节讲到，bfs一般用在层序遍历和无权图的路径问题上，所以拓扑排序用bfs更合适
事实上，图的大部分问题用bfs也能解决，只不过用dfs更容易处理，所以硬用bfs属于自找罪受
也就是说，除了树的层次遍历和拓扑排序，其他问题不要用bfs
定义：
拓扑排序是一种应用在有向无环图(DAG)上、给出结点输出先后顺序的算法
举个例子，下面的图，其拓扑排序结果可以是“微积分-机器学习”、“线性代数-机器学习”、“概率论与数理统计-机器学习”
即排序结果并不唯一
为什么一定要求是有向无环图呢
应用场景
- 环的检测
-
模板
题型
平行课程
思考一下这题涉及哪些点
func minimumSemesters(n int, relations [][]int) int { //图的构造 graph := make([]map[int]bool, n) for i := 0; i < n; i++ { graph[i] = make(map[int]bool, 0) } //入度构造 indgree := make([]int, n) //入度 for i := 0; i < len(relations); i++ { graph[relations[i][0]-1][relations[i][1]-1] = true indgree[relations[i][1]-1] += 1 } var queue []int for i := 0; i < len(indgree); i++ { if indgree[i] == 0 { queue = append(queue, i) } } //bfs模版 var ret int var visitedCount int for len(queue) > 0 { levelN := len(queue) for i := 0; i < levelN; i++ { visitedCount += 1 for vertex, _ := range graph[queue[0]] { indgree[vertex] -= 1 if indgree[vertex] == 0 { queue = append(queue, vertex) } } queue = queue[1:] } ret += 1 } if visitedCount != n { return -1 } return ret }其他题型
- 课程表 II
-
环的问题小结
检测图中是否有环
无向图：dfs、bfs(类似拓扑排序)、并查集
-
其他不常考的图论知识点
正常图论相关题目上述知识点已经完全满足了，题型最多的还是连通问题、环问题、路径问题
最小生成树
Kruskal 算法
-
最短路径
单源最短路径：Dijkstra 算法
-
并查集
概念
并查集（Union Find）也叫「不相交集合（Disjoint Set）」，专门用于 动态处理 不相交集合的「查询」与「合并」问题，所谓「动态」的意思是：要处理的数据不是一开始就确定好的，而是在遍历的过程中变化的
举个例子
有这么几组数据：{1->2}、{2->3}、{4->5}
我们能知道123是连通的，45是连通的，那么我们怎么知道123连通45不连通的呢
首先需要将123合并的一个集合里去，并查集的「合并」就是解决这个问题的
其次要查询某个树是否在某个集合里，并查集的「查询」就是解决这个问题的
应用场景
并查集通常只解决连接的问题，而不解决路径的问题
而用并查集能解决的问题，dfs通常都能解决
那为啥要用并查集呢
简单、效率高
合并方式 代表元法
随机选择一个「代表元素」，以{1->2}、{2->3}、{4->5}为例子，比如选择2为代表元，合并结果就是{1->3>2}
那么就会出现这种情况 
复杂度就退互道O(n)了，优化方式就是「按秩合并」和「路径压缩了」
- 按秩合并
“秩”的意思就是书的高度，每次合并的时候比较下两棵树的高度，高度小的合并到高度大的树下面 
模板
type joinSet2 struct { parent []int rank []int } func (set joinSet2) init() { for i := 0; i < len(set.parent); i++ { set.parent[i] = i set.rank[i] = 1 } return } func (set joinSet2) find(x int) int { if set.parent[x] == x { return x } return set.find(set.parent[x]) } //按秩合并 func (set joinSet2) merge(i, j int) { x, y := set.find(i), set.find(j) rankX, rankY := set.rank[x], set.rank[y] if rankX <= rankY { set.parent[x] = y } else { set.parent[y] = x } if rankX == rankY && x != y { set.rank[y] += 1 } return }
- 路径压缩
每一次查询都会把所有节点指定唯一的父亲节点，即合并树的查找路径为1 
模板
type joinSet struct { parent map[string]string } func (set joinSet) init(equations [][]string) { set.parent = make(map[string]string, 0) for i := 0; i < len(equations); i++ { set.parent[equations[i][0]], set.parent[equations[i][1]] = equations[i][0], equations[i][1] } return } func (set joinSet) find(x string) string { if set.parent[x] == x { return x } tempParent := set.find(set.parent[x]) set.parent[x] = tempParent return set.parent[x] } func (set *joinSet) merge(x, y string, divRet float64) { parentX, parentY := set.find(x), set.find(y) if parentX != parentY { set.parent[parentX] = parentY } }
题型
省份数量
省份数量 有 n 个城市，其中一些彼此相连，另一些没有相连。如果城市 a 与城市 b 直接相连，且城市 b 与城市 c 直接相连，那么城市 a 与城市 c 间接相连。 省份 是一组直接或间接相连的城市，组内不含其他没有相连的城市。 给你一个 n x n 的矩阵 isConnected ，其中 isConnected[i][j] = 1 表示第 i 个城市和第 j 个城市直接相连，而 isConnected[i][j] = 0 表示二者不直接相连。 返回矩阵中 省份 的数量。
算法
二分
二分查找的思想很简单，就是循环两边找，每次循环去一半，但二分的代码非常难写：mid加1还是减1，for循环里用”<=”号还是”<”号，kmp算法的发明者Knuth大佬对二分的评价：思路很简单，细节是魔鬼
本节给出了一个统一的二分模板，能解决几乎所有的二分场景，“fuckxxxx细节”
常用场景：
- 找一个数
- 找左边界
-
找一个数
模板
left, right := 0, n-1 for left <= right { mid := left + (right-left)/2 if nums[mid] < target { left = mid + 1 } else if nums[mid] > target { right = mid -1 } else { return mid } }
找边界
这类问题一般是要求找到第一个或者最后一个出现的元素
最大化最小值/最小化最大值类题型一般都是用二分模板-左边界
left, right := 0, n-1 for left <= right { mid := left + (right-left)/2 if nums[mid] < target { left = mid + 1 } else if nums[mid] > target { right = mid -1 } else { right = mid - 1//找左边界 } } if left >= n || nums[left] != target { return []int{-1, -1} }
模板-右边界
left, right := 0, n-1 for left <= right { mid := left + (right-left)/2 if nums[mid] < target { left = mid + 1 } else if nums[mid] > target { right = mid -1 } else { left = mid + 1//找右边界 } } if right < 0 || nums[right] != target { return []int{-1, -1} }
为什么左右边界模板里比正常二分模板多了下面的判断
题型
1、分割数组的最大值
分割数组的最大值 给定一个非负整数数组 nums 和一个整数 m ，你需要将这个数组分成 m 个非空的连续子数组。 设计一个算法使得这 m 个子数组各自和的最大值最小。 示例 1： 输入：nums = [7,2, 5, 10,8], m = 2 输出：18 解释： 一共有四种方法将 nums 分割为 2 个子数组。 其中最好的方式是将其分为 [7,2,5] 和 [10,8] 。 因为此时这两个子数组各自的和的最大值为18，在所有情况中最小。
2、在排序数组中查找元素的第一个和最后一个位置
在排序数组中查找元素的第一个和最后一个位置 给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。 如果数组中不存在目标值 target，返回 [-1, -1]。 进阶： 你可以设计并实现时间复杂度为 O(log n) 的算法解决此问题吗？ 示例 1： 输入：nums = [5,7,7,8,8,10], target = 8 输出：[3,4]
其他题型 - 爱吃香蕉的珂珂
- 在 D 天内送达包裹的能力
- 剑指 Offer 11. 旋转数组的最小数字
-
业务应用
双指针与滑动窗口
顾名思义，就是通过两个指针的不同行为来寻找答案，是一种常见的技巧类思想
使用场景：
指针的行为类型包含： 快慢指针
- 左右指针
-
快慢指针
模板
slow, fast := 0, 0 for fast < n { //算法逻辑 … fast += 2 } return slow
题型
移除元素
移除元素 给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。 不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。 元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。 示例 1： 输入：nums = [3,2,2,3], val = 3 输出：2, nums = [2,2] 解释：函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。你不需要考虑数组中超出新长度后面的元素。例如，函数返回的新长度为 2 ，而 nums = [2,2,3,3] 或 nums = [2,2,0,0]，也会被视作正确答案。左右指针
数组类问题大都靠左右指针：反转数组、二分(二分本质上也是靠左右指针)
相向而行
模板
left, right := 0, n-1 for left < right { for left < right && xxx {//算法逻辑 left += 1 } for left < right && xxx {//算法逻辑 right -= 1 } //算法逻辑 … }
题型
上面的移除元素如何用相向指针完成？分别使用相向指针和快慢指针区别的区别在哪？
相背而行(中心扩展)
模板
left,right := 0,0 for left >= 0 && right < len(s) && xxx {//算法逻辑 left, right = left-1, right+1 } //算法逻辑 …
题型
最长回文子串
最长回文子串 给你一个字符串 s，找到 s 中最长的回文子串。 示例 1： 输入：s = “babad” 输出：”bab” 解释：”aba” 同样是符合题意的答案。其他题型
-
滑动窗口
子串问题大都靠滑动窗口解决；有一定难度，主要在窗口的边界维护和更新处理上比较麻烦
但是！！！如果基于模板来做问题会变的很简单！！！模板
s t aaanv abca 4 2 //need代表窗口内需要凑齐的字符数量 //windew代表窗口内已凑齐的字符数量 //validCnt代表窗口内已凑齐的字符种类数量 need, window, validCnt := make(map[byte]int, 0), make(map[byte]int, 0), 0 //初始化need for i := 0; i < m; i++ { … } left, right := 0, 0 for right < n { // 右边入窗口，窗口内数据的更新 if , exist := need[s[right]]; exist { window[s[right]]++ if window[s[right]] == need[s[right]] { validCnt += 1 } } right += 1 // 左侧窗口收缩条件 for window needs shrink { // 采集答案 … // 左边移出窗口，窗口内数据的更新 if , exist := need[s[left]]; exist { if window[s[left]] == need[s[left]] { validCnt -= 1 } window[s[left]] -= 1 } left -= 1 } }
题型
最小覆盖子串
最小覆盖子串 给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 “” 。 注意： 对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。 如果 s 中存在这样的子串，我们保证它是唯一的答案。 示例 1： 输入：s = “EBBANCF”, t = “ABC” 输出：”BANC”
滑动过程：
初始状态
增加 right，直到窗口 [left, right) 包含了 T 中所有字符：
现在开始增加 left，缩小窗口 [left, right)：
直到窗口中的字符串不再符合要求，left 不再继续移动：
之后重复上述过程，先移动 right，再移动 left…… 直到 right 指针到达字符串 S 的末端，算法结束。其他题型
- 找到字符串中所有字母异位词
- 无重复字符的最长子串
- 串联所有单词的子串（按步长滑动）
-
dfs(深度优先遍历)
勇往直前的深度优先遍历，不撞南墙不回头
在线性结构中，按照顺序一个一个地看到所有的元素，称为线性遍历。在非线性结构中，由于元素之间的组织方式变得复杂，就有了不同的遍历行为。其中最常见的遍历有：深度优先遍历（Depth-First-Search）和广度优先遍历（Breadth-First-Search）
本节介绍深度优先遍历，也叫做深度优先搜索，思想就是穷举，通过穷举，搜索符合的答案
深度优先遍历的两种实现方式 递归
- 迭代
递归的本质也是栈，只不过是系统帮我们做了栈该做的工作
比较下这两种方式 
除了一些常见dfs会考察栈的方式(比如树的前中后序迭代遍历，「树」的专节会讲)，其他大部分题型用递归方式即可解决
本节的dfs只介绍递归的方式
递归
递归是指一段程序直接或者间接调用自身的一种方法，是一种代码技巧，而不是一种算法思想
我们可以借助递归实现dfs的算法思想
递归代码编写三要素
- 递归函数的参数和返回值
- 终止条件
-
模版
func dfs(nums []int) int{ //终止条件 if xxx { return 0 } //算法逻辑 … dfsPermute(ret, path, nums, used) } }
题型
斐波那契数
全排列 给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。 示例 1： 输入：nums = [1,2,3] 输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
func fib(n int) int { if n == 0 { return 0 } if n == 1 || n == 2 { return 1 } return fib(n-1) + fib(n-2) }回溯
定义
回溯算法是一种通过不断尝试 ，搜索一个问题的一个解或者 所有解的方法。在求解的过程中，如果继续求解不能得到题目要求的结果，就需要回退到上一步尝试新的求解路径
在代码层面上，在递归方法结束以后，执行递归方法之前的操作的逆向操作即可模版
func dfs(nums []int) int{ //终止条件 if xxx { return 0 } //访问前处理，从前完后 … dfsPermute(ret, path, nums, used) //访问后处理，即回溯，从后往前 … } }
题型
全排列
全排列 给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。 示例 1： 输入：nums = [1,2,3] 输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
func permute(nums []int) [][]int { used := make([]bool, len(nums)) var ret [][]int dfsPermute(&ret, []int{}, nums, used) return ret } func dfsPermute(ret [][]int, path []int, nums []int, used []bool) { if len(path) == len(nums) { pathCopy := make([]int, len(nums)) copy(pathCopy, path) ret = append(*ret, pathCopy) return } for i := 0; i < len(nums); i++ { if used[i] { continue } used[i] = true path = append(path, nums[i]) dfsPermute(ret, path, nums, used) used[i] = false path = path[:len(path)-1] } }剪枝
什么是剪枝
回溯算法本质上是遍历算法，如果 在遍历的过程中，可以分析得到这样一条分支一定不存在需要的结果，就可以跳过这个分支。
剪纸的好坏决定了dfs搜索的路径数量，即也决定了dfs的效率
通常情况下leetcode里的dfs题型是一定要剪枝的，不然跟暴力没啥区别，会超时题型
组合总和 II
组合总和 II 给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。 candidates 中的每个数字在每个组合中只能使用 一次 。 注意：解集不能包含重复的组合。 示例 1: 输入: candidates = [10,1,2,7,6,1,5], target = 8, 输出: [ [1,1,6], [1,2,5], [1,7], [2,6] ]
如何确定剪枝范围
func combinationSum1(candidates []int, target int) [][]int { var ret [][]int sort.Ints(candidates) dfsCombinationSum1(&ret, []int{}, candidates, target, 0) return ret } func dfsCombinationSum1(ret [][]int, path []int, candidates []int, target int, start int) { if start > len(candidates) { return } if target == 0 { pathCopy := make([]int, len(path)) copy(pathCopy, path) ret = append(*ret, pathCopy) } for i := start; i < len(candidates); i++ { //剪枝 if target < candidates[i] { break } if i > start && candidates[i-1] == candidates[i] {//去重剪枝 continue } path = append(path, candidates[i]) dfsCombinationSum2(ret, path, candidates, target-candidates[i], i+1) path = path[:len(path)-1] } }其他题型
排列组合系列
数组分组类问题(也可以用动态规划做，动态规划比较难想，我做第二遍的时候dp已经完全想不起来了，还是dfs香)
- 最大平均值和的分组
- 安排邮筒(先套组合模板，在加记忆化)
分割数组的最大值(二分也可)
bfs(广度优先遍历)
齐头并进的广度优先遍历
与dfs某个节点一直走到底不同，bfs是所有当前节点手牵手一起往下走
举个例子
如果我们要找一个医生或者律师，我们会先在自己的一度人脉中遍历（查找），如果没有找到，继续在自己的二度人脉中遍历（查找），直到找到为止。
使用场景层序遍历
- 无权图的路径问题(拓扑排序、最短路径)
除了这两个场景，其他场景还是尽量使用dfs解决，不考虑复杂度问题，dfs的代码比bfs好写的多，毕竟递归是写给人看的
树的广度优先遍历
思考：树的前中后序是用栈，那么层次便利该用什么数据结构？如何保存逐层打印呢？
模板
需要关注层次信息
queue := []TreeNode{root} for len(queue) > 0 { if queue[0].Left != nil { queue = append(queue, queue[0].Left) } if queue[0].Right != nil { queue = append(queue, queue[0].Right) } queue = queue[1:] }
不需要关注层次信息
queue := []TreeNode{root} for len(queue) > 0 { levelN := len(queue) //记录当前层数量，按层遍历 var level []int for i := 0; i < levelN; i++ { level = append(level, queue[0].Val) if queue[0].Left != nil { queue = append(queue, queue[0].Left) } if queue[0].Right != nil { queue = append(queue, queue[0].Right) } queue = queue[1:] } }
二叉树的层序遍历
在看树的深度
讲树的时候我们通过遍历思想和分治思想给出了两种解法，用bfs是不是更简单了
二叉树的最大深度
如果求树的最小深度呢？
其他题型
- 二叉树的最小深度
-
图的广度优先遍历
图上用到的bfs在目前我遇到的题型里只有拓扑排序，详见「图」节
动态规划
发明者Bellman，是个数学家，英文名是「Dynamic programming」，这里「programming」不是编程，是决策的意思，即「动态决策」。但是这个决策太大了，我们需要一步一步的积累出来
quora对动态规划有个高赞的解释
在这个例子中，在式子最左边加了个1后要求解新问题，就把该问题分解成“ 新加了1 ”和“ 八个1相加等于几 ”这 两个子问题 ，而且 性质相同 ，都是加法。
其中第二个子问题“八个1相加等于几”，在刚刚已经 求解过并且记录下来了 ，所以能很快地求解出新问题的解
听起来像分治，和分治有什么区别？
分治：自顶向下，然后将子问题合并
动态规划：自底向上，对子问题的求解往往会存在大量重叠，需要通过记忆化的方式防止重复计算
动态规划三要素 重叠子问题
允许有重叠子问题，但不允许重复计算。
比如斐波那契数列，使用递归的方式会产生很多字问题重复计算，使用动归就不会，因为那个字问题计算的答案会被以备忘录的形式记录下来
- 最优子结构
把问题分解成规模更小、性质相同的子问题，每个子问题求最优解
- 状态转移方程
将原问题和子问题关联起来，用方程的形式表达出来，基于状态转移方程编写代码
模板
动归题目当然没有模板了，每个题型系列会有模版。动归题型难是难在在他的思考过程
分享给大家之前困扰我很久的状态转移方程的遍历顺序问题
- dp[i] = dp[i-1]
- dp[i] = dp[i+1]
- dp[i][j] = dp[i-1][j-1]
- dp[i][j] = dp[i+1][j-1]
- dp[i][j] = dp[i-1][j+1]
- dp[i][j] = dp[i+1][j-1]
网上对动态规划题型的划分方式有很多种，按线性和非线形、一维和二维度、有状态和无状态等等
但由于动态规划没有固定的套路，目前还没看到特别满意的划分方式
我个人倾向于按各个经典系列划分，大部分题目都是源自经典系列改造的，如果经典系列的吃透了，是可以做到融会贯通的（但说实话，遇到没见过的动归还是很难想），另外针对某个系列的模板是可以套的
下面分享下我总结的经典系列
背包系列
01背包
有N件物品和一个容量是V的背包。每件物品有且只有一件。 第i件物品的体积是V[i]，价值是W[i] 。 求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。 示例 1： 输入: N = 3, V = 4, v = [4,2,3], w = [4,2,3]输出: 4解释: 只选第一件物品，可使价值最大 示例 2： 输入: N = 3, V = 5, v = [4,2,3], w = [4,2,3]输出: 5解释: 不选第一件物品，选择第二件和第三件物品，可使价值最大
状态转移方程
dp[i][j] : 表示 i 件物品，占用了 j 空间，所能取得的最大价值。 dp[i][j] = dp[i - 1][j] 当前物品不选 dp[i - 1][j - v[i]] + w[i] 当前物品选，j - v[i] 要大于等于 0
完全背包
有N件物品和一个容量是V的背包。每件物品有无限件。 第i件物品的体积是V[i]，价值是W[i] 。 求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。 示例 1： 输入: N = 2, C = 5, v = [1,2], w = [1,2]输出: 5解释: 选一件物品 1，再选两件物品 2，可使价值最大。
状态转移方程
dp[i][j] : 表示 i 件物品，占用了 j 空间，所能取得的最大价值。 dp[i][j] = dp[i - 1][j] 当前物品不选 dp[i][j - v[i]] + w[i] 当前物品选，j - v[i] 要大于等于 0
多重背包
有N件物品和一个容量是V的背包。每件物品数量有限。 第i件物品的体积是V[i]，价值是W[i]，数量为 S[i] 。 求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。 示例 1： 输入: N = 2, C = 5, v = [1,2], w = [1,2], s = [2,1] 输出: 4 解释: 选两件物品 1，再选一件物品 2，可使价值最大。
状态转移方程
dp[i][j] : 表示 i 件物品，占用了 j 空间，所能取得的最大价值。 dp[i][j] = dp[i - 1][j] 当前物品不选 max(dp[i][j - kv[i]] + kw[i]) 当前物品选，j - k*v[i] 要大于等于 0,k表示当前物品的可选数量 0
滚动数组优化
比如有这样的状态转移方程：
dp[i] = dp[i-1]
我们需要用一个数组去存储吗
当然不需要，用一个变量记录上一个值就可以，空间复杂度可以从O(n)降到O(1)
同样的对于二维状态转移方程也适用
背包问题如何降维
01背包和完全背包的降维方程一摸一样，只是遍历顺序不一样，由于写起来更方便，并且考察的题型较多，建议记住两个模板即可，遇到类似的题目如果能套背包问题，可直接秒杀
01背包
dp[j] = max(dp[j], dp[j - v[i]] + w[i]) 从大到小遍历j
完全背包
dp[j] = max(dp[j], dp[j - v[i]] + w[i]) 从小到大遍历j
多重背包
多重背包不常见，滚动数组优化也麻烦，不建议记忆
其他题型
- 分割等和子集
- 一和零
- 目标和
- 盈利计划
- 最后一块石头的重量 II
- 零钱兑换
- 零钱兑换 II
- 完全平方数
- 数位成本和为目标值的最大数字
- 组合总和 Ⅳ（对比零钱兑换有啥区别）
抛掷硬币（第i件物品选或不选 且 带概率）
子数组系列
比较简单，但是是很多二维(矩阵)结构的动态规划类型题目的基础
题型
最大子数组和
给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。 子数组 是数组中的一个连续部分。 示例 1： 输入：nums = [-2,1,-3,4,-1,2,1,-5,4] 输出：6 解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
状态转移方程
dp[i]:第i个数结尾的最大子数组和 dp[i] = max{dp[i-1]+nums[i],nums[i]}其他题型
-
子序列系列
子序列的针对对象是字符串
我们在滑动窗口节讲到大部分子串问题都是用滑动窗口解决，为什么动态规划里出了一个子序列系列？
子序列和子串有啥区别？题型
最长递增子序列（LIS问题)
给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。 子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。 示例 1： 输入：nums = [10,9,2,5,3,7,101,18] 输出：4 解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。
状态转移方程
dp[i]:以nums[i]结尾的最长递增子序列的长度 dp[i] = max(dp[i], dp[j] + 1) 其中：dp[j]表示nums[0:i]中任意一个数字nums[j] 小于nums[i]结尾的子序列
func lengthOfLIS(nums []int) int { n := len(nums) dp := make([]int, n) dp[0] = 1 ret := 1 for i := 1; i < n; i++ { dp[i] = 1 for j := i - 1; j >= 0; j— { if nums[j] < nums[i] { dp[i] = getMax(dp[i], dp[j]+1) } } ret = getMax(ret, dp[i]) } return ret }
最长公共子序列(LCS问题)
给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。 一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。 例如，”ace” 是 “abcde” 的子序列，但 “aec” 不是 “abcde” 的子序列。 两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。 示例 1： 输入：text1 = “abcde”, text2 = “ace” 输出：3 解释：最长公共子序列是 “ace” ，它的长度为 3 。
状态转移方程
dp[i][j]:text1[0:i-1]和text2[0:j-1]的最长公共子串 dp[i][j] = if text1[i]==text2[j] dp[i-1][j-1]+1 else max(dp[i-1][j],dp[i][j-1])
text1[i]==text2[j] text1[i]！=text2[j]
编辑距离(SES问题，也是git diff原理)
给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数 。 你可以对一个单词进行如下三种操作： 插入一个字符 删除一个字符 替换一个字符 示例 1： 输入：word1 = “horse”, word2 = “ros” 输出：3 解释： horse -> rorse (将 ‘h’ 替换为 ‘r’) rorse -> rose (删除 ‘r’) rose -> ros (删除 ‘e’)
状态转移方程
编辑的几种操作： if (word1[i] == word2[j]) 不操作 if (word1[i] != word2[j]) 增 / 删 / 换 即每个单词各有3种编辑方式，最多有33=9种组合编辑方式 但是我们发现，假设有单词 A 和单词 B： 对单词 A 删除一个字符和对单词 B 插入一个字符是等价的。 例如当单词 A 为 doge，单词 B 为 dog 时，我们既可以删除单词 A 的最后一个字符 e，得到相同的 dog，也可以在单词 B 末尾添加一个字符 e，得到相同的 doge； 同理，对单词 B 删除一个字符和对单词 A 插入一个字符也是等价的； 对单词 A 替换一个字符和对单词 B 替换一个字符是等价的。例如当单词 A 为 bat，单词 B 为 cat 时，我们修改单词 A 的第一个字母 b -> c，和修改单词 B 的第一个字母 c -> b 是等价的。 这样以来，本质不同的操作实际上只有三种： 在单词 A 中插入一个字符 在单词 B 中插入一个字符 修改单词 A 的一个字符 当然反过来也是可以的，就最短编辑距离这个要求不影响最终结果 在单词 B 中插入一个字符 在单词 A 中插入一个字符 修改单词 B 的一个字符 那么反过来会影响啥呢？ dp[i][j]：word1[0:i-1] 和 word2[0:j-1] 的最小编辑距离 dp[i][j] = if word1[i]==word[j] dp[i][j]== dp[i-1][j-1] 即不用编辑 else = min( dp[i][j - 1] + 1, // 在 s1 中插入字符 dp[i - 1][j] + 1, // 在 s1 中删除字符 dp[i - 1][j - 1] + 1 // 替换字符 )
*假如编辑距离不允许「换」操作，这题该怎么做其他题型
- 判断子序列
- 最长连续递增序列
- 俄罗斯套娃信封问题
- 两个字符串的最小ASCII删除和
- 最长重复子数组
- 通配符匹配
- 正则表达式匹配
- 不同的子序列
- 不相交的线
-
股票系列
题型
买卖股票的最佳时机
给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。 你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。 返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。 示例 1： 输入：[7,1,5,3,6,4] 输出：5 解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。 注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。
状态转移方程
dp[i]：前i天的最大收益 dp[i] = max{dp[i-1]，price[i]-前i-1天中的最小价格}
func maxProfit(prices []int) int { var ret int minInt := prices[0] for i := 1; i < len(prices); i++ { minInt = getMin(minInt, prices[i]) ret = getMax(ret, prices[i]-minInt) } return ret }
买卖股票的最佳时机 II
给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。 在每一天，你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买，然后在 同一天 出售。 返回 你能获得的 最大 利润 。 示例 1： 输入：prices = [7,1,5,3,6,4] 输出：7 解释：在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4 。 随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6 - 3 = 3 。 总利润为 4 + 3 = 7 。
状态转移方程
dp[i][j]: j为状态值，0和1，0代表不持股 1代表持股， 即dp[i][0]第i天不持股时的最大利润，dp[i][1]第i天持股时的最大利润 dp[i][0] = max{dp[i-1][0],dp[i-1][1]+prices[i]} dp[i][1] = max{dp[i-1][1],dp[i-1][0]-prices[i]}
最佳买卖股票时机含冷冻期
给定一个整数数组prices，其中第 prices[i] 表示第 i 天的股票价格 。 设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）: 卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。 注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。 示例 1: 输入: prices = [1,2,3,0,2] 输出: 3 解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]
状态转移方程
dp[i][j] j为状态值，0、1、2，0不持股且不处于冷冻，1持股 2不持股且冷冻 即dp[i][j]代表j状态下的最大利润 dp[i][0] = max(dp[i-1][0]，dp[i-1][2]） dp[i][1] = max(dp[i-1][1]，dp[i-1][0]-price[i]) dp[i][2] = dp[i-1][1]+price[i]
本身是一维，dp带状态(其他维度)的动态规划是一类题型，我把他们都放在了股票系列（个人感觉这类题目是最难思考的，状态选取容易搞错）其他题型
股票系列
- 买卖股票的最佳时机 II
- 买卖股票的最佳时机 III
- 买卖股票的最佳时机 IV
- 买卖股票的最佳时机含手续费
- 最佳买卖股票时机含冷冻期
一维带状态(其他维度)系列
- 最大平均值和的分组
- 鸡蛋掉落(谷歌面试题)
- 粉刷房子
- 粉刷房子 II
- 奇偶跳
- 青蛙过河
- 安排邮筒
- 抛掷硬币
-
矩阵系列
二维矩阵里的规则子矩阵问题一般使用动态规划，不规则子图一般使用dfs，比如岛屿数量
题型
最大正方形
状态转移方程
dp[i][j]:以(i,j)为右下角且只包含1的正方形边长最大值 dp[i][j] = if matrix[i][j]==1 min(dp[i-1][j],dp[i-1][j-1],dp[i][j-1])+1 else 0
最大矩形
与正方形不同，矩形通过左、上、左上是推不出当前矩阵的，所以我们得另辟蹊径
这里就引入了前缀和的概念，我们可以考虑通过暴力的方式枚举整行或整列在某个区间的值
什么是前缀和，以行为例，假如我有3行，编号0-2，那么对于这个二维数组，预处理行的区间列和，
即按照行号0-0、0-1、0-2、1-1、1-2、2-2处理，得到这些行区间的列和
那么这么问题就转换成了一维数组的问题
即求一维数组上，连续1的个数，解法也是用动态规划，这就简单多了
这个思路也可以解决上面最大正方形的问题
思考：有其他思路吗其他题型
- 最大子矩阵
- 3n 块披萨
- 切披萨的方案数
- 三角形最小路径和
- 最小路径和
- 地下城游戏
-
打家劫舍系列
题型
打家劫舍
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。 给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。 示例 1： 输入：[1,2,3,1] 输出：4 解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。 偷窃到的最高金额 = 1 + 3 = 4 。
状态转移方程
dp[i]:前i间能偷到的最高金额 dp[i]=max(dp[i−2]+nums[i],dp[i−1])其他题型
- 打家劫舍 III（这题跟动态规划没关系）
- 删除并获得点数
-
回文系列
回文本身既有子串也有子序列问题，单独拿出来是出现因为频率较高
如果回文属于子串系列，用双指针基本都能解决，但由于回文子串的特殊性，也能用动态规划解决
从刷题和可理解的角度，我个人建议优先使用双指针题型
最长回文子串
给你一个字符串 s，找到 s 中最长的回文子串。 示例 1： 输入：s = “babad” 输出：”bab” 解释：”aba” 同样是符合题意的答案。 示例 2： 输入：s = “cbbd” 输出：”bb”
状态转移方程
dp[i][i]:s[i][j]组成的子串是否为回文串 dp[i][j] == dp[i+1][j-1] && s[i]==s[j] if j-i+1==2 else s[i]==s[j] 最后答案为dp[i][j]为true时j-i+1的最大值其他题型
- 最长回文子序列
- 段式回文
- 统计不同回文子序列
- 让字符串成为回文串的最少插入次数
-
其他
归并
原理大家都懂，一看就会，一写就废，写完一个星期后又废……
但是树的前中后序递归遍历，我熟！！！永远忘不掉！！！
我们从树的角度去理解归并排序
归并：先把左半边数组排好序，再把右半边数组排好序，然后把两半数组合并(具体操作)
树的后序遍历：先访问左子树，在访问右子树，在访问当前节点(具体操作)
再看看代码框架
再从合并树的角度理解一下
合并从最下面一层开始，自底向上的进行合并，跟后序遍历从后往前的处理一摸一样(回溯)
题型
计算右侧小于当前元素的个数
给你一个整数数组 nums ，按要求返回一个新数组 counts 。 数组 counts 有该性质： counts[i] 的值是 nums[i] 右侧小于 nums[i] 的元素的数量。 示例 1： 输入：nums = [5,2,6,1] 输出：[2,1,1,0] 解释： 5 的右侧有 2 个更小的元素 (2 和 1) 2 的右侧仅有 1 个更小的元素 (1) 6 的右侧有 1 个更小的元素 (1) 1 的右侧有 0 个更小的元素其他题型
- 区间和的个数
- 数组中的逆序对
快排
快速排序是先确定一个基数，将小于该基数的数移到左边，大于该基数的数放到右边，然后递归对左右两边重复这个过程
即：将一个元素排好序，然后再将剩下的元素排好序
无独有偶，快排对比树的前序遍历，我们直接对比代码框架
题型
来看一个我们之前做过的题目
数组中的第K个最大元素
给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。 请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。 示例 1: 输入: [3,2,1,5,6,4] 和 k = 2 输出: 5
用堆可以达到nlogk的复杂度，有没有更快的方案呢？
期望复杂度O(n)总结
还有一些题型，比如贪心、位运算、设计类题目(lru,lfu等)后续会慢慢补上去
比较好的算法能力提升方法是，先按专项刷，每个专项有所了解后混合刷
算法能力不是一蹴而就的，需要长期的累积
若有收获，就点个赞吧
0 人点赞
