跳至主要內容

 

labuladong约 6342 字大约 21 分钟配套学习工具

可视化你的代码

可视化面板编辑器已上线,可以在网页访问:

https://labuladong.online/algo-visualize/open in new window

另外,本站以及所有配套插件中嵌套的算法可视化面板也添加了「编辑」按钮,点击后即可直接修改并执行你的代码进行可视化

目前可视化面板只支持 JavaScript 代码。如果你阅读可视化面板中的 JavaScript 代码有困难,我专门写了一个使用可视化面板的 极简 JavaScript 教程,帮助你 5 分钟上手。

希望你能看到本文的最后,因为在最后一部分,我会结合具体的算法题场景教给你使用可视化面板的实用技巧,手把手带你利用这些技巧高效分析题目和算法的执行过程。等你认识到可视化面板的强大之处,你就会发现它能巨幅提升你对算法的理解深度。

基本用法

顶部主要是一些控制按钮和滑动条,可以控制代码逐步执行。

左侧是代码面板,当前执行到的代码行会高亮显示,点击代码可以直接运行到指定位置。点击顶部的「编辑」按钮后,左侧代码面板会变成编辑器,你可以直接修改代码并运行。

最常用的技巧

点击代码运行到指定位置是最常用的,这个功能就和你在 IDE 中 debug 代码的那个「运行到光标位置」功能一样。

一般我们不会从头开始一步步播放算法的执行,而是直接点击代码跳转到某个感兴趣的位置,然后再一步步执行,观察算法的执行过程。

右侧是可视化区域,用来显示变量、数据结构、堆栈信息、递归数等等。

左下角是 Log Console,如果你的代码中使用了 console.log,输出内容会被打印在这里。console.log 函数被我加强了,可以自动根据递归深度给输出内容加上缩进,方便你观察递归过程。你可以仔细看一下上图中 Log Console 的输出。

右下角有一些悬浮按钮,提供刷新面板、全屏显示、显示/隐藏 Log Console 等功能。

了解这些就足够你玩转可视化面板了,你可以在这两个面板上玩一玩点一点,尝试一下这些功能。

后面的内容主要是可视化编辑器的功能,用于执行你自己的代码。

数据结构的可视化

面板可以可视化数组、链表、二叉树、哈希表、哈希集合等常见数据结构,下面具体介绍一下如何创建这些数据结构。

标准库数据结构

类似数组、哈希表等 JavaScript 内置的数据结构,就正常初始化和操作它们即可,比如:

需要着重讲的是 力扣/LeetCode 中一些特殊的数据结构,比如单链表 ListNode 和二叉树 TreeNode,它们的基本定义和用法和力扣上一样,下面提供一些例子。

单链表

首先说一下单链表,单链表的每个节点有 val, next 属性,和力扣上的定义完全一致:

// 单链表节点的定义
// 此类型已经内置,可以直接使用,不需要你再进行声明
function ListNode(val, next) {
    this.val = (val===undefined ? 0 : val)
    this.next = (next===undefined ? null : next)
}

你可以用 ListNode.create 方法快速创建一条单链表,这是一个简单的例子:

双链表

双链表的每个节点有 val, prev, next 属性,构造函数和力扣完全一致:

// 双链表节点的定义
// 此类型已经内置,可以直接使用,不需要你再进行声明
function DoubleListNode(val, prev, next) {
    this.val = (val===undefined ? 0 : val)
    this.prev = (prev===undefined ? null : prev)
    this.next = (next===undefined ? null : next)
}

你可以用 DoubleListNode.create 方法快速创建一条双链表,或者手动组装双链表。这是一些简单的例子:

二叉树

再说一下二叉树,二叉树每个节点有 val, left, right 属性,构造函数和力扣保持一致:

// 二叉树节点的定义
// 此类型已经内置,可以直接使用,不需要你再进行声明
function TreeNode(val, left, right) {
    this.val = (val===undefined ? 0 : val)
    this.left = (left===undefined ? null : left)
    this.right = (right===undefined ? null : right)
}

