框架思维
计算机思维就是递归解决重复问题，自顶向下，从抽象到具体。
数据结构的存储方式
数组：顺序存储
链表：链式存储
栈、队列、散列表、堆、树、图都是在上面两种存储方式的基础上的特殊操作。
数据结构
存储方式
说明
栈、队列
数组
链表
用数组实现，要处理扩容缩容问题
用链表实现，没有扩容问题，但需要更多的内存空间存储节点指针
散列表
数组+链表（拉链法）
通过散列函数把键映射到一个大数组里。解决散列冲突的方法：拉链法需要链表特性，操作简单，但需要额外的空间存储指针、线性探查法需要数组特性，以便连续寻址，不需要指针的存储空间，但操作稍微复杂些
堆
数组
堆是一个完全二叉树
树
链表
不是完全二叉树时，不适合用数组实现，在树的递归结构上有各种巧妙地设计：二叉搜索树、AVL树、红黑树、区间树、B树
图
二位数组（邻接矩阵）
链表（邻接表）
邻接矩阵判断连通性迅速，可以进行矩阵运算解决一些问题，如果图比较稀疏很耗费空间
邻接表比较节省空间，但是很多操作效率比不过邻接矩阵
虽然数据结构的种类很多，但是底层存储只有数组和链表两种，二者的优缺点如下：
存储方式
说明
数组
紧凑连续存储，可以随机访问，通过元素快速找到对应元素，节约存储空间
内存空间一次性分配，数组扩容需要重新分配更大空间，再把数据全部复制过去，时间复杂度 `O(N)`
数组中插入或删除，每次必须搬移后面的所有数据以保持连续，时间复杂度 `O(N)`
链表
元素不连续，无法根据索引算出对应元素的地址，所以不能随机访问，依赖指针指向下一个元素的位置，不存在扩容问题
知道某一元素的前驱和后驱，操作指针即可删除该元素或者插入新元素，时间复杂度 `O(1)`
而且由于每个元素必须存储指向前后元素位置的指针，会消耗相对更多的储存空间
数据结构的基本操作
对于任何的数据结构，基本操作包括：
遍历和查找分为线性（for/while迭代为代表）和非线性（递归为代表）。
遍历
查找
增加
删除
修改
数据结构种类很多，但它们存在的目的都是在不同的应用场景，尽可能高效地增删查改。
数组遍历
线性迭代：
func iterate(nums []int) {
for i := 0; i < len(nums); i++ {
// TODO:对nums[i]进行操作
}
}链表遍历
链表节点：
type ListNode struct {
Val int
Next node
}线性迭代：
func iterate(head *ListNode) {
for cur := head; cur != nil; cur = cur.Next {
// TODO:对cur.Val进行操作
}
}非线性递归：
func recursion(head *ListNode) {
if head == nil {
return
}
// TODO:对head.Val进行操作
recursion(head.Next)
}二叉树遍历
二叉树节点：
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}线性迭代：
// 需要用一个栈来存储当前处理的节点
// 下面的逻辑无法实现后序遍历
func iterate(root *TreeNode) {
stack := make([]*TreeNode,0)
for root != nil || len(stack) != 0 {
for root != nil {
// TODO: 操作root.Val（前序遍历）
stack = append(stack,root)
root = root.Left
}
if stack.Len() != 0 {
root = stack[len(stack)-1]
stack = stack[:len(stack)-1]
// TODO: 操作root.Val（中序遍历）
root = root.Right
}
}
}
// 后序遍历
func iterate(root *TreeNode){
stack := make([]*TreeNode,0)
var listVisit *TreeNode
for root!=nil||len(stack)!=0{
for root!=nil{
stack = append(stack,root)
root = root.left
}
// 先获取当前根节点，但不出栈
root := stack[len(stack-1)]
// 因为根节点需要在右节点访问过之后才能出栈
if root.Right == nil || root.Right == lastVisit {
stack = stack[:len(stack)-1]
// TODO: 操作 root.Val (后序遍历)
lastVisit = root
}else{
root = root.Right
}
}
}非线性递归：
func recursion(root *TreeNode) {
if root == nil {
return
}
// TODO:操作root.Val的位置不同
// 就是不同的遍历顺序
recursion(root.Left)
recursion(root.Right)
}多叉树遍历
多叉树节点：
type TreeNode struct {
Val int
Children []*TreeNode
}非线性递归：
func recursion(root *TreeNode) {
if root == nil {
return
}
for _, child := range root.Children {
recursion(child)
}
}动态规划框架
计算机解决问题唯一的解决办法就是穷举所有可能性。算法设计就是先思考“如何穷举”，然后再追求“如何聪明地穷举”（备忘录和DP table 就是追求聪明地穷举）。
列出动态转移方程，就是在解决“如何穷举”的问题。之所以说它难，一是因为很多穷举需要递归实现，二是因为有的问题本身的解空间复杂，不那么容易穷举完整。
动态规划问题的一般形式是求最值，求解动态规划的核心问题是穷举：
求最长递增子序列
求最小编辑距离
动态规划的穷举比较特别：
存在重叠子问题：使用备忘录或DP table优化穷举过程，避免重复计算
具备最优子结构：通过子问题最值得到原问题最值
正确的状态转移方程：穷举所以可行解太难，状态状态转移方程才能正确穷举
思维框架：
明确base case
确定状态：base case的变化
确定选择：导致状态发生变化的行为
确定DP数组/函数的定义
DP数组（自底向上）：存储每一个中间状态
DP函数（自顶向下）：一个递归的DP函数，函数的参数就是状态转移中会变化的量（状态），函数的返回值就是题目要求计算的量
// base case
dp[0][0] = base
// 进行状态转移
for 状态1 range 状态1的所有取值{
for 状态2 range 状态2的所有取值{
for ...
dp[状态1][状态2][...] = 求最值(选择1，选择2...)
}
}重叠子问题优化方法
使用递归穷举
递归算法的时间复杂度：用子问题个数乘以解决一个子问题需要的时间。
但凡遇到需要递归的问题，最好都画出递归树，这对分析算法的复杂度，寻找算法低效的原因都有巨大帮助。
带备忘录（数组/哈希表）的递归
递归耗时的原因是重复计算，那么可以造一个备忘录，每次算出某个子问题的答案后别急着返回，先记到备忘录里再返回
每次遇到一个子问题先去备忘录里查一查，如果发现之前已经解决过这个问题了，直接把答案拿出来用，不要再耗时去计算了
实际上，带备忘录的递归算法，把一棵存在巨量冗余的递归树通过剪枝，改造成了一幅不存在冗余的递归图，极大减少了子问题（即递归图中节点）的个数。
带备忘录的递归解法的效率和迭代的动态规划解法一样，这里的备忘录完成后就是动态规划中的DP table。
带备忘录的递归叫做「自顶向下」，动态规划叫做「自底向上」。
自顶向下：按照递归树从上向下延伸，从一个规模较大的原问题，向下逐渐分解规模，直到分解到base case，然后逐层返回答案
自底向上：从最底下，最简单，问题规模最小的base case开始往上推，直到推到想要的答案，这就是动态规划的思路，这也是为什么动态规划一般都脱离了递归，而是由循环迭代完成计算
DP数组迭代解法
把递归中的备忘录独立出来成为一张表，叫做 DP table，在这张表上完成自底向上的推算。
状态转移方程：实际上就是描述问题结构的数学形式，备忘录或者DP table都是围绕这个方程式的不同表现形式。
其实状态转移方程直接代表着暴力解法，优化方法无非是用备忘录或者 DP table。
状态压缩：根据斐波那契数列的状态转移方程，当前状态只和之前的两个状态有关，并不需要那么长的一个 DP table 来存储所有的状态，只要想办法存储之前的两个状态就行了。所以，可以进一步优化，把空间复杂度降为 O(1)。
如果发现每次状态转移只需要 DP table 中的一部分，那么可以尝试用状态压缩来缩小 DP table 的大小，只记录必要的数据，一般来说是把一个二维的 DP table 压缩成一维，即把空间复杂度从
O(n^2)压缩到O(n)。
最优子结构优化方法
要符合最优子结构，子问题间必须互相独立，子问题的最优解之间不会相互影响。如果子问题相互影响，那子问题之间无法同时得到最优解，动态规划的最优子结构条件就被破坏了。
暴力递归
以凑零钱问题为例，给你 k 种面值的硬币，面值分别为 c1, c2 ... ck，每种硬币的数量无限，再给一个总金额 amount，问你最少需要几枚硬币凑出这个金额，如果不可能凑出，算法返回 -1 。
base case：amount=0
确定状态：硬币变化导致amout变化
确定选择：硬币的面值就是选择
DP函数定义：输入一个目标金额 n，返回凑出目标金额 n 的最少硬币数量
func coinChange(coins []int, amount int) int {
// 题目要求的最终结果是dp(amount)
return dp(coins, amount)
}
// 定义：要凑出金额n，至少要dp(n)个硬币
func dp(coins []int, n int) int {
// base case
if n == 0 {
return 0
}
if n < 0 {
return -1
}
// 求最小值，初始化为最大正数
res := 1<<63 - 1
// 做选择，选择需要硬币最少的那个结果
for _, coin := range coins {
subProblem := dp(coins, n-coin)
// 子问题无解，跳出
if subProblem == -1 {
continue
}
res = min(res, 1+subProblem)
}
if res != 1<<63-1 {
return res
} else {
return -1
}
}
func min(i, j int) int {
if i < j {
return i
}
return j
}带备忘录的递归
在暴力递归的基础上增加备忘录:
func coinChange(coins []int, amount int) int {
// 备忘录
tmp := make(map[int]int)
// 题目要求的最终结果是dp(amount)
return dp(coins, amount, &tmp)
}
// 定义：要凑出金额n，至少要dp(n)个硬币
func dp(coins []int, n int, tmp *map[int]int) int {
if val, ok := (*tmp)[n]; ok {
return val
}
// base case
if n == 0 {
return 0
}
if n < 0 {
return -1
}
// 求最小值，初始化为最大正数
res := 1<<63 - 1
// 做选择，选择需要硬币最少的那个结果
for _, coin := range coins {
subProblem := dp(coins, n-coin, tmp)
// 子问题无解，跳出
if subProblem == -1 {
continue
}
res = min(res, 1+subProblem)
}
(*tmp)[n] = res
if res != 1<<63-1 {
return (*tmp)[n]
} else {
return -1
}
}
func min(i, j int) int {
if i < j {
return i
}
return j
}DP数组迭代解法
自底向上使用DP table来消除重叠子问题，状态，选择和base case与dp函数一样，dp数组的定义目标金额作为变量，体现在dp数组的索引中。
dp数组定义：当目标金额为 i 时，至少需要 dp[i] 枚硬币凑出。
func coinChange(coins []int, amount int) int {
// 数组大小为amount+1
dp := make([]int, amount+1)
// base case
dp[0] = 0
dp[amount] = 1<<63 - 1
// 外层for循环遍历所有状态的所有取值
for i := 0; i < len(dp); i++ {
for _, coin := range coins {
if (i - coin) < 0 {
continue
}
dp[i] = min(dp[i], 1+dp[i-coin])
}
}
if dp[amount] == 1<<63-1 {
return -1
} else {
return dp[amount]
}
}回溯框架
回溯算法不像动态规划存在重叠子问题可以优化，回溯算法就是纯暴力穷举，复杂度一般都很高。
解决一个回溯问题，实际上就是一个决策树（多叉树）的遍历过程，二叉树的话，就是DFS（深度优先搜索）。只需要思考 3 个问题：
路径：也就是已经做出的选择
选择列表：也就是当前可以做的选择
结束条件：也就是到达决策树底层，无法再做选择的条件
将选择列表和路径当做是决策树中，每个节点的属性。
回溯算法的框架，核心就是 for 循环里面的递归，在递归调用之前做选择，在递归调用之后撤销选择：
var res []int
func backtrack(路径,选择列表){
if 满足结束条件 {
res = appned(res,路径)
return
}
for _ , 选择 := range 选择列表 {
做选择
将该选择在选择列表中移除
路径 = append (路径,选择)
backtrack(路径,选择列表)
撤销选择
路径 = 路径[:len(路径)-1]
将该选择再加入到选择列表中
}
}我们定义的 backtrack 函数其实就像一个指针，在这棵树上游走，同时要正确维护每个节点的属性，每当走到树的底层，其「路径」就是一个解。整棵决策树的访问过程就是多叉树遍历的过程。
所谓的前序遍历和后序遍历，只是两个很有用的时间点：前序遍历的代码在进入某一个节点之前的那个时间点执行，后序遍历代码在离开某个节点之后的那个时间点执行。
backtrack函数在决策树上游走的时候，需要正确的维护每个节点的属性（走过的路径和当前的选择列表），那就在前序/后序这两个时间点执行一些操作：做选择和撤销选择。只要在递归之前做出选择，在递归之后撤销刚才的选择，就能正确得到每个节点的选择列表和路径，当触发结束条件时，将路径记入结果集中。
BFS（深度优先搜索）框架
BFS 的核心思想是把一些问题抽象成图，从一个点开始，向四周开始扩散。一般来说，写 BFS 算法都是用队列这种数据结构，每次将一个节点周围的所有节点加入队列。
BFS 找到的路径一定是最短的，因为步数没增加一次，队列中的所有节点都向前迈一步，这保证了第一次到达终点的时候，走的步数是最少的，但代价就是空间复杂度比 DFS 大很多。
各种花里胡哨的问题，包装的很高大上，本质都是一幅图，从一个起点走到终点，最短路径问题。
走出迷宫的最短路径
带传送门的迷宫的最短路径
把一个单词变成另一个单词，每次只替换一个字符，最少几次
连连看游戏，图案相同，且两个方块之间的最短连线只有两个拐点
func BFS(start, target Node) int {
queue := list.New() // 核心数据结构
visited := make(map[Node]bool) // 避免走回头路
queue.PushBack(start) // 将起点加入队列
visited[start] = true
step := 0 // 记录扩散的步数
for queue.Len() != 0 {
sz := queue.Len()
// 将当前队列中的所有节点向四周扩散
for i := 0; i < sz; i++ {
cur := queue.Front()
queue.Remove(cur)
// 划重点：这里判断是否到达终点
if cur == target {
return step
}
// 将cur的相邻节点加入队列中
for _, x := range cur.Next { // cur.Next泛指cur相邻的节点
if !visited[x] {
queue.PushBack(x)
visited[x] = true
}
}
}
// 划重点：更新步数在这里
step++
}
return step
}
// 二叉树不存在子节点到父节点的指针，不需要使用visited双向BFS
双向 BFS，可以进一步提高算法的效率，不过，双向 BFS 也有局限，就是必须知道终点在哪里。
传统的 BFS 框架就是从起点开始向四周扩散，遇到终点时停止；而双向 BFS 则是从起点和终点同时开始扩散，当两边有交集的时候停止。
双向 BFS 还是遵循 BFS 算法框架的，只是不再使用队列，而是使用 Hash 方便快速判断两个集合是否有交集。
滑动窗口框架
这个算法技巧的思路非常简单，就是维护一个窗口，不断滑动，然后更新答案。
// TODO位置填入具体更新窗口数据的逻辑
func slidingWindow(s,t string){
need := make(map[byte]int)
window := make(map[byte]int)
for i := 0; i < len(t); i++ {
need[t[i]]++
}
left,right,valid := 0,0,0
for right<len(s){
c:= s[right] // c是将要移入窗口的字符
right++ // 右移窗口
// TODO：进行窗口内数据的一系列更新
// debug输出位置
fmt.Printf("window：[%d, %d]\n",left,right)
// 判断左侧窗口是否要收缩
for (window needs shrink){
d:=s[left] // d的将要移除窗口的字符
left++ // 左移窗口
// TODO: 进行窗口内数据的一系列更新
}
}
}最后更新于
这有帮助吗？