看完这两期视频，让你对递归的理解更上一层楼！

【基础算法精讲 09】

【基础算法精讲 10】

答疑

问：代码中的 $-1$ 是怎么产生的？怎么返回的？

答：在某次递归中，发现左右子树高度绝对差大于 $1$，我们会返回 $-1$。这个 $-1$ 会一路向上不断返回，直到根节点。

写法一

class Solution:
    def isBalanced(self, root: Optional[TreeNode]) -> bool:
        def get_height(node: Optional[TreeNode]) -> int:
            if node is None:
                return 0
            left_h = get_height(node.left)
            right_h = get_height(node.right)
            if left_h == -1 or right_h == -1 or abs(left_h - right_h) > 1:
                return -1
            return max(left_h, right_h) + 1
        return get_height(root) != -1

class Solution {
    public boolean isBalanced(TreeNode root) {
        return getHeight(root) != -1;
    }

    private int getHeight(TreeNode node) {
        if (node == null) {
            return 0;
        }
        int leftH = getHeight(node.left);
        int rightH = getHeight(node.right);
        if (leftH == -1 || rightH == -1 || Math.abs(leftH - rightH) > 1) {
            return -1;
        }
        return Math.max(leftH, rightH) + 1;
    }
}

class Solution {
    int get_height(TreeNode* node) {
        if (node == nullptr) {
            return 0;
        }
        int left_h = get_height(node->left);
        int right_h = get_height(node->right);
        if (left_h == -1 || right_h == -1 || abs(left_h - right_h) > 1) {
            return -1;
        }
        return max(left_h, right_h) + 1;
    }

public:
    bool isBalanced(TreeNode* root) {
        return get_height(root) != -1;
    }
};

#define MAX(a, b) ((b) > (a) ? (b) : (a))

int getHeight(struct TreeNode* node) {
    if (node == NULL) {
        return 0;
    }
    int left_h = getHeight(node->left);
    int right_h = getHeight(node->right);
    if (left_h == -1 || right_h == -1 || abs(left_h - right_h) > 1) {
        return -1;
    }
    return MAX(left_h, right_h) + 1;
}

bool isBalanced(struct TreeNode* root) {
    return getHeight(root) != -1;
}

func getHeight(node *TreeNode) int {
    if node == nil {
        return 0
    }
    leftH := getHeight(node.Left)
    rightH := getHeight(node.Right)
    if leftH == -1 || rightH == -1 || abs(leftH-rightH) > 1 {
        return -1
    }
    return max(leftH, rightH) + 1
}

func isBalanced(root *TreeNode) bool {
    return getHeight(root) != -1
}

func abs(x int) int { if x < 0 { return -x }; return x }

function getHeight(node) {
    if (node === null) {
        return 0;
    }
    const leftH = getHeight(node.left);
    const rightH = getHeight(node.right);
    if (leftH === -1 || rightH === -1 || Math.abs(leftH - rightH) > 1) {
        return -1;
    }
    return Math.max(leftH, rightH) + 1;
}

var isBalanced = function(root) {
    return getHeight(root) !== -1;
};

use std::rc::Rc;
use std::cell::RefCell;

impl Solution {
    pub fn is_balanced(root: Option<Rc<RefCell<TreeNode>>>) -> bool {
        fn get_height(node: &Option<Rc<RefCell<TreeNode>>>) -> i32 {
            if let Some(node) = node {
                let node = node.borrow();
                let left_h = get_height(&node.left);
                let right_h = get_height(&node.right);
                if left_h == -1 || right_h == -1 || (left_h - right_h).abs() > 1 {
                    return -1;
                }
                return left_h.max(right_h) + 1;
            }
            0
        }
        get_height(&root) != -1
    }
}

写法二

class Solution:
    def isBalanced(self, root: Optional[TreeNode]) -> bool:
        def get_height(node: Optional[TreeNode]) -> int:
            if node is None:
                return 0
            left_h = get_height(node.left)
            if left_h == -1:
                return -1  # 提前退出，不再递归
            right_h = get_height(node.right)
            if right_h == -1 or abs(left_h - right_h) > 1:
                return -1
            return max(left_h, right_h) + 1
        return get_height(root) != -1

