数据结构

数组#

前缀和#

下标设计：preSum 偏移一位，第0项空出固定为0 含义是前i项的和 这样求区间和 right+1 - left 即可 不用考虑left=0的情况

局限性：

1. 原数组不变化
2. 前缀和技巧只适用于存在逆运算的场景。

前缀积#

单调栈#

倒着遍历

下一个/上一个 更大/小 元素的 索引

链表#

什么时候需要用虚拟头结点dummy？我这里总结下：当你需要创造一条新链表的时候，可以使用虚拟头结点简化边界情况的处理。

递归#

递归版实际上是利用系统栈

• 每次递归调用都会将当前状态（参数、局部变量、返回地址）入栈（类似push）。
• 当递归返回时，系统从栈顶弹出（pop）状态，恢复现场并继续执行。

把问题抽象成树结构，然后用代码去遍历这棵树，就是递归的本质。

所有递归的算法，你甭管它是干什么的，本质上都是在遍历一棵（递归）树，然后在节点（前中后序位置）上执行代码，你要写递归算法，本质上就是要告诉每个节点需要做什么。

递归算法复杂度: 子问题个数 x 解决一个子问题的复杂度

二叉树#

二叉树解题的思维模式分两类：

1、是否可以通过遍历一遍二叉树得到答案？如果可以，用一个 traverse 函数配合外部变量来实现，这叫「遍历」的思维模式。

2、是否可以定义一个递归函数，通过子问题（子树）的答案推导出原问题的答案？如果可以，写出这个递归函数的定义，并充分利用这个函数的返回值，这叫「分解问题」的思维模式。

无论使用哪种思维模式，你都需要思考：

如果单独抽出一个二叉树节点，它需要做什么事情？需要在什么时候（前/中/后序位置）做？其他的节点不用你操心，递归函数会帮你在所有节点上执行相同的操作。

这种「分解问题」的思路，核心在于你要给递归函数一个合适的定义，然后用函数的定义来解释你的代码；如果你的逻辑成功自恰，那么说明你这个算法是正确的。如果你想用「分解问题」的思维模式来写递归算法，那么这个递归函数一定要有一个清晰的定义，说明这个函数参数的含义是什么，返回什么结果。

图#

我们什么时候才必须把无向边存储两次？ 答案是：当我们需要使用邻接表 (Adjacency List) 进行图遍历时。

排序#

排序

滑动窗口#

滑动窗口算法技巧主要用来解决子数组问题，比如让你寻找符合某个条件的最长/最短子数组

核心是维护一个“左闭右开”的区间 [left, right)，通过两个指针的交替移动来在 $O(N)$ 时间复杂度内找到最优解。

算法框架模板：

1. 扩大窗口： 移动 right 指针，将新元素加入窗口，并更新窗口状态（如计数器）。
2. 缩小窗口： 判断当前窗口状态是否满足收缩条件。如果满足，则移动 left 指针，将元素移出窗口，并更新窗口状态，直到窗口不再满足收缩条件。
3. 更新答案： 根据题目要求，在扩大窗口后（找可行解/最长子串）或缩小窗口时（找最优解/最短子串）更新最终结果。

 遇到题目，只需思考三个问题即可套用模板： 1、什么时候应该移动 right 扩大窗口？窗口加入字符时，应该更新哪些数据？ 2、什么时候窗口应该暂停扩大，开始移动 left 缩小窗口？从窗口移出字符时，应该更新哪些数据？ 3、什么时候应该更新要返回的结果？

