前缀和 + 滑动窗口

为了方便，我们将 $nums$ 的长度记为 $n$。

题目要对「旋转数组」做逻辑，容易想到将 $nums$ 进行复制拼接，得到长度为 $2 * n$ 的新数组，在新数组上任意一个长度为 $n$ 的滑动窗口都对应了一个旋转数组。

然后考虑在窗口的滑动过程中，计算结果会如何变化，假设当前我们处理到下标为 $[i, i + n - 1]$ 的滑动窗口，根据题意，当前结果为：

$$
cur = nums[i] * 0 + nums[i + 1] * 1 + ... + nums[i + n - 1] * (n - 1)
$$

当窗口往后移动一位，也就是窗口的右端点来到 $i + n$ 的位置，左端点来到 $i + 1$ 的位置。

我们需要增加「新右端点」的值，即增加 $nums[i + n] * (n - 1)$，同时减去「旧左端点」的值，即减少 $nums[i] * 0$（固定为 $0$），然后更新新旧窗口的公共部分 $[i + 1, i + n - 1]$。

不难发现，随着窗口的逐步右移，每一位公共部分的权值系数都会进行减一。

$$
nums[i + 1] * 1 + nums[i + 2] * 2 + ... + nums[i + n - 1] * (n - 1)
$$

变为

$$
nums[i + 1] * 0 + nums[i + 2] * 1 + ... + nums[i + n - 1] * (n - 2)
$$

因此，公共部分的差值为 $\sum_{idx = i + 1}^{i + n - 1}nums[idx]$，这引导我们可以使用前缀和进行优化。

至此，我们从旧窗口到新窗口的过渡，都是 $O(1)$，整体复杂度为 $O(n)$。

实现上，我们并不需要真正对 $nums$ 进行复制拼接，而只需要在计算前缀和数组 $sum$ 进行简单的下标处理即可。

代码：

###Java

class Solution {
    public int maxRotateFunction(int[] nums) {
        int n = nums.length;
        int[] sum = new int[n * 2 + 10];
        for (int i = 1; i <= 2 * n; i++) sum[i] = sum[i - 1] + nums[(i - 1) % n];
        int ans = 0;
        for (int i = 1; i <= n; i++) ans += nums[i - 1] * (i - 1);
        for (int i = n + 1, cur = ans; i < 2 * n; i++) {
            cur += nums[(i - 1) % n] * (n - 1);
            cur -= sum[i - 1] - sum[i - n];
            if (cur > ans) ans = cur;
        }
        return ans;
    }
}

• 时间复杂度：$O(n)$
• 空间复杂度：$O(n)$

最后