class Solution {
    public boolean isBalanced(TreeNode root) {
        return getHeight(root) != -1;
    }

    private int getHeight(TreeNode node) {
        if (node == null) {
            return 0;
        }
        int leftH = getHeight(node.left);
        if (leftH == -1) {
            return -1; // 提前退出，不再递归
        }
        int rightH = getHeight(node.right);
        if (rightH == -1 || Math.abs(leftH - rightH) > 1) {
            return -1;
        }
        return Math.max(leftH, rightH) + 1;
    }
}

class Solution {
    int get_height(TreeNode* node) {
        if (node == nullptr) {
            return 0;
        }
        int left_h = get_height(node->left);
        if (left_h == -1) {
            return -1; // 提前退出，不再递归
        }
        int right_h = get_height(node->right);
        if (right_h == -1 || abs(left_h - right_h) > 1) {
            return -1;
        }
        return max(left_h, right_h) + 1;
    }

public:
    bool isBalanced(TreeNode* root) {
        return get_height(root) != -1;
    }
};

#define MAX(a, b) ((b) > (a) ? (b) : (a))

int getHeight(struct TreeNode* node) {
    if (node == NULL) {
        return 0;
    }

    int left_h = getHeight(node->left);
    if (left_h == -1) {
        return -1; // 提前退出，不再递归
    }

    int right_h = getHeight(node->right);
    if (right_h == -1 || abs(left_h - right_h) > 1) {
        return -1;
    }

    return MAX(left_h, right_h) + 1;
}

bool isBalanced(struct TreeNode* root) {
    return getHeight(root) != -1;
}

func getHeight(node *TreeNode) int {
    if node == nil {
        return 0
    }
    leftH := getHeight(node.Left)
    if leftH == -1 {
        return -1 // 提前退出，不再递归
    }
    rightH := getHeight(node.Right)
    if rightH == -1 || abs(leftH-rightH) > 1 {
        return -1
    }
    return max(leftH, rightH) + 1
}

func isBalanced(root *TreeNode) bool {
    return getHeight(root) != -1
}

func abs(x int) int { if x < 0 { return -x }; return x }

function getHeight(node) {
    if (node === null) {
        return 0;
    }
    const leftH = getHeight(node.left);
    if (leftH === -1) {
        return -1; // 提前退出，不再递归
    }
    const rightH = getHeight(node.right);
    if (rightH === -1 || Math.abs(leftH - rightH) > 1) {
        return -1;
    }
    return Math.max(leftH, rightH) + 1;
}

var isBalanced = function(root) {
    return getHeight(root) !== -1;
};

use std::rc::Rc;
use std::cell::RefCell;

impl Solution {
    pub fn is_balanced(root: Option<Rc<RefCell<TreeNode>>>) -> bool {
        fn get_height(node: &Option<Rc<RefCell<TreeNode>>>) -> i32 {
            if let Some(node) = node {
                let node = node.borrow();
                let left_h = get_height(&node.left);
                if left_h == -1 {
                    return -1; // 提前退出，不再递归
                }
                let right_h = get_height(&node.right);
                if right_h == -1 || (left_h - right_h).abs() > 1 {
                    return -1;
                }
                return left_h.max(right_h) + 1;
            }
            0
        }
        get_height(&root) != -1
    }
}

复杂度分析

• 时间复杂度：$\mathcal{O}(n)$，其中 $n$ 为二叉树的节点个数。
• 空间复杂度：$\mathcal{O}(n)$。最坏情况下，二叉树退化成一条链，递归需要 $\mathcal{O}(n)$ 的栈空间。

分类题单

如何科学刷题？