// 滑动窗口算法伪码框架
void slidingWindow(String s) {
    // 用合适的数据结构记录窗口中的数据，根据具体场景变通
    // 比如说，我想记录窗口中元素出现的次数，就用 map
    // 如果我想记录窗口中的元素和，就可以只用一个 int
    Object window = ...
    
    int left = 0, right = 0;
    while (right < s.length()) {
        // c 是将移入窗口的字符
        char c = s[right];
        window.add(c)
        // 增大窗口
        right++;
        // 进行窗口内数据的一系列更新
        ...

        // *** debug 输出的位置 ***
        // 注意在最终的解法代码中不要 print
        // 因为 IO 操作很耗时，可能导致超时
        printf("window: [%d, %d)\n", left, right);
        // ***********************

        // 判断左侧窗口是否要收缩
        while (left < right && window needs shrink) {
            // d 是将移出窗口的字符
            char d = s[left];
            window.remove(d)
            // 缩小窗口
            left++;
            // 进行窗口内数据的一系列更新
            ...
        }
    }
}

二分搜索#

class Solution {
    // 标准的二分搜索框架，搜索目标元素的索引，若不存在则返回 -1
    public int search(int[] nums, int target) {
        int left = 0;
        // 注意
        int right = nums.length - 1;

        while(left <= right) {
            int mid = left + (right - left) / 2;
            if(nums[mid] == target) {
                return mid;   
            } else if (nums[mid] < target) {
                // 注意
                left = mid + 1;
            } else if (nums[mid] > target) {
                // 注意
                right = mid - 1;
            }
        }
        return -1;
    }
}

常见变形：

1. 寻找左/右侧边界

双指针#

搜索区间#

选择两端都闭的 [left, right] 好处理 对应初始化： left = 0 right为最后一个元素的索引 while(left <= right) 的终止条件就是 left == right + 1 mid = (left + right) >>> 1; 没有溢出风险

寻找target的左/右侧边界#

把找到target后的搜索边界继续收紧即可 如：right = mid - 1;

当目标元素 target 不存在数组 nums 中时，搜索左侧边界的二分搜索的返回值可以做以下几种解读： 1、返回的这个值是 nums 中大于等于 target 的最小元素索引。 2、返回的这个值是 target 应该插入在 nums 中的索引位置。 3、返回的这个值是 nums 中小于 target 的元素个数。

数组未必是“全局严格有序”的，只要它满足“二段性”就可以用二分思想将时间复杂度降到 $O(\log n)$。

多维坐标之间的映射转换#

任何多维数组都可以被映射到一维，所以甭管几维数组，你统一把多维的坐标转化成一维，然后再从一维坐标转化到多维。

回溯算法#

回溯问题，实际上就是遍历一棵决策树的过程 ：树的每个叶子节点存放着一个合法答案。你把整棵树遍历一遍，把叶子节点上的答案都收集起来，就能得到所有的合法答案。

类比多叉树DFS，和二叉唯一的区别是，多叉树没有了中序位置

回溯算法。递归前做选择，递归后撤销选择

private void backtrack(...)
//base case 是在叶子节点
    for 选择 in 选择列表://不同树枝
        剪枝逻辑 或者说 是去掉不合法的选择列表 //注意这里continue 和 break 的区别
        做选择，即维护走过的「路径」
        backtrack(...)
        撤销选择

写 backtrack 函数时，需要维护走过的「路径」和当前可以做的「选择列表」，当触发「结束条件」时，将「路径」记入结果集 把「路径」和「选择」列表看作决策树上每个节点的属性

为什么dfs的撤销在for循环外面？ 它俩的本质是一样的，都是「遍历」思维下的暴力穷举算法。唯一的区别在于关注点不同，回溯算法的关注点在「树枝」，DFS 算法的关注点在「节点」

对于 backtrack/dfs/traverse 函数，就作为单纯的遍历函数，请保持 void 类型，不要给它们带返回值。

排列/组合/子集问题#

来回顾一下排列/组合/子集问题的三种形式在代码上的区别。

由于子集问题和组合问题本质上是一样的，无非就是 base case 有一些区别，所以把这两个问题放在一起看。

形式一、元素无重不可复选，即 nums 中的元素都是唯一的，每个元素最多只能被使用一次，backtrack 核心代码如下：

