❌

普通视图

发现新文章，点击刷新页面。
今天 — 2026年2月8日LeetCode 每日一题题解

每日一题-平衡二叉树🟢

✇LeetCode 每日一题题解
2026年2月8日 00:00

给定一个二叉树，判断它是否是 平衡二叉树  

 

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：true

示例 2：

输入：root = [1,2,2,3,3,null,null,4,4]
输出：false

示例 3：

输入：root = []
输出：true

 

提示：

  • 树中的节点数在范围 [0, 5000] 内
  • -104 <= Node.val <= 104

【视频】如何灵活运用递归？（Python/Java/C++/C/Go/JS/Rust）

✇LeetCode 每日一题题解
作者 endlesscheng
2022年12月10日 18:20

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

【基础算法精讲 09】

【基础算法精讲 10】

答疑

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

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

写法一

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

写法二

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

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

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

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

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

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

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

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

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

    return MAX(left_h, right_h) + 1;
}

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

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

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

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

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

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

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

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

复杂度分析

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

分类题单

如何科学刷题？

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

我的题解精选（已分类）

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

平衡二叉树

✇LeetCode 每日一题题解
作者 LeetCode-Solution
2020年8月16日 23:00

前言

这道题中的平衡二叉树的定义是：二叉树的每个节点的左右子树的高度差的绝对值不超过 $1$，则二叉树是平衡二叉树。根据定义，一棵二叉树是平衡二叉树，当且仅当其所有子树也都是平衡二叉树，因此可以使用递归的方式判断二叉树是不是平衡二叉树，递归的顺序可以是自顶向下或者自底向上。

方法一：自顶向下的递归

定义函数 $\texttt{height}$，用于计算二叉树中的任意一个节点 $p$ 的高度：

$$
\texttt{height}(p) =
\begin{cases}
0 & p \text{ 是空节点}\
\max(\texttt{height}(p.\textit{left}), \texttt{height}(p.\textit{right}))+1 & p \text{ 是非空节点}
\end{cases}
$$

有了计算节点高度的函数，即可判断二叉树是否平衡。具体做法类似于二叉树的前序遍历，即对于当前遍历到的节点，首先计算左右子树的高度，如果左右子树的高度差是否不超过 $1$，再分别递归地遍历左右子节点，并判断左子树和右子树是否平衡。这是一个自顶向下的递归的过程。

<fig1,fig2,fig3,fig4,fig5,fig6,fig7,fig8,fig9,fig10,fig11,fig12,fig13,fig14,fig15,fig16,fig17,fig18,fig19,fig20,fig21,fig22,fig23,fig24,fig25,fig26,fig27,fig28,fig29,fig30,fig31>

###Java

class Solution {
    public boolean isBalanced(TreeNode root) {
        if (root == null) {
            return true;
        } else {
            return Math.abs(height(root.left) - height(root.right)) <= 1 && isBalanced(root.left) && isBalanced(root.right);
        }
    }

    public int height(TreeNode root) {
        if (root == null) {
            return 0;
        } else {
            return Math.max(height(root.left), height(root.right)) + 1;
        }
    }
}

###C++

class Solution {
public:
    int height(TreeNode* root) {
        if (root == NULL) {
            return 0;
        } else {
            return max(height(root->left), height(root->right)) + 1;
        }
    }

    bool isBalanced(TreeNode* root) {
        if (root == NULL) {
            return true;
        } else {
            return abs(height(root->left) - height(root->right)) <= 1 && isBalanced(root->left) && isBalanced(root->right);
        }
    }
};

###Python

class Solution:
    def isBalanced(self, root: TreeNode) -> bool:
        def height(root: TreeNode) -> int:
            if not root:
                return 0
            return max(height(root.left), height(root.right)) + 1

        if not root:
            return True
        return abs(height(root.left) - height(root.right)) <= 1 and self.isBalanced(root.left) and self.isBalanced(root.right)

###C

int height(struct TreeNode* root) {
    if (root == NULL) {
        return 0;
    } else {
        return fmax(height(root->left), height(root->right)) + 1;
    }
}

bool isBalanced(struct TreeNode* root) {
    if (root == NULL) {
        return true;
    } else {
        return fabs(height(root->left) - height(root->right)) <= 1 && isBalanced(root->left) && isBalanced(root->right);
    }
}

###golang

func isBalanced(root *TreeNode) bool {
    if root == nil {
        return true
    }
    return abs(height(root.Left) - height(root.Right)) <= 1 && isBalanced(root.Left) && isBalanced(root.Right)
}

func height(root *TreeNode) int {
    if root == nil {
        return 0
    }
    return max(height(root.Left), height(root.Right)) + 1
}

func max(x, y int) int {
    if x > y {
        return x
    }
    return y
}

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

