❌

阅读视图

发现新文章，点击刷新页面。

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

✇LeetCode 每日一题题解

给你一个字符串 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

方法一：动态规划

我们定义 $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

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

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) {
        var s = S.toCharArray();
        int del = 0;
        for (var c : s)
            del += 'b' - c; // 统计 'a' 的个数
        int ans = del;
        for (var 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)
        if del < ans {
            ans = del
        }
    }
    return ans
}

复杂度分析

  • 时间复杂度：$O(n)$，其中 $n$ 为 $s$ 的长度。
  • 空间复杂度：$O(1)$，仅用到若干额外变量。

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

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

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

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

设 $\textit{cntB}$ 为前 $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})$。

代码实现时，可以只用一个变量表示 $f$。

答疑

问：这一次遍历怎么没两次遍历快啊？

答：方法一解释了。通过这两种方法的对比，相信你能感受到随机数据对分支预测的影响。

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, 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
}

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

复杂度分析

  • 时间复杂度：$O(n)$，其中 $n$ 为 $s$ 的长度。
  • 空间复杂度：$O(1)$，仅用到若干额外变量。

相似题目（前后缀分解，部分题目要结合 DP）

附：我的 每日一题·高质量题解精选，已分类整理好。

欢迎关注【biIibiIi@灵茶山艾府】，高质量算法教学，持续更新中~

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

✇LeetCode 每日一题题解
LeetCode-Solution

方法一：枚举

思路

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

  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 每日一题题解

给你一个整数数组 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

解法

思路和算法

根据题意模拟，计算结果数组 $\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

解法：模拟

按题意模拟即可。复杂度 $\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

操作相当于从下标 $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站@灵茶山艾府

❌