1. 滑动窗口与双指针（定长/不定长/单序列/双序列/三指针/分组循环）
2. 二分算法（二分答案/最小化最大值/最大化最小值/第K小）
3. 单调栈（基础/矩形面积/贡献法/最小字典序）
4. 网格图（DFS/BFS/综合应用）
5. 位运算（基础/性质/拆位/试填/恒等式/思维）
6. 图论算法（DFS/BFS/拓扑排序/基环树/最短路/最小生成树/网络流）
7. 动态规划（入门/背包/划分/状态机/区间/状压/数位/数据结构优化/树形/博弈/概率期望）
8. 常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树）
9. 数学算法（数论/组合/概率期望/博弈/计算几何/随机算法）
10. 贪心与思维（基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造）
11. 链表、二叉树与回溯（前后指针/快慢指针/DFS/BFS/直径/LCA/一般树）
12. 字符串（KMP/Z函数/Manacher/字符串哈希/AC自动机/后缀数组/子序列自动机）

我的题解精选（已分类）

欢迎关注 B站@灵茶山艾府

方法一：前后缀分解（两次遍历）

答疑

问：为什么把 if-else 写成 (c - 'a') * 2 - 1 会快很多？

答：CPU 在遇到分支（条件跳转指令）时会预测代码要执行哪个分支，如果预测正确，CPU 就会继续按照预测的路径执行程序。但如果预测失败，CPU 就需要回滚之前的指令并加载正确的指令，以确保程序执行的正确性。

对于本题的数据，字符 $\text{a'}$ 和 $\text{b'}$ 可以认为是随机出现的，在这种情况下分支预测就会有 $50%$ 的概率失败。失败导致的回滚和加载操作需要消耗额外的 CPU 周期，如果能用较小的代价去掉分支，对于本题的情况必然可以带来效率上的提升。

注：这种优化方法会降低可读性，不建议在业务代码中使用。

class Solution:
    def minimumDeletions(self, s: str) -> int:
        ans = delete = s.count('a')
        for c in s:
            delete -= 1 if c == 'a' else -1
            if delete < ans:  # 手动计算 min 会快很多
                ans = delete
        return ans

class Solution {
    public int minimumDeletions(String S) {
        char[] s = S.toCharArray();
        int del = 0;
        for (char c : s) {
            del += 'b' - c; // 统计 'a' 的个数
        }

        int ans = del;
        for (char c : s) {
            // 'a' -> -1    'b' -> 1
            del += (c - 'a') * 2 - 1;
            ans = Math.min(ans, del);
        }
        return ans;
    }
}

class Solution {
public:
    int minimumDeletions(string s) {
        int del = 0;
        for (char c : s) {
            del += 'b' - c; // 统计 'a' 的个数
        }

        int ans = del;
        for (char c : s) {
            // 'a' -> -1    'b' -> 1
            del += (c - 'a') * 2 - 1;
            ans = min(ans, del);
        }
        return ans;
    }
};

func minimumDeletions(s string) int {
del := strings.Count(s, "a")
ans := del
for _, c := range s {
// 'a' -> -1    'b' -> 1
del += int((c-'a')*2 - 1)
ans = min(ans, del)
}
return ans
}

复杂度分析

• 时间复杂度：$\mathcal{O}(n)$，其中 $n$ 是 $s$ 的长度。
• 空间复杂度：$\mathcal{O}(1)$。

方法二：动态规划（一次遍历）

如果你还不熟悉动态规划（包括空间优化），可以先看看 动态规划入门。

考虑 $s$ 的最后一个字母：