复杂度分析

  • 时间复杂度：$O(n^2)$，其中 $n$ 是二叉树中的节点个数。
    最坏情况下，二叉树是满二叉树，需要遍历二叉树中的所有节点，时间复杂度是 $O(n)$。
    对于节点 $p$，如果它的高度是 $d$，则 $\texttt{height}(p)$ 最多会被调用 $d$ 次（即遍历到它的每一个祖先节点时）。对于平均的情况，一棵树的高度 $h$ 满足 $O(h)=O(\log n)$，因为 $d \leq h$，所以总时间复杂度为 $O(n \log n)$。对于最坏的情况，二叉树形成链式结构，高度为 $O(n)$，此时总时间复杂度为 $O(n^2)$。

  • 空间复杂度：$O(n)$，其中 $n$ 是二叉树中的节点个数。空间复杂度主要取决于递归调用的层数，递归调用的层数不会超过 $n$。

方法二：自底向上的递归

方法一由于是自顶向下递归，因此对于同一个节点，函数 $\texttt{height}$ 会被重复调用，导致时间复杂度较高。如果使用自底向上的做法，则对于每个节点，函数 $\texttt{height}$ 只会被调用一次。

自底向上递归的做法类似于后序遍历，对于当前遍历到的节点，先递归地判断其左右子树是否平衡，再判断以当前节点为根的子树是否平衡。如果一棵子树是平衡的，则返回其高度（高度一定是非负整数），否则返回 $-1$。如果存在一棵子树不平衡，则整个二叉树一定不平衡。

<fig1,fig2,fig3,fig4,fig5,fig6,fig7,fig8,fig9,fig10,fig11,fig12,fig13,fig14,fig15,fig16,fig17,fig18,fig19,fig20,fig21,fig22,fig23,fig24,fig25,fig26,fig27,fig28,fig29,fig30,fig31,fig32>

###Java

class Solution {
    public boolean isBalanced(TreeNode root) {
        return height(root) >= 0;
    }

    public int height(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftHeight = height(root.left);
        int rightHeight = height(root.right);
        if (leftHeight == -1 || rightHeight == -1 || Math.abs(leftHeight - rightHeight) > 1) {
            return -1;
        } else {
            return Math.max(leftHeight, rightHeight) + 1;
        }
    }
}

###C++

class Solution {
public:
    int height(TreeNode* root) {
        if (root == NULL) {
            return 0;
        }
        int leftHeight = height(root->left);
        int rightHeight = height(root->right);
        if (leftHeight == -1 || rightHeight == -1 || abs(leftHeight - rightHeight) > 1) {
            return -1;
        } else {
            return max(leftHeight, rightHeight) + 1;
        }
    }

    bool isBalanced(TreeNode* root) {
        return height(root) >= 0;
    }
};

###Python

class Solution:
    def isBalanced(self, root: TreeNode) -> bool:
        def height(root: TreeNode) -> int:
            if not root:
                return 0
            leftHeight = height(root.left)
            rightHeight = height(root.right)
            if leftHeight == -1 or rightHeight == -1 or abs(leftHeight - rightHeight) > 1:
                return -1
            else:
                return max(leftHeight, rightHeight) + 1

        return height(root) >= 0

###C

int height(struct TreeNode* root) {
    if (root == NULL) {
        return 0;
    }
    int leftHeight = height(root->left);
    int rightHeight = height(root->right);
    if (leftHeight == -1 || rightHeight == -1 || fabs(leftHeight - rightHeight) > 1) {
        return -1;
    } else {
        return fmax(leftHeight, rightHeight) + 1;
    }
}

bool isBalanced(struct TreeNode* root) {
    return height(root) >= 0;
}

###golang

func isBalanced(root *TreeNode) bool {
    return height(root) >= 0
}

func height(root *TreeNode) int {
    if root == nil {
        return 0
    }
    leftHeight := height(root.Left)
    rightHeight := height(root.Right)
    if leftHeight == -1 || rightHeight == -1 || abs(leftHeight - rightHeight) > 1 {
        return -1
    }
    return max(leftHeight, rightHeight) + 1
}

func max(x, y int) int {
    if x > y {
        return x
    }
    return y
}

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

复杂度分析

  • 时间复杂度：$O(n)$，其中 $n$ 是二叉树中的节点个数。使用自底向上的递归，每个节点的计算高度和判断是否平衡都只需要处理一次，最坏情况下需要遍历二叉树中的所有节点，因此时间复杂度是 $O(n)$。

  • 空间复杂度：$O(n)$，其中 $n$ 是二叉树中的节点个数。空间复杂度主要取决于递归调用的层数，递归调用的层数不会超过 $n$。

110. 平衡二叉树（先序或后序遍历，清晰图解）

✇LeetCode 每日一题题解
作者 jyd
2019年6月13日 16:39

解题思路：

以下两种方法均基于以下性质推出：当前树的深度 等于 左子树的深度 与 右子树的深度 中的 最大值 $+1$ 。

