LeetCode 每日一题题解
直接调用 84 题代码解决（Python/Java/C++/C/Go/JS/Rust）endlesscheng
2025年6月19日 19:14

Rust）

LeetCode 每日一题题解

作者 endlesscheng

2025年6月19日 19:14

回顾一下，这是 84. 柱状图中最大的矩形的图：

{:width=400}

对于本题，设 $\textit{matrix}$ 有 $m$ 行，我们可以枚举矩形的底边，做 $m$ 次 84 题。

{:width=300}

以第一行为底的柱子高度为 $[1,0,1,0,0]$，最大矩形面积为 $1$。
以第二行为底的柱子高度为 $[2,0,2,1,1]$，最大矩形面积为 $3$。
以第三行为底的柱子高度为 $[3,1,3,2,2]$，最大矩形面积为 $6$。
以第四行为底的柱子高度为 $[4,0,0,3,0]$，最大矩形面积为 $4$。
答案为 $\max(1,3,6,4) = 6$。

由于我们枚举的是矩形的底边，如果 $\textit{matrix}[i][j]=0$，那么没有柱子，高度等于 $0$。否则，在上一行柱子的基础上，把柱子高度增加 $1$。形象地说，就是在柱子下面垫一块石头，把柱子抬高。

###py

class Solution:
    # 84. 柱状图中最大的矩形
    def largestRectangleArea(self, heights: List[int]) -> int:
        st = [-1]  # 在栈中只有一个数的时候，栈顶的「下面那个数」是 -1，对应 left[i] = -1 的情况
        ans = 0
        for right, h in enumerate(heights):
            while len(st) > 1 and heights[st[-1]] >= h:
                i = st.pop()  # 矩形的高（的下标）
                left = st[-1]  # 栈顶下面那个数就是 left
                ans = max(ans, heights[i] * (right - left - 1))
            st.append(right)
        return ans

    def maximalRectangle(self, matrix: List[List[str]]) -> int:
        n = len(matrix[0])
        heights = [0] * (n + 1)  # 末尾多一个 0，理由见我 84 题题解
        ans = 0
        for row in matrix:
            # 计算底边为 row 的柱子高度
            for j, c in enumerate(row):
                if c == '0':
                    heights[j] = 0  # 柱子高度为 0
                else:
                    heights[j] += 1  # 柱子高度加一
            ans = max(ans, self.largestRectangleArea(heights))  # 调用 84 题代码
        return ans

###java

class Solution {
    int maximalRectangle(char[][] matrix) {
        int n = matrix[0].length;
        int[] heights = new int[n + 1]; // 末尾多一个 0，理由见我 84 题题解
        int ans = 0;
        for (char[] row : matrix) {
            // 计算底边为 row 的柱子高度
            for (int j = 0; j < n; j++) {
                if (row[j] == '0') {
                    heights[j] = 0; // 柱子高度为 0
                } else {
                    heights[j]++; // 柱子高度加一
                }
            }
            ans = Math.max(ans, largestRectangleArea(heights)); // 调用 84 题代码
        }
        return ans;
    }

    // 84. 柱状图中最大的矩形
    private int largestRectangleArea(int[] heights) {
        int n = heights.length;
        int[] st = new int[n]; // 用数组模拟栈
        int top = -1; // 栈顶下标
        st[++top] = -1; // 在栈中只有一个数的时候，栈顶的「下面那个数」是 -1，对应 left[i] = -1 的情况
        int ans = 0;
        for (int right = 0; right < n; right++) {
            int h = heights[right];
            while (top > 0 && heights[st[top]] >= h) {
                int i = st[top--]; // 矩形的高（的下标）
                int left = st[top]; // 栈顶下面那个数就是 left
                ans = Math.max(ans, heights[i] * (right - left - 1));
            }
            st[++top] = right;
        }
        return ans;
    }
}

###cpp

class Solution {
    // 84. 柱状图中最大的矩形
    int largestRectangleArea(vector<int>& heights) {
        stack<int> st;
        st.push(-1); // 在栈中只有一个数的时候，栈顶的「下面那个数」是 -1，对应 left[i] = -1 的情况
        int ans = 0;
        for (int right = 0; right < heights.size(); right++) {
            int h = heights[right];
            while (st.size() > 1 && heights[st.top()] >= h) {
                int i = st.top(); // 矩形的高（的下标）
                st.pop();
                int left = st.top(); // 栈顶下面那个数就是 left
                ans = max(ans, heights[i] * (right - left - 1));
            }
            st.push(right);
        }
        return ans;
    }

public:
    int maximalRectangle(vector<vector<char>>& matrix) {
        int n = matrix[0].size();
        vector<int> heights(n + 1); // 末尾多一个 0，理由见我 84 题题解
        int ans = 0;
        for (auto& row : matrix) {
            // 计算底边为 row 的柱子高度
            for (int j = 0; j < n; j++) {
                if (row[j] == '0') {
                    heights[j] = 0; // 柱子高度为 0
                } else {
                    heights[j]++; // 柱子高度加一
                }
            }
            ans = max(ans, largestRectangleArea(heights)); // 调用 84 题代码
        }
        return ans;
    }
};

###c

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

// 84. 柱状图中最大的矩形
int largestRectangleArea(int* heights, int n) {
    int* stack = malloc(n * sizeof(int));
    int top = -1; // 栈顶下标
    stack[++top] = -1; // 在栈中只有一个数的时候，栈顶的「下面那个数」是 -1，对应 left[i] = -1 的情况
    int ans = 0;
    for (int right = 0; right < n; right++) {
        int h = heights[right];
        while (top > 0 && heights[stack[top]] >= h) {
            int i = stack[top--]; // 矩形的高（的下标）
            int left = stack[top]; // 栈顶下面那个数就是 left
            ans = MAX(ans, heights[i] * (right - left - 1));
        }
        stack[++top] = right;
    }
    free(stack);
    return ans;
}

int maximalRectangle(char** matrix, int matrixSize, int* matrixColSize) {
    int n = matrixColSize[0];
    int* heights = calloc(n + 1, sizeof(int)); // 末尾多一个 0，理由见我 84 题题解
    int ans = 0;
    for (int i = 0; i < matrixSize; i++) {
        char* row = matrix[i];
        // 计算底边为 row 的柱子高度
        for (int j = 0; j < n; j++) {
            if (row[j] == '0') {
                heights[j] = 0; // 柱子高度为 0
            } else {
                heights[j]++; // 柱子高度加一
            }
        }
        ans = MAX(ans, largestRectangleArea(heights, n + 1)); // 调用 84 题代码，注意传入的是 n+1
    }
    free(heights);
    return ans;
}

###go

// 84. 柱状图中最大的矩形
func largestRectangleArea(heights []int) (ans int) {
    st := []int{-1} // 在栈中只有一个数的时候，栈顶的「下面那个数」是 -1，对应 left[i] = -1 的情况
    for right, h := range heights {
        for len(st) > 1 && heights[st[len(st)-1]] >= h {
            i := st[len(st)-1] // 矩形的高（的下标）
            st = st[:len(st)-1]
            left := st[len(st)-1] // 栈顶下面那个数就是 left
            ans = max(ans, heights[i]*(right-left-1))
        }
        st = append(st, right)
    }
    return
}

func maximalRectangle(matrix [][]byte) (ans int) {
    heights := make([]int, len(matrix[0])+1) // 末尾多一个 0，理由见我 84 题题解
    for _, row := range matrix {
        // 计算底边为 row 的柱子高度
        for j, c := range row {
            if c == '0' {
                heights[j] = 0 // 柱子高度为 0
            } else {
                heights[j]++ // 柱子高度加一
            }
        }
        ans = max(ans, largestRectangleArea(heights)) // 调用 84 题代码
    }
    return
}

###js

// 84. 柱状图中最大的矩形
var largestRectangleArea = function(heights) {
    const st = [-1]; // 在栈中只有一个数的时候，栈顶的「下面那个数」是 -1，对应 left[i] = -1 的情况
    let ans = 0;
    for (let right = 0; right < heights.length; right++) {
        const h = heights[right]
        while (st.length > 1 && heights[st[st.length - 1]] >= h) {
            const i = st.pop(); // 矩形的高（的下标）
            const left = st[st.length - 1]; // 栈顶下面那个数就是 left
            ans = Math.max(ans, heights[i] * (right - left - 1));
        }
        st.push(right);
    }
    return ans;
};

var maximalRectangle = function(matrix) {
    const n = matrix[0].length;
    let heights = Array(n + 1).fill(0); // 末尾多一个 0，理由见我 84 题题解
    let ans = 0;
    for (const row of matrix) {
        // 计算底边为 row 的柱子高度
        for (let j = 0; j < n; j++) {
            if (row[j] === '0') {
                heights[j] = 0; // 柱子高度为 0
            } else {
                heights[j]++; // 柱子高度加一
            }
        }
        ans = Math.max(ans, largestRectangleArea(heights)); // 调用 84 题代码
    }
    return ans;
};

###rust

impl Solution {
    // 84. 柱状图中最大的矩形
    fn largest_rectangle_area(heights: &[i32]) -> i32 {
        let mut st = vec![-1]; // 在栈中只有一个数的时候，栈顶的「下面那个数」是 -1，对应 left[i] = -1 的情况
        let mut ans = 0;
        for (right, &h) in heights.iter().enumerate() {
            let right = right as i32;
            while st.len() > 1 && heights[*st.last().unwrap() as usize] >= h {
                let i = st.pop().unwrap() as usize; // 矩形的高（的下标）
                let left = *st.last().unwrap(); // 栈顶下面那个数就是 left
                ans = ans.max(heights[i] * (right - left - 1));
            }
            st.push(right);
        }
        ans
    }

    pub fn maximal_rectangle(matrix: Vec<Vec<char>>) -> i32 {
        let n = matrix[0].len();
        let mut heights = vec![0; n + 1]; // 末尾多一个 0，理由见我 84 题题解
        let mut ans = 0;
        for row in matrix {
            // 计算底边为 row 的柱子高度
            for (j, c) in row.into_iter().enumerate() {
                if c == '0' {
                    heights[j] = 0; // 柱子高度为 0
                } else {
                    heights[j] += 1; // 柱子高度加一
                }
            }
            ans = ans.max(Self::largest_rectangle_area(&heights)); // 调用 84 题代码
        }
        ans
    }
}

复杂度分析

时间复杂度：$\mathcal{O}(mn)$，其中 $m$ 和 $n$ 分别为 $\textit{matrix}$ 的行数和列数。做 $m$ 次 84 题，每次 $\mathcal{O}(n)$。
空间复杂度：$\mathcal{O}(n)$。

相似题目

见下面单调栈题单的「二、矩形」。

分类题单

如何科学刷题？

我的题解精选（已分类）

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

LeetCode 每日一题题解
正难则反：计算最多保留的 ASCII 之和（Python/Java/C++/Go）endlesscheng
2025年12月31日 13:36

正难则反：计算最多保留的 ASCII 之和（Python/Java/C++/Go）

LeetCode 每日一题题解

作者 endlesscheng

2025年12月31日 13:36

用 $s_1$ 和 $s_2$ 的 ASCII 值之和，减去保留的 ASCII 之和的最大值，就是删除字符的 ASCII 值之和的最小值。

计算最多保留的 ASCII 之和，方法和 1143. 最长公共子序列一样：

1143 题，$s_1[i] = s_2[j]$ 时，都保留，最长公共子序列长度增加 $1$。
本题，$s_1[i] = s_2[j]$ 时，都保留，保留的 ASCII 之和增加 $\text{ASCII}(s_1[i])\cdot 2$。

所以只需把 1143 题的 $+1$ 改成 $+\text{ASCII}(s_1[i])\cdot 2$。

也可以改成 $+\text{ASCII}(s_1[i])$，最后返回时再乘以 $2$。

###py

class Solution:
    def minimumDeleteSum(self, s1: str, s2: str) -> int:
        n, m = len(s1), len(s2)
        total = sum(map(ord, s1)) + sum(map(ord, s2))

        f = [[0] * (m + 1) for _ in range(n + 1)]
        for i, x in enumerate(s1):
            for j, y in enumerate(s2):
                if x == y:
                    f[i + 1][j + 1] = f[i][j] + ord(x)
                else:
                    f[i + 1][j + 1] = max(f[i][j + 1], f[i + 1][j])
        return total - f[n][m] * 2

###java

class Solution {
    public int minimumDeleteSum(String s1, String s2) {
        int total = s1.chars().sum() + s2.chars().sum();

        char[] s = s1.toCharArray();
        char[] t = s2.toCharArray();
        int n = s.length;
        int m = t.length;

        int[][] f = new int[n + 1][m + 1];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (s[i] == t[j]) {
                    f[i + 1][j + 1] = f[i][j] + s[i];
                } else {
                    f[i + 1][j + 1] = Math.max(f[i][j + 1], f[i + 1][j]);
                }
            }
        }
        return total - f[n][m] * 2;
    }
}

###cpp

class Solution {
public:
    int minimumDeleteSum(string s1, string s2) {
        int n = s1.size(), m = s2.size();
        int total = reduce(s1.begin(), s1.end(), 0) + reduce(s2.begin(), s2.end(), 0);

        vector f(n + 1, vector<int>(m + 1));
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (s1[i] == s2[j]) {
                    f[i + 1][j + 1] = f[i][j] + s1[i];
                } else {
                    f[i + 1][j + 1] = max(f[i][j + 1], f[i + 1][j]);
                }
            }
        }
        return total - f[n][m] * 2;
    }
};

###go

func minimumDeleteSum(s1, s2 string) int {
n, m := len(s1), len(s2)
total := 0
for _, c := range s1 {
total += int(c)
}
for _, c := range s2 {
total += int(c)
}

f := make([][]int, n+1)
for i := range f {
f[i] = make([]int, m+1)
}
for i, x := range s1 {
for j, y := range s2 {
if x == y {
f[i+1][j+1] = f[i][j] + int(x)
} else {
f[i+1][j+1] = max(f[i][j+1], f[i+1][j])
}
}
}
return total - f[n][m]*2
}

空间优化：

###py

# 更快的写法见【Python3 手写 max】
class Solution:
    def minimumDeleteSum(self, s1: str, s2: str) -> int:
        m = len(s2)
        total = sum(map(ord, s1)) + sum(map(ord, s2))

        f = [0] * (m + 1)
        for x in s1:
            ord_x = ord(x)
            pre = 0  # f[0]
            for j, y in enumerate(s2):
                tmp = f[j + 1]
                if x == y:
                    f[j + 1] = pre + ord_x
                else:
                    f[j + 1] = max(f[j + 1], f[j])
                pre = tmp
        return total - f[m] * 2

###py

class Solution:
    def minimumDeleteSum(self, s1: str, s2: str) -> int:
        m = len(s2)
        total = sum(map(ord, s1)) + sum(map(ord, s2))

        f = [0] * (m + 1)
        for x in s1:
            ord_x = ord(x)
            pre = 0  # f[0]
            for j, y in enumerate(s2):
                tmp = f[j + 1]
                if x == y:
                    f[j + 1] = pre + ord_x
                elif f[j] > f[j + 1]:
                    f[j + 1] = f[j]
                pre = tmp
        return total - f[m] * 2

###java

class Solution {
    public int minimumDeleteSum(String s1, String s2) {
        int total = s1.chars().sum() + s2.chars().sum();

        char[] s = s1.toCharArray();
        char[] t = s2.toCharArray();
        int m = t.length;

        int[] f = new int[m + 1];
        for (char x : s) {
            int pre = 0; // f[0]
            for (int j = 0; j < m; j++) {
                int tmp = f[j + 1];
                if (x == t[j]) {
                    f[j + 1] = pre + x;
                } else {
                    f[j + 1] = Math.max(f[j + 1], f[j]);
                }
                pre = tmp;
            }
        }
        return total - f[m] * 2;
    }
}

###cpp

class Solution {
public:
    int minimumDeleteSum(string s1, string s2) {
        int m = s2.size();
        int total = reduce(s1.begin(), s1.end(), 0) + reduce(s2.begin(), s2.end(), 0);

        vector<int> f(m + 1);
        for (char x : s1) {
            int pre = 0; // f[0]
            for (int j = 0; j < m; j++) {
                int tmp = f[j + 1];
                if (x == s2[j]) {
                    f[j + 1] = pre + x;
                } else {
                    f[j + 1] = max(f[j + 1], f[j]);
                }
                pre = tmp;
            }
        }
        return total - f[m] * 2;
    }
};

###go

func minimumDeleteSum(s1, s2 string) int {
m := len(s2)
total := 0
for _, c := range s1 {
total += int(c)
}
for _, c := range s2 {
total += int(c)
}

f := make([]int, m+1)
for _, x := range s1 {
pre := 0 // f[0]
for j, y := range s2 {
tmp := f[j+1]
if x == y {
f[j+1] = pre + int(x)
} else {
f[j+1] = max(f[j+1], f[j])
}
pre = tmp
}
}
return total - f[m]*2
}

复杂度分析

时间复杂度：$\mathcal{O}(nm)$，其中 $n$ 是 $s_1$ 的长度，$m$ 是 $s_2$ 的长度。
空间复杂度：$\mathcal{O}(m)$。

专题训练

见下面动态规划题单的「§4.1 最长公共子序列（LCS）」。

分类题单

如何科学刷题？

我的题解精选（已分类）

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

LeetCode 每日一题题解
两种 O(n) 递归写法（Python/Java/C++/Go/JS）endlesscheng
2023年9月6日 08:01

两种 O(n) 递归写法（Python/Java/C++/Go/JS）

LeetCode 每日一题题解

作者 endlesscheng

2023年9月6日 08:01

前置题目：236. 二叉树的最近公共祖先。

视频讲解：二叉树的最近公共祖先【基础算法精讲 12】。

方法一：递归递归，有递有归

{:width=360px}

看上图（示例 1），这棵树的节点 $3,5,2$ 都是最深叶节点 $7,4$ 的公共祖先，但只有节点 $2$ 是最近的公共祖先。

上面视频中提到，如果我们要找的节点只在左子树中，那么最近公共祖先也必然只在左子树中。对于本题，如果左子树的最大深度比右子树的大，那么最深叶结点就只在左子树中，所以最近公共祖先也只在左子树中。

如果左右子树的最大深度一样呢？当前节点一定是最近公共祖先吗？

不一定。比如节点 $1$ 的左右子树最深叶节点 $0,8$ 的深度都是 $2$，但该深度并不是全局最大深度，所以节点 $1$ 并不能是答案。

根据以上讨论，正确做法如下：

递归这棵二叉树，同时维护全局最大深度 $\textit{maxDepth}$。
在「递」的时候往下传 $\textit{depth}$，用来表示当前节点的深度。
在「归」的时候往上传当前子树最深叶节点的深度。
设左子树最深叶节点的深度为 $\textit{leftMaxDepth}$，右子树最深叶节点的深度为 $\textit{rightMaxDepth}$。如果 $\textit{leftMaxDepth}=\textit{rightMaxDepth}=\textit{maxDepth}$，那么更新答案为当前节点。⚠注意：这并不代表我们立刻找到了答案，如果后面发现了更深的叶节点，答案还会更新。