• 如果它是 $\text{`b'}$，则无需删除，问题规模缩小，变成「使 $s$ 的前 $n-1$ 个字母平衡的最少删除次数」。
• 如果它是 $\text{`a'}$：
  • 删除它，则答案为「使 $s$ 的前 $n-1$ 个字母平衡的最少删除次数」加上 $1$。
  • 保留它，那么前面的所有 $\text{`b'}$ 都要删除；

设 $\textit{cntB}_i$ 为前 $i$ 个字母中 $\text{`b'}$ 的个数。定义 $f_i$ 表示使 $s$ 的前 $i$ 个字母平衡的最少删除次数：

• 如果第 $i$ 个字母是 $\text{`b'}$，则 $f_i = f_{i-1}$；
• 如果第 $i$ 个字母是 $\text{`a'}$，则 $f_i = \min(f_{i-1}+1,\textit{cntB}_i)$。

class Solution:
    def minimumDeletions(self, s: str) -> int:
        f = cnt_b = 0
        for c in s:
            if c == 'b':
                cnt_b += 1  # f 值不变
            else:
                f = min(f + 1, cnt_b)
        return f

class Solution {
    public int minimumDeletions(String s) {
        int f = 0;
        int cntB = 0;
        for (char c : s.toCharArray()) {
            if (c == 'b') {
                cntB++; // f 值不变
            } else {
                f = Math.min(f + 1, cntB);
            }
        }
        return f;
    }
}

class Solution {
public:
    int minimumDeletions(string s) {
        int f = 0, cnt_b = 0;
        for (char c : s) {
            if (c == 'b') {
                cnt_b++; // f 值不变
            } else {
                f = min(f + 1, cnt_b);
            }
        }
        return f;
    }
};

func minimumDeletions(s string) int {
    f, cntB := 0, 0
    for _, c := range s {
        if c == 'b' { // f 值不变
            cntB++
        } else {
            f = min(f+1, cntB)
        }
    }
    return f
}

这份代码也可以像方法一那样去掉分支：

• 如果第 $i$ 个字母是 $\text{b'}$，则 $\textit{cntB}$ 增加 $1$，$f[i] = \min(f[i-1],\textit{cntB})$，这里也考虑全部删除 $\text{b'}$；
• 如果第 $i$ 个字母是 $\text{`a'}$，则 $\textit{cntB}$ 增加 $0$，$f[i] = \min(f[i-1]+1,\textit{cntB})$。

这两种情况可以合并成：

设当前字母为 $c$，$x=c-\text{`a'}$，则 $\textit{cntB}$ 增加 $x$，$f[i] = \min(f[i-1]+(x\oplus 1),\textit{cntB})$。其中 $\oplus$ 表示异或。

class Solution:
    def minimumDeletions(self, s: str) -> int:
        f = cnt_b = 0
        for c in s:
            x = ord(c) - ord('a')  # ord 很慢
            cnt_b += x
            f = min(f + (x ^ 1), cnt_b)
        return f

class Solution {
    public int minimumDeletions(String s) {
        int f = 0;
        int cntB = 0;
        for (char c : s.toCharArray()) {
            int x = c - 'a';
            cntB += x;
            f = Math.min(f + (x ^ 1), cntB);
        }
        return f;
    }
}

class Solution {
public:
    int minimumDeletions(string s) {
        int f = 0, cnt_b = 0;
        for (char c : s) {
            int x = c - 'a';
            cnt_b += x;
            f = min(f + (x ^ 1), cnt_b);
        }
        return f;
    }
};

func minimumDeletions(s string) int {
    f, cntB := 0, 0
    for _, c := range s {
        x := int(c - 'a')
        cntB += x
        f = min(f+(x^1), cntB)
    }
    return f
}

复杂度分析

• 时间复杂度：$\mathcal{O}(n)$，其中 $n$ 是 $s$ 的长度。
• 空间复杂度：$\mathcal{O}(1)$。

专题训练

见下面动态规划题单的「专题：前后缀分解」。

分类题单

如何科学刷题？

1. 滑动窗口与双指针（定长/不定长/单序列/双序列/三指针/分组循环）
2. 二分算法（二分答案/最小化最大值/最大化最小值/第K小）
3. 单调栈（基础/矩形面积/贡献法/最小字典序）
4. 网格图（DFS/BFS/综合应用）
5. 位运算（基础/性质/拆位/试填/恒等式/思维）
6. 图论算法（DFS/BFS/拓扑排序/基环树/最短路/最小生成树/网络流）
7. 动态规划（入门/背包/划分/状态机/区间/状压/数位/数据结构优化/树形/博弈/概率期望）
8. 常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树）
9. 数学算法（数论/组合/概率期望/博弈/计算几何/随机算法）
10. 贪心与思维（基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造）
11. 链表、树与回溯（前后指针/快慢指针/DFS/BFS/直径/LCA）
12. 字符串（KMP/Z函数/Manacher/字符串哈希/AC自动机/后缀数组/子序列自动机）

我的题解精选（已分类）

欢迎关注 B站@灵茶山艾府

操作相当于从下标 $i$ 移动到下标 $i+\textit{nums}[i]$。

如果 $i+\textit{nums}[i]$ 下标越界呢？

需要把 $i+\textit{nums}[i]$ 调整到 $[0,n-1]$ 范围中。具体来说，把下标 $i+\textit{nums}[i]$ 模 $n$。比如 $n=4$，在循环数组中，正数下标 $5,9,13,\ldots$ 都是下标 $1$，负数下标 $-3,-7,-11,\ldots$ 也都是下标 $1$。

不了解取模的同学，请看 模运算的世界：当加减乘除遇上取模。

本题视频讲解，欢迎点赞关注~

###py

class Solution:
    def constructTransformedArray(self, nums: List[int]) -> List[int]:
        n = len(nums)
        return [nums[(i + x) % n] for i, x in enumerate(nums)]

###java

class Solution {
    public int[] constructTransformedArray(int[] nums) {
        int n = nums.length;
        int[] result = new int[n];
        for (int i = 0; i < n; i++) {
            result[i] = nums[((i + nums[i]) % n + n) % n]; // 保证结果在 [0,n-1] 中
        }
        return result;
    }
}

###cpp

class Solution {
public:
    vector<int> constructTransformedArray(vector<int>& nums) {
        int n = nums.size();
        vector<int> result(n);
        for (int i = 0; i < n; i++) {
            result[i] = nums[((i + nums[i]) % n + n) % n]; // 保证结果在 [0,n-1] 中
        }
        return result;
    }
};

###c

int* constructTransformedArray(int* nums, int numsSize, int* returnSize) {
    int n = numsSize;
    int* result = malloc(n * sizeof(int));
    for (int i = 0; i < n; i++) {
        result[i] = nums[((i + nums[i]) % n + n) % n]; // 保证结果在 [0,n-1] 中
    }
    *returnSize = n;
    return result;
}

###go

func constructTransformedArray(nums []int) []int {
n := len(nums)
result := make([]int, n)
for i, x := range nums {
result[i] = nums[((i+x)%n+n)%n] // 保证结果在 [0,n-1] 中
}
return result
}

###js

var constructTransformedArray = function(nums) {
    const n = nums.length;
    const result = new Array(n);
    for (let i = 0; i < n; i++) {
        result[i] = nums[((i + nums[i]) % n + n) % n]; // 保证结果在 [0,n-1] 中
    }
    return result;
};

###rust

impl Solution {
    pub fn construct_transformed_array(nums: Vec<i32>) -> Vec<i32> {
        let n = nums.len();
        let m = n as i32;
        let mut result = vec![0; n];
        for i in 0..n {
            let j = ((i as i32 + nums[i]) % m + m) % m; // 保证结果在 [0,n-1] 中
            result[i] = nums[j as usize];
        }
        result
    }
}

复杂度分析

• 时间复杂度：$\mathcal{O}(n)$，其中 $n$ 是 $\textit{nums}$ 的长度。
• 空间复杂度：$\mathcal{O}(1)$。返回值不计入。

分类题单

如何科学刷题？

1. 滑动窗口与双指针（定长/不定长/单序列/双序列/三指针/分组循环）
2. 二分算法（二分答案/最小化最大值/最大化最小值/第K小）
3. 单调栈（基础/矩形面积/贡献法/最小字典序）
4. 网格图（DFS/BFS/综合应用）
5. 位运算（基础/性质/拆位/试填/恒等式/思维）
6. 图论算法（DFS/BFS/拓扑排序/基环树/最短路/最小生成树/网络流）
7. 动态规划（入门/背包/划分/状态机/区间/状压/数位/数据结构优化/树形/博弈/概率期望）
8. 常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树）
9. 数学算法（数论/组合/概率期望/博弈/计算几何/随机算法）
10. 贪心与思维（基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造）
11. 链表、树与回溯（前后指针/快慢指针/DFS/BFS/直径/LCA）
12. 字符串（KMP/Z函数/Manacher/字符串哈希/AC自动机/后缀数组/子序列自动机）

我的题解精选（已分类）

欢迎关注 B站@灵茶山艾府