Picture1.png{:width=450}

方法一：后序遍历 + 剪枝 （从底至顶）

此方法为本题的最优解法，但剪枝的方法不易第一时间想到。

思路是对二叉树做后序遍历，从底至顶返回子树深度，若判定某子树不是平衡树则 “剪枝” ，直接向上返回。

算法流程：

函数 recur(root) ：

  • 返回值：
    1. 当节点root 左 / 右子树的深度差 $\leq 1$ ：则返回当前子树的深度，即节点 root 的左 / 右子树的深度最大值 $+1$ （ max(left, right) + 1 ）。
    2. 当节点root 左 / 右子树的深度差 $> 1$ ：则返回 $-1$ ，代表 此子树不是平衡树 。
  • 终止条件：
    1. 当 root 为空：说明越过叶节点，因此返回高度 $0$ 。
    2. 当左（右）子树深度为 $-1$ ：代表此树的 左（右）子树 不是平衡树，因此剪枝，直接返回 $-1$ 。

函数 isBalanced(root) ：

  • 返回值： 若 recur(root) != -1 ，则说明此树平衡，返回 $true$ ； 否则返回 $false$ 。

<Picture3.png,Picture4.png,Picture5.png,Picture6.png,Picture7.png,Picture8.png,Picture9.png,Picture10.png,Picture11.png,Picture12.png>

代码：

###Python

class Solution:
    def isBalanced(self, root: Optional[TreeNode]) -> bool:
        def recur(root):
            if not root: return 0
            left = recur(root.left)
            if left == -1: return -1
            right = recur(root.right)
            if right == -1: return -1
            return max(left, right) + 1 if abs(left - right) <= 1 else -1

        return recur(root) != -1

###Java

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

    private int recur(TreeNode root) {
        if (root == null) return 0;
        int left = recur(root.left);
        if (left == -1) return -1;
        int right = recur(root.right);
        if (right == -1) return -1;
        return Math.abs(left - right) < 2 ? Math.max(left, right) + 1 : -1;
    }
}

###C++

class Solution {
public:
    bool isBalanced(TreeNode* root) {
        return recur(root) != -1;
    }
private:
    int recur(TreeNode* root) {
        if (root == nullptr) return 0;
        int left = recur(root->left);
        if (left == -1) return -1;
        int right = recur(root->right);
        if (right == -1) return -1;
        return abs(left - right) < 2 ? max(left, right) + 1 : -1;
    }
};

复杂度分析：

  • 时间复杂度 $O(N)$： $N$ 为树的节点数；最差情况下，需要递归遍历树的所有节点。
  • 空间复杂度 $O(N)$： 最差情况下（树退化为链表时），系统递归需要使用 $O(N)$ 的栈空间。

方法二：先序遍历 + 判断深度 （从顶至底）

此方法容易想到，但会产生大量重复计算，时间复杂度较高。

思路是构造一个获取当前子树的深度的函数 depth(root) ，通过比较某子树的左右子树的深度差 abs(depth(root.left) - depth(root.right)) <= 1 是否成立，来判断某子树是否是二叉平衡树。若所有子树都平衡，则此树平衡。

算法流程：

函数 isBalanced(root) ： 判断树 root 是否平衡

  • 特例处理： 若树根节点 root 为空，则直接返回 $true$ 。
  • 返回值： 所有子树都需要满足平衡树性质，因此以下三者使用与逻辑 $&&$ 连接。
    1. abs(self.depth(root.left) - self.depth(root.right)) <= 1 ：判断 当前子树 是否是平衡树。
    2. self.isBalanced(root.left) ： 先序遍历递归，判断 当前子树的左子树 是否是平衡树。
    3. self.isBalanced(root.right) ： 先序遍历递归，判断 当前子树的右子树 是否是平衡树。

函数 depth(root) ： 计算树 root 的深度

  • 终止条件： 当 root 为空，即越过叶子节点，则返回高度 $0$ 。
  • 返回值： 返回左 / 右子树的深度的最大值 $+1$ 。

<Picture13.png,Picture14.png,Picture15.png,Picture16.png,Picture17.png,Picture18.png>

代码：

###Python

class Solution:
    def isBalanced(self, root: Optional[TreeNode]) -> bool:
        if not root: return True
        return abs(self.depth(root.left) - self.depth(root.right)) <= 1 and \
            self.isBalanced(root.left) and self.isBalanced(root.right)

    def depth(self, root):
        if not root: return 0
        return max(self.depth(root.left), self.depth(root.right)) + 1

###Java

class Solution {
    public boolean isBalanced(TreeNode root) {
        if (root == null) return true;
        return Math.abs(depth(root.left) - depth(root.right)) <= 1 && isBalanced(root.left) && isBalanced(root.right);
    }

