算法可视化

变量就像带名字的盒子,赋值就是把值装进盒子。重新赋值会覆盖旧值。

循环把一段代码重复执行:每次执行循环体,累加器把当前值加上去,直到循环结束。

不同数据类型之间可以转换:整数除法会丢小数,C 风格强制转换会截断,字符可以转成 ASCII 码。

先乘除后加减,括号可以改变运算顺序;同级运算从左到右。

比较运算得到 true/false;&& 两边都真才为真,|| 一边为真即为真。

程序根据条件决定走哪条路:条件成立执行 if 分支,否则依次尝试 else if,最后都不满足走 else。

while 循环:每次进入循环体前先检查条件,条件成立就执行,直到条件不成立。

数组是一排连续的元素,用下标访问:a[0] 是第一个元素。下标从 0 开始。

调用函数时,系统把当前状态压入调用栈,执行完函数后弹栈返回,继续执行原来的代码。

递归就是函数调用自己:fact(4) = 4 × fact(3),一层层展开,直到基准条件返回,再一层层回溯相乘。

把 n 个盘从 A 移到 C,借助 B。规则:一次移一个,大盘不能压小盘。递归:先把 n-1 个移走,再移最大的,再移回来。

在迷宫里找路:能走就走,走不通就退回上一步换方向(回溯)。绿色是最终路径,红色是尝试后回退的格子。

每个物品只能拿或不拿,求容量限制下的最大价值。dp[i][c] 表示前 i 个物品、容量 c 的最大价值,逐个填表。

把长度 10、8、7 的木棍切成每段长度相同的小段,要求正好 3 段,求每段最长能是多少。答案在 1~10 之间二分。

前缀和 pre[i] = 前 i 个元素之和。区间 [l, r] 的和 = pre[r+1] - pre[l],一次减法搞定,不用循环累加。

递归版 f(5) 会重复计算很多次(红色节点是重复计算的);递推版从前往后每个只算一次,效率高得多。

把指数 10 转成二进制 1010:2^10 = 2^8 × 2^2,只需 4 次循环而不是 10 次乘法。

dp[i] = 以 a[i] 结尾的最长上升子序列长度。对每个 i,看前面所有比它小的 j,取 dp[j]+1 的最大值。

dp[i][j] = 两个字符串前 i、j 个字符的最长公共子序列。字符相等取左上+1,不等取上/左较大者。

频率越高的字符编码越短:每次合并频率最小的两个节点,形成二叉树,左 0 右 1 得到编码。

一个固定大小的窗口在数组上滑动,每移动一步,左边出去一个,右边进来一个,求每个窗口的最大值。

计算机底层用二进制,位运算直接操作二进制位:& 按位与,| 按位或,^ 异或,<< 左移(×2),>> 右移(÷2)。

依次允许经过第 0、1、2、3 号节点中转,逐步更新所有点对之间的距离,最后得到任意两点间的最短距离。

从顶层走到底层,每次只能向下或右下,求路径上数字和的最大值。自底向上合并:dp[j] = a[i][j] + max(下一层的两个)。

主串和模式串对齐比较,失配时不回退主串,而是利用 next 数组让模式串跳到合适位置,效率 O(n+m)。

每一轮把相邻元素两两比较,大的往后冒泡,像气泡一样浮到末尾。经过 n-1 轮,数组有序。

每一轮在未排序区里找出最小的元素,放到未排序区的开头。经过 n-1 轮全部就位。

像整理扑克牌:把当前元素抽出来,在已排序区从后往前比较,找到合适位置插入。

选一个基准(pivot),把比它小的放左边、大的放右边,然后对左右两半递归做同样的事。

先把数组不断对半拆成单个元素,再把相邻的两段按大小合并起来。拆到底再合起来,就是有序的。

同一个数组,分别用冒泡排序和快速排序处理,看谁的比较、交换次数更少。数据量越大差距越明显。

先把数组建成大根堆(堆顶最大),再把堆顶和末尾交换(最大值就位),缩小堆后重新调整,重复直到排完。

统计每个值出现的次数(count),再按值从小到大把元素放回原数组。适合值域不大的整数排序。

在有序数组中,每次和中间元素比,直接排除一半。7 个元素最多 3 次就能找到。

从头到尾一个一个比较,找到就停。虽然慢,但数组不需要有序。

栈像一个装盘子的架子:后放上去的先拿走(后进先出 LIFO)。栈顶是唯一能操作的位置。

队列像排队买饭:先来的人先服务(先进先出 FIFO)。队首出队,队尾入队。

单链表:每个节点存数据和指向下一个节点的指针(next)。插入删除只需改指针,不用搬动元素。

双链表:每个节点有 prev(指向前一个)和 next(指向后一个)两个指针,可以双向移动。

循环链表:最后一个节点的 next 指回头节点,形成一个环。遍历时从 head 出发会回到 head。

二叉搜索树左小右大。三种遍历:前序(根→左→右)、中序(左→根→右,有序序列)、后序(左→右→根)。

DFS:从一个节点出发,沿着一条路一直走到头,走不动了再回头(用递归/栈实现)。

BFS:从起点出发,一层一层向外扩散,先访问所有距离为 1 的,再访问距离为 2 的(用队列实现)。

贪心求单源最短路:每次选距离最短的未确定点,用它去更新邻居(松弛)。边上的数字是权重。

堆是完全二叉树:每个节点比孩子小(小根堆),堆顶永远是最小值。插入时上浮,删除堆顶时下沉。

有向无环图,有些任务要先做(Kahn 算法):每次拿走入度为 0 的节点(没有前置依赖的)。

把所有边按权重从小到大排序,从最小的开始:不成环就加入生成树,成环就跳过(并查集判断)。

并查集管理集合:find 找根,union 合并两个集合,路径压缩让查找更快。树形结构,根是代表元素。

查找:比根小走左,大走右。删除分三种:叶子直接删、只有一个孩子用孩子顶替、有两个孩子用后继(右子树最小值)替代。

AVL 树要求每个节点左右子树高度差不超过 1。插入 20 后 50 的左子树过高(LL 型失衡),右旋一次恢复平衡。