class Solution:
    def subtreeWithAllDeepest(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        max_depth = -1  # 全局最大深度
        ans = None

        def dfs(node: Optional[TreeNode], depth: int) -> int:
            nonlocal ans, max_depth
            if node is None:
                max_depth = max(max_depth, depth)  # 维护全局最大深度
                return depth

            left_max_depth = dfs(node.left, depth + 1)  # 获取左子树最深叶节点的深度
            right_max_depth = dfs(node.right, depth + 1)  # 获取右子树最深叶节点的深度

            if left_max_depth == right_max_depth == max_depth:
                ans = node  # node 可能是答案

            return max(left_max_depth, right_max_depth)  # 当前子树最深叶节点的深度

        dfs(root, 0)
        return ans

class Solution {
    private int maxDepth = -1; // 全局最大深度
    private TreeNode ans;

    public TreeNode subtreeWithAllDeepest(TreeNode root) {
        dfs(root, 0);
        return ans;
    }

    private int dfs(TreeNode node, int depth) {
        if (node == null) {
            maxDepth = Math.max(maxDepth, depth); // 维护全局最大深度
            return depth;
        }

        int leftMaxDepth = dfs(node.left, depth + 1); // 获取左子树最深叶节点的深度
        int rightMaxDepth = dfs(node.right, depth + 1); // 获取右子树最深叶节点的深度

        if (leftMaxDepth == rightMaxDepth && leftMaxDepth == maxDepth) {
            ans = node; // node 可能是答案
        }

        return Math.max(leftMaxDepth, rightMaxDepth); // 当前子树最深叶节点的深度
    }
}

class Solution {
public:
    TreeNode* subtreeWithAllDeepest(TreeNode* root) {
        int max_depth = -1; // 全局最大深度
        TreeNode* ans;

        auto dfs = [&](this auto&& dfs, TreeNode* node, int depth) {
            if (node == nullptr) {
                max_depth = max(max_depth, depth); // 维护全局最大深度
                return depth;
            }

            int left_max_depth = dfs(node->left, depth + 1); // 获取左子树最深叶节点的深度
            int right_max_depth = dfs(node->right, depth + 1); // 获取右子树最深叶节点的深度

            if (left_max_depth == right_max_depth && left_max_depth == max_depth) {
                ans = node; // node 可能是答案
            }

            return max(left_max_depth, right_max_depth); // 当前子树最深叶节点的深度
        };

        dfs(root, 0);
        return ans;
    }
};

func subtreeWithAllDeepest(root *TreeNode) (ans *TreeNode) {
    maxDepth := -1 // 全局最大深度

    var dfs func(*TreeNode, int) int
    dfs = func(node *TreeNode, depth int) int {
        if node == nil {
            maxDepth = max(maxDepth, depth) // 维护全局最大深度
            return depth
        }

        leftMaxDepth := dfs(node.Left, depth+1) // 获取左子树最深叶节点的深度
        rightMaxDepth := dfs(node.Right, depth+1) // 获取右子树最深叶节点的深度

        if leftMaxDepth == rightMaxDepth && leftMaxDepth == maxDepth {
            ans = node // node 可能是答案
        }

        return max(leftMaxDepth, rightMaxDepth) // 当前子树最深叶节点的深度
    }

    dfs(root, 0)
    return
}

var subtreeWithAllDeepest = function(root) {
    let maxDepth = -1; // 全局最大深度
    let ans = null;

    function dfs(node, depth) {
        if (node === null) {
            maxDepth = Math.max(maxDepth, depth); // 维护全局最大深度
            return depth;
        }

        const leftMaxDepth = dfs(node.left, depth + 1); // 获取左子树最深叶节点的深度
        const rightMaxDepth = dfs(node.right, depth + 1); // 获取右子树最深叶节点的深度

        if (leftMaxDepth === rightMaxDepth && leftMaxDepth === maxDepth) {
            ans = node; // node 可能是答案
        }

        return Math.max(leftMaxDepth, rightMaxDepth); // 当前子树最深叶节点的深度
    }

    dfs(root, 0);
    return ans;
};

复杂度分析

时间复杂度：$\mathcal{O}(n)$。每个节点都会恰好访问一次。
空间复杂度：$\mathcal{O}(n)$。最坏情况下，二叉树是一条链，递归需要 $\mathcal{O}(n)$ 的栈空间。

方法二：自底向上

也可以不用全局变量，而是把每棵子树都看成是一个「子问题」，即对于每棵子树，我们需要知道：

这棵子树最深叶结点的深度。这里是指叶子在这棵子树内的深度，而不是在整棵二叉树的视角下的深度。相当于这棵子树的高度。
这棵子树的最深叶结点的最近公共祖先 $\textit{lca}$。

分类讨论：

设子树的根节点为 $\textit{node}$，$\textit{node}$ 的左子树的高度为 $\textit{leftHeight}$，$\textit{node}$ 的右子树的高度为 $\textit{rightHeight}$。
如果 $\textit{leftHeight} > \textit{rightHeight}$，那么子树的高度为 $\textit{leftHeight} + 1$，$\textit{lca}$ 是左子树的 $\textit{lca}$。
如果 $\textit{leftHeight} < \textit{rightHeight}$，那么子树的高度为 $\textit{rightHeight} + 1$，$\textit{lca}$ 是右子树的 $\textit{lca}$。
如果 $\textit{leftHeight} = \textit{rightHeight}$，那么子树的高度为 $\textit{leftHeight} + 1$，$\textit{lca}$ 就是 $\textit{node}$。反证法：如果 $\textit{lca}$ 在左子树中，那么 $\textit{lca}$ 不是右子树的最深叶结点的祖先，这不对；如果 $\textit{lca}$ 在右子树中，那么 $\textit{lca}$ 不是左子树的最深叶结点的祖先，这也不对；如果 $\textit{lca}$ 在 $\textit{node}$ 的上面，那就不符合「最近」的要求。所以 $\textit{lca}$ 只能是 $\textit{node}$。

class Solution:
    def subtreeWithAllDeepest(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        def dfs(node: Optional[TreeNode]) -> Tuple[int, Optional[TreeNode]]:
            if node is None:
                return 0, None

            left_height, left_lca = dfs(node.left)
            right_height, right_lca = dfs(node.right)

            if left_height > right_height:  # 左子树更高
                return left_height + 1, left_lca
            if left_height < right_height:  # 右子树更高
                return right_height + 1, right_lca
            return left_height + 1, node  # 一样高

        return dfs(root)[1]

class Solution {
    private record Pair(int height, TreeNode lca) {}

    public TreeNode subtreeWithAllDeepest(TreeNode root) {
        return dfs(root).lca;
    }

    private Pair dfs(TreeNode node) {
        if (node == null) {
            return new Pair(0, null);
        }

        Pair left = dfs(node.left);
        Pair right = dfs(node.right);

        if (left.height > right.height) { // 左子树更高
            return new Pair(left.height + 1, left.lca);
        }
        if (left.height < right.height) { // 右子树更高
            return new Pair(right.height + 1, right.lca);
        }
        return new Pair(left.height + 1, node); // 一样高
    }
}

class Solution {
    pair<int, TreeNode*> dfs(TreeNode* node) {
        if (node == nullptr) {
            return {0, nullptr};
        }

        auto [left_height, left_lca] = dfs(node->left);
        auto [right_height, right_lca] = dfs(node->right);

        if (left_height > right_height) { // 左子树更高
            return {left_height + 1, left_lca};
        }
        if (left_height < right_height) { // 右子树更高
            return {right_height + 1, right_lca};
        }
        return {left_height + 1, node}; // 一样高
    }

public:
    TreeNode* subtreeWithAllDeepest(TreeNode* root) {
        return dfs(root).second;
    }
};

func dfs(node *TreeNode) (int, *TreeNode) {
    if node == nil {
        return 0, nil
    }

    leftHeight, leftLCA := dfs(node.Left)
    rightHeight, rightLCA := dfs(node.Right)

    if leftHeight > rightHeight { // 左子树更高
        return leftHeight + 1, leftLCA
    }
    if leftHeight < rightHeight { // 右子树更高
        return rightHeight + 1, rightLCA
    }
    return leftHeight + 1, node // 一样高
}

func subtreeWithAllDeepest(root *TreeNode) *TreeNode {
    _, lca := dfs(root)
    return lca
}

function dfs(node) {
    if (node === null) {
        return [0, null];
    }

    const [leftHeight, leftLca] = dfs(node.left);
    const [rightHeight, rightLca] = dfs(node.right);

    if (leftHeight > rightHeight) { // 左子树更高
        return [leftHeight + 1, leftLca];
    }
    if (leftHeight < rightHeight) { // 右子树更高
        return [rightHeight + 1, rightLca];
    }
    return [leftHeight + 1, node]; // 一样高
}

var subtreeWithAllDeepest = function(root) {
    return dfs(root)[1];
};

复杂度分析

时间复杂度：$\mathcal{O}(n)$。每个节点都会恰好访问一次。
空间复杂度：$\mathcal{O}(n)$。最坏情况下，二叉树是一条链，递归需要 $\mathcal{O}(n)$ 的栈空间。

分类题单

如何科学刷题？

我的题解精选（已分类）

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

LeetCode 每日一题题解
教你一步步思考 DP：从记忆化搜索到递推到空间优化（Python/Java/C++/Go）endlesscheng
2025年12月31日 12:12

教你一步步思考 DP：从记忆化搜索到递推到空间优化（Python/Java/C++/Go）

LeetCode 每日一题题解

作者 endlesscheng

2025年12月31日 12:12

一、寻找子问题

为方便描述，下文把 $\textit{nums}_1$ 和 $\textit{nums}_2$ 简称为 $a$ 和 $b$。

在示例 1 中，我们要解决的问题（原问题）是：

从 $a=[2,1,-2,5]$ 和 $b=[3,0,-6]$ 中选两个长度相等的非空子序列 $c$ 和 $d$，计算 $c$ 和 $d$ 的点积的最大值。

⚠注意：选出的子序列必须是非空的。

考虑从右往左选数字，用「选或不选」分类讨论：

选 $a[3]$ 和 $b[2]$，需要解决的子问题为：从 $a=[2,1,-2]$ 和 $b=[3,0]$ 中选两个长度相等的子序列，计算两个子序列点积的最大值。由于我们选了元素，所以子序列可以为空。但这样思考的话，子问题就和原问题不相似了。为了保证子问题和原问题相似，我们可以再细分为两种情况：
- 选 $a[3]$ 和 $b[2]$，且前面不再选数字。这意味着点积就是 $a[3]\cdot b[2]$。
- 选 $a[3]$ 和 $b[2]$，且前面还要选数字。需要解决的子问题为：从 $a=[2,1,-2]$ 和 $b=[3,0]$ 中选两个长度相等的非空子序列，计算两个子序列点积的最大值。
不选 $a[3]$，需要解决的子问题为：从 $a=[2,1,-2]$ 和 $b=[3,0,-6]$ 中选两个长度相等的非空子序列，计算两个子序列点积的最大值。
不选 $b[2]$，需要解决的子问题为：从 $a=[2,1,-2,5]$ 和 $b=[3,0]$ 中选两个长度相等的非空子序列，计算两个子序列点积的最大值。

由于选或不选都会把原问题变成一个和原问题相似的、规模更小的子问题，所以可以用递归解决。

注 1：从右往左思考，主要是为了方便把递归翻译成递推。从左往右思考也是可以的。

注 2：动态规划有「选或不选」和「枚举选哪个」两种基本思考方式。子序列相邻无关一般是「选或不选」，子序列相邻相关（例如 LIS 问题）一般是「枚举选哪个」。本题用到的是「选或不选」。

二、状态定义与状态转移方程

根据上面的讨论，定义状态为 $\textit{dfs}(i,j)$，表示从 $a$ 的前缀 $[0,i]$ 和 $b$ 的前缀 $[0,j]$ 中选两个长度相等的非空子序列，计算两个子序列点积的最大值。

接下来，思考如何从一个状态转移到另一个状态。

用「选或不选」分类讨论：

选 $a[i]$ 和 $b[j]$，且前面不再选数字。这意味着点积就是 $a[i]\cdot b[j]$。
选 $a[i]$ 和 $b[j]$，且前面还要选数字。需要解决的子问题为：从 $a$ 的前缀 $[0,i-1]$ 和 $b$ 的前缀 $[0,j-1]$ 中选两个长度相等的非空子序列，计算两个子序列点积的最大值，即 $\textit{dfs}(i-1,j-1)$。再加上 $a[i]\cdot b[j]$，就得到了 $\textit{dfs}(i,j)$。
前两种情况可以合并为：$\max(\textit{dfs}(i-1,j-1), 0) + a[i]\cdot b[j]$。
不选 $a[i]$，需要解决的子问题为：从 $a$ 的前缀 $[0,i-1]$ 和 $b$ 的前缀 $[0,j]$ 中选两个长度相等的非空子序列，计算两个子序列点积的最大值，即 $\textit{dfs}(i-1,j)$。
不选 $b[j]$，需要解决的子问题为：从 $a$ 的前缀 $[0,i]$ 和 $b$ 的前缀 $[0,j-1]$ 中选两个长度相等的非空子序列，计算两个子序列点积的最大值，即 $\textit{dfs}(i,j-1)$。

这四种情况取最大值，就得到了 $\textit{dfs}(i,j)$，即

$$
\textit{dfs}(i,j) = \max{\max(\textit{dfs}(i-1,j-1), 0) + a[i]\cdot b[j], \textit{dfs}(i-1,j),\textit{dfs}(i,j-1)}
$$

递归边界：$\textit{dfs}(-1,j)=\textit{dfs}(i,-1)=-\infty$。此时其中一个数组没有元素，无法选出非空子序列，不合法。用 $-\infty$ 表示不合法的状态，从而保证 $\max$ 不会取到不合法的状态。

递归入口：$\textit{dfs}(n-1,m-1)$，这是原问题，也是答案。其中 $n$ 是 $a$ 的长度，$m$ 是 $b$ 的长度。

三、递归搜索 + 保存递归返回值 = 记忆化搜索

考虑到整个递归过程中有大量重复递归调用（递归入参相同）。由于递归函数没有副作用，同样的入参无论计算多少次，算出来的结果都是一样的，因此可以用记忆化搜索来优化：

如果一个状态（递归入参）是第一次遇到，那么可以在返回前，把状态及其结果记到一个 $\textit{memo}$ 数组中。
如果一个状态不是第一次遇到（$\textit{memo}$ 中保存的结果不等于 $\textit{memo}$ 的初始值），那么可以直接返回 $\textit{memo}$ 中保存的结果。

⚠注意：$\textit{memo}$ 数组的初始值一定不能等于要记忆化的值！例如初始值设置为 $0$，并且要记忆化的 $\textit{dfs}(i,j)$ 也等于 $0$，那就没法判断 $0$ 到底表示第一次遇到这个状态，还是表示之前遇到过了，从而导致记忆化失效。一般把初始值设置为 $-1$，但本题子序列点积可能是负数，可以初始化为 $\infty$。

Python 用户可以无视上面这段，直接用 @cache 装饰器。

具体请看视频讲解动态规划入门：从记忆化搜索到递推【基础算法精讲 17】，其中包含把记忆化搜索 1:1 翻译成递推的技巧。

###py

class Solution:
    def maxDotProduct(self, nums1: List[int], nums2: List[int]) -> int:
        # 返回从 nums1[:i+1] 和 nums2[:j+1] 中选两个长度相同的【非空】子序列的最大点积
        @cache  # 缓存装饰器，避免重复计算 dfs（一行代码实现记忆化）
        def dfs(i: int, j: int) -> int:
            if i < 0 or j < 0:
                # 其中一个数组没有元素，无法选出非空子序列
                return -inf  # 下面计算 max 不会取到无解情况

            # 选 nums1[i] 和 nums2[j]
            # 和前面的子序列拼起来，或者不拼（作为子序列的第一个数）
            res1 = max(dfs(i - 1, j - 1), 0) + nums1[i] * nums2[j]

            # 不选 nums1[i]
            res2 = dfs(i - 1, j)

            # 不选 nums2[j]
            res3 = dfs(i, j - 1)

            return max(res1, res2, res3)

        return dfs(len(nums1) - 1, len(nums2) - 1)

###java

class Solution {
    public int maxDotProduct(int[] nums1, int[] nums2) {
        int n = nums1.length;
        int m = nums2.length;

        int[][] memo = new int[n][m];
        for (int[] row : memo) {
            Arrays.fill(row, Integer.MAX_VALUE);
        }

        return dfs(n - 1, m - 1, nums1, nums2, memo);
    }

    // 从 nums1[0,i] 和 nums2[0,j] 中选两个长度相同的【非空】子序列的最大点积
    private int dfs(int i, int j, int[] nums1, int[] nums2, int[][] memo) {
        if (i < 0 || j < 0) {
            // 其中一个数组没有元素，无法选出非空子序列
            return Integer.MIN_VALUE; // 下面计算 max 不会取到无解情况
        }

        if (memo[i][j] != Integer.MAX_VALUE) { // 之前计算过
            return memo[i][j];
        }

        // 选 nums1[i] 和 nums2[j]
        // 和前面的子序列拼起来，或者不拼（作为子序列的第一个数）
        int res1 = Math.max(dfs(i - 1, j - 1, nums1, nums2, memo), 0) + nums1[i] * nums2[j];

        // 不选 nums1[i]
        int res2 = dfs(i - 1, j, nums1, nums2, memo);

        // 不选 nums2[j]
        int res3 = dfs(i, j - 1, nums1, nums2, memo);

        memo[i][j] = Math.max(res1, Math.max(res2, res3)); // 记忆化
        return memo[i][j];
    }
}

###cpp

class Solution {
public:
    int maxDotProduct(vector<int>& nums1, vector<int>& nums2) {
        int n = nums1.size();
        int m = nums2.size();
        vector memo(n, vector<int>(m, INT_MAX));

        // 从 nums1[0,i] 和 nums2[0,j] 中选两个长度相同的【非空】子序列的最大点积
        auto dfs = [&](this auto&& dfs, int i, int j) -> int {
            if (i < 0 || j < 0) {
                // 其中一个数组没有元素，无法选出非空子序列
                return INT_MIN; // 下面计算 max 不会取到无解情况
            }

            int& res = memo[i][j]; // 注意这里是引用
            if (res != INT_MAX) { // 之前计算过
                return res;
            }

            // 选 nums1[i] 和 nums2[j]
            // 和前面的子序列拼起来，或者不拼（作为子序列的第一个数）
            res = max(dfs(i - 1, j - 1), 0) + nums1[i] * nums2[j];

            // 不选 nums1[i]
            res = max(res, dfs(i - 1, j));

            // 不选 nums2[j]
            res = max(res, dfs(i, j - 1));

            return res;
        };

        return dfs(n - 1, m - 1);
    }
};

###go

func maxDotProduct(nums1, nums2 []int) int {
n := len(nums1)
m := len(nums2)
memo := make([][]int, n)
for i := range memo {
memo[i] = make([]int, m)
for j := range memo[i] {
memo[i][j] = math.MaxInt
}
}

// 从 nums1[:i+1] 和 nums2[:j+1] 中选两个长度相同的【非空】子序列的最大点积
var dfs func(int, int) int
dfs = func(i, j int) int {
if i < 0 || j < 0 {
// 其中一个数组没有元素，无法选出非空子序列
return math.MinInt // 下面计算 max 不会取到无解情况
}

p := &memo[i][j]
if *p != math.MaxInt { // 之前计算过
return *p
}

// 选 nums1[i] 和 nums2[j]
// 和前面的子序列拼起来，或者不拼（作为子序列的第一个数）
res1 := max(dfs(i-1, j-1), 0) + nums1[i]*nums2[j]

// 不选 nums1[i]
res2 := dfs(i-1, j)

// 不选 nums2[j]
res3 := dfs(i, j-1)

*p = max(res1, res2, res3) // 记忆化
return *p
}

return dfs(n-1, m-1)
}

复杂度分析

时间复杂度：$\mathcal{O}(nm)$，其中 $n$ 是 $\textit{nums}_1$ 的长度，$m$ 是 $\textit{nums}_2$ 的长度。由于每个状态只会计算一次，动态规划的时间复杂度 $=$ 状态个数 $\times$ 单个状态的计算时间。本题状态个数等于 $\mathcal{O}(nm)$，单个状态的计算时间为 $\mathcal{O}(1)$，所以总的时间复杂度为 $\mathcal{O}(nm)$。
空间复杂度：$\mathcal{O}(nm)$。保存多少状态，就需要多少空间。

四、1:1 翻译成递推

我们可以去掉递归中的「递」，只保留「归」的部分，即自底向上计算。

具体来说，$f[i+1][j+1]$ 的定义和 $\textit{dfs}(i,j)$ 的定义是一样的，都表示从 $a$ 的前缀 $[0,i]$ 和 $b$ 的前缀 $[0,j]$ 中选两个长度相等的非空子序列，计算两个子序列点积的最大值。这里 $+1$ 是为了把 $\textit{dfs}(-1,j)$ 和 $\textit{dfs}(i,-1)$ 也翻译过来，这样我们可以把 $f[0][j]$ 和 $f[i][0]$ 作为初始值。

相应的递推式（状态转移方程）也和 $\textit{dfs}$ 一样：

$$
f[i+1][j+1] = \max{\max(f[i][j], 0) + a[i]\cdot b[j], f[i][j+1],f[i+1][j]}
$$

初始值：$f$ 第一行和第一列初始化成 $-\infty$，翻译自递归边界 $\textit{dfs}(-1,j)=\textit{dfs}(i,-1)=-\infty$。

答案为 $f[n][m]$，翻译自递归入口 $\textit{dfs}(n-1,m-1)$。

###py

class Solution:
    def maxDotProduct(self, nums1: List[int], nums2: List[int]) -> int:
        n, m = len(nums1), len(nums2)
        f = [[-inf] * (m + 1) for _ in range(n + 1)]
        for i, x in enumerate(nums1):
            for j, y in enumerate(nums2):
                f[i + 1][j + 1] = max(max(f[i][j], 0) + x * y, f[i][j + 1], f[i + 1][j])
        return f[n][m]

###java

class Solution {
    public int maxDotProduct(int[] nums1, int[] nums2) {
        int n = nums1.length;
        int m = nums2.length;

        int[][] f = new int[n + 1][m + 1];
        for (int[] row : f) {
            Arrays.fill(row, Integer.MIN_VALUE);
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                f[i + 1][j + 1] = Math.max(
                    Math.max(f[i][j], 0) + nums1[i] * nums2[j],
                    Math.max(f[i][j + 1], f[i + 1][j])
                );
            }
        }
        return f[n][m];
    }
}

###cpp

class Solution {
public:
    int maxDotProduct(vector<int>& nums1, vector<int>& nums2) {
        int n = nums1.size();
        int m = nums2.size();
        vector f(n + 1, vector<int>(m + 1, INT_MIN));
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                int res1 = max(f[i][j], 0) + nums1[i] * nums2[j];
                // 注：max({...}) 比 max(..., max(...)) 慢
                f[i + 1][j + 1] = max(res1, max(f[i][j + 1], f[i + 1][j]));
            }
        }
        return f[n][m];
    }
};