你可以用 TreeNode.create 方法快速创建一棵二叉树。注意我们用列表来表示二叉树,表示方式和 力扣题目中表示二叉树的方式open in new window 相同,这里举两个例子:

每个二叉树节点有 val, left, right 属性,和力扣上的定义完全一致。

多叉树

多叉树的每个节点有 val, children 属性,构造函数和力扣完全一致:

// 多叉树节点的定义
// 此类型已经内置,可以直接使用,不需要你再进行声明
function Node(val, children) {
    this.val = val;
    this.children = children;
}

你可以用 Node.create 来创建多叉树,大家主要注意一下多叉树的表示方法,我们还是用列表来表示多叉树,使用层序遍历的顺序,并用 null 来分割每组子节点。具体可以参考这道力扣题目 429. N 叉树的层序遍历open in new window 的示例。

每个多叉树节点有 val, children 属性,和力扣上的定义完全一致。

变量隐藏和作用域提升

使用 @visualize global 可以将变量的作用域提升到全局,这样,一些闭包变量就可以一直显示在右侧的可视化面板中。

使用 @visualize hide 可以隐藏变量,这样,你可以把一些无关的数据结构隐藏起来,避免右侧可视化面板过于拥挤。

用一个例子说明上面这两种注释的用法。比如说我想实现一个简单的 Stack 类,实现栈的 push, pop, peek 三个方法,我可以利用 JavaScript 函数的闭包这样来写:

但是拉到最后一步可以看到,stack 这个变量一直作为一个 Object 存在于右侧的可视化面板中,并没有什么实际意义,还占很大的地方。

其实我们更关心的是那个 items 变量,因为我们可以观察这个数组中元素变化的情况以了解 push, pop 方法是如何工作的。

然而由于 items 是在 Stack 函数内部声明的变量,所以当代码在函数体之外执行时,items 变量不在当前的作用域,所以右侧面板也不会把它可视化出来。

对于这种情况,我们可以使用 @visualize global 注释将 items 变量提升到全局作用域,然后用 @visualize hide 注释让 stack 变量在右侧面板中隐藏

这样就可以达到我们想要的效果。请你点击 stack.push(1); 这行代码并往下执行,可以看到 stack 变量不会再出现,且 items 数组的更新过程会显示在右侧:

递归过程的可视化(可选)

提示

新手可以跳过这部分内容。

等你学过了二叉树章节或动归/回溯的章节,且需要可视化自己的递归函数时,这部分内容才会被用到。

递归算法是很多读者头痛的,我之前写过一篇 从树的角度理解一切递归算法,从理论上抽象出了递归算法最基本的思维模型和编写技巧。

简单来说就是:把递归函数理解成递归树上的一个指针,回溯算法是在遍历一棵多叉树,并收集叶子节点的值;动态规划是在分解问题,用子问题的答案来推导原问题的答案

现在,我把文章中所阐述的思维模型融入了算法可视化面板,一定可以让你更直观地理解递归算法的执行过程。

对于递归算法,@visualize status@visualize choose@visualize unchoose 这几种注释可以帮到大忙,下面一一介绍。

@visualize status 举例

一句话,@visualize status 注释可以放在需要可视化的递归函数的上方,用来控制递归树上节点的值

看个最简单的例子,我在讲解 动态规划算法核心框架 时画出了斐波那契问题的递归树,上层规模较大的问题逐渐被分解:

如何描述算法运行的过程?递归函数 fib 就好像递归树上的一个指针,它不断把原问题分解成子问题,当问题分解到 base case(叶子节点)时,开始逐层返回子问题的答案,推导出原问题的答案。

结合 @visualize status 注释,可以很直观地看到这个过程。下面这个面板是斐波那契算法运行的第 27 步,正在试图计算 fib(3) 的值:

@visualize status 注释写在 fib 函数上边,具体含义是:

1、对这个 fib 函数开启递归树可视化功能,每次递归调用会被可视化为递归树上的一个节点,函数参数中的 n 的值会作为状态显示在节点上。