// 组合/子集问题回溯算法框架
void backtrack(int[] nums, int start) {
    // 回溯算法标准框架
    for (int i = start; i < nums.length; i++) {
        // 做选择
        track.addLast(nums[i]);
        // 注意参数
        backtrack(nums, i + 1);
        // 撤销选择
        track.removeLast();
    }
}

// 排列问题回溯算法框架

void backtrack(int[] nums) {
    for (int i = 0; i < nums.length; i++) {
        // 剪枝逻辑
        if (used[i]) {
            continue;
        }
        // 做选择
        used[i] = true;
        track.addLast(nums[i]);

        backtrack(nums);
        // 撤销选择
        track.removeLast();
        used[i] = false;
    }
}

形式二、元素可重不可复选，即 nums 中的元素可以存在重复，每个元素最多只能被使用一次，其关键在于排序和剪枝，backtrack 核心代码如下：

Arrays.sort(nums);
// 组合/子集问题回溯算法框架
void backtrack(int[] nums, int start) {
    // 回溯算法标准框架
    for (int i = start; i < nums.length; i++) {
        // 剪枝逻辑，跳过值相同的相邻树枝
        if (i > start && nums[i] == nums[i - 1]) {
            continue;
        }
        // 做选择
        track.addLast(nums[i]);
        // 注意参数
        backtrack(nums, i + 1);
        // 撤销选择
        track.removeLast();
    }
}


Arrays.sort(nums);
// 排列问题回溯算法框架
void backtrack(int[] nums) {
    for (int i = 0; i < nums.length; i++) {
        // 剪枝逻辑
        if (used[i]) {
            continue;
        }
        // 剪枝逻辑，固定相同的元素在排列中的相对位置
        if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) {
            continue;
        }
        // 做选择
        used[i] = true;
        track.addLast(nums[i]);

        backtrack(nums);
        // 撤销选择
        track.removeLast();
        used[i] = false;
    }
}

形式三、元素无重可复选，即 nums 中的元素都是唯一的，每个元素可以被使用若干次，只要删掉去重逻辑即可，backtrack 核心代码如下：

// 组合/子集问题回溯算法框架
void backtrack(int[] nums, int start) {
    // 回溯算法标准框架
    for (int i = start; i < nums.length; i++) {
        // 做选择
        track.addLast(nums[i]);
        // 注意参数
        backtrack(nums, i);
        // 撤销选择
        track.removeLast();
    }
}

// 排列问题回溯算法框架
void backtrack(int[] nums) {
    for (int i = 0; i < nums.length; i++) {
        // 做选择
        track.addLast(nums[i]);
        backtrack(nums);
        // 撤销选择
        track.removeLast();
    }
}

只要从树的角度思考，这些问题看似复杂多变，实则改改 base case 就能解决，这也是为什么我在 学习算法和数据结构的框架思维 ↗ 和 手把手刷二叉树（纲领篇） ↗ 中强调树类型题目重要性的原因。

动态规划#

符合 最优子结构（子问题间必须互相独立）的问题

如何列出正确的状态转移方程？#

通法：

1. 找到问题的「状态」，「选择」 也就是原问题和子问题中会变化的变量
2. 明确dp 数组/函数的含义，根据定义找base case （Base Case的值，完全是由你的“状态转移方程”决定的) 一般来说dp函数的参数就是状态转移中会变化的量，也就是上面说到的「状态」；dp的返回值就是题目要求我们计算的量
3. 根据「选择」和 dp定义，思考状态转移的逻辑。

思考状态转移方程的一个基本方法是数学归纳法，即明确 dp 函数或数组的定义，然后使用这个定义，从已知的「状态」中推导出未知的「状态」。

优化#

• 「状态」就是 递归树 的节点，树枝就是选择，「备忘录」剪枝消除重叠子问题
• DP table 的迭代解法，或称为「自底向上」的解法，也就是用 for 循环去迭代 dp 数组进行求解

动态规划迭代写法的一个优势，就是可以将 dp 数组进行空间压缩（一般称为滚动数组技巧），降低空间复杂度。