###go

func maxDotProduct(nums1, nums2 []int) int {
n := len(nums1)
m := len(nums2)
f := make([][]int, n+1)
for i := range f {
f[i] = make([]int, m+1)
for j := range f[i] {
f[i][j] = math.MinInt
}
}

for i, x := range nums1 {
for j, y := range nums2 {
f[i+1][j+1] = max(max(f[i][j], 0)+x*y, f[i][j+1], f[i+1][j])
}
}
return f[n][m]
}

复杂度分析

时间复杂度：$\mathcal{O}(nm)$，其中 $n$ 是 $\textit{nums}_1$ 的长度，$m$ 是 $\textit{nums}_2$ 的长度。
空间复杂度：$\mathcal{O}(nm)$。

五、空间优化

类似 1143. 最长公共子序列的空间优化方法，只用一个长为 $m+1$ 的一维数组，原理讲解请看最长公共子序列编辑距离【基础算法精讲 19】。

###py

# 更快的写法见【Python3 手写 max】
class Solution:
    def maxDotProduct(self, nums1: List[int], nums2: List[int]) -> int:
        m = len(nums2)
        f = [-inf] * (m + 1)
        for x in nums1:
            pre = f[0]
            for j, y in enumerate(nums2):
                tmp = f[j + 1]
                f[j + 1] = max(max(pre, 0) + x * y, f[j + 1], f[j])
                pre = tmp
        return f[m]

###py

class Solution:
    def maxDotProduct(self, nums1: List[int], nums2: List[int]) -> int:
        m = len(nums2)
        f = [-inf] * (m + 1)
        for x in nums1:
            pre = f[0]
            for j, y in enumerate(nums2):
                tmp = f[j + 1]
                res = x * y
                if pre > 0: res += pre
                if f[j] > res: res = f[j]
                if f[j + 1] > res: res = f[j + 1]
                f[j + 1] = res
                pre = tmp
        return f[m]

###java

class Solution {
    public int maxDotProduct(int[] nums1, int[] nums2) {
        int m = nums2.length;
        int[] f = new int[m + 1];
        Arrays.fill(f, Integer.MIN_VALUE);
        for (int x : nums1) {
            int pre = f[0];
            for (int j = 0; j < m; j++) {
                int tmp = f[j + 1];
                f[j + 1] = Math.max(Math.max(pre, 0) + x * nums2[j], Math.max(f[j + 1], f[j]));
                pre = tmp;
            }
        }
        return f[m];
    }
}

###cpp

class Solution {
public:
    int maxDotProduct(vector<int>& nums1, vector<int>& nums2) {
        int m = nums2.size();
        vector<int> f(m + 1, INT_MIN);
        for (int x : nums1) {
            int pre = f[0];
            for (int j = 0; j < m; j++) {
                int tmp = f[j + 1];
                f[j + 1] = max(max(pre, 0) + x * nums2[j], max(f[j + 1], f[j]));
                pre = tmp;
            }
        }
        return f[m];
    }
};

###go

func maxDotProduct(nums1, nums2 []int) int {
m := len(nums2)
f := make([]int, m+1)
for i := range f {
f[i] = math.MinInt
}
for _, x := range nums1 {
pre := f[0]
for j, y := range nums2 {
tmp := f[j+1]
f[j+1] = max(max(pre, 0)+x*y, f[j+1], f[j])
pre = tmp
}
}
return f[m]
}

复杂度分析

时间复杂度：$\mathcal{O}(nm)$，其中 $n$ 是 $\textit{nums}_1$ 的长度，$m$ 是 $\textit{nums}_2$ 的长度。
空间复杂度：$\mathcal{O}(m)$。

专题训练

见下面动态规划题单的「§4.1 最长公共子序列（LCS）」。

分类题单

如何科学刷题？

我的题解精选（已分类）

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

LeetCode 每日一题题解
两次 DFS，或者提前保存子树和（Python/Java/C++/C/Go/JS/Rust）endlesscheng
2026年1月1日 12:07

两次 DFS，或者提前保存子树和（Python/Java/C++/C/Go/JS/Rust）

LeetCode 每日一题题解

作者 endlesscheng

2026年1月1日 12:07

第一次 DFS：计算整棵树的点权和 $\textit{total}$。

第二次 DFS：计算子树点权和 $s$，那么删除当前节点到其父节点的边后，另一部分的和就是 $\textit{total} - s$，二者乘积为

$$
s\cdot(\textit{total} - s)
$$

用其更新答案的最大值。

由于本题保证点权是非负，我们无需判断当前节点是根节点的特殊情况（无父节点），此时上式为 $0$，不影响答案。

如果有负数点权，就需要跳过当前节点是根节点的情况。

也可以在第一次 DFS 时，把子树和保存到一个列表中，第二次只需遍历这个列表，见 Python3 的第一份代码。

###py

class Solution:
    def maxProduct(self, root: Optional[TreeNode]) -> int:
        def dfs(node: Optional[TreeNode]) -> int:
            if node is None:
                return 0
            s = node.val + dfs(node.left) + dfs(node.right)
            sub_sum.append(s)
            return s

        sub_sum = []
        total = dfs(root)

        ans = max(s * (total - s) for s in sub_sum)
        return ans % 1_000_000_007

###py

class Solution:
    def maxProduct(self, root: Optional[TreeNode]) -> int:
        def dfs1(node: Optional[TreeNode]) -> int:
            if node is None:
                return 0
            return node.val + dfs1(node.left) + dfs1(node.right)

        def dfs2(node: Optional[TreeNode]) -> int:
            if node is None:
                return 0
            s = node.val + dfs2(node.left) + dfs2(node.right)
            nonlocal ans
            ans = max(ans, s * (total - s))
            return s

        total = dfs1(root)

        ans = 0
        dfs2(root)

        return ans % 1_000_000_007

###java

class Solution {
    private static final int MOD = 1_000_000_007;
    private long ans = 0;

    public int maxProduct(TreeNode root) {
        int total = dfs1(root);
        dfs2(root, total);
        return (int) (ans % MOD);
    }

    private int dfs1(TreeNode node) {
        if (node == null) {
            return 0;
        }
        return node.val + dfs1(node.left) + dfs1(node.right);
    }

    private int dfs2(TreeNode node, int total) {
        if (node == null) {
            return 0;
        }
        int s = node.val + dfs2(node.left, total) + dfs2(node.right, total);
        ans = Math.max(ans, (long) s * (total - s));
        return s;
    }
}

###cpp

class Solution {
public:
    int maxProduct(TreeNode* root) {
        auto dfs1 = [&](this auto&& dfs1, TreeNode* node) -> int {
            if (node == nullptr) {
                return 0;
            }
            return node->val + dfs1(node->left) + dfs1(node->right);
        };
        long long total = dfs1(root);

        long long ans = 0;
        auto dfs2 = [&](this auto&& dfs2, TreeNode* node) -> int {
            if (node == nullptr) {
                return 0;
            }
            int s = node->val + dfs2(node->left) + dfs2(node->right);
            ans = max(ans, s * (total - s));
            return s;
        };
        dfs2(root);

        return ans % 1'000'000'007;
    }
};

###c

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

int maxProduct(struct TreeNode* root) {
    int dfs1(struct TreeNode* node) {
        if (node == NULL) {
            return 0;
        }
        return node->val + dfs1(node->left) + dfs1(node->right);
    }

    long long total = dfs1(root);
    long long ans = 0;

    int dfs2(struct TreeNode* node) {
        if (node == NULL) {
            return 0;
        }
        int s = node->val + dfs2(node->left) + dfs2(node->right);
        ans = MAX(ans, s * (total - s));
        return s;
    }

    dfs2(root);
    return ans % 1000000007;
}

###go

func maxProduct(root *TreeNode) (ans int) {
var dfs1 func(*TreeNode) int
dfs1 = func(node *TreeNode) int {
if node == nil {
return 0
}
return node.Val + dfs1(node.Left) + dfs1(node.Right)
}
total := dfs1(root)

var dfs2 func(*TreeNode) int
dfs2 = func(node *TreeNode) int {
if node == nil {
return 0
}
s := node.Val + dfs2(node.Left) + dfs2(node.Right)
ans = max(ans, s*(total-s))
return s
}
dfs2(root)

return ans % 1_000_000_007
}

###js

var maxProduct = function(root) {
    function dfs1(node) {
        if (node === null) {
            return 0;
        }
        return node.val + dfs1(node.left) + dfs1(node.right);
    }

    function dfs2(node) {
        if (node === null) {
            return 0;
        }
        const s = node.val + dfs2(node.left) + dfs2(node.right);
        ans = Math.max(ans, s * (total - s));
        return s;
    }

    const total = dfs1(root);

    let ans = 0;
    dfs2(root);

    return ans % 1_000_000_007;
};

###rust

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

impl Solution {
    pub fn max_product(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
        fn dfs1(node: &Option<Rc<RefCell<TreeNode>>>) -> i32 {
            if let Some(n) = node {
                let n = n.borrow();
                n.val + dfs1(&n.left) + dfs1(&n.right)
            } else {
                0
            }
        }

        fn dfs2(node: &Option<Rc<RefCell<TreeNode>>>, total: i32, ans: &mut i64) -> i32 {
            if let Some(n) = node {
                let n = n.borrow();
                let s = n.val + dfs2(&n.left, total, ans) + dfs2(&n.right, total, ans);
                *ans = (*ans).max(s as i64 * (total - s) as i64);
                s
            } else {
                0
            }
        }

        let total = dfs1(&root);

        let mut ans = 0;
        dfs2(&root, total, &mut ans);

        (ans % 1_000_000_007) as _
    }
}

复杂度分析

时间复杂度：$\mathcal{O}(n)$，其中 $n$ 是二叉树的节点个数。
空间复杂度：$\mathcal{O}(h)$，其中 $h$ 是二叉树的高度。递归需要消耗 $\mathcal{O}(h)$ 的栈空间。

专题训练

见下面树题单的「§2.3 自底向上 DFS」。

分类题单

如何科学刷题？

我的题解精选（已分类）

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

LeetCode 每日一题题解
两种方法：BFS / DFS（Python/Java/C++/Go）endlesscheng
2026年1月3日 09:10

两种方法：BFS / DFS（Python/Java/C++/Go）

LeetCode 每日一题题解

作者 endlesscheng

2026年1月3日 09:10

方法一：BFS

本题需要计算每一层的节点值之和，适合用 BFS。原理讲解【基础算法精讲 13】。

维护两个信息：最大层和 $\textit{maxSum}$，以及对应的层号 $\textit{ans}$。如果当前层的和大于 $\textit{maxSum}$，那么更新 $\textit{maxSum}$ 和 $\textit{ans}$。

class Solution:
    def maxLevelSum(self, root: Optional[TreeNode]) -> int:
        max_sum = -inf
        ans = 0

        q = [root]
        level = 1
        while q:
            tmp = q
            q = []
            s = 0
            for node in tmp:
                s += node.val
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)

            if s > max_sum:
                max_sum = s
                ans = level

            level += 1

        return ans

class Solution {
    public int maxLevelSum(TreeNode root) {
        int max_sum = Integer.MIN_VALUE;
        int ans = 0;

        List<TreeNode> q = new ArrayList<>();
        q.add(root);

        for (int level = 1; !q.isEmpty(); level++) {
            List<TreeNode> tmp = q;
            q = new ArrayList<>();
            int s = 0;

            for (TreeNode node : tmp) {
                s += node.val;
                if (node.left != null) {
                    q.add(node.left);
                }
                if (node.right != null) {
                    q.add(node.right);
                }
            }

            if (s > max_sum) {
                max_sum = s;
                ans = level;
            }
        }

        return ans;
    }
}

class Solution {
public:
    int maxLevelSum(TreeNode* root) {
        int max_sum = INT_MIN;
        int ans = 0;

        vector<TreeNode*> q = {root};
        for (int level = 1; !q.empty(); level++) {
            auto tmp = q;
            q.clear();
            int s = 0;

            for (auto node : tmp) {
                s += node->val;
                if (node->left) {
                    q.push_back(node->left);
                }
                if (node->right) {
                    q.push_back(node->right);
                }
            }

            if (s > max_sum) {
                max_sum = s;
                ans = level;
            }
        }

        return ans;
    }
};

func maxLevelSum(root *TreeNode) (ans int) {
maxSum := math.MinInt
q := []*TreeNode{root}

for level := 1; q != nil; level++ {
tmp := q
q = nil
s := 0

for _, node := range tmp {
s += node.Val
if node.Left != nil {
q = append(q, node.Left)
}
if node.Right != nil {
q = append(q, node.Right)
}
}

if s > maxSum {
maxSum = s
ans = level
}
}

return ans
}

复杂度分析

时间复杂度：$\mathcal{O}(n)$，其中 $n$ 是二叉树的节点个数。
空间复杂度：$\mathcal{O}(n)$。

方法二：DFS

创建一个列表 $\textit{rowSum}$，维护每一层的元素和。

在 DFS 的同时，把节点值加到这一层的元素和中。

最后求出最大层和对应的层号。

class Solution:
    def maxLevelSum(self, root: Optional[TreeNode]) -> int:
        def dfs(node: Optional[TreeNode], level: int) -> None:
            if node is None:
                return

            if len(row_sum) == level:  # 首次访问 level 层
                row_sum.append(node.val)  # 节点值作为层和的初始值
            else:
                row_sum[level] += node.val

            dfs(node.left, level + 1)
            dfs(node.right, level + 1)

        row_sum = []
        dfs(root, 0)
        return row_sum.index(max(row_sum)) + 1  # 层号从 1 开始

class Solution {

    private void dfs(TreeNode node, int level, List<Integer> rowSum) {
        if (node == null) {
            return;
        }

        if (rowSum.size() == level) { // 首次访问 level 层
            rowSum.add(node.val); // 节点值作为层和的初始值
        } else {
            rowSum.set(level, rowSum.get(level) + node.val);
        }

        dfs(node.left, level + 1, rowSum);
        dfs(node.right, level + 1, rowSum);
    }

    public int maxLevelSum(TreeNode root) {
        List<Integer> rowSum = new ArrayList<>();
        dfs(root, 0, rowSum);

        int ans = 0;
        for (int i = 1; i < rowSum.size(); i++) {
            if (rowSum.get(i) > rowSum.get(ans)) {
                ans = i;
            }
        }
        return ans + 1; // 层号从 1 开始
    }
}

class Solution {
public:
    int maxLevelSum(TreeNode* root) {
        vector<int> row_sum;

        auto dfs = [&](this auto&& dfs, TreeNode* node, int level) -> void {
            if (node == nullptr) {
                return;
            }

            if (row_sum.size() == level) { // 首次访问 level 层
                row_sum.push_back(node->val); // 节点值作为层和的初始值
            } else {
                row_sum[level] += node->val;
            }

            dfs(node->left, level + 1);
            dfs(node->right, level + 1);
        };

        dfs(root, 0);
        return ranges::max_element(row_sum) - row_sum.begin() + 1; // 层号从 1 开始
    }
};

func maxLevelSum(root *TreeNode) (ans int) {
rowSum := []int{}

var dfs func(*TreeNode, int)
dfs = func(node *TreeNode, level int) {
if node == nil {
return
}

if len(rowSum) == level { // 首次访问 level 层
rowSum = append(rowSum, node.Val) // 节点值作为层和的初始值
} else {
rowSum[level] += node.Val
}

dfs(node.Left, level+1)
dfs(node.Right, level+1)
}

dfs(root, 0)

for i, s := range rowSum {
if s > rowSum[ans] {
ans = i
}
}
return ans + 1 // 层号从 1 开始
}

复杂度分析

时间复杂度：$\mathcal{O}(n)$，其中 $n$ 是二叉树的节点个数。
空间复杂度：$\mathcal{O}(n)$。

专题训练

见下面树题单的「§2.13 二叉树 BFS」。

分类题单

如何科学刷题？

我的题解精选（已分类）

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

LeetCode 每日一题题解
脑筋急转弯 + 分类讨论（Python/Java/C++/C/Go/JS/Rust）endlesscheng
2021年8月22日 00:13

脑筋急转弯 + 分类讨论（Python/Java/C++/C/Go/JS/Rust）

LeetCode 每日一题题解

作者 endlesscheng

2021年8月22日 00:13

虽然题目规定我们只能操作相邻的元素，但我们可以通过多次操作，把任意两个元素都乘以 $-1$。

每次操作，恰好改变两个数的正负号。

多次操作，恰好改变偶数个数的正负号。

分类讨论：

如果 $\textit{matrix}$ 有偶数个负数，那么可以把所有数都变成非负数。
如果 $\textit{matrix}$ 有奇数个负数且没有 $0$，那么最终必然剩下奇数个负数。剩下一个负数是最优的。贪心地，选择 $\textit{matrix}$ 中的绝对值最小的数，给它加上负号。
如果 $\textit{matrix}$ 有奇数个负数且有 $0$，那么可以把一个 $0$ 和最终剩下的一个负数操作一次，从而把所有数都变成非负数。

代码实现时，无需特判是否有 $0$。如果有 $0$，那么代码中的 $\textit{mn}=0$，对 $\textit{total}$ 无影响。

class Solution:
    def maxMatrixSum(self, matrix: List[List[int]]) -> int:
        total = neg_cnt = 0
        mn = inf
        for row in matrix:
            for x in row:
                if x < 0:
                    neg_cnt += 1
                    x = -x  # 先把负数都变成正数
                mn = min(mn, x)
                total += x

        if neg_cnt % 2:
            total -= mn * 2  # 给绝对值最小的数添加负号
        return total

class Solution {
    public long maxMatrixSum(int[][] matrix) {
        long total = 0;
        int negCnt = 0;
        int mn = Integer.MAX_VALUE;
        for (int[] row : matrix) {
            for (int x : row) {
                if (x < 0) {
                    negCnt++;
                    x = -x; // 先把负数都变成正数
                }
                mn = Math.min(mn, x);
                total += x;
            }
        }

        if (negCnt % 2 > 0) {
            total -= mn * 2; // 给绝对值最小的数添加负号
        }
        return total;
    }
}

class Solution {
public:
    long long maxMatrixSum(vector<vector<int>>& matrix) {
        long long total = 0;
        int neg_cnt = 0;
        int mn = INT_MAX;
        for (auto& row : matrix) {
            for (int x : row) {
                if (x < 0) {
                    neg_cnt++;
                    x = -x; // 先把负数都变成正数
                }
                mn = min(mn, x);
                total += x;
            }
        }

        if (neg_cnt % 2) {
            total -= mn * 2; // 给绝对值最小的数添加负号
        }
        return total;
    }
};