2、fib 函数被视为一个遍历这棵递归树的指针,处于堆栈路径的树枝会加粗显示。

3、如果函数有返回值,那么当函数结束,计算出某个节点返回值时,鼠标移动到这个节点上,会显示该返回值。

使用 `@visualize` 的注意事项

1、定义函数时,必须使用 var fib = function(n) { ... } 的方式,不要使用 function fib(n) { ... } 或者箭头函数 var fib = (n) => { ... } 的方式,否则无法追踪递归过程。

2、@visualize 注释必须写在函数定义的上一行,否则无法追踪递归过程。

实操

请你在步数栏输入 27 并敲回车,就可以跳转到第 27 步。把鼠标移动到节点 (2) 上,可以看到 fib(2) = 1,这说明 fib(2) 的值已经被计算出来了。

而处在递归路径上的 (5),(4),(3) 节点,它们的值还没被计算出来,你把鼠标移动上去也不会显示返回值。

实操

请你尝试点击可视化面板的前进后退按钮,让算法向后运行几步,理解动态规划算法的递归树生长过程。

实操

待到整棵递归树遍历完成之时,就是原问题 fib(5) 被计算出来之日,那时候整棵递归树上的所有节点都会显示返回值。

请你尝试拉动进度条到最后,看看这棵递归树的样子,并把鼠标移动到各个节点上,看看显示什么。

前面展示的斐波那契解法代码没有添加备忘录,是一个指数级时间复杂度的算法,现在我们来体验一下添加备忘录之后会对整棵递归树的生长产生什么影响。

实操

👇 请你拉动进度条到算法的最后,看看递归树长什么样子。

实操

👇 这是一个带备忘录优化的版本,请你拉动进度条到算法的最后,看看递归树长什么样子,和不带备忘录优化的递归树进行对比。

这样把整棵树可视化出来,你是不是就能很直观地理解动态规划通过备忘录消除重叠子问题的原理了?

@visualize choose/unchoose 举例

一句话,@visualize choose/unchoose 注释分别放在递归函数调用之前和之后,控制递归树树枝上的值

我编一个简单的回溯算法的题目吧,比如让你写一个 generateBinaryNumber 函数,生成长度为 n 的二进制数,比如 n = 3 时,生成 000, 001, 010, 011, 100, 101, 110, 111 这 8 个二进制数。

这道题的解法代码也不复杂,我来展示一下如何用 @visualize choose/unchoose 注释来可视化回溯过程的:

你可以把鼠标移动到递归树上的任意节点,就可以显示出从根节点到该节点的路径上的所有信息。

你结合这棵递归树去理解递归算法的代码,是不是就很直观了?

场景练习题

下面我会结合具体的算法题目,向你提问,要求你利用可视化面板高效分析题目和算法的执行过程。我会给出问题的答案,你可以先自己思考,然后再看我的解答。

这部分主要用到的是可视化面板的「执行到指定代码位置」的功能:你可以点击代码的某一部分,然后算法就会执行到那里,并将执行过程可视化。这个功能用得好,可以大幅提升你对算法的理解

热身

首先,我带大家熟悉一下「执行到指定代码位置」的功能,在之前展示的单链表成环算法中,我其实已经带你用过了,我让你不断点击代码中的 if (slow === fast) 这一行,观看快板指针的追逐过程:

为什么点击这部分就可以展示快慢指针的追逐呢?因为执行这部分代码时,fast, slow 指针刚刚移动完毕,所以点击这里,可以看到它们最完整的移动过程。

在下面的练习中,请你着重思考代码执行到某一部分时算法的状态,这样你就能更好地利用可视化面板,精确地控制算法的执行。

场景一:二叉树的前中后序遍历

实操

上面这段代码是二叉树前中后序遍历,相信大家都不陌生。

请你点击播放按钮,查看这段代码的执行流程。播放时,上一步/下一步按钮将变成加速/减速按钮,用来调整播放速度。

提问

你可以看到,二叉树将会被可视化出来,root 变量就好像一个指针,在二叉树上游走。我希望你能够使用「执行到指定代码位置」的功能,点击代码中的合适位置,精确控制 root 指针的移动顺序。