如果有帮助到你，请给题解点个赞和收藏，让更多的人看到 ~ ("▔□▔)/

也欢迎你 关注我 和 加入我们的「组队打卡」小群 ，提供写「证明」&「思路」的高质量题解。

所有题解已经加入 刷题指南，欢迎 star 哦 ~

模拟

根据题目给定的移动规则可知，机器人总是在外圈移动（共上下左右四条），而移动方向分为四类：

当行走步数为 $mod = 2 * (w - 1) + 2 * (h - 1)$ 的整数倍时，会回到起始位置，因此我们可以通过维护一个变量 loc 来记录行走的总步数，并且每次将 loc 对 mod 进行取模来得到有效步数。

在回答 getPos 和 getDir 询问时，根据当前 loc 进行分情况讨论（见注释）。

另外还有一个小细节：根据题意，如果当前处于 $(0, 0)$ 位置，并且没有移动过，方向为 East，若移动过，方向则为 South，这可以通过一个变量 moved 来进行特判处理。

代码：

###Java

class Robot {
    String[] ss = new String[]{"East", "North", "West", "South"};
    int w, h, loc; // loc: 有效（取模后）移动步数
    boolean moved; // 记录是否经过移动，用于特判 (0,0) 的方向
    public Robot(int width, int height) {
        w = width; h = height;
    }
    public void step(int num) {
        moved = true;
        loc += num;
        loc %= 2 * (w - 1) + 2 * (h - 1);
    }
    public int[] getPos() {
        int[] info = move();
        return new int[]{info[0], info[1]};
    }
    public String getDir() {
        int[] info = move();
        int x = info[0], y = info[1], dir = info[2];
        // 特殊处理当前在 (0,0) 的情况，当未移动过方向为 East，移动过方向为 South
        if (x == 0 && y == 0) return moved ? ss[3] : ss[0];
        return ss[dir];
    }
    int[] move() {
        if (loc <= w - 1) {
            // 当移动步数范围在 [0,w-1] 时，所在位置为外圈的下方，方向为 East
            return new int[]{loc, 0, 0};
        } else if (loc <= (w - 1) + (h - 1)) {
            // 当移动步数范围在 [w,(w-1)+(h-1)] 时，所在位置为外圈的右方，方向为 North
            return new int[]{w - 1, loc - (w - 1), 1};
        } else if (loc <= 2 * (w - 1) + (h - 1)) {
            // 当移动步数范围在 [(w-1)+(h-1)+1,2*(w-1)+(h-1)] 时，所在位置为外圈的上方，方向为 West
            return new int[]{(w - 1) - (loc - ((w - 1) + (h - 1))), h - 1, 2};
        } else {
            // 当移动步数范围在 [2*(w-1)+(h-1)+1,2*(w-1)+2*(h-1)] 时，所在位置为外圈的左方，方向为 South
            return new int[]{0, (h - 1) - (loc - (2 * (w - 1) + (h - 1))), 3};
        }
    }
}

• 时间复杂度：$O(1)$
• 空间复杂度：$O(1)$

最后

如果有帮助到你，请给题解点个赞和收藏，让更多的人看到 ~ ("▔□▔)/

也欢迎你 关注我 和 加入我们的「组队打卡」小群 ，提供写「证明」&「思路」的高质量题解。

所有题解已经加入 刷题指南，欢迎 star 哦 ~

模拟

根据题意进行模拟即可。

代码：

###Java

class Solution {
    public boolean checkOnesSegment(String s) {
        int n = s.length(), cnt = 0, idx = 0;
        while (idx < n && cnt <= 1) {
            while (idx < n && s.charAt(idx) == '0') idx++;
            if (idx < n) {
                while (idx < n && s.charAt(idx) == '1') idx++;
                cnt++;
            }
        }
        return cnt <= 1;
    }
}

###TypeScript

function checkOnesSegment(s: string): boolean {
    let n = s.length, cnt = 0, idx = 0
    while (idx < n && cnt <= 1) {
        while (idx < n && s[idx] == '0') idx++
        if (idx < n) {
            while (idx < n && s[idx] == '1') idx++
            cnt++
        }
    }
    return cnt <= 1
};

###Python

class Solution:
    def checkOnesSegment(self, s: str) -> bool:
        n, cnt, idx = len(s), 0, 0
        while idx < n and cnt <= 1:
            while idx < n and s[idx] == '0':
                idx += 1
            if idx < n:
                while idx < n and s[idx] == '1':
                    idx += 1
                cnt += 1
        return cnt <= 1

• 时间复杂度：$O(n)$
• 空间复杂度：$O(1)$

模拟

最终结果只有「从 0 开始的交替串」和「从 1 开始的交替串」两种。

对于一个长度为 n 的未知序列 A 而言，假设我们需要花费 cnt 次操作将其变为「从 0 开始的交替串」，那么我们想要将其变为「从 1 开始的交替串」则需要 n - cnt 次操作：原本操作的 cnt 个位置不能动，而原本没操作的位置则都需要翻转，从而确保两种交替串对应位均相反。

代码：

###Java

class Solution {
    public int minOperations(String s) {
        int n = s.length(), cnt = 0;
        for (int i = 0; i < n; i++) cnt += (s.charAt(i) - '0') ^ (i & 1);
        return Math.min(cnt, n - cnt);
    }
}

###TypeScript

function minOperations(s: string): number {
    let n = s.length, cnt = 0
    for (let i = 0; i < n; i++) cnt += (s.charCodeAt(i) - '0'.charCodeAt(0)) ^ (i & 1)
    return Math.min(cnt, n - cnt)
}

###Python3

class Solution:
    def minOperations(self, s: str) -> int:
        n, cnt = len(s), 0
        for i, c in enumerate(s):
            cnt += (ord(c) - ord('0')) ^ (i & 1)
        return min(cnt, n - cnt)

• 时间复杂度：$O(n)$
• 空间复杂度：$O(1)$

最后

如果有帮助到你，请给题解点个赞和收藏，让更多的人看到 ~ ("▔□▔)/

也欢迎你 关注我，提供写「证明」&「思路」的高质量题解。

所有题解已经加入 刷题指南，欢迎 star 哦 ~