#define MIN(a, b) ((b) < (a) ? (b) : (a))

long long maxMatrixSum(int** matrix, int matrixSize, int* matrixColSize) {
    long long total = 0;
    int neg_cnt = 0;
    int mn = INT_MAX;
    for (int i = 0; i < matrixSize; i++) {
        for (int j = 0; j < matrixColSize[i]; j++) {
            int x = matrix[i][j];
            if (x < 0) {
                neg_cnt++;
                x = -x; // 先把负数都变成正数
            }
            mn = MIN(mn, x);
            total += x;
        }
    }

    if (neg_cnt % 2) {
        total -= mn * 2; // 给绝对值最小的数添加负号
    }
    return total;
}

func maxMatrixSum(matrix [][]int) int64 {
total, negCnt, mn := 0, 0, math.MaxInt
for _, row := range matrix {
for _, x := range row {
if x < 0 {
negCnt++
x = -x // 先把负数都变成正数
}
mn = min(mn, x)
total += x
}
}

if negCnt%2 > 0 {
total -= mn * 2 // 给绝对值最小的数添加负号
}
return int64(total)
}

var maxMatrixSum = function(matrix) {
    let total = 0;
    let negCnt = 0;
    let mn = Infinity;
    for (const row of matrix) {
        for (let x of row) {
            if (x < 0) {
                negCnt++;
                x = -x; // 先把负数都变成正数
            }
            mn = Math.min(mn, x);
            total += x;
        }
    }

    if (negCnt % 2) {
        total -= mn * 2; // 给绝对值最小的数添加负号
    }
    return total;
};

impl Solution {
    pub fn max_matrix_sum(matrix: Vec<Vec<i32>>) -> i64 {
        let mut total = 0;
        let mut neg_cnt = 0;
        let mut mn = i32::MAX;
        for row in matrix {
            for mut x in row {
                if x < 0 {
                    neg_cnt += 1;
                    x = -x; // 先把负数都变成正数
                }
                mn = mn.min(x);
                total += x as i64;
            }
        }

        if neg_cnt % 2 > 0 {
            total -= (mn * 2) as i64; // 给绝对值最小的数添加负号
        }
        total
    }
}

复杂度分析

时间复杂度：$\mathcal{O}(mn)$，其中 $m$ 和 $n$ 分别是 $\textit{matrix}$ 的行数和列数。
空间复杂度：$\mathcal{O}(1)$。

专题训练

见下面贪心与思维题单的「§5.2 脑筋急转弯」。

分类题单

如何科学刷题？

我的题解精选（已分类）

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

LeetCode 每日一题题解
【模板】预处理每个数的因子个数、因子和（Python/Java/C++/Go）endlesscheng
2025年12月28日 20:13

【模板】预处理每个数的因子个数、因子和（Python/Java/C++/Go）

LeetCode 每日一题题解

作者 endlesscheng

2025年12月28日 20:13

对于一个数，它有哪些因子？这不能一眼看出来。

但反过来，对于一个数 $i$，$i$ 的倍数都有因子 $i$。

枚举 $i=1,2,3,\ldots,10^5$，以及 $i$ 的倍数 $j$，把 $j$ 的因子个数加一，因子和加上 $i$。

对于 $\textit{nums}$ 中的因子个数为 $4$ 的元素，累加这些元素的因子和，即为答案。

###py

MX = 100_001
divisor_num = [0] * MX
divisor_sum = [0] * MX
for i in range(1, MX):
    for j in range(i, MX, i):  # 枚举 i 的倍数 j
        divisor_num[j] += 1  # i 是 j 的因子
        divisor_sum[j] += i

class Solution:
    def sumFourDivisors(self, nums: List[int]) -> int:
        ans = 0
        for x in nums:
            if divisor_num[x] == 4:
                ans += divisor_sum[x]
        return ans

###java

class Solution {
    private static final int MX = 100_001;
    private static final int[] divisorNum = new int[MX];
    private static final int[] divisorSum = new int[MX];
    private static boolean initialized = false;

    // 这样写比 static block 快
    public Solution() {
        if (initialized) {
            return;
        }
        initialized = true;

        for (int i = 1; i < MX; i++) {
            for (int j = i; j < MX; j += i) { // 枚举 i 的倍数 j
                divisorNum[j]++; // i 是 j 的因子
                divisorSum[j] += i;
            }
        }
    }

    public int sumFourDivisors(int[] nums) {
        int ans = 0;
        for (int x : nums) {
            if (divisorNum[x] == 4) {
                ans += divisorSum[x];
            }
        }
        return ans;
    }
}

###cpp

constexpr int MX = 100'001;
int divisor_num[MX];
int divisor_sum[MX];

int init = [] {
    for (int i = 1; i < MX; i++) {
        for (int j = i; j < MX; j += i) { // 枚举 i 的倍数 j
            divisor_num[j]++; // i 是 j 的因子
            divisor_sum[j] += i;
        }
    }
    return 0;
}();

class Solution {
public:
    int sumFourDivisors(vector<int>& nums) {
        int ans = 0;
        for (int x : nums) {
            if (divisor_num[x] == 4) {
                ans += divisor_sum[x];
            }
        }
        return ans;
    }
};

###go

const mx = 100_001

var divisorNum, divisorSum [mx]int

func init() {
for i := 1; i < mx; i++ {
for j := i; j < mx; j += i { // 枚举 i 的倍数 j
divisorNum[j]++ // i 是 j 的因子
divisorSum[j] += i
}
}
}

func sumFourDivisors(nums []int) (ans int) {
for _, x := range nums {
if divisorNum[x] == 4 {
ans += divisorSum[x]
}
}
return
}

复杂度分析

设 $U=\max(\textit{nums})$。预处理的时间为 $\mathcal{O}(U\log U)$（调和级数和），空间为 $\mathcal{O}(U)$，不计入。

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

专题训练

见下面数学题单的「§1.5 因子」。

分类题单

如何科学刷题？

我的题解精选（已分类）

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

LeetCode 每日一题题解
三种方法：记忆化搜索/递推/矩阵快速幂（Python/Java/C++/Go）endlesscheng
2025年12月30日 16:17

三种方法：记忆化搜索/递推/矩阵快速幂（Python/Java/C++/Go）

LeetCode 每日一题题解

作者 endlesscheng

2025年12月30日 16:17

方法一：记忆化搜索（轮廓线 DP）

考虑暴力搜索，枚举每个格子涂哪种颜色。

从下往上涂色（这样可以在多组测试数据间复用记忆化的结果），我们需要知道：

当前在给哪个格子涂色？用 $(i,j)$ 表示，即 $i$ 行 $j$ 列。
$i+1$ 行具体怎么涂色？用 $\textit{preRow}$ 表示。$(i,j)$ 的颜色不能等于 $(i+1,j)$ 的颜色。
$i$ 行具体怎么涂色？用 $\textit{curRow}$ 表示。$(i,j)$ 的颜色不能等于 $(i,j-1)$ 的颜色。

三种颜色分别用 $0,1,2$ 表示，存储一个格子的颜色信息需要 $2$ 个比特位，一行的颜色就需要 $2\cdot 3 = 6$ 个比特位。

注意取模。为什么可以在中途取模？原理见模运算的世界：当加减乘除遇上取模。

###py

MOD = 1_000_000_007

# (i, j)：当前位置 
# pre_row：上一行（i+1 行）的颜色
# cur_row：当前这一行已填入的颜色
@cache  # 缓存装饰器，避免重复计算 dfs（一行代码实现记忆化）
def dfs(i: int, j: int, pre_row: int, cur_row: int) -> int:
    if i == 0:  # 所有格子都已涂色
        return 1  # 找到一个合法方案

    if j == 3:  # i 行已涂色
        # 开始对 i-1 行涂色，cur_row 变成 pre_row
        return dfs(i - 1, 0, cur_row, 0)

    res = 0
    for color in range(3):  # 枚举 (i, j) 的颜色 color
        # 不能和下面相邻格子 (i+1, j) 颜色相同
        # 不能和左侧相邻格子 (i, j-1) 颜色相同
        if pre_row and color == pre_row >> (j * 2) & 3 or \
                 j and color == cur_row >> ((j - 1) * 2) & 3:
            continue
        res += dfs(i, j + 1, pre_row, cur_row | (color << (j * 2)))
    return res % MOD

class Solution:
    def numOfWays(self, n: int) -> int:
        return dfs(n, 0, 0, 0)  # 从最后一行开始涂色

###java

class Solution {
private static final int MOD = 1_000_000_007;

// 全局 memo，记忆化的内容可以在不同测试数据间共享
private static Map<Integer, Integer> memo = new HashMap<>();

public int numOfWays(int n) {
return dfs(n, 0, 0, 0);
}

    // (i, j)：当前位置 
    // preRow：上一行（i+1 行）的颜色
    // curRow：当前这一行已填入的颜色
private int dfs(int i, int j, int preRow, int curRow) {
if (i == 0) { // 所有格子都已涂色
return 1; // 找到一个合法方案
}

if (j == 3) { // i 行已涂色
    // 开始对 i-1 行涂色，curRow 变成 preRow
return dfs(i - 1, 0, curRow, 0);
}

        // 参数压缩到一个 int 中
int key = (i << 14) | (j << 12) | (preRow << 6) | curRow;
if (memo.containsKey(key)) { // 之前计算过
return memo.get(key);
}

int res = 0;
for (int color = 0; color < 3; color++) { // 枚举 (i, j) 的颜色 color
if (preRow > 0 && color == (preRow >> (j * 2) & 3) || // 不能和下面相邻格子 (i+1, j) 颜色相同
j > 0 && color == (curRow >> ((j - 1) * 2) & 3)) { // 不能和左侧相邻格子 (i, j-1) 颜色相同
continue;
}
res = (res + dfs(i, j + 1, preRow, curRow | (color << (j * 2)))) % MOD;
}

memo.put(key, res); // 记忆化
return res;
}
}

###cpp

constexpr int MOD = 1'000'000'007;

// 全局 memo，记忆化的内容可以在不同测试数据间共享
unordered_map<int, int> memo;

// (i, j)：当前位置 
// pre_row：上一行（i+1 行）的颜色
// cur_row：当前这一行已填入的颜色
int dfs(int i, int j, int pre_row, int cur_row) {
    if (i == 0) { // 所有格子都已涂色
        return 1; // 找到一个合法方案
    }

    if (j == 3) { // i 行已涂色
        // 开始对 i-1 行涂色，cur_row 变成 pre_row
        return dfs(i - 1, 0, cur_row, 0);
    }

    // 参数压缩到一个 int 中
    int key = (i << 14) | (j << 12) | (pre_row << 6) | cur_row;
    if (memo.contains(key)) { // 之前计算过
        return memo[key];
    }

    int res = 0;
    for (int color = 0; color < 3; color++) { // 枚举 (i, j) 的颜色 color
        if (pre_row > 0 && color == (pre_row >> (j * 2) & 3) || // 不能和下面相邻格子 (i+1, j) 颜色相同
            j > 0 && color == (cur_row >> ((j - 1) * 2) & 3)) { // 不能和左侧相邻格子 (i, j-1) 颜色相同
            continue;
        }
        res = (res + dfs(i, j + 1, pre_row, cur_row | (color << (j * 2)))) % MOD;
    }

    memo[key] = res; // 记忆化
    return res;
}

class Solution {
public:
int numOfWays(int n) {
return dfs(n, 0, 0, 0);
}
};

###go

const mod = 1_000_000_007

type tuple struct{ i, j, preRow, curRow int }

// 全局 memo，记忆化的内容可以在不同测试数据间共享
var memo = map[tuple]int{}

// (i, j)：当前位置 
// preRow：上一行（i+1 行）的颜色
// curRow：当前这一行已填入的颜色
func dfs(i, j, preRow, curRow int) int {
if i == 0 { // 所有格子都已涂色
return 1 // 找到一个合法方案
}

if j == 3 { // i 行已涂色
// 开始对 i-1 行涂色，curRow 变成 preRow
return dfs(i-1, 0, curRow, 0)
}

t := tuple{i, j, preRow, curRow}
if res, ok := memo[t]; ok { // 之前计算过
return res
}

res := 0
for color := range 3 { // 枚举 (i, j) 的颜色 color
if preRow > 0 && color == preRow>>(j*2)&3 || // 不能和下面相邻格子 (i+1, j) 颜色相同
j > 0 && color == curRow>>((j-1)*2)&3 { // 不能和左侧相邻格子 (i, j-1) 颜色相同
continue
}
res = (res + dfs(i, j+1, preRow, curRow|color<<(j*2))) % mod
}

memo[t] = res // 记忆化
return res
}

func numOfWays(n int) int {
return dfs(n, 0, 0, 0)
}

复杂度分析

时间复杂度：$\mathcal{O}(nmk^{2m+1})$，其中 $m=3$ 是列数，$k=3$ 是颜色数。由于存在大量不合法的状态，复杂度不会跑满。
空间复杂度：$\mathcal{O}(nmk^{2m})$。

方法二：递推

回顾方法一，总体上看，DP 过程是一个线性递推（从 $(n-1)\times 3$ 网格图最后一行的所有涂色方案线性转移到 $n\times 3$ 网格图的最后一行），所以必然有线性递推式。

定义 $f[n]$ 表示给 $n\times 3$ 网格图涂色的方案数。

根据 Berlekamp-Massey 算法，用方法一求出 $f$ 的连续若干项（具体多少在文章中有解释，本题只需 $4$ 项），就可以用 Berlekamp-Massey 算法直接得到线性递推式

$$
f[i] = 5\cdot f[i-1]-2\cdot f[i-2] \ \ (i \ge 3)
$$

初始值 $f[1] = 12,\ f[2] = 54$。

也可以倒推出 $f[0]=3$，把 $f[0]$ 和 $f[1]$ 作为初始值。

###py

class Solution:
    def numOfWays(self, n: int) -> int:
        MOD = 1_000_000_007
        f = [0] * (n + 1)
        f[0] = 3
        f[1] = 12
        for i in range(2, n + 1):
            f[i] = (f[i - 1] * 5 - f[i - 2] * 2) % MOD
        return f[n]

###java

class Solution {
    public int numOfWays(int n) {
        final int MOD = 1_000_000_007;
        int[] f = new int[n + 1];
        f[0] = 3;
        f[1] = 12;
        for (int i = 2; i <= n; i++) {
            f[i] = (int) ((f[i - 1] * 5L - f[i - 2] * 2L) % MOD); // 注意这里有减法，结果可能是负数
        }
        return (f[n] + MOD) % MOD; // 保证结果非负
    }
}

###cpp

class Solution {
public:
    int numOfWays(int n) {
        constexpr int MOD = 1'000'000'007;
        vector<int> f(n + 1);
        f[0] = 3;
        f[1] = 12;
        for (int i = 2; i <= n; i++) {
            f[i] = (f[i - 1] * 5LL - f[i - 2] * 2LL) % MOD; // 注意这里有减法，结果可能是负数
        }
        return (f[n] + MOD) % MOD; // 保证结果非负
    }
};

###go

func numOfWays(n int) int {
const mod = 1_000_000_007
f := make([]int, n+1)
f[0] = 3
f[1] = 12
for i := 2; i <= n; i++ {
f[i] = (f[i-1]*5 - f[i-2]*2) % mod // 注意这里有减法，结果可能是负数
}
return (f[n] + mod) % mod // 保证结果非负
}

复杂度分析

时间复杂度：$\mathcal{O}(n)$。
空间复杂度：$\mathcal{O}(n)$。注：可以用滚动变量优化至 $\mathcal{O}(1)$。

方法三：矩阵快速幂

把方法二的递推式用矩阵乘法表示，即

$$
\begin{bmatrix}
f[i] \
f[i-1] \
\end{bmatrix}
= \begin{bmatrix}
5 & -2 \
1 & 0 \
\end{bmatrix}
\begin{bmatrix}
f[i-1] \
f[i-2] \
\end{bmatrix}
$$

把上式中的三个矩阵分别记作 $F[i],M,F[i-1]$，即

$$
F[i] = M\times F[i-1]
$$

那么有

$$
\begin{aligned}
F[n] &= M\times F[n-1] \
&= M\times M\times F[n-2] \
&= M\times M\times M\times F[n-3] \
&\ \ \vdots \
&= M^{n-1}\times F[1] \
\end{aligned}
$$

其中 $M^{n-1}$ 可以用快速幂计算，原理请看【图解】一张图秒懂快速幂。

初始值

$$
F[1] = \begin{bmatrix}
f[1] \
f[0] \
\end{bmatrix}
= \begin{bmatrix}
12 \
3 \
\end{bmatrix}
$$

答案为 $f[n]$，即 $F[n]$ 的第一项。

###py

MOD = 1_000_000_007

# a @ b，其中 @ 是矩阵乘法
def mul(a: List[List[int]], b: List[List[int]]) -> List[List[int]]:
    return [[sum(x * y for x, y in zip(row, col)) % MOD for col in zip(*b)]
            for row in a]

# a^n @ f0
def pow_mul(a: List[List[int]], n: int, f0: List[List[int]]) -> List[List[int]]:
    res = f0
    while n:
        if n & 1:
            res = mul(a, res)
        a = mul(a, a)
        n >>= 1
    return res

class Solution:
    def numOfWays(self, n: int) -> int:
        m = [[5, -2], [1, 0]]
        f1 = [[12], [3]]
        fn = pow_mul(m, n - 1, f1)
        return fn[0][0]

###py

import numpy as np

class Solution:
    def numOfWays(self, n: int) -> int:
        MOD = 1_000_000_007
        m = np.array([[5, -2], [1, 0]], dtype=object)
        f1 = np.array([12, 3], dtype=object)
        fn = np.linalg.matrix_power(m, n - 1) @ f1
        return fn[0] % MOD

###java

class Solution {
    private static final int MOD = 1_000_000_007;

    public int numOfWays(int n) {
        int[][] m = {
            {5, -2},
            {1, 0},
        };
        int[][] f1 = {{12}, {3}};
        int[][] fn = powMul(m, n - 1, f1);
        return (fn[0][0] + MOD) % MOD; // 保证结果非负
    }

    // a^n * f0
    private int[][] powMul(int[][] a, int n, int[][] f0) {
        int[][] res = f0;
        while (n > 0) {
            if ((n & 1) > 0) {
                res = mul(a, res);
            }
            a = mul(a, a);
            n >>= 1;
        }
        return res;
    }

    // 返回矩阵 a 和矩阵 b 相乘的结果
    private int[][] mul(int[][] a, int[][] b) {
        int[][] c = new int[a.length][b[0].length];
        for (int i = 0; i < a.length; i++) {
            for (int k = 0; k < a[i].length; k++) {
                if (a[i][k] == 0) {
                    continue;
                }
                for (int j = 0; j < b[k].length; j++) {
                    c[i][j] = (int) ((c[i][j] + (long) a[i][k] * b[k][j]) % MOD);
                }
            }
        }
        return c;
    }
}

###cpp

constexpr int MOD = 1'000'000'007;

using matrix = vector<vector<int>>;

// 返回矩阵 a 和矩阵 b 相乘的结果
matrix mul(matrix& a, matrix& b) {
    int n = a.size(), m = b[0].size();
    matrix c = matrix(n, vector<int>(m));
    for (int i = 0; i < n; i++) {
        for (int k = 0; k < a[i].size(); k++) {
            if (a[i][k] == 0) {
                continue;
            }
            for (int j = 0; j < m; j++) {
                c[i][j] = (c[i][j] + 1LL * a[i][k] * b[k][j]) % MOD;
            }
        }
    }
    return c;
}

// a^n * f0
matrix pow_mul(matrix a, int n, matrix& f0) {
    matrix res = f0;
    while (n) {
        if (n & 1) {
            res = mul(a, res);
        }
        a = mul(a, a);
        n >>= 1;
    }
    return res;
}

class Solution {
public:
    int numOfWays(int n) {
        matrix m = {
            {5, -2},
            {1, 0},
        };
        matrix f1 = {{12}, {3}};
        matrix fn = pow_mul(m, n - 1, f1);
        return (fn[0][0] + MOD) % MOD; // 保证结果非负
    }
};

###go

const mod = 1_000_000_007

type matrix [][]int

func newMatrix(n, m int) matrix {
a := make(matrix, n)
for i := range a {
a[i] = make([]int, m)
}
return a
}