    private int depth(TreeNode root) {
        if (root == null) return 0;
        return Math.max(depth(root.left), depth(root.right)) + 1;
    }
}

###C++

class Solution {
public:
    bool isBalanced(TreeNode* root) {
        if (root == nullptr) return true;
        return abs(depth(root->left) - depth(root->right)) <= 1 && isBalanced(root->left) && isBalanced(root->right);
    }
private:
    int depth(TreeNode* root) {
        if (root == nullptr) return 0;
        return max(depth(root->left), depth(root->right)) + 1;
    }
};

复杂度分析：

  • 时间复杂度 $O(N \log N)$： 最差情况下（为 “满二叉树” 时）， isBalanced(root) 遍历树所有节点，判断每个节点的深度 depth(root) 需要遍历 各子树的所有节点 。
    • 满二叉树高度的复杂度 $O(log N)$ ，将满二叉树按层分为 $log (N+1)$ 层。
    • 通过调用 depth(root) ，判断二叉树各层的节点的对应子树的深度，需遍历节点数量为 $N \times 1, \frac{N-1}{2} \times 2, \frac{N-3}{4} \times 4, \frac{N-7}{8} \times 8, ..., 1 \times \frac{N+1}{2}$ 。因此各层执行 depth(root) 的时间复杂度为 $O(N)$ （每层开始，最多遍历 $N$ 个节点，最少遍历 $\frac{N+1}{2}$ 个节点）。

    其中，$\frac{N-3}{4} \times 4$ 代表从此层开始总共需遍历 $N-3$ 个节点，此层共有 $4$ 个节点，因此每个子树需遍历 $\frac{N-3}{4}$ 个节点。

    • 因此，总体时间复杂度 $=$ 每层执行复杂度 $\times$ 层数复杂度 = $O(N \times \log N)$ 。

Picture2.png{:width=550}

  • 空间复杂度 $O(N)$： 最差情况下（树退化为链表时），系统递归需要使用 $O(N)$ 的栈空间。

link

本学习计划配有代码仓，内含测试样例与数据结构封装，便于本地调试。可前往我的个人主页获取。

昨天 — 2026年2月7日LeetCode 每日一题题解

每日一题-使字符串平衡的最少删除次数🟡

✇LeetCode 每日一题题解
2026年2月7日 00:00

给你一个字符串 s ，它仅包含字符 'a' 和 'b' 。

你可以删除 s 中任意数目的字符，使得 s 平衡 。当不存在下标对 (i,j) 满足 i < j ，且 s[i] = 'b' 的同时 s[j]= 'a' ，此时认为 s 是 平衡 的。

请你返回使 s 平衡 的 最少 删除次数。

 

示例 1：

输入：s = "aababbab"
输出：2
解释：你可以选择以下任意一种方案：
下标从 0 开始，删除第 2 和第 6 个字符（"aababbab" -> "aaabbb"），
下标从 0 开始，删除第 3 和第 6 个字符（"aababbab" -> "aabbbb"）。

示例 2：

输入：s = "bbaaaaabb"
输出：2
解释：唯一的最优解是删除最前面两个字符。

 

提示：

  • 1 <= s.length <= 105
  • s[i] 要么是 'a' 要么是 'b' 。

[Python3/Java/C++/Go] 一题双解：动态规划 & 枚举+前缀和（清晰题解）

✇LeetCode 每日一题题解
作者 lcbin
2023年3月6日 08:50

方法一：动态规划

我们定义 $f[i]$ 表示前 $i$ 个字符中，删除最少的字符数，使得字符串平衡。初始时 $f[0]=0$。答案为 $f[n]$。

我们遍历字符串 $s$，维护变量 $b$，表示当前遍历到的位置之前的字符中，字符 $b$ 的个数。

  • 如果当前字符为 'b'，此时不影响前 $i$ 个字符的平衡性，因此 $f[i]=f[i-1]$，然后我们更新 $b \leftarrow b+1$。
  • 如果当前字符为 'a'，此时我们可以选择删除当前字符，那么有 $f[i]=f[i-1]+1$；也可以选择删除之前的字符 $b$，那么有 $f[i]=b$。因此我们取两者的最小值，即 $f[i]=\min(f[i-1]+1,b)$。

综上，我们可以得到状态转移方程：

$$
f[i]=\begin{cases}
f[i-1], & s[i-1]='b'\
\min(f[i-1]+1,b), & s[i-1]='a'
\end{cases}
$$

最终答案为 $f[n]$。

class Solution:
    def minimumDeletions(self, s: str) -> int:
        n = len(s)
        f = [0] * (n + 1)
        b = 0
        for i, c in enumerate(s, 1):
            if c == 'b':
                f[i] = f[i - 1]
                b += 1
            else:
                f[i] = min(f[i - 1] + 1, b)
        return f[n]