两者本质相同，带备忘录的递归解法中的那个「备忘录」memo 数组，最终完成后就是这个解法中的 dp 数组。

dp table数组大小设置：为什么要有一位索引偏移 答：是为了方便处理base case 毕竟索引不能为-1

最优子结构#

最优子结构并不是动态规划独有的一种性质，能求最值的问题大部分都具有这个性质；（最优子结构本质上是一种“可以被合理拆解”的性质。除了动态规划，贪心算法和分治法也都依赖这个性质） 但反过来，最优子结构性质作为动态规划问题的必要条件，一定是让你求最值的

重叠子问题需要用备忘录优化,但使用了 DP Table，就自然不需要再额外使用备忘录

memo 的初始值一定得是特殊值，和合法的答案有所区分

最优子结构决定了问题“能不能”被拆解推导（保证正确性），而重叠子问题决定了“值不值得”用动态规划去优化（决定效率）

贪心算法#

贪心选择性质就是说能够通过局部最优解直接推导出全局最优解。

分题目心得#

给定一棵完全二叉树的后序遍历，请你给出这棵树的层序遍历结果#

外部维护一个变量，dfs式的遍历隐式还原了一个虚拟的二叉树。为什么选择在后序位置”插入“节点 就是因为题目给的就是后序遍历的数据 dfs正是模拟了这一过程 又因为是完全二叉 所以数组下标正好是层序顺序 直接输出便是答案

递归退出弹栈条件分析： root == null 和 x > n 在逻辑上是完全等价的。它们都在回答同一个根本问题：“我接下来要访问的这个节点，它存在吗？”

x > n 可以看作是 root == null 在“用数组表示完全二-叉树”这种特定数据结构下的具体表现形式。

非递归实现二叉树遍历#

-前序中序：

void preOrder(TreeNode *root) {
    TreeNode *p = root;
    stack<TreeNode*> st;

    while (p != nullptr || !st.empty()) {
        if (p != nullptr) {
            // 情况一：当前节点不为空
	        visit(p);                // 前序遍历：此时访问节点
            st.push(p);              // 当前节点入栈，保留回溯信息

            p = p->left;             // 转向左子树
        } else {
            // 情况二：当前节点为空，但栈不空（说明左子树走到底）
            p = st.top(); st.pop();  
            // 中序遍历：此时访问节点
            // visit(p);   // 如果写中序遍历，访问节点应放在这里
            p = p->right;            // 转向右子树
        }
    }
}

• 只要 p 还有节点，说明还能往下走。
• 即便 p 是空的，但栈里还有记录，说明之前经过的节点可能还有 右子树没访问，还没遍历完，必须继续处理

后序遍历： 另一种思路：状态机模型

• 第一次遇到 (status == 0): 我们刚从它的父节点“走下来”，第一次看到它。根据遍历规则，我们接下来的任务是去探索它的左子树。所以我们把它的状态改为 1（预约下次回来做中序处理），然后就立刻去处理左孩子了。
• 第二次遇到 (status == 1): 什么时候会回到这里？当它整个左子树（无论多深多复杂）都已经被完全处理并弹出栈之后，这个节点就重新出现在了栈顶。这意味着“左”的部分已经全部结束。根据中根遍历（左 -> 根 -> 右）的定义，此刻正是处理根的最佳时机。处理完后，我们把状态改为 2（预约下次回来做后序处理），然后出发去探索它的右子树。
• 第三次遇到 (status == 2): 当右子树也全部被处理完后，我们第三次也是最后一次回到这个节点。此刻，它的“左”和“右”都已完成。根据后根遍历（左 -> 右 -> 根）的定义，此刻正是处理根的最佳时机。 这里出栈 = 任务彻底完成：只有当一个节点的左右子树都探索完毕，并且它自身也被处理（后序输出）后，它作为父节点的“路标”作用才算结束，此时才能将它弹出

确定多数问题#

• 核心思路：摩尔投票法 (Boyer-Moore Voting Algorithm)