// 返回矩阵 a 和矩阵 b 相乘的结果
func (a matrix) mul(b matrix) matrix {
c := newMatrix(len(a), len(b[0]))
for i, row := range a {
for k, x := range row {
if x == 0 {
continue
}
for j, y := range b[k] {
c[i][j] = (c[i][j] + x*y) % mod
}
}
}
return c
}

// a^n * f0
func (a matrix) powMul(n int, f0 matrix) matrix {
res := f0
for ; n > 0; n /= 2 {
if n%2 > 0 {
res = a.mul(res)
}
a = a.mul(a)
}
return res
}

func numOfWays(n int) int {
m := matrix{
{5, -2},
{1, 0},
}
f1 := matrix{{12}, {3}}
fn := m.powMul(n-1, f1)
return (fn[0][0] + mod) % mod // 保证结果非负
}

复杂度分析

时间复杂度：$\mathcal{O}(\log n)$。
空间复杂度：$\mathcal{O}(1)$。

注：也可以用 Kitamasa 算法计算，在矩阵更大（递推式更长）时有优势。

相似题目

专题训练

见下面动态规划题单的「§9.5 轮廓线 DP」和「§11.6 矩阵快速幂优化 DP」。

分类题单

如何科学刷题？

我的题解精选（已分类）

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

LeetCode 每日一题题解
四种方法：哈希集合/摩尔投票/邻近元素/随机（Python/Java/C++/Go）endlesscheng
2026年1月2日 08:28

四种方法：哈希集合/摩尔投票/邻近元素/随机（Python/Java/C++/Go）

LeetCode 每日一题题解

作者 endlesscheng

2026年1月2日 08:28

方法一：哈希集合（暴力）

遍历 $\textit{nums}$，同时用一个哈希集合记录遍历过的数。

如果遍历到相同数字（哈希集合中有），由于题目保证只有一个数字是重复的，返回这个数。

class Solution:
    def repeatedNTimes(self, nums: List[int]) -> int:
        seen = set()
        for x in nums:
            if x in seen:
                return x
            seen.add(x)

class Solution {
    public int repeatedNTimes(int[] nums) {
        HashSet<Integer> seen = new HashSet<>();
        for (int x : nums) {
            if (!seen.add(x)) { // x 在 seen 中
                return x;
            }
        }
        return -1; // 代码不会执行到这里
    }
}

class Solution {
public:
    int repeatedNTimes(vector<int>& nums) {
        unordered_set<int> seen;
        for (int x : nums) {
            if (!seen.insert(x).second) { // x 在 seen 中
                return x;
            }
        }
        return -1; // 代码不会执行到这里
    }
};

func repeatedNTimes(nums []int) int {
seen := map[int]struct{}{}
for _, x := range nums {
if _, ok := seen[x]; ok {
return x
}
seen[x] = struct{}{}
}
panic(-1)
}

复杂度分析

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

如何做到 $\mathcal{O}(1)$ 空间？下面再介绍三种方法。

方法二：摩尔投票

请先完成 169. 多数元素，我的题解。

为了让出现 $n$ 次的那个数变成绝对众数，我们可以分类讨论：

如果 $\textit{nums}[0]$ 在下标 $[1,n-1]$ 中出现过，那么返回 $\textit{nums}[0]$。
否则，去掉 $\textit{nums}[0]$，剩下 $2n-1$ 个数，出现次数为 $n$ 的那个数变成绝对众数，可以用 169 题的算法解决。

这两件事情可以在同一个循环中完成。

class Solution:
    def repeatedNTimes(self, nums: List[int]) -> int:
        ans = hp = 0
        for x in nums[1:]:  # 也可以写 for i in range(1, len(nums)) 避免切片
            if x == nums[0]:
                return x
            if hp == 0:  # x 是初始擂主，生命值为 1
                ans, hp = x, 1
            else:  # 比武，同门加血，否则扣血
                hp += 1 if x == ans else -1
        return ans

class Solution {
    public int repeatedNTimes(int[] nums) {
        int ans = 0;
        int hp = 0;
        for (int i = 1; i < nums.length; i++) {
            int x = nums[i];
            if (x == nums[0]) {
                return x;
            }
            if (hp == 0) { // x 是初始擂主，生命值为 1
                ans = x;
                hp = 1;
            } else { // 比武，同门加血，否则扣血
                hp += x == ans ? 1 : -1;
            }
        }
        return ans;
    }
}

class Solution {
public:
    int repeatedNTimes(vector<int>& nums) {
        int ans = 0, hp = 0;
        for (int i = 1; i < nums.size(); i++) {
            int x = nums[i];
            if (x == nums[0]) {
                return x;
            }
            if (hp == 0) { // x 是初始擂主，生命值为 1
                ans = x;
                hp = 1;
            } else { // 比武，同门加血，否则扣血
                hp += x == ans ? 1 : -1;
            }
        }
        return ans;
    }
};

func repeatedNTimes(nums []int) (ans int) {
hp := 0
for _, x := range nums[1:] {
if x == nums[0] {
return x
}
if hp == 0 { // x 是初始擂主，生命值为 1
ans, hp = x, 1
} else if x == ans { // 比武，同门加血，否则扣血
hp++
} else {
hp--
}
}
return
}

复杂度分析

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

方法三：检查邻近元素

设出现次数为 $n$ 的那个数为 $x$。

如果相邻两个 $x$ 之间都至少有一个数，那么 $\textit{nums}$ 至少要有 $2n-1$ 个数，这是合法的。

如果相邻两个 $x$ 之间都至少有两个数，那么 $\textit{nums}$ 至少要有 $3n-2$ 个数。

如果 $n=2$，这是合法的，例如 $[3,1,2,3]$。
如果 $n\ge 3$，那么 $3n-2 > 2n$，不合法。这意味着，当 $n\ge 3$ 时，一定存在 $\textit{nums}[i] = \textit{nums}[i-1]$ 或者 $\textit{nums}[i] = \textit{nums}[i-2]$。

为了兼容 $n=2$ 的情况，我们可以判断 $\textit{nums}[i]$ 是否与下标 $[i-3, i-1]$ 中的元素相等。

class Solution:
    def repeatedNTimes(self, nums: List[int]) -> int:
        for i in range(1, len(nums)):
            x = nums[i]
            if x == nums[i - 1] or \
               i > 1 and x == nums[i - 2] or \
               i > 2 and x == nums[i - 3]:
                return x

class Solution {
    public int repeatedNTimes(int[] nums) {
        for (int i = 1; ; i++) {
            int x = nums[i];
            if (x == nums[i - 1] || 
                i > 1 && x == nums[i - 2] || 
                i > 2 && x == nums[i - 3]) {
                return x;
            }
        }
    }
}

class Solution {
public:
    int repeatedNTimes(vector<int>& nums) {
        for (int i = 1; ; i++) {
            int x = nums[i];
            if (x == nums[i - 1] || 
                i > 1 && x == nums[i - 2] || 
                i > 2 && x == nums[i - 3]) {
                return x;
            }
        }
    }
};

func repeatedNTimes(nums []int) int {
for i := 1; ; i++ {
x := nums[i]
if x == nums[i-1] ||
i > 1 && x == nums[i-2] ||
i > 2 && x == nums[i-3] {
return x
}
}
}

复杂度分析

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

方法四：随机

在 $\textit{nums}$ 中随机选择两个下标不同的元素，如果两数相等，即找到了重复元素。

首先，在 $[0,n-1]$ 中随机一个数，作为下标 $i$。

然后，我们要在 $[0,i-1]\cup [i+1,n-1]$ 中随机另一个下标 $j$。

但是，标准库只支持在一个连续范围中随机元素，如何在一个间断的区间中随机元素呢？

考虑映射，把 $[0,n-2]$ 映射到 $[0,i-1]\cup [i+1,n-1]$ 中：

$$
f(x) =
\begin{cases}
x, & 0\le x \le i-1 \
x+1, & i\le x \le n-2 \
\end{cases}
$$

具体地，在 $[0,n-2]$ 中随机一个数 $x$：

如果 $x < i$，那么把 $x$ 作为下标 $j$。
如果 $x \ge i$，那么把 $x+1$ 作为下标 $j$。

class Solution:
    def repeatedNTimes(self, nums: List[int]) -> int:
        n = len(nums)
        while True:
            # 在 [0, n-1] 中随机生成两个不同下标
            i = randrange(n)
            j = randrange(n - 1)
            if j >= i:
                j += 1
            if nums[i] == nums[j]:
                return nums[i]

class Solution {
    private static final Random rand = new Random();

    public int repeatedNTimes(int[] nums) {
        int n = nums.length;
        while (true) {
            // 在 [0, n-1] 中随机生成两个不同下标
            int i = rand.nextInt(n);
            int j = rand.nextInt(n - 1);
            if (j >= i) {
                j++;
            }
            if (nums[i] == nums[j]) {
                return nums[i];
            }
        }
    }
}

class Solution {
public:
    int repeatedNTimes(vector<int>& nums) {
        int n = nums.size();
        mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
        while (true) {
            // 在 [0, n-1] 中随机生成两个不同下标
            int i = uniform_int_distribution<>(0, n - 1)(rng);
            int j = uniform_int_distribution<>(0, n - 2)(rng);
            if (j >= i) {
                j++;
            }
            if (nums[i] == nums[j]) {
                return nums[i];
            }
        }
    }
};

func repeatedNTimes(nums []int) int {
n := len(nums)
for {
// 在 [0, n-1] 中随机生成两个不同下标
i := rand.Intn(n)
j := rand.Intn(n - 1)
if j >= i {
j++
}
if nums[i] == nums[j] {
return nums[i]
}
}
}

复杂度分析

时间复杂度：期望 $\mathcal{O}(1)$。在 $\textit{nums}$ 中随机选择两个下标不同的元素，两数相等的概率为 $\dfrac{n}{2n}\times \dfrac{n-1}{2n-1}$，当 $n=2$ 时概率为 $p=\dfrac{1}{6}$，当 $n$ 增大时概率 $p\to\dfrac{1}{4}$，期望循环次数 $\dfrac{1}{p} \le 6 = \mathcal{O}(1)$。
空间复杂度：$\mathcal{O}(1)$。

专题训练

见下面数学题单的「§6.2 随机化技巧」。

分类题单

如何科学刷题？

我的题解精选（已分类）

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

LeetCode 每日一题题解
简单题，简单做（Python/Java/C++/C/Go/JS/Rust）endlesscheng
2025年9月17日 14:30

简单题，简单做（Python/Java/C++/C/Go/JS/Rust）

LeetCode 每日一题题解

作者 endlesscheng

2025年9月17日 14:30

题目让我们模拟加一运算。

比如 $23999+1 = 24000$，$999+1=1000$。

算法：

从右往左找第一个不等于 $9$ 的数，记作 $\textit{digits}[i]$。
进位，把 $\textit{digits}[i]$ 加一，把下标在 $[i+1,n-1]$ 中的数全变成 $0$。
特别地，如果所有数都等于 $9$，那么答案为 $[1,0,0,\dots,0]$，其中有 $n$ 个 $0$。

class Solution:
    def plusOne(self, digits: List[int]) -> List[int]:
        for i in range(len(digits) - 1, -1, -1):
            if digits[i] < 9:
                digits[i] += 1  # 进位
                return digits
            digits[i] = 0  # 进位数字的右边数字都变成 0

        # digits 全是 9，加一后变成 100...00
        return [1] + digits

class Solution {
    public int[] plusOne(int[] digits) {
        int n = digits.length;
        for (int i = n - 1; i >= 0; i--) {
            if (digits[i] < 9) {
                digits[i]++; // 进位
                return digits;
            }
            digits[i] = 0; // 进位数字的右边数字都变成 0
        }

        // digits 全是 9，加一后变成 100...00
        int[] ans = new int[n + 1];
        ans[0] = 1;
        return ans;
    }
}

class Solution {
public:
    vector<int> plusOne(vector<int>& digits) {
        for (int i = digits.size() - 1; i >= 0; i--) {
            if (digits[i] < 9) {
                digits[i]++; // 进位
                return digits;
            }
            digits[i] = 0; // 进位数字的右边数字都变成 0
        }

        // digits 全是 9，加一后变成 100...00
        digits.push_back(0);
        digits[0] = 1;
        return digits;
    }
};

int* plusOne(int* digits, int digitsSize, int* returnSize) {
    for (int i = digitsSize - 1; i >= 0; i--) {
        if (digits[i] < 9) {
            digits[i]++; // 进位
            *returnSize = digitsSize;
            return digits;
        }
        digits[i] = 0; // 进位数字的右边数字都变成 0
    }

    // digits 全是 9，加一后变成 100...00
    *returnSize = digitsSize + 1;
    int* ans = calloc(digitsSize + 1, sizeof(int));
    ans[0] = 1;
    return ans;
}

func plusOne(digits []int) []int {
    for i, d := range slices.Backward(digits) {
        if d < 9 {
            digits[i]++ // 进位
            return digits
        }
        digits[i] = 0 // 进位数字的右边数字都变成 0
    }

    // digits 全是 9，加一后变成 100...00
    digits = append(digits, 0)
    digits[0] = 1
    return digits
}

var plusOne = function(digits) {
    for (let i = digits.length - 1; i >= 0; i--) {
        if (digits[i] < 9) {
            digits[i]++; // 进位
            return digits;
        }
        digits[i] = 0; // 进位数字的右边数字都变成 0
    }

    // digits 全是 9，加一后变成 100...00
    digits.push(0);
    digits[0] = 1;
    return digits;
};

impl Solution {
    pub fn plus_one(mut digits: Vec<i32>) -> Vec<i32> {
        for d in digits.iter_mut().rev() {
            if *d < 9 {
                *d += 1; // 进位
                return digits;
            }
            *d = 0; // 进位数字的右边数字都变成 0
        }

        // digits 全是 9，加一后变成 100...00
        digits.push(0);
        digits[0] = 1;
        digits
    }
}

复杂度分析

时间复杂度：$\mathcal{O}(m)$，其中 $m$ 是 $\textit{digits}$ 末尾 $9$ 的个数。
空间复杂度：$\mathcal{O}(1)$。返回值不计入。

分类题单

如何科学刷题？

我的题解精选（已分类）

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

LeetCode 每日一题题解
无需计算第三行列的和，以及对角线的和，数学证明（Python/Java/C++/Go）endlesscheng
2025年12月27日 14:45

无需计算第三行列的和，以及对角线的和，数学证明（Python/Java/C++/Go）

LeetCode 每日一题题解

作者 endlesscheng

2025年12月27日 14:45

幻方正中心一定是 5

$3\times 3$ 的幻方必须包含 $1$ 到 $9$ 所有数字，这意味着幻方元素和为 $1+2+\cdots + 9 = 45$。

由于每行的和都要相等，所以每行的和为 $\dfrac{45}{3} = 15$。这也是每列的和，对角线的和。

有 $4$ 条经过幻方正中心的线：第二行，第二列，两条对角线。

这 $4$ 条线：

覆盖了 $3\times 3$ 幻方的每个数，正中心的数覆盖了 $4$ 次（多覆盖了 $3$ 次），其余数恰好覆盖一次。
总和为 $15\cdot 4 = 60$。

设正中心的数为 $x$ ，则有

$$
1+2+\cdots + 9 + 3x = 60
$$

解得

$$
x = 5
$$

换言之（逆否命题），如果 $3\times 3$ 矩阵正中心的数不是 $5$，那么该矩阵必然不是幻方。

无需计算第三行的和，第三列的和

如果 $3\times 3$ 矩阵包含 $1$ 到 $9$ 所有整数，且前两行的和都是 $15$，那么第三行的和为

$$
1+2+\cdots+9-15-15 = 15
$$

同理，如果前两列的和都是 $15$，那么第三列的和必然是 $15$。

无需计算对角线的和

如果 $3\times 3$ 矩阵：

正中心的数是 $5$。
包含 $1$ 到 $9$ 所有整数。
前两行的和都是 $15$。
前两列的和都是 $15$。

下面证明：矩阵对角线的和一定都是 $15$。

设矩阵为

$$
\begin{bmatrix}
a & b & c \
d & 5 & f \
g & h & i \
\end{bmatrix}
$$

由于正中心的数是 $5$，只需证明对角两数之和等于 $10$，即 $a+i=c+g=10$。

在 $1$ 到 $9$ 中选两个不同整数相加等于 $10$，只有如下 $4$ 种情况：

$1+9=10$。
$2+8=10$。
$3+7=10$。
$4+6=10$。

由于已知 $b+h=d+f=10$，消耗了两种情况，剩余的四个数必然在 $a,c,g,i$ 中。比如 $b+h=1+9$，$d+f=3+7$，那么剩余的 $2,4,6,8$ 必然在 $a,c,g,i$ 中。

比如左上角的 $a=4$，那么 $6$ 在哪？

在右上角？此时 $a+c=10$，由于已知 $a+b+c=15$，得到 $b=5$，与正中心的数相同，矛盾。
在左下角？此时 $a+g=10$，由于已知 $a+d+g=15$，得到 $d=5$，与正中心的数相同，矛盾。
所以 $6$ 只能在右下角，即 $a+i=10$ 成立。
剩余两个数 $2$ 和 $8$ 在另一对角，所以 $c+g=10$ 成立。

用同样的方法可以证明，$a$ 等于其他数的时候，对角的数 $i$ 一定等于 $10-a$。剩余的另一对和为 $10$ 的数在另一对角。

综上，由已知条件可得，两条对角线的和都是 $15$。

如何快速判断矩阵包含 $1$ 到 $9$ 所有数？可以把数字压缩到一个二进制数 $\textit{mask}$ 中，$\textit{mask}$ 从低到高的 $i$ 位是 $1$ 表示 $i$ 在矩阵中。矩阵包含 $1$ 到 $9$ 所有数相当于 $\textit{mask} = 1111111110_{(2)} = 2^{10}-2=1022$。

###py