class Solution {
    public int minimumDeletions(String s) {
        int n = s.length();
        int[] f = new int[n + 1];
        int b = 0;
        for (int i = 1; i <= n; ++i) {
            if (s.charAt(i - 1) == 'b') {
                f[i] = f[i - 1];
                ++b;
            } else {
                f[i] = Math.min(f[i - 1] + 1, b);
            }
        }
        return f[n];
    }
}

class Solution {
public:
    int minimumDeletions(string s) {
        int n = s.size();
        int f[n + 1];
        memset(f, 0, sizeof(f));
        int b = 0;
        for (int i = 1; i <= n; ++i) {
            if (s[i - 1] == 'b') {
                f[i] = f[i - 1];
                ++b;
            } else {
                f[i] = min(f[i - 1] + 1, b);
            }
        }
        return f[n];
    }
};

func minimumDeletions(s string) int {
n := len(s)
f := make([]int, n+1)
b := 0
for i, c := range s {
i++
if c == 'b' {
f[i] = f[i-1]
b++
} else {
f[i] = min(f[i-1]+1, b)
}
}
return f[n]
}

func min(a, b int) int {
if a < b {
return a
}
return b
}

function minimumDeletions(s: string): number {
    const n = s.length;
    const f = new Array(n + 1).fill(0);
    let b = 0;
    for (let i = 1; i <= n; ++i) {
        if (s.charAt(i - 1) === 'b') {
            f[i] = f[i - 1];
            ++b;
        } else {
            f[i] = Math.min(f[i - 1] + 1, b);
        }
    }
    return f[n];
}

我们注意到，状态转移方程中只与前一个状态以及变量 $b$ 有关，因此我们可以仅用一个答案变量 $ans$ 维护当前的 $f[i]$，并不需要开辟数组 $f$。

class Solution:
    def minimumDeletions(self, s: str) -> int:
        ans = b = 0
        for c in s:
            if c == 'b':
                b += 1
            else:
                ans = min(ans + 1, b)
        return ans

class Solution {
    public int minimumDeletions(String s) {
        int n = s.length();
        int ans = 0, b = 0;
        for (int i = 0; i < n; ++i) {
            if (s.charAt(i) == 'b') {
                ++b;
            } else {
                ans = Math.min(ans + 1, b);
            }
        }
        return ans;
    }
}

class Solution {
public:
    int minimumDeletions(string s) {
        int ans = 0, b = 0;
        for (char& c : s) {
            if (c == 'b') {
                ++b;
            } else {
                ans = min(ans + 1, b);
            }
        }
        return ans;
    }
};

func minimumDeletions(s string) int {
ans, b := 0, 0
for _, c := range s {
if c == 'b' {
b++
} else {
ans = min(ans+1, b)
}
}
return ans
}

func min(a, b int) int {
if a < b {
return a
}
return b
}

function minimumDeletions(s: string): number {
    const n = s.length;
    let ans = 0,
        b = 0;
    for (let i = 0; i < n; ++i) {
        if (s.charAt(i) === 'b') {
            ++b;
        } else {
            ans = Math.min(ans + 1, b);
        }
    }
    return ans;
}

时间复杂度 $O(n)$，空间复杂度 $O(1)$。其中 $n$ 为字符串 $s$ 的长度。

方法二：枚举 + 前缀和

我们可以枚举字符串 $s$ 中的每一个位置 $i$，将字符串 $s$ 分成两部分，分别为 $s[0,..,i-1]$ 和 $s[i+1,..n-1]$，要使得字符串平衡，我们在当前位置 $i$ 需要删除的字符数为 $s[0,..,i-1]$ 中字符 $b$ 的个数加上 $s[i+1,..n-1]$ 中字符 $a$ 的个数。

因此，我们维护两个变量 $lb$ 和 $ra$ 分别表示 $s[0,..,i-1]$ 中字符 $b$ 的个数以及 $s[i+1,..n-1]$ 中字符 $a$ 的个数，那么我们需要删除的字符数为 $lb+ra$。枚举过程中，更新变量 $lb$ 和 $ra$。

class Solution:
    def minimumDeletions(self, s: str) -> int:
        lb, ra = 0, s.count('a')
        ans = len(s)
        for c in s:
            ra -= c == 'a'
            ans = min(ans, lb + ra)
            lb += c == 'b'
        return ans

class Solution {
    public int minimumDeletions(String s) {
        int lb = 0, ra = 0;
        int n = s.length();
        for (int i = 0; i < n; ++i) {
            if (s.charAt(i) == 'a') {
                ++ra;
            }
        }
        int ans = n;
        for (int i = 0; i < n; ++i) {
            ra -= (s.charAt(i) == 'a' ? 1 : 0);
            ans = Math.min(ans, lb + ra);
            lb += (s.charAt(i) == 'b' ? 1 : 0);
        }
        return ans;
    }
}

