框架思维

计算机思维就是递归解决重复问题，自顶向下，从抽象到具体。

数据结构的存储方式

  • 数组：顺序存储

  • 链表：链式存储

栈、队列、散列表、堆、树、图都是在上面两种存储方式的基础上的特殊操作。

数据结构

存储方式

说明

栈、队列

数组

链表

用数组实现，要处理扩容缩容问题

用链表实现，没有扩容问题，但需要更多的内存空间存储节点指针

散列表

数组+链表（拉链法）

通过散列函数把键映射到一个大数组里。解决散列冲突的方法：拉链法需要链表特性，操作简单，但需要额外的空间存储指针、线性探查法需要数组特性，以便连续寻址，不需要指针的存储空间，但操作稍微复杂些

堆

数组

堆是一个完全二叉树

树

链表

不是完全二叉树时，不适合用数组实现，在树的递归结构上有各种巧妙地设计：二叉搜索树、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优化穷举过程，避免重复计算

  • 具备最优子结构：通过子问题最值得到原问题最值

  • 正确的状态转移方程：穷举所以可行解太难，状态状态转移方程才能正确穷举

思维框架：

  1. 明确base case

  2. 确定状态：base case的变化

  3. 确定选择：导致状态发生变化的行为

  4. 确定DP数组/函数的定义

    1. DP数组（自底向上）：存储每一个中间状态

    2. DP函数（自顶向下）：一个递归的DP函数，函数的参数就是状态转移中会变化的量（状态），函数的返回值就是题目要求计算的量

// base case
dp[0][0] = base
// 进行状态转移
for 状态1 range 状态1的所有取值{
    for 状态2 range 状态2的所有取值{
        for ...
            dp[状态1][状态2][...] = 求最值(选择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 。

  1. base case：amount=0

  2. 确定状态：硬币变化导致amout变化

  3. 确定选择：硬币的面值就是选择

  4. 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 个问题：

  1. 路径：也就是已经做出的选择

  2. 选择列表：也就是当前可以做的选择

  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: 进行窗口内数据的一系列更新
        }
    }
}
上一页第三部分 数据结构与算法下一页复杂度分析

最后更新于

这有帮助吗？