class Solution:
    def numMagicSquaresInside(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        ans = 0

        for i in range(m - 2):
            for j in range(n - 2):
                if grid[i + 1][j + 1] != 5:
                    continue

                mask = 0
                r_sum = [0] * 3
                c_sum = [0] * 3
                for r in range(3):
                    for c in range(3):
                        x = grid[i + r][j + c]
                        mask |= 1 << x
                        r_sum[r] += x
                        c_sum[c] += x

                if mask == 1022 and r_sum[0] == r_sum[1] == c_sum[0] == c_sum[1] == 15:
                    ans += 1

        return ans

###java

class Solution {
    public int numMagicSquaresInside(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int ans = 0;

        for (int i = 0; i < m - 2; i++) {
            for (int j = 0; j < n - 2; j++) {
                if (grid[i + 1][j + 1] != 5) {
                    continue;
                }

                int mask = 0;
                int[] rSum = new int[3];
                int[] cSum = new int[3];
                for (int r = 0; r < 3; r++) {
                    for (int c = 0; c < 3; c++) {
                        int x = grid[i + r][j + c];
                        mask |= 1 << x;
                        rSum[r] += x;
                        cSum[c] += x;
                    }
                }

                if (mask == (1 << 10) - 2 &&
                    rSum[0] == 15 && rSum[1] == 15 &&
                    cSum[0] == 15 && cSum[1] == 15) {
                    ans++;
                }
            }
        }

        return ans;
    }
}

###cpp

class Solution {
public:
    int numMagicSquaresInside(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        int ans = 0;

        for (int i = 0; i < m - 2; i++) {
            for (int j = 0; j < n - 2; j++) {
                if (grid[i + 1][j + 1] != 5) {
                    continue;
                }

                int mask = 0;
                int r_sum[3]{};
                int c_sum[3]{};
                for (int r = 0; r < 3; r++) {
                    for (int c = 0; c < 3; c++) {
                        int x = grid[i + r][j + c];
                        mask |= 1 << x;
                        r_sum[r] += x;
                        c_sum[c] += x;
                    }
                }

                if (mask == (1 << 10) - 2 &&
                    r_sum[0] == 15 && r_sum[1] == 15 &&
                    c_sum[0] == 15 && c_sum[1] == 15) {
                    ans++;
                }
            }
        }

        return ans;
    }
};

###c

int numMagicSquaresInside(int** grid, int gridSize, int* gridColSize) {
    int m = gridSize, n = gridColSize[0];
    int ans = 0;

    for (int i = 0; i < m - 2; i++) {
        for (int j = 0; j < n - 2; j++) {
            if (grid[i + 1][j + 1] != 5) {
                continue;
            }

            int mask = 0;
            int r_sum[3] = {};
            int c_sum[3] = {};
            for (int r = 0; r < 3; r++) {
                for (int c = 0; c < 3; c++) {
                    int x = grid[i + r][j + c];
                    mask |= 1 << x;
                    r_sum[r] += x;
                    c_sum[c] += x;
                }
            }

            if (mask == (1 << 10) - 2 &&
                r_sum[0] == 15 && r_sum[1] == 15 &&
                c_sum[0] == 15 && c_sum[1] == 15) {
                ans++;
            }
        }
    }

    return ans;
}

###go

func numMagicSquaresInside(grid [][]int) (ans int) {
m, n := len(grid), len(grid[0])
for i := range m - 2 {
for j := range n - 2 {
if grid[i+1][j+1] != 5 {
continue
}

mask := 0
var rSum, cSum [3]int
for r, row := range grid[i : i+3] {
for c, x := range row[j : j+3] {
mask |= 1 << x
rSum[r] += x
cSum[c] += x
}
}

if mask == 1<<10-2 &&
rSum[0] == 15 && rSum[1] == 15 &&
cSum[0] == 15 && cSum[1] == 15 {
ans++
}
}
}
return
}

###js

var numMagicSquaresInside = function (grid) {
    const m = grid.length;
    const n = grid[0].length;
    let ans = 0;

    for (let i = 0; i < m - 2; i++) {
        for (let j = 0; j < n - 2; j++) {
            if (grid[i + 1][j + 1] !== 5) {
                continue;
            }

            let mask = 0;
            const rSum = [0, 0, 0];
            const cSum = [0, 0, 0];
            for (let r = 0; r < 3; r++) {
                for (let c = 0; c < 3; c++) {
                    const x = grid[i + r][j + c];
                    mask |= 1 << x;
                    rSum[r] += x;
                    cSum[c] += x;
                }
            }

            if (mask === (1 << 10) - 2 &&
                rSum[0] === 15 && rSum[1] === 15 &&
                cSum[0] === 15 && cSum[1] === 15) {
                ans++;
            }
        }
    }

    return ans;
};

###rust

impl Solution {
    pub fn num_magic_squares_inside(grid: Vec<Vec<i32>>) -> i32 {
        let m = grid.len();
        let n = grid[0].len();
        let mut ans = 0;

        for i in 0..m.saturating_sub(2) {
            for j in 0..n.saturating_sub(2) {
                if grid[i + 1][j + 1] != 5 {
                    continue;
                }

                let mut mask = 0;
                let mut r_sum = [0; 3];
                let mut c_sum = [0; 3];
                for (r, row) in grid[i..i + 3].iter().enumerate() {
                    for (c, &x) in row[j..j + 3].iter().enumerate() {
                        mask |= 1 << x;
                        r_sum[r] += x;
                        c_sum[c] += x;
                    }
                }

                if mask == (1 << 10) - 2 &&
                    r_sum[0] == 15 && r_sum[1] == 15 &&
                    c_sum[0] == 15 && c_sum[1] == 15 {
                    ans += 1;
                }
            }
        }

        ans
    }
}

复杂度分析

时间复杂度：$\mathcal{O}(mn)$，其中 $m$ 和 $n$ 分别是 $\textit{grid}$ 的行数和列数。
空间复杂度：$\mathcal{O}(1)$。

分类题单

如何科学刷题？

我的题解精选（已分类）

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

LeetCode 每日一题题解
【图解】回溯 + vis 优化 + 位运算优化（Python/Java/C++/Go）endlesscheng
2025年12月26日 16:49

【图解】回溯 + vis 优化 + 位运算优化（Python/Java/C++/Go）

LeetCode 每日一题题解

作者 endlesscheng

2025年12月26日 16:49

写一个类似 17. 电话号码的字母组合的回溯（搜索）。从下往上，从左到右，枚举金字塔的每个格子填什么字母。

{:width=600px}

比如 $\textit{allowed}$ 中有 $\texttt{AAB}$ 和 $\texttt{AAC}$，那么当 $(i+1,j)$ 和 $(i+1,j+1)$ 都填 $\texttt{A}$ 的时候，$(i,j)$ 可以填 $\texttt{B}$，也可以填 $\texttt{C}$。枚举填哪个。

为了快速知道 $\texttt{AA}\to [\texttt{B}, \texttt{C}]$ 的对应关系，可以把 $\textit{allowed}$ 用哈希表（或者二维数组）分组，把 $\textit{allowed}[i]$ 前两个字母对应的第三个字母，记录在一个列表中。

优化前

###py

class Solution:
    def pyramidTransition(self, bottom: str, allowed: List[str]) -> bool:
        groups = defaultdict(list)  # 三角形底部两个字母 -> [三角形顶部字母]
        for s in allowed:
            groups[s[:2]].append(s[2])

        n = len(bottom)
        pyramid = [[''] * (i + 1) for i in range(n)]
        pyramid[-1] = bottom

        # 现在准备填 (i, j) 这个格子
        # 返回继续填能否填完所有格子（从下往上填，每行从左到右填）
        def dfs(i: int, j: int) -> bool:
            if i < 0:  # 所有格子都已填完
                return True

            if j == i + 1:  # i 行已填完
                return dfs(i - 1, 0)  # 开始填 i-1 行

            # 枚举 (i, j) 填什么字母
            # 这取决于 (i+1, j) 和 (i+1, j+1) 填的字母
            for top in groups[pyramid[i + 1][j] + pyramid[i + 1][j + 1]]:
                pyramid[i][j] = top
                if dfs(i, j + 1):
                    return True
            return False

        # 从倒数第二行开始填
        return dfs(n - 2, 0)

###java

class Solution {
    public boolean pyramidTransition(String bottom, List<String> allowed) {
        // 三角形底部两个字母 -> [三角形顶部字母]
        List<Character>[][] groups = new ArrayList[6][6];
        for (List<Character>[] row : groups) {
            Arrays.setAll(row, _ -> new ArrayList<>());
        }
        for (String S : allowed) {
            char[] s = S.toCharArray();
            groups[s[0] - 'A'][s[1] - 'A'].add(s[2]);
        }

        int n = bottom.length();
        char[][] pyramid = new char[n][];
        for (int i = 0; i < n - 1; i++) {
            pyramid[i] = new char[i + 1];
        }
        pyramid[n - 1] = bottom.toCharArray();

        // 从倒数第二行开始填
        return dfs(n - 2, 0, pyramid, groups);
    }

    // 现在准备填 (i, j) 这个格子
    // 返回继续填能否填完所有格子（从下往上填，每行从左到右填）
    private boolean dfs(int i, int j, char[][] pyramid, List<Character>[][] groups) {
        if (i < 0) { // 所有格子都已填完
            return true;
        }

        if (j == i + 1) { // i 行已填完
            return dfs(i - 1, 0, pyramid, groups); // 开始填 i-1 行
        }

        // 枚举 (i, j) 填什么字母
        // 这取决于 (i+1, j) 和 (i+1, j+1) 填的字母
        for (char top : groups[pyramid[i + 1][j] - 'A'][pyramid[i + 1][j + 1] - 'A']) {
            pyramid[i][j] = top;
            if (dfs(i, j + 1, pyramid, groups)) {
                return true;
            }
        }
        return false;
    }
}

###cpp

class Solution {
public:
    bool pyramidTransition(string bottom, vector<string>& allowed) {
        string groups[6][6]{}; // 三角形底部两个字母 -> [三角形顶部字母]
        for (auto& s : allowed) {
            groups[s[0] - 'A'][s[1] - 'A'] += s[2];
        }

        int n = bottom.size();
        vector<string> pyramid(n);
        for (int i = 0; i < n - 1; i++) {
            pyramid[i].resize(i + 1);
        }
        pyramid[n - 1] = move(bottom);

        // 现在准备填 (i, j) 这个格子
        // 返回继续填能否填完所有格子（从下往上填，每行从左到右填）
        auto dfs = [&](this auto&& dfs, int i, int j) -> bool {
            if (i < 0) { // 所有格子都已填完
                return true;
            }

            if (j == i + 1) { // i 行已填完
                return dfs(i - 1, 0); // 开始填 i-1 行
            }

            // 枚举 (i, j) 填什么字母
            // 这取决于 (i+1, j) 和 (i+1, j+1) 填的字母
            for (char top : groups[pyramid[i + 1][j] - 'A'][pyramid[i + 1][j + 1] - 'A']) {
                pyramid[i][j] = top;
                if (dfs(i, j + 1)) {
                    return true;
                }
            }
            return false;
        };

        // 从倒数第二行开始填
        return dfs(n - 2, 0);
    }
};

###go

func pyramidTransition(bottom string, allowed []string) bool {
groups := [6][6][]byte{} // 三角形底部两个字母 -> [三角形顶部字母]
for _, s := range allowed {
a, b := s[0]-'A', s[1]-'A'
groups[a][b] = append(groups[a][b], s[2])
}

n := len(bottom)
pyramid := make([][]byte, n)
for i := range n - 1 {
pyramid[i] = make([]byte, i+1)
}
pyramid[n-1] = []byte(bottom)

// 现在准备填 (i, j) 这个格子
// 返回继续填能否填完所有格子（从下往上填，每行从左到右填）
var dfs func(int, int) bool
dfs = func(i, j int) bool {
if i < 0 { // 所有格子都已填完
return true
}

if j == i+1 { // i 行已填完
return dfs(i-1, 0) // 开始填 i-1 行
}

// 枚举 (i, j) 填什么字母
// 这取决于 (i+1, j) 和 (i+1, j+1) 填的字母
for _, top := range groups[pyramid[i+1][j]-'A'][pyramid[i+1][j+1]-'A'] {
pyramid[i][j] = top
if dfs(i, j+1) {
return true
}
}
return false
}

// 从倒数第二行开始填
return dfs(n-2, 0)
}

复杂度分析

时间复杂度：$\mathcal{O}(|\Sigma|^{n^2})$，其中 $n$ 是 $\textit{bottom}$ 的长度，$|\Sigma|=6$ 是字符集合的大小。搜索树的高度为 $\mathcal{O}(n^2)$，每个节点至多有 $|\Sigma|$ 个儿子，所以搜索树有 $\mathcal{O}(|\Sigma|^{n^2})$ 个节点，遍历这棵搜索树需要 $\mathcal{O}(|\Sigma|^{n^2})$ 的时间。
空间复杂度：$\mathcal{O}(m + n^2)$，其中 $m$ 是 $\textit{allowed}$ 的长度。

优化一：减少重复搜索

{:width=600px}

###py

class Solution:
    def pyramidTransition(self, bottom: str, allowed: List[str]) -> bool:
        groups = defaultdict(list)
        for s in allowed:
            groups[s[:2]].append(s[2])

        n = len(bottom)
        pyramid = [[''] * (i + 1) for i in range(n)]
        pyramid[-1] = bottom

        vis = set()  # 访问标记

        def dfs(i: int, j: int) -> bool:
            if i < 0:
                return True

            if j == i + 1:
                row = ''.join(pyramid[i])
                if row in vis:  # 这一行之前填过一模一样的，继续填，没能填到塔顶
                    return False  # 直接返回
                vis.add(row)
                return dfs(i - 1, 0)

            for top in groups[pyramid[i + 1][j] + pyramid[i + 1][j + 1]]:
                pyramid[i][j] = top
                if dfs(i, j + 1):
                    return True
            return False

        return dfs(n - 2, 0)

###java

class Solution {
    public boolean pyramidTransition(String bottom, List<String> allowed) {
        List<Character>[][] groups = new ArrayList[6][6];
        for (List<Character>[] row : groups) {
            Arrays.setAll(row, _ -> new ArrayList<>());
        }
        for (String S : allowed) {
            char[] s = S.toCharArray();
            groups[s[0] - 'A'][s[1] - 'A'].add(s[2]);
        }

        int n = bottom.length();
        char[][] pyramid = new char[n][];
        for (int i = 0; i < n - 1; i++) {
            pyramid[i] = new char[i + 1];
        }
        pyramid[n - 1] = bottom.toCharArray();

        Set<String> vis = new HashSet<>(); // 访问标记

        return dfs(n - 2, 0, pyramid, vis, groups);
    }

    private boolean dfs(int i, int j, char[][] pyramid, Set<String> vis, List<Character>[][] groups) {
        if (i < 0) {
            return true;
        }

        if (j == i + 1) {
            String row = new String(pyramid[i]);
            if (!vis.add(row)) { // 这一行之前填过一模一样的，继续填，没能填到塔顶
                return false; // 直接返回
            }
            return dfs(i - 1, 0, pyramid, vis, groups);
        }

        for (char top : groups[pyramid[i + 1][j] - 'A'][pyramid[i + 1][j + 1] - 'A']) {
            pyramid[i][j] = top;
            if (dfs(i, j + 1, pyramid, vis, groups)) {
                return true;
            }
        }
        return false;
    }
}

###cpp

class Solution {
public:
    bool pyramidTransition(string bottom, vector<string>& allowed) {
        string groups[6][6];
        for (auto& s : allowed) {
            groups[s[0] - 'A'][s[1] - 'A'] += s[2];
        }

        int n = bottom.size();
        vector<string> pyramid(n);
        for (int i = 0; i < n - 1; i++) {
            pyramid[i].resize(i + 1);
        }
        pyramid[n - 1] = move(bottom);

        unordered_set<string> vis; // 访问标记

        auto dfs = [&](this auto&& dfs, int i, int j) -> bool {
            if (i < 0) {
                return true;
            }

            if (j == i + 1) {
                if (!vis.insert(pyramid[i]).second) { // 这一行之前填过一模一样的，继续填，没能填到塔顶
                    return false; // 直接返回
                }
                return dfs(i - 1, 0);
            }

            for (char top : groups[pyramid[i + 1][j] - 'A'][pyramid[i + 1][j + 1] - 'A']) {
                pyramid[i][j] = top;
                if (dfs(i, j + 1)) {
                    return true;
                }
            }
            return false;
        };

        return dfs(n - 2, 0);
    }
};

###go

func pyramidTransition(bottom string, allowed []string) bool {
groups := [6][6][]byte{}
for _, s := range allowed {
a, b := s[0]-'A', s[1]-'A'
groups[a][b] = append(groups[a][b], s[2])
}

n := len(bottom)
pyramid := make([][]byte, n)
for i := range n - 1 {
pyramid[i] = make([]byte, i+1)
}
pyramid[n-1] = []byte(bottom)

vis := map[string]struct{}{} // 访问标记

var dfs func(int, int) bool
dfs = func(i, j int) bool {
if i < 0 {
return true
}

if j == i+1 {
row := string(pyramid[i])
if _, ok := vis[row]; ok { // 这一行之前填过一模一样的，继续填，没能填到塔顶
return false // 直接返回
}
vis[row] = struct{}{}
return dfs(i-1, 0)
}

for _, top := range groups[pyramid[i+1][j]-'A'][pyramid[i+1][j+1]-'A'] {
pyramid[i][j] = top
if dfs(i, j+1) {
return true
}
}
return false
}

return dfs(n-2, 0)
}

优化二：减少更多重复搜索

{:width=600px}

###py

class Solution:
    def pyramidTransition(self, bottom: str, allowed: List[str]) -> bool:
        groups = defaultdict(list)
        for s in allowed:
            groups[s[:2]].append(s[2])

        n = len(bottom)
        pyramid = [[] for _ in range(n)]
        pyramid[-1] = bottom

        vis = set()

        def dfs(i: int, j: int) -> bool:
            if i < 0:
                return True

            row = ''.join(pyramid[i])
            if row in vis:  # 之前填过一模一样的，这个局部的金字塔无法填完
                return False  # 继续递归也无法填完，直接返回

            if j == i + 1:
                vis.add(row)
                return dfs(i - 1, 0)

            for top in groups[pyramid[i + 1][j] + pyramid[i + 1][j + 1]]:
                pyramid[i].append(top)
                if dfs(i, j + 1):
                    return True
                pyramid[i].pop()
            return False

        return dfs(n - 2, 0)

###java

class Solution {
    public boolean pyramidTransition(String bottom, List<String> allowed) {
        List<Character>[][] groups = new ArrayList[6][6];
        for (List<Character>[] row : groups) {
            Arrays.setAll(row, _ -> new ArrayList<>());
        }
        for (String S : allowed) {
            char[] s = S.toCharArray();
            groups[s[0] - 'A'][s[1] - 'A'].add(s[2]);
        }

        int n = bottom.length();
        char[][] pyramid = new char[n][];
        for (int i = 0; i < n - 1; i++) {
            pyramid[i] = new char[i + 1];
        }
        pyramid[n - 1] = bottom.toCharArray();

        Set<String> vis = new HashSet<>();

        return dfs(n - 2, 0, pyramid, vis, groups);
    }

    private boolean dfs(int i, int j, char[][] pyramid, Set<String> vis, List<Character>[][] groups) {
        if (i < 0) {
            return true;
        }

        String row = new String(pyramid[i], 0, j);
        if (vis.contains(row)) { // 之前填过一模一样的，这个局部的金字塔无法填完
            return false; // 继续递归也无法填完，直接返回
        }

        if (j == i + 1) {
            vis.add(row);
            return dfs(i - 1, 0, pyramid, vis, groups);
        }

        for (char top : groups[pyramid[i + 1][j] - 'A'][pyramid[i + 1][j + 1] - 'A']) {
            pyramid[i][j] = top;
            if (dfs(i, j + 1, pyramid, vis, groups)) {
                return true;
            }
        }
        return false;
    }
}

###cpp

class Solution {
public:
    bool pyramidTransition(string bottom, vector<string>& allowed) {
        string groups[6][6];
        for (auto& s : allowed) {
            groups[s[0] - 'A'][s[1] - 'A'] += s[2];
        }

        int n = bottom.size();
        vector<string> pyramid(n);
        pyramid[n - 1] = move(bottom);

        unordered_set<string> vis;

        auto dfs = [&](this auto&& dfs, int i, int j) -> bool {
            if (i < 0) {
                return true;
            }

            if (vis.contains(pyramid[i])) { // 之前填过一模一样的，这个局部的金字塔无法填完
                return false; // 继续递归也无法填完，直接返回
            }

            if (j == i + 1) {
                vis.insert(pyramid[i]);
                return dfs(i - 1, 0);
            }

            for (char top : groups[pyramid[i + 1][j] - 'A'][pyramid[i + 1][j + 1] - 'A']) {
                pyramid[i] += top;
                if (dfs(i, j + 1)) {
                    return true;
                }
                pyramid[i].pop_back();
            }
            return false;
        };

        return dfs(n - 2, 0);
    }
};

###go

func pyramidTransition(bottom string, allowed []string) bool {
groups := [6][6][]byte{}
for _, s := range allowed {
a, b := s[0]-'A', s[1]-'A'
groups[a][b] = append(groups[a][b], s[2])
}

n := len(bottom)
pyramid := make([][]byte, n)
for i := range n - 1 {
pyramid[i] = make([]byte, i+1)
}
pyramid[n-1] = []byte(bottom)

vis := map[string]struct{}{}

var dfs func(int, int) bool
dfs = func(i, j int) bool {
if i < 0 {
return true
}

row := string(pyramid[i][:j])
if _, ok := vis[row]; ok { // 之前填过一模一样的，这个局部的金字塔无法填完
return false // 继续递归也无法填完，直接返回
}

if j == i+1 {
vis[row] = struct{}{}
return dfs(i-1, 0)
}

for _, top := range groups[pyramid[i+1][j]-'A'][pyramid[i+1][j+1]-'A'] {
pyramid[i][j] = top
if dfs(i, j+1) {
return true
}
}
return false
}

return dfs(n-2, 0)
}

复杂度分析

时间复杂度：$\mathcal{O}(n|\Sigma|^n)$，其中 $n$ 是 $\textit{bottom}$ 的长度，$|\Sigma|=6$ 是字符集合的大小。把字符串按照长度分类，长为 $k$ 的字符串至多有 $|\Sigma|^k$ 个。等比数列求和 $|\Sigma| + |\Sigma|^2 + \cdots + |\Sigma|^{n-1} = \mathcal{O}(|\Sigma|^n)$。一共有 $\mathcal{O}(|\Sigma|^n)$ 个字符串，每个字符串花费 $\mathcal{O}(n)$ 的时间与 $\textit{vis}$ 交互（查询，插入）。
空间复杂度：$\mathcal{O}(n|\Sigma|^n)$。$\textit{vis}$ 保存了 $\mathcal{O}(|\Sigma|^n)$ 个字符串，每个字符串需要 $\mathcal{O}(n)$ 的空间。

优化三：位运算

把 $\texttt{A}$ 到 $\texttt{F}$ 映射为 $1$ 到 $6$。由于每个字母只占用 $3$ 个比特位，可以用二进制数表示字符串。

由于倒数第二排最多 $5$ 个字母，所以记录到 $\textit{vis}$ 中的二进制数的长度最多为 $15$。

问：为什么不映射为 $0$ 到 $5$？

答：比如，我们无法区分 $\texttt{AA}$ 和 $\texttt{AAA}$，二者都是 $0$。

###py

class Solution:
    def pyramidTransition(self, bottom: str, allowed: List[str]) -> bool:
        groups = [[[] for _ in range(7)] for _ in range(7)]
        for a, b, c in allowed:
            # A~F -> 1~6
            groups[ord(a) & 31][ord(b) & 31].append(ord(c) & 31)

        n = len(bottom)
        pyramid = [0] * n
        for i, ch in enumerate(bottom):
            pyramid[-1] |= (ord(ch) & 31) << (i * 3)  # 等价于 pyramid[-1][i] = ord(ch)&31

        vis = set()

        def dfs(i: int, j: int) -> bool:
            if i < 0:
                return True

            if pyramid[i] in vis:
                return False

            if j == i + 1:
                vis.add(pyramid[i])
                return dfs(i - 1, 0)

            for top in groups[pyramid[i + 1] >> (j * 3) & 7][pyramid[i + 1] >> ((j + 1) * 3) & 7]:
                pyramid[i] &= ~(7 << (j * 3))  # 清除之前填的字母，等价于 pyramid[i][j] = 0
                pyramid[i] |= top << (j * 3)  # 等价于 pyramid[i][j] = top
                if dfs(i, j + 1):
                    return True
            return False

        return dfs(n - 2, 0)

###java

class Solution {
    public boolean pyramidTransition(String bottom, List<String> allowed) {
        List<Integer>[][] groups = new ArrayList[7][7];
        for (List<Integer>[] row : groups) {
            Arrays.setAll(row, _ -> new ArrayList<>());
        }
        for (String S : allowed) {
            char[] s = S.toCharArray();
            // A~F -> 1~6
            groups[s[0] & 31][s[1] & 31].add(s[2] & 31);
        }

        char[] s = bottom.toCharArray();
        int n = s.length;
        int[] pyramid = new int[n];
        for (int i = 0; i < n; i++) {
            pyramid[n - 1] |= (s[i] & 31) << (i * 3); // 等价于 pyramid[n-1][i] = s[i]&31
        }

        boolean[] vis = new boolean[1 << ((n - 1) * 3)];

        return dfs(n - 2, 0, pyramid, vis, groups);
    }

    private boolean dfs(int i, int j, int[] pyramid, boolean[] vis, List<Integer>[][] groups) {
        if (i < 0) {
            return true;
        }

        if (vis[pyramid[i]]) {
            return false;
        }

        if (j == i + 1) {
            vis[pyramid[i]] = true;
            return dfs(i - 1, 0, pyramid, vis, groups);
        }

        for (int top : groups[pyramid[i + 1] >> (j * 3) & 7][pyramid[i + 1] >> ((j + 1) * 3) & 7]) {
            pyramid[i] &= ~(7 << (j * 3)); // 清除之前填的字母，等价于 pyramid[i][j] = 0
            pyramid[i] |= top << (j * 3); // 等价于 pyramid[i][j] = top
            if (dfs(i, j + 1, pyramid, vis, groups)) {
                return true;
            }
        }
        return false;
    }
}

###cpp

class Solution {
public:
    bool pyramidTransition(string bottom, vector<string>& allowed) {
        vector<int> groups[7][7];
        for (auto& s : allowed) {
            // A~F -> 1~6
            groups[s[0] & 31][s[1] & 31].push_back(s[2] & 31);
        }

        int n = bottom.size();
        vector<int> pyramid(n);
        for (int i = 0; i < n; i++) {
            pyramid[n - 1] |= (bottom[i] & 31) << (i * 3); // 等价于 pyramid[n-1][i] = bottom[i]&31
        }

        vector<uint8_t> vis(1 << ((n - 1) * 3));

        auto dfs = [&](this auto&& dfs, int i, int j) -> bool {
            if (i < 0) {
                return true;
            }

            if (vis[pyramid[i]]) {
                return false;
            }

            if (j == i + 1) {
                vis[pyramid[i]] = true;
                return dfs(i - 1, 0);
            }

            for (int top : groups[pyramid[i + 1] >> (j * 3) & 7][pyramid[i + 1] >> ((j + 1) * 3) & 7]) {
                pyramid[i] &= ~(7 << (j * 3)); // 清除之前填的字母，等价于 pyramid[i][j] = 0
                pyramid[i] |= top << (j * 3); // 等价于 pyramid[i][j] = top
                if (dfs(i, j + 1)) {
                    return true;
                }
            }
            return false;
        };

        return dfs(n - 2, 0);
    }
};

###go

func pyramidTransition(bottom string, allowed []string) bool {
groups := [7][7][]byte{}
for _, s := range allowed {
a, b := s[0]&31, s[1]&31 // A~F -> 1~6
groups[a][b] = append(groups[a][b], s[2]&31)
}

n := len(bottom)
pyramid := make([]int, n)
for i, ch := range bottom {
pyramid[n-1] |= int(ch&31) << (i * 3) // 等价于 pyramid[n-1][i] = ch&31
}

vis := make([]bool, 1<<((n-1)*3))

var dfs func(int, int) bool
dfs = func(i, j int) bool {
if i < 0 {
return true
}

if vis[pyramid[i]] {
return false
}

if j == i+1 {
vis[pyramid[i]] = true
return dfs(i-1, 0)
}

for _, top := range groups[pyramid[i+1]>>(j*3)&7][pyramid[i+1]>>((j+1)*3)&7] {
pyramid[i] &^= 7 << (j * 3) // 清除之前填的字母，等价于 pyramid[i][j] = 0
pyramid[i] |= int(top) << (j * 3) // 等价于 pyramid[i][j] = top
if dfs(i, j+1) {
return true
}
}
return false
}

return dfs(n-2, 0)
}

复杂度分析

时间复杂度：$\mathcal{O}(|\Sigma|^n)$，其中 $n$ 是 $\textit{bottom}$ 的长度，$|\Sigma|=6$ 是字符集合的大小。
空间复杂度：$\mathcal{O}(|\Sigma|^n)$。

专题训练

见下面回溯题单的「§4.7 搜索」。

分类题单

如何科学刷题？

我的题解精选（已分类）

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

LeetCode 每日一题题解
【图解】疯狂撕数字，一图秒懂（Python/Java/C++/C/Go/JS/Rust）endlesscheng
2025年12月19日 19:41

【图解】疯狂撕数字，一图秒懂（Python/Java/C++/C/Go/JS/Rust）

LeetCode 每日一题题解

作者 endlesscheng

2025年12月19日 19:41

{:width=600px}

注：也可以从左下角开始，方法类似。

总结：利用 $\textit{grid}$ 行列有序的性质，我们可以用 $\mathcal{O}(1)$ 的时间获取 $\mathcal{O}(m)$ 或 $\mathcal{O}(n)$ 的信息。相比之下，$\mathcal{O}(mn)$ 的暴力查找（一个一个地找），每次花费 $\mathcal{O}(1)$ 的时间，只获取了 $\mathcal{O}(1)$ 的信息。

这就是为什么我们可以把 $\mathcal{O}(mn)$ 的暴力查找优化成 $\mathcal{O}(m+n)$。

###py

class Solution:
    def countNegatives(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        ans = 0
        i, j = 0, n - 1  # 从右上角开始
        while i < m and j >= 0:  # 还有剩余元素
            if grid[i][j] < 0:
                ans += m - i  # 这一列剩余元素都是负数
                j -= 1
            else:
                i += 1  # 这一行剩余元素全都非负，排除
        return ans

###java

class Solution {
    public int countNegatives(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int ans = 0;
        int i = 0;
        int j = n - 1; // 从右上角开始
        while (i < m && j >= 0) { // 还有剩余元素
            if (grid[i][j] < 0) {
                ans += m - i; // 这一列剩余元素都是负数
                j--;
            } else {
                i++; // 这一行剩余元素全都非负，排除
            }
        }
        return ans;
    }
}

###cpp

class Solution {
public:
    int countNegatives(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        int ans = 0;
        int i = 0, j = n - 1; // 从右上角开始
        while (i < m && j >= 0) { // 还有剩余元素
            if (grid[i][j] < 0) {
                ans += m - i; // 这一列剩余元素都是负数
                j--;
            } else {
                i++; // 这一行剩余元素全都非负，排除
            }
        }
        return ans;
    }
};

###c

int countNegatives(int** grid, int gridSize, int* gridColSize) {
    int m = gridSize, n = gridColSize[0];
    int ans = 0;
    int i = 0, j = n - 1; // 从右上角开始
    while (i < m && j >= 0) { // 还有剩余元素
        if (grid[i][j] < 0) {
            ans += m - i; // 这一列剩余元素都是负数
            j--;
        } else {
            i++; // 这一行剩余元素全都非负，排除
        }
    }
    return ans;
}

###go

func countNegatives(grid [][]int) (ans int) {
m, n := len(grid), len(grid[0])
i, j := 0, n-1 // 从右上角开始
for i < m && j >= 0 { // 还有剩余元素
if grid[i][j] < 0 {
ans += m - i // 这一列剩余元素都是负数
j--
} else {
i++ // 这一行剩余元素全都非负，排除
}
}
return
}

###js

var countNegatives = function(grid) {
    const m = grid.length, n = grid[0].length;
    let ans = 0;
    let i = 0, j = n - 1; // 从右上角开始
    while (i < m && j >= 0) { // 还有剩余元素
        if (grid[i][j] < 0) {
            ans += m - i; // 这一列剩余元素都是负数
            j--;
        } else {
            i++; // 这一行剩余元素全都非负，排除
        }
    }
    return ans;
};

###rust

impl Solution {
    pub fn count_negatives(grid: Vec<Vec<i32>>) -> i32 {
        let m = grid.len();
        let n = grid[0].len();
        let mut ans = 0;
        let mut i = 0;
        let mut j = n - 1; // 从右上角开始
        while i < m && j < n { // 还有剩余元素
            if grid[i][j] < 0 {
                ans += m - i; // 这一列剩余元素都是负数
                j -= 1;
            } else {
                i += 1; // 这一行剩余元素全都非负，排除
            }
        }
        ans as _
    }
}

复杂度分析

时间复杂度：$\mathcal{O}(m + n)$，其中 $m$ 和 $n$ 分别是 $\textit{grid}$ 的行数和列数。
空间复杂度：$\mathcal{O}(1)$。

注：本题不存在时间复杂度低于 $\mathcal{O}(m + n)$ 的算法，见 240 题我的题解文末的注。

相似题目

240. 搜索二维矩阵 II

分类题单

如何科学刷题？

我的题解精选（已分类）

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

双堆模拟（Python/Java/C++/Go）

LeetCode 每日一题题解

作者 endlesscheng

2022年9月4日 12:07

按照时间顺序模拟开会过程。

对于会议 $[\textit{start},\textit{end})$，我们需要知道：

在 $\textit{start}$ 时刻空闲的会议室中，编号最小的会议室。可以用一个最小堆 $\textit{idle}$ 维护空闲会议室的编号。
如果没有空闲的会议室呢？我们需要找最早结束的会议室。可以用一个最小堆 $\textit{using}$ 维护使用中的会议室的结束时间和编号。

这两类会议室是互补关系，伴随着会议的开始和结束，会议室在这两类中来回倒：

首先，从 $\textit{using}$ 中去掉结束时间小于等于 $\textit{start}$ 的所有会议室，将其编号添加到 $\textit{idle}$ 中。
然后分类讨论：
- 如果此时有空闲的会议室，那么从 $\textit{idle}$ 中弹出编号最小的会议室，和 $\textit{end}$ 一起，添加到 $\textit{using}$ 中。
- 否则，从 $\textit{using}$ 中弹出一个最早结束的会议室（若有多个同时结束，弹出编号最小的会议室），设其结束时间为 $e$，则我们等待了 $e-\textit{start}$ 时间，所以当前会议的结束时间为 $\textit{end} + e-\textit{start}$。

在上述模拟的过程中，每使用一个编号为 $i$ 的会议室，就把 $i$ 的出现次数加一。最后返回出现次数最大的编号（如果有多个编号的出现次数相同，返回其中最小的编号）。

注意题目保证所有会议的开始时间互不相同。

class Solution:
    def mostBooked(self, n: int, meetings: List[List[int]]) -> int:
        meetings.sort(key=lambda m: m[0])

        idle = list(range(n))  # 会议室编号
        using = []  # (结束时间，会议室编号)
        cnt = [0] * n  # 会议室的开会次数

        for start, end in meetings:
            # 在 start 时刻空出来的会议室
            while using and using[0][0] <= start:
                heappush(idle, heappop(using)[1])

            if idle:  # 有空闲的会议室
                i = heappop(idle)
            else:  # 没有空闲的会议室
                e, i = heappop(using)  # 弹出一个最早结束的会议室（若有多个同时结束，弹出编号最小的会议室）
                end += e - start  # 更新当前会议的结束时间

            heappush(using, (end, i))  # 使用一个会议室
            cnt[i] += 1

        return cnt.index(max(cnt))

class Solution {
    public int mostBooked(int n, int[][] meetings) {
        Arrays.sort(meetings, (a, b) -> a[0] - b[0]);

        PriorityQueue<Integer> idle = new PriorityQueue<>(); // 会议室编号
        for (int i = 0; i < n; i++) {
            idle.offer(i);
        }
        PriorityQueue<long[]> using = new PriorityQueue<>(
            (a, b) -> a[0] != b[0] ? Long.compare(a[0], b[0]) : Long.compare(a[1], b[1])
        ); // (结束时间，会议室编号)
        int[] cnt = new int[n]; // 会议室的开会次数

        for (int[] m : meetings) {
            long start = m[0];
            long end = m[1];

            // 在 start 时刻空出来的会议室
            while (!using.isEmpty() && using.peek()[0] <= start) {
                idle.offer((int) using.poll()[1]);
            }

            int i;
            if (!idle.isEmpty()) { // 有空闲的会议室
                i = idle.poll();
            } else { // 没有空闲的会议室
                long[] p = using.poll(); // 弹出一个最早结束的会议室（若有多个同时结束，弹出编号最小的会议室）
                end += p[0] - start; // 更新当前会议的结束时间
                i = (int) p[1];
            }

            using.offer(new long[]{end, i}); // 使用一个会议室
            cnt[i]++;
        }

        int ans = 0;
        for (int i = 1; i < n; i++) {
            if (cnt[i] > cnt[ans]) {
                ans = i;
            }
        }
        return ans;
    }
}

class Solution {
public:
    int mostBooked(int n, vector<vector<int>>& meetings) {
        ranges::sort(meetings, {}, [](auto& m) { return m[0]; });

        priority_queue<int, vector<int>, greater<>> idle; // 会议室编号
        for (int i = 0; i < n; i++) {
            idle.push(i);
        }
        priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<>> using_; // (结束时间，会议室编号)
        vector<int> cnt(n); // 会议室的开会次数

        for (auto& m : meetings) {
            long long start = m[0], end = m[1];

            // 在 start 时刻空出来的会议室
            while (!using_.empty() && using_.top().first <= start) {
                idle.push(using_.top().second);
                using_.pop();
            }

            int i;
            if (!idle.empty()) { // 有空闲的会议室
                i = idle.top();
                idle.pop();
            } else { // 没有空闲的会议室
                // 弹出一个最早结束的会议室（若有多个同时结束，弹出编号最小的会议室）
                auto [e, room] = using_.top();
                i = room;
                using_.pop(); 
                end += e - start; // 更新当前会议的结束时间
            }

            using_.emplace(end, i); // 使用一个会议室
            cnt[i]++;
        }

        return ranges::max_element(cnt) - cnt.begin();
    }
};

func mostBooked(n int, meetings [][]int) (ans int) {
slices.SortFunc(meetings, func(a, b []int) int { return a[0] - b[0] })

idle := hp{make([]int, n)} // 会议室编号
for i := range n {
idle.IntSlice[i] = i
}
using := hp2{} // (结束时间，会议室编号)
cnt := make([]int, n) // 会议室的开会次数

for _, m := range meetings {
start, end := m[0], m[1]

// 在 start 时刻空出来的会议室
for len(using) > 0 && using[0].end <= start {
heap.Push(&idle, heap.Pop(&using).(pair).i)
}

var i int
if idle.Len() > 0 { // 有空闲的会议室
i = heap.Pop(&idle).(int)
} else {
// 弹出一个最早结束的会议室（若有多个同时结束，弹出编号最小的会议室）
p := heap.Pop(&using).(pair)
end += p.end - start // 更新当前会议的结束时间  
i = p.i
}

heap.Push(&using, pair{end, i}) // 使用一个会议室
cnt[i]++
}

for i, c := range cnt {
if c > cnt[ans] {
ans = i
}
}
return
}

type hp struct{ sort.IntSlice }
func (h *hp) Push(v any) { h.IntSlice = append(h.IntSlice, v.(int)) }
func (h *hp) Pop() any   { a := h.IntSlice; v := a[len(a)-1]; h.IntSlice = a[:len(a)-1]; return v }

type pair struct{ end, i int }
type hp2 []pair
func (h hp2) Len() int { return len(h) }
func (h hp2) Less(i, j int) bool {
a, b := h[i], h[j]
return a.end < b.end || a.end == b.end && a.i < b.i
}
func (h hp2) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *hp2) Push(v any)   { *h = append(*h, v.(pair)) }
func (h *hp2) Pop() any     { a := *h; v := a[len(a)-1]; *h = a[:len(a)-1]; return v }

复杂度分析

时间复杂度：$\mathcal{O}(m\log m + n + m\log n)$，其中 $m$ 是 $\textit{meetings}$ 的长度。注意每个会议至多入堆出堆各一次。
空间复杂度：$\mathcal{O}(n)$。

相似题目

分类题单

如何科学刷题？

我的题解精选（已分类）

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

LeetCode 每日一题题解
前后缀分解，一次遍历优化（Python/Java/C++/Go）endlesscheng
2022年11月27日 09:02

前后缀分解，一次遍历优化（Python/Java/C++/Go）

LeetCode 每日一题题解

作者 endlesscheng

2022年11月27日 09:02

题意

把 $\textit{customers}$ 分成两段，第一段计算 $\texttt{N}$ 的个数 $\textit{preN}$，第二段计算 $\texttt{Y}$ 的个数 $\textit{sufY}$。

计算 $\textit{preN}+\textit{sufY}$ 的最小值对应的最小分割位置 $i$，其中 $[0,i-1]$ 是第一段，$[i,n-1]$ 是第二段。

注：也可以不分割，相当于其中一段是空的。

思路

先假设所有字母都在第二段，统计 $\textit{customers}$ 中 $\texttt{Y}$ 的个数 $\textit{sufY}$。

想象一根分割线在从左到右移动，$\textit{customers}[i]$ 原来在第二段，现在在第一段。如果 $\textit{customers}[i] = \texttt{N}$，那么把 $\textit{preN}$ 加一（$\textit{preN}$ 初始值为 $0$），否则把 $\textit{sufY}$ 减一。

答案为 $\textit{preN}+\textit{sufY}$ 最小时对应的分割位置。

代码实现时，$\textit{preN}+\textit{sufY}$ 可以合并为一个变量 $\textit{penalty}$。

优化前

class Solution:
    def bestClosingTime(self, customers: str) -> int:
        min_penalty = penalty = customers.count('Y')
        ans = 0  # [0,n-1] 是第二段
        for i, c in enumerate(customers):
            penalty += 1 if c == 'N' else -1
            if penalty < min_penalty:
                min_penalty = penalty
                ans = i + 1  # [0,i] 是第一段，[i+1,n-1] 是第二段
        return ans

class Solution {
    public int bestClosingTime(String customers) {
        char[] s = customers.toCharArray();
        int penalty = 0;
        for (char c : s) {
            if (c == 'Y') {
                penalty++;
            }
        }

        int minPenalty = penalty;
        int ans = 0; // [0,n-1] 是第二段
        for (int i = 0; i < s.length; i++) {
            penalty += s[i] == 'N' ? 1 : -1;
            if (penalty < minPenalty) {
                minPenalty = penalty;
                ans = i + 1; // [0,i] 是第一段，[i+1,n-1] 是第二段
            }
        }
        return ans;
    }
}

class Solution {
public:
    int bestClosingTime(string customers) {
        int penalty = ranges::count(customers, 'Y');
        int min_penalty = penalty;
        int ans = 0; // [0,n-1] 是第二段
        for (int i = 0; i < customers.size(); i++) {
            penalty += customers[i] == 'N' ? 1 : -1;
            if (penalty < min_penalty) {
                min_penalty = penalty;
                ans = i + 1; // [0,i] 是第一段，[i+1,n-1] 是第二段
            }
        }
        return ans;
    }
};

func bestClosingTime(customers string) int {
penalty := strings.Count(customers, "Y")
minPenalty := penalty
ans := 0 // [0,n-1] 是第二段
for i, c := range customers {
if c == 'N' {
penalty++
} else {
penalty--
}
if penalty < minPenalty {
minPenalty = penalty
ans = i + 1 // [0,i] 是第一段，[i+1,n-1] 是第二段
}
}
return ans
}

优化：一次遍历

第一次遍历（统计 $\texttt{Y}$ 的个数）是多余的。

打个比方，绝对温度下冰点为 $273,\mathrm{K}$，摄氏温度下冰点为 $0~^\circ\mathrm{C}$。如果只关心哪一天最冷，用哪个单位计算都可以。

或者说，把折线图往下平移（第一个点移到坐标零点），最低点的横坐标仍然不变。

class Solution:
    def bestClosingTime(self, customers: str) -> int:
        min_penalty = penalty = ans = 0
        for i, c in enumerate(customers):
            penalty += 1 if c == 'N' else -1
            if penalty < min_penalty:
                min_penalty = penalty
                ans = i + 1
        return ans

class Solution {
    public int bestClosingTime(String customers) {
        int penalty = 0;
        int minPenalty = 0;
        int ans = 0;
        for (int i = 0; i < customers.length(); i++) {
            penalty += customers.charAt(i) == 'N' ? 1 : -1;
            if (penalty < minPenalty) {
                minPenalty = penalty;
                ans = i + 1;
            }
        }
        return ans;
    }
}

class Solution {
public:
    int bestClosingTime(string customers) {
        int penalty = 0, min_penalty = 0, ans = 0;
        for (int i = 0; i < customers.size(); i++) {
            penalty += customers[i] == 'N' ? 1 : -1;
            if (penalty < min_penalty) {
                min_penalty = penalty;
                ans = i + 1;
            }
        }
        return ans;
    }
};

func bestClosingTime(customers string) (ans int) {
penalty, minPenalty := 0, 0
for i, c := range customers {
if c == 'N' {
penalty++
} else {
penalty--
}
if penalty < minPenalty {
minPenalty = penalty
ans = i + 1
}
}
return
}

复杂度分析

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

相似题目

3694. 删除子字符串后不同的终点

分类题单

如何科学刷题？

我的题解精选（已分类）

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

LeetCode 每日一题题解
排序 + 贪心（Python/Java/C++/C/Go/JS/Rust）endlesscheng
2024年3月10日 12:26

排序 + 贪心（Python/Java/C++/C/Go/JS/Rust）

LeetCode 每日一题题解

作者 endlesscheng

2024年3月10日 12:26

本质是选一些数求和，为了让和最大，我们要选 $\textit{happiness}$ 最大的 $k$ 个数。

这 $k$ 个数要按照什么顺序选呢？

由于小的数减成 $0$ 就不再减少了，优先选大的数更好。

比如 $2,1,1$，如果按照 $1,1,2$ 的顺序选，答案为 $1+0+0=1$；但按照 $2,1,1$ 的顺序选，答案为 $2+0+0=2$，更优。

###py

class Solution:
    def maximumHappinessSum(self, happiness: List[int], k: int) -> int:
        happiness.sort(reverse=True)
        ans = 0
        for i, x in enumerate(happiness[:k]):
            if x <= i:
                break
            ans += x - i
        return ans

###java

class Solution {
    public long maximumHappinessSum(int[] happiness, int k) {
        Arrays.sort(happiness);
        int n = happiness.length;
        long ans = 0;
        for (int i = n - 1; i >= n - k && happiness[i] > n - 1 - i; i--) {
            ans += happiness[i] - (n - 1 - i);
        }
        return ans;
    }
}

###cpp

class Solution {
public:
    long long maximumHappinessSum(vector<int>& happiness, int k) {
        ranges::sort(happiness, greater());
        long long ans = 0;
        for (int i = 0; i < k && happiness[i] > i; i++) {
            ans += happiness[i] - i;
        }
        return ans;
    }
};

###c

int cmp(const void* a, const void* b) {
    return *(int*)b - *(int*)a;
}

long long maximumHappinessSum(int* happiness, int happinessSize, int k) {
    qsort(happiness, happinessSize, sizeof(int), cmp);
    long long ans = 0;
    for (int i = 0; i < k && happiness[i] > i; i++) {
        ans += happiness[i] - i;
    }
    return ans;
}

###go

func maximumHappinessSum(happiness []int, k int) (ans int64) {
slices.SortFunc(happiness, func(a, b int) int { return b - a })
for i, x := range happiness[:k] {
if x <= i {
break
}
ans += int64(x - i)
}
return
}

###js

var maximumHappinessSum = function(happiness, k) {
    happiness.sort((a, b) => b - a);
    let ans = 0;
    for (let i = 0; i < k && happiness[i] > i; i++) {
        ans += happiness[i] - i;
    }
    return ans;
};

###rust

impl Solution {
    pub fn maximum_happiness_sum(mut happiness: Vec<i32>, k: i32) -> i64 {
        happiness.sort_unstable_by_key(|x| -x);
        let mut ans = 0;
        for (i, &x) in happiness[..k as usize].iter().enumerate() {
            if x <= i as i32 {
                break;
            }
            ans += (x - i as i32) as i64;
        }
        ans
    }
}

复杂度分析

时间复杂度：$\mathcal{O}(n\log n)$，其中 $n$ 是 $\textit{happiness}$ 的长度。
空间复杂度：$\mathcal{O}(1)$。忽略排序的栈开销。Python 的切片可以用枚举代替。

分类题单

如何科学刷题？

我的题解精选（已分类）

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

LeetCode 每日一题题解
排序贪心（Python/Java/C++/C/Go/JS/Rust）endlesscheng
2024年3月10日 16:46

排序贪心（Python/Java/C++/C/Go/JS/Rust）

LeetCode 每日一题题解

作者 endlesscheng

2024年3月10日 16:46

既然同一个包裹中的苹果可以分装到不同的箱子中，那就先把所有苹果堆在一起，然后一个个地装箱。

为了少用箱子，要先装大箱子，再装小箱子。

注：题目保证可以将所有苹果重新分装到箱子中。

###py

class Solution:
    def minimumBoxes(self, apple: List[int], capacity: List[int]) -> int:
        s = sum(apple)  # 把所有苹果堆在一起
        capacity.sort(reverse=True)  # 先装大箱子，再装小箱子
        for i, x in enumerate(capacity):
            s -= x
            if s <= 0:  # 所有苹果都装入了箱子
                return i + 1  # 从 0 到 i 有 i+1 个箱子

###java

class Solution {
    public int minimumBoxes(int[] apple, int[] capacity) {
        int s = 0;
        for (int x : apple) {
            s += x; // 把所有苹果堆在一起
        }

        Arrays.sort(capacity);

        int m = capacity.length;
        int i = m - 1; // 先装大箱子，再装小箱子
        while (s > 0) { // 还有剩余苹果
            s -= capacity[i--]; // 使用一个箱子
        }
        return m - 1 - i;
    }
}

###cpp

class Solution {
public:
    int minimumBoxes(vector<int>& apple, vector<int>& capacity) {
        int s = reduce(apple.begin(), apple.end()); // 把所有苹果堆在一起
        ranges::sort(capacity, greater()); // 先装大箱子，再装小箱子
        int i = 0;
        while (s > 0) { // 还有剩余苹果
            s -= capacity[i++]; // 使用一个箱子
        }
        return i;
    }
};

###c

int cmp(const void* a, const void* b) {
    return *(int*)b - *(int*)a;
}

int minimumBoxes(int* apple, int appleSize, int* capacity, int capacitySize) {
    int s = 0;
    for (int i = 0; i < appleSize; i++) {
        s += apple[i]; // 把所有苹果堆在一起
    }

    qsort(capacity, capacitySize, sizeof(int), cmp); // 先装大箱子，再装小箱子

    int i = 0;
    while (s > 0) { // 还有剩余苹果
        s -= capacity[i++]; // 使用一个箱子
    }
    return i;
}

###go

func minimumBoxes(apple, capacity []int) int {
s := 0
for _, x := range apple {
s += x // 把所有苹果堆在一起
}
slices.SortFunc(capacity, func(a, b int) int { return b - a }) // 先装大箱子，再装小箱子
for i, c := range capacity {
s -= c
if s <= 0 { // 所有苹果都装入了箱子
return i + 1 // 从 0 到 i 有 i+1 个箱子
}
}
return -1
}

###js

var minimumBoxes = function(apple, capacity) {
    let s = _.sum(apple); // 把所有苹果堆在一起
    capacity.sort((a, b) => b - a); // 先装大箱子，再装小箱子
    let i = 0;
    while (s > 0) { // 还有剩余苹果
        s -= capacity[i++]; // 使用一个箱子
    }
    return i;
};

###rust

impl Solution {
    pub fn minimum_boxes(apple: Vec<i32>, mut capacity: Vec<i32>) -> i32 {
        let mut s = apple.iter().sum::<i32>(); // 把所有苹果堆在一起
        capacity.sort_unstable_by_key(|a| -a); // 先装大箱子，再装小箱子
        for (i, x) in capacity.iter().enumerate() {
            s -= x;
            if s <= 0 { // 所有苹果都装入了箱子
                return (i + 1) as _; // 从 0 到 i 有 i+1 个箱子
            }
        }
        unreachable!()
    }
}

复杂度分析

时间复杂度：$\mathcal{O}(n+m\log m)$，其中 $n$ 为 $\textit{apple}$ 的长度，$m$ 为 $\textit{capacity}$ 的长度。
空间复杂度：$\mathcal{O}(1)$。忽略排序的栈开销。

专题训练

见贪心题单的「§1.1 从最小/最大开始贪心」。

分类题单

如何科学刷题？

我的题解精选（已分类）

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

LeetCode 每日一题题解
排序 + 单调栈二分（Python/Java/C++/Go）endlesscheng
2021年10月31日 07:38

排序 + 单调栈二分（Python/Java/C++/Go）

LeetCode 每日一题题解

作者 endlesscheng

2021年10月31日 07:38

设参加的第二个活动的开始时间为 $\textit{startTime}$，那么第一个活动选哪个最好？

在结束时间小于 $\textit{startTime}$ 的活动中，选择价值最大的活动。

为了方便查找，先把 $\textit{events}$ 按照结束时间从小到大排序。

排序后，对比如下两个活动：

活动一：结束于 $3$ 时刻，价值 $999$。
活动二：结束于 $6$ 时刻，价值 $9$。

活动二的结束时间又晚，价值又小，全方面不如活动一，是垃圾数据，直接忽略。

换句话说，在遍历 $\textit{events}$ 的过程中（注意 $\textit{events}$ 已按照结束时间排序），只在遇到更大价值的活动时，才记录该活动。把这些活动记录到一个栈（列表）中，那么从栈底到栈顶，结束时间是递增的，价值也是递增的，非常适合二分查找。关于二分查找的原理，请看二分查找红蓝染色法【基础算法精讲 04】。

枚举第二个活动，在单调栈中二分查找结束时间严格小于 $\textit{startTime}$ 的最后一个活动，即为价值最大的第一个活动。如果没找到，那么只能选一个活动。

为了简化判断逻辑，可以在栈底加一个结束时间为 $0$，价值也为 $0$ 的哨兵。

写法一

class Solution:
    def maxTwoEvents(self, events: List[List[int]]) -> int:
        # 按照结束时间排序
        events.sort(key=lambda e: e[1])  

        # 从栈底到栈顶，结束时间递增，价值递增
        st = [(0, 0)]  # 栈底哨兵 
        ans = 0
        for start_time, end_time, value in events:
            # 二分查找最后一个结束时间 < start_time 的活动
            i = bisect_left(st, (start_time,)) - 1
            ans = max(ans, st[i][1] + value)
            # 遇到比栈顶更大的价值，入栈
            if value > st[-1][1]:
                st.append((end_time, value))
        return ans

class Solution {
    public int maxTwoEvents(int[][] events) {
        // 按照结束时间排序
        Arrays.sort(events, (a, b) -> a[1] - b[1]);

        // 从栈底到栈顶，结束时间递增，价值递增
        ArrayList<int[]> st = new ArrayList<>(); // (结束时间, 价值)
        st.add(new int[]{0, 0}); // 栈底哨兵

        int ans = 0;
        for (int[] e : events) {
            int i = search(st, e[0]);
            int value = e[2];
            ans = Math.max(ans, st.get(i)[1] + value);
            // 遇到比栈顶更大的价值，入栈
            if (value > st.getLast()[1]) {
                st.add(new int[]{e[1], value});
            }
        }
        return ans;
    }

    // 返回最后一个满足 st[i][0] < target 的 i
    private int search(List<int[]> st, int target) {
        int left = -1, right = st.size();
        while (left + 1 < right) { // 开区间二分
            int mid = left + (right - left) / 2;
            if (st.get(mid)[0] < target) {
                left = mid;
            } else {
                right = mid;
            }
        }
        return left;
    }
}

class Solution {
public:
    int maxTwoEvents(vector<vector<int>>& events) {
        // 按照结束时间排序
        ranges::sort(events, {}, [](auto& e) { return e[1]; });

        // 从栈底到栈顶，结束时间递增，价值递增
        vector<pair<int, int>> st = {{0, 0}}; // 栈底哨兵
        int ans = 0;
        for (auto& e : events) {
            int start_time = e[0], value = e[2];
            // 二分查找最后一个结束时间 < start_time 的活动
            auto it = --ranges::lower_bound(st, start_time, {}, &pair<int, int>::first);
            ans = max(ans, it->second + value);
            // 遇到比栈顶更大的价值，入栈
            if (value > st.back().second) {
                st.emplace_back(e[1], value);
            }
        }
        return ans;
    }
};

func maxTwoEvents(events [][]int) (ans int) {
// 按照结束时间排序
slices.SortFunc(events, func(a, b []int) int { return a[1] - b[1] })

// 从栈底到栈顶，结束时间递增，价值递增
type pair struct{ endTime, value int }
st := []pair{{}} // 栈底哨兵
for _, e := range events {
startTime, value := e[0], e[2]
// 二分查找最后一个结束时间 < startTime 的活动
i := sort.Search(len(st), func(i int) bool { return st[i].endTime >= startTime }) - 1
ans = max(ans, st[i].value+value)
// 遇到比栈顶更大的价值，入栈
if value > st[len(st)-1].value {
st = append(st, pair{e[1], value})
}
}
return
}

复杂度分析

时间复杂度：$\mathcal{O}(n\log n)$，其中 $n$ 是 $\textit{events}$ 的长度。
空间复杂度：$\mathcal{O}(n)$。

写法二：原地

也可以把 $\textit{events}$ 当作栈。

缺点是没法用哨兵。

class Solution:
    def maxTwoEvents(self, events: List[List[int]]) -> int:
        events.sort(key=lambda e: e[1])

        ans = size = 0  # 把 events 当作栈
        for start_time, end_time, value in events:
            i = bisect_left(events, (start_time,), hi=size) - 1
            if i >= 0:
                ans = max(ans, value + events[i][1])
            else:
                ans = max(ans, value)

            if size == 0 or value > events[size - 1][1]:
                events[size] = (end_time, value)
                size += 1
        return ans

class Solution {
    public int maxTwoEvents(int[][] events) {
        Arrays.sort(events, (a, b) -> a[1] - b[1]);

        int ans = 0;
        int size = 0; // 把 events 当作栈
        for (int[] e : events) {
            int i = search(events, size, e[0]);
            int value = e[2];
            if (i >= 0) {
                ans = Math.max(ans, value + events[i][2]);
            } else {
                ans = Math.max(ans, value);
            }

            if (size == 0 || value > events[size - 1][2]) {
                events[size++] = e;
            }
        }
        return ans;
    }

    // 返回最后一个满足 st[i][1] < target 的 i
    private int search(int[][] st, int right, int target) {
        int left = -1;
        while (left + 1 < right) { // 开区间二分
            int mid = left + (right - left) / 2;
            if (st[mid][1] < target) {
                left = mid;
            } else {
                right = mid;
            }
        }
        return left;
    }
}

class Solution {
public:
    int maxTwoEvents(vector<vector<int>>& events) {
        ranges::sort(events, {}, [](auto& e) { return e[1]; });

        int ans = 0, size = 0; // 把 events 当作栈
        for (auto& e : events) {
            int start_time = e[0], value = e[2];
            auto it = ranges::lower_bound(events.begin(), events.begin() + size, start_time, {}, [](auto& e) { return e[1]; });
            if (it != events.begin()) {
                ans = max(ans, value + (*--it)[2]);
            } else {
                ans = max(ans, value);
            }

            if (size == 0 || value > events[size - 1][2]) {
                events[size++] = e;
            }
        }
        return ans;
    }
};

func maxTwoEvents(events [][]int) (ans int) {
slices.SortFunc(events, func(a, b []int) int { return a[1] - b[1] })

st := events[:0] // 把 events 当作栈
for _, e := range events {
startTime, value := e[0], e[2]
i := sort.Search(len(st), func(i int) bool { return st[i][1] >= startTime }) - 1
if i >= 0 {
ans = max(ans, value+events[i][2])
} else {
ans = max(ans, value)
}
if len(st) == 0 || value > st[len(st)-1][2] {
st = append(st, e)
}
}
return
}

复杂度分析

时间复杂度：$\mathcal{O}(n\log n)$，其中 $n$ 是 $\textit{events}$ 的长度。
空间复杂度：$\mathcal{O}(1)$。忽略排序的栈开销。

专题训练

单调栈题单。
动态规划题单的「§7.2 不相交区间」。

分类题单

如何科学刷题？

我的题解精选（已分类）

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

普通视图

复杂度分析

相似题目

分类题单

复杂度分析

专题训练

分类题单

方法一：递归递归，有递有归

复杂度分析

方法二：自底向上

复杂度分析

分类题单

一、寻找子问题

二、状态定义与状态转移方程

三、递归搜索 + 保存递归返回值 = 记忆化搜索

复杂度分析

四、1:1 翻译成递推

复杂度分析

五、空间优化

复杂度分析

专题训练

分类题单

复杂度分析

专题训练

分类题单

方法一：BFS

复杂度分析

方法二：DFS

复杂度分析

专题训练

分类题单

复杂度分析

专题训练

分类题单

复杂度分析

专题训练

分类题单

方法一：记忆化搜索（轮廓线 DP）

复杂度分析

方法二：递推

复杂度分析

方法三：矩阵快速幂

复杂度分析

相似题目

专题训练

分类题单

方法一：哈希集合（暴力）

复杂度分析

方法二：摩尔投票

复杂度分析

方法三：检查邻近元素

复杂度分析

方法四：随机

复杂度分析

专题训练

分类题单

复杂度分析

分类题单

幻方正中心一定是 5

无需计算第三行的和，第三列的和

无需计算对角线的和

复杂度分析

分类题单

优化前

复杂度分析

优化一：减少重复搜索

优化二：减少更多重复搜索

复杂度分析

优化三：位运算

复杂度分析

专题训练

分类题单

复杂度分析

相似题目

分类题单

复杂度分析

相似题目

分类题单

题意

思路