class Solution {
public:
    int minimumDeletions(string s) {
        int lb = 0, ra = count(s.begin(), s.end(), 'a');
        int ans = ra;
        for (char& c : s) {
            ra -= c == 'a';
            ans = min(ans, lb + ra);
            lb += c == 'b';
        }
        return ans;
    }
};

func minimumDeletions(s string) int {
lb, ra := 0, strings.Count(s, "a")
ans := ra
for _, c := range s {
if c == 'a' {
ra--
}
if t := lb + ra; ans > t {
ans = t
}
if c == 'b' {
lb++
}
}
return ans
}

function minimumDeletions(s: string): number {
    let lb = 0,
        ra = 0;
    const n = s.length;
    for (let i = 0; i < n; ++i) {
        if (s.charAt(i) === 'a') {
            ++ra;
        }
    }
    let ans = n;
    for (let i = 0; i < n; ++i) {
        ra -= s.charAt(i) === 'a' ? 1 : 0;
        ans = Math.min(ans, lb + ra);
        lb += s.charAt(i) === 'b' ? 1 : 0;
    }
    return ans;
}

时间复杂度 $O(n)$，空间复杂度 $O(1)$。其中 $n$ 为字符串 $s$ 的长度。

有任何问题，欢迎评论区交流，欢迎评论区提供其它解题思路（代码），也可以点个赞支持一下作者哈😄~

前后缀分解，一张图秒懂！（附动态规划）Python/Java/C++/Go

✇LeetCode 每日一题题解
作者 endlesscheng
2023年3月5日 22:02

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

1653-2-cut3.png

答疑

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

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

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

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

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

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

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

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

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

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

复杂度分析

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

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

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

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

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

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

  • 如果第 $i$ 个字母是 $\text{`b'}$，则 $f_i = f_{i-1}$；
  • 如果第 $i$ 个字母是 $\text{`a'}$，则 $f_i = \min(f_{i-1}+1,\textit{cntB}_i)$。
class Solution:
    def minimumDeletions(self, s: str) -> int:
        f = cnt_b = 0
        for c in s:
            if c == 'b':
                cnt_b += 1  # f 值不变
            else:
                f = min(f + 1, cnt_b)
        return f

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

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

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

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

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

这两种情况可以合并成：

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

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

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

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

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

复杂度分析

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

专题训练

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

分类题单

如何科学刷题？

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

我的题解精选（已分类）

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

使字符串平衡的最少删除次数

✇LeetCode 每日一题题解
作者 LeetCode-Solution
2023年3月4日 18:36

方法一：枚举

思路

通过删除部分字符串，使得字符串达到下列三种情况之一，即为平衡状态：

  1. 字符串全为 $\text{``a''}$；
  2. 字符串全为 $\text{``b''}$；
  3. 字符串既有 $\text{a''}$ 也有 $\text{b''}$，且所有 $\text{a''}$ 都在所有 $\text{b''}$ 左侧。

其中，为了达到第 $1$ 种情况，最少需要删除所有的 $\text{b''}$。为了达到第 $2$ 种情况，最少需要删除所有的 $\text{a''}$。而第 $3$ 种情况，可以在原字符串相邻的两个字符之间划一条间隔，删除间隔左侧所有的 $\text{b''}$ 和间隔右侧所有的 $\text{a''}$ 即可达到。用 $\textit{leftb}$ 表示间隔左侧的 $\text{b''}$ 的数目，$\textit{righta}$ 表示间隔左侧的 $\text{a''}$ 的数目，$\textit{leftb}+\textit{righta}$ 即为当前划分的间隔下最少需要删除的字符数。这样的间隔一共有 $n-1$ 种，其中 $n$ 是 $s$ 的长度。遍历字符串 $s$，即可以遍历 $n-1$ 种间隔，同时更新 $\textit{leftb}$ 和 $\textit{righta}$ 的数目。而上文讨论的前两种情况，其实就是间隔位于首字符前和末字符后的两种特殊情况，可以加入第 $3$ 种情况一并计算。

代码

###Python

class Solution:
    def minimumDeletions(self, s: str) -> int:
        leftb, righta = 0, s.count('a')
        res = righta
        for c in s:
            if c == 'a':
                righta -= 1
            else:
                leftb += 1
            res = min(res, leftb + righta)
        return res

###Java

class Solution {
    public int minimumDeletions(String s) {
        int leftb = 0, righta = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == 'a') {
                righta++;
            }
        }
        int res = righta;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == 'a') {
                righta--;
            } else {
                leftb++;
            }
            res = Math.min(res, leftb + righta);
        }
        return res;
    }
}

###C#

public class Solution {
    public int MinimumDeletions(string s) {
        int leftb = 0, righta = 0;
        foreach (char c in s) {
            if (c == 'a') {
                righta++;
            }
        }
        int res = righta;
        foreach (char c in s) {
            if (c == 'a') {
                righta--;
            } else {
                leftb++;
            }
            res = Math.Min(res, leftb + righta);
        }
        return res;
    }
}