1、把面板复位,让 root 指针按照前序顺序访问整棵二叉树,即 root 指针按照 1,2,4,3,5,6 的顺序遍历二叉树。

2、把面板复位,root 指针按照中序顺序访问整棵二叉树,即 root 指针按照 2,4,1,5,3,6 的顺序遍历二叉树。

3、把面板复位,root 指针按照后序顺序访问整棵二叉树,即 root 指针按照 4,2,5,6,3,1 的顺序遍历二叉树。

答案

这几个问题不难:

1、不断点击 preorderResult.push(root.val) 这部分代码。

2、不断点击 inorderResult.push(root.val) 这部分代码。

3、不断点击 postorderResult.push(root.val) 这部分代码。

场景二:观察递归树的生长

提问

👇 这是刚才讲到的不带备忘录的斐波那契算法,现在请结合你对递归树的理解,点击代码中的合适位置,使得每点击一次,递归树就向下生长一个节点,直到递归树完全长成。

答案

你可以不断点击代码中 if (n < 2) 这一行,观察递归树的生长过程。

为什么点击这部分就可以展示递归树的生长过程呢?因为这部分代码是递归函数的 base case,每次递归必然都会执行这个判断逻辑,而递归树的每个节点其实就对应着每次递归,所以点击这个 if 语句就可以看到递归树上节点的生长过程。

这是一个非常常用的技巧,可以用来观察递归过程。

场景三:快速获得一个穷举结果

提问一

👇 这是前文展示的全排列算法的可视化面板,在场景二中你观察了斐波那契问题的递归树生长,现在请你点击代码中的合适位置,观察全排列问题的递归树生长。

答案一

这个很简单,不断点击 if (track.length === nums.length) 这部分代码即可观察递归树的生长。

提问二

将面板复位。

现在,我不想看递归树一个一个节点地生长了,没什么意思,我希望你点击代码中的合适位置,每点击一次,递归树就生长出一条「树枝」。

这是个回溯算法中很常见的场景哦,因为每条「树枝」的末端是叶子节点,而叶子节点一般就存储这回溯算法穷举出来的一个结果。比如你看这道题,每条树枝末端的叶子节点就是一个排列结果。

答案二

不断点击 res.push([...track]) 这部分代码,每次点击,回溯树都将生长出一条「树枝」。

因为叶子节点其实就是递归树结束生长的节点,即 backtrack 函数的 base case。那么我们只要点击 base case 中的代码,就可以直接跳到递归树的叶子节点,也就相当于生长出了一条树枝。

场景四:理解自顶向下/自底向上两种思维模式

提问

我在 动态规划核心框架 中讲过,自顶向下用 memo 备忘录的递归解法和自底向上用 dp 数组的迭代解法本质上是一样的,dp 数组中的值和 memo 备忘录中的值完全一样,两种解法可以互相转化。

下面我将同时给你自顶向下的递归解法和自底向上的迭代解法,请你完成如下题目:

1、在自顶向下递归解法的面板上,点击代码的合适位置,使得每次点击都在 memo 中更新一个元素。

2、在自底向上迭代解法的面板上,点击代码的合适位置,使得每次点击都在 dp 中更新一个元素。

3、对比两个解法中 dp 数组和 memo 数组的更新,理解自顶向下的递归解法和自底向上的迭代解法本质上是相同的。

答案

1、在自顶向下递归解法的面板上,每次点击 memo[n] = dp(memo, n - 1) + dp(memo, n - 2) 这部分代码,都会在 memo 数组中更新一个元素。

2、在自底向上迭代解法的面板上,每次点击 dp[i] = dp[i - 1] + dp[i - 2] 这部分代码,都会在 dp 数组中更新一个元素。

3、结合可视化面板应该不难理解,不过你会发现 memo[1]dp[1] 的值不一样,那是因为我们把 dp[1] 作为 base case 设置了初始值,而递归解法中的 base case 是直接 return 的,并不需要设置在 memo 中。