###C++

class Solution {
public:
    int minimumDeletions(string s) {
        int leftb = 0, righta = 0;
        for (int i = 0; i < s.size(); i++) {
            if (s[i] == 'a') {
                righta++;
            }
        }
        int res = righta;
        for (int i = 0; i < s.size(); i++) {
            char c = s[i];
            if (c == 'a') {
                righta--;
            } else {
                leftb++;
            }
            res = min(res, leftb + righta);
        }
        return res;
    }
};

###C

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

int minimumDeletions(char * s) {
    int len = strlen(s);
    int leftb = 0, righta = 0;
    for (int i = 0; i < len; i++) {
        if (s[i] == 'a') {
            righta++;
        }
    }
    int res = righta;
    for (int i = 0; i < len; i++) {
        char c = s[i];
        if (c == 'a') {
            righta--;
        } else {
            leftb++;
        }
        res = MIN(res, leftb + righta);
    }
    return res;
}

###JavaScript

var minimumDeletions = function(s) {
    let leftb = 0, righta = 0;
    for (let i = 0; i < s.length; i++) {
        if (s[i] === 'a') {
            righta++;
        }
    }
    let res = righta;
    for (let i = 0; i < s.length; i++) {
        const c = s[i];
        if (c === 'a') {
            righta--;
        } else {
            leftb++;
        }
        res = Math.min(res, leftb + righta);
    }
    return res;
};

###go

func minimumDeletions(s string) int {
    leftb := 0
    righta := 0
    for _, c := range s {
        if c == 'a' {
            righta++
        }
    }
    res := righta
    for _, c := range s {
        if c == 'a' {
            righta--
        } else {
            leftb++
        }
        res = min(res, leftb+righta)
    }
    return res
}

func min(a, b int) int {
    if a > b {
        return b
    }
    return a
}

复杂度分析

  • 时间复杂度：$O(n)$，其中 $n$ 是 $s$ 的长度。需要遍历两遍 $s$，第一遍计算出 $s$ 中 $\text{``a''}$ 的数量，第二遍遍历所有的间隔，求出最小需要删除的字符数。

  • 空间复杂度：$O(1)$，只需要常数空间。

昨天以前LeetCode 每日一题题解

每日一题-转换数组🟢

✇LeetCode 每日一题题解
2026年2月5日 00:00

给你一个整数数组 nums，它表示一个循环数组。请你遵循以下规则创建一个大小 相同 的新数组 result ：

对于每个下标 i（其中 0 <= i < nums.length），独立执行以下操作：
  • 如果 nums[i] > 0：从下标 i 开始，向 右 移动 nums[i] 步，在循环数组中落脚的下标对应的值赋给 result[i]。
  • 如果 nums[i] < 0：从下标 i 开始，向 左 移动 abs(nums[i]) 步，在循环数组中落脚的下标对应的值赋给 result[i]。
  • 如果 nums[i] == 0：将 nums[i] 的值赋给 result[i]。

返回新数组 result。

注意：由于 nums 是循环数组，向右移动超过最后一个元素时将回到开头，向左移动超过第一个元素时将回到末尾。

 

示例 1：

输入： nums = [3,-2,1,1]

输出： [1,1,1,3]

解释：

  • 对于 nums[0] 等于 3，向右移动 3 步到 nums[3]，因此 result[0] 为 1。
  • 对于 nums[1] 等于 -2，向左移动 2 步到 nums[3]，因此 result[1] 为 1。
  • 对于 nums[2] 等于 1，向右移动 1 步到 nums[3]，因此 result[2] 为 1。
  • 对于 nums[3] 等于 1，向右移动 1 步到 nums[0]，因此 result[3] 为 3。

示例 2：

输入： nums = [-1,4,-1]

输出： [-1,-1,4]

解释：

  • 对于 nums[0] 等于 -1，向左移动 1 步到 nums[2]，因此 result[0] 为 -1。
  • 对于 nums[1] 等于 4，向右移动 4 步到 nums[2]，因此 result[1] 为 -1。
  • 对于 nums[2] 等于 -1，向左移动 1 步到 nums[1]，因此 result[2] 为 4。

 

提示：

  • 1 <= nums.length <= 100
  • -100 <= nums[i] <= 100

3379. 转换数组

✇LeetCode 每日一题题解
作者 stormsunshine
2024年12月8日 21:16

解法

思路和算法

根据题意模拟，计算结果数组 $\textit{result}$ 即可。

用 $n$ 表示数组 $\textit{nums}$ 的长度。对于 $0 \le i < n$ 的每个下标 $i$，计算 $\textit{result}[i]$ 的方法如下。

  • 当 $\textit{nums}[i] > 0$ 时，$\textit{result}[i]$ 的值等于数组 $\textit{nums}$ 的下标 $i$ 向右移动 $\textit{nums}[i]$ 的下标处的值，即数组 $\textit{nums}[i]$ 的下标 $i + \textit{nums}[i]$ 对应的范围 $[0, n - 1]$ 中的下标。

  • 当 $\textit{nums}[i] < 0$ 时，$\textit{result}[i]$ 的值等于数组 $\textit{nums}$ 的下标 $i$ 向左移动 $-\textit{nums}[i]$ 的下标处的值，即数组 $\textit{nums}[i]$ 的下标 $i + \textit{nums}[i]$ 对应的范围 $[0, n - 1]$ 中的下标。

  • 当 $\textit{nums}[i] = 0$ 时，$\textit{result}[i]$ 的值等于数组 $\textit{nums}$ 的下标 $i$ 处的值。

上述情况可以统一表示成数组 $\textit{nums}[i]$ 的下标 $i + \textit{nums}[i]$ 对应的范围 $[0, n - 1]$ 中的下标。对于 $0 \le i < n$ 的每个下标 $i$，计算 $\textit{result}[i]$ 时为了确保得到范围 $[0, n - 1]$ 中的下标，应计算 $\textit{index} = ((i + \textit{nums}[i]) \bmod n + n) \bmod n$，则 $\textit{result}[i] = \textit{nums}[\textit{index}]$。

计算数组 $\textit{result}$ 中的所有元素之后，即可得到结果数组。

代码

###Java

class Solution {
    public int[] constructTransformedArray(int[] nums) {
        int n = nums.length;
        int[] result = new int[n];
        for (int i = 0; i < n; i++) {
            int index = ((i + nums[i]) % n + n) % n;
            result[i] = nums[index];
        }
        return result;
    }
}

###C#

public class Solution {
    public int[] ConstructTransformedArray(int[] nums) {
        int n = nums.Length;
        int[] result = new int[n];
        for (int i = 0; i < n; i++) {
            int index = ((i + nums[i]) % n + n) % n;
            result[i] = nums[index];
        }
        return result;
    }
}

###C++

class Solution {
public:
    vector<int> constructTransformedArray(vector<int>& nums) {
        int n = nums.size();
        vector<int> result(n);
        for (int i = 0; i < n; i++) {
            int index = ((i + nums[i]) % n + n) % n;
            result[i] = nums[index];
        }
        return result;
    }
};

###Python

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

###C

int* constructTransformedArray(int* nums, int numsSize, int* returnSize) {
    int* result = (int*) malloc(sizeof(int) * numsSize);
    for (int i = 0; i < numsSize; i++) {
        int index = ((i + nums[i]) % numsSize + numsSize) % numsSize;
        result[i] = nums[index];
    }
    *returnSize = numsSize;
    return result;
}

###Go

func constructTransformedArray(nums []int) []int {
    n := len(nums)
    result := make([]int, n)
    for i := 0; i < n; i++ {
        index := ((i + nums[i]) % n + n) % n
        result[i] = nums[index]
    }
    return result
}

###JavaScript

var constructTransformedArray = function(nums) {
    let n = nums.length;
    let result = new Array(n);
    for (let i = 0; i < n; i++) {
        let index = ((i + nums[i]) % n + n) % n;
        result[i] = nums[index];
    }
    return result;
};

###TypeScript

function constructTransformedArray(nums: number[]): number[] {
    let n = nums.length;
    let result = new Array(n);
    for (let i = 0; i < n; i++) {
        let index = ((i + nums[i]) % n + n) % n;
        result[i] = nums[index];
    }
    return result;
};

复杂度分析

  • 时间复杂度：$O(n)$，其中 $n$ 是数组 $\textit{nums}$ 的长度。结果数组的每个元素的计算时间都是 $O(1)$。

  • 空间复杂度：$O(1)$。注意返回值不计入空间复杂度。

模拟

✇LeetCode 每日一题题解
作者 tsreaper
2024年12月8日 12:23

解法：模拟

按题意模拟即可。复杂度 $\mathcal{O}(n)$。

参考代码（c++）

###cpp

class Solution {
public:
    vector<int> constructTransformedArray(vector<int>& nums) {
        int n = nums.size();
        vector<int> ans;
        for (int i = 0; i < n; i++) {
            int j = (i + nums[i] % n + n) % n;
            ans.push_back(nums[j]);
        }
        return ans;
    }
};

简洁写法（Python/Java/C++/C/Go/JS/Rust）

✇LeetCode 每日一题题解
作者 endlesscheng
2024年12月8日 12:20

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

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

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

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

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

###py

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

###java

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

###cpp

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

###c

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

###go

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

###js

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

###rust

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

复杂度分析

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

分类题单

如何科学刷题？

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

我的题解精选（已分类）

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

❌
❌