模拟

由于每次旋转操作都是将最左侧字符移动到最右侧，因此如果 goal 可由 s 经过多步旋转而来，那么 goal 必然会出现在 s + s 中，即满足 (s + s).contains(goal)，同时为了 s 本身过长导致的结果成立，我们需要先确保两字符串长度相等。

代码：

###Java

class Solution {
    public boolean rotateString(String s, String goal) {
        return s.length() == goal.length() && (s + s).contains(goal);
    }
}

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

关于 contains 操作的复杂度说明

看到不少同学对 contains 的复杂度写成 $O(n)$ 有疑问。

在 Java 中，contains 实际最终是通过 indexOf(char[] source, int sourceOffset, int sourceCount, char[] target, int targetOffset, int targetCount, int fromIndex) 来拿到子串在原串的下标，通过判断下标是否为 $-1$ 来得知子串是否在原串出现过。

我们知道一个较为普通的子串匹配算法的复杂度通为 $O(n*k)$，其中 $n$ 和 $k$ 分别是原串和子串的长度，而一些复杂度上较为优秀的算法可以做到 $O(n + k)$，例如 KMP。

从复杂度上来看 KMP 似乎要更好，但实际上对于 indexOf 这一高频操作而言，KMP 的预处理逻辑和空间开销都是不可接受的。

因此在 OpenJDK 中的 indexOf 源码中，你看不到诸如 KMP 这一类「最坏情况下仍为线性复杂度」的算法实现。

但是 contains 的复杂度真的就是 $O(n * k)$ 吗？

其实并不是，这取决于 JVM 是否有针对 indexOf 的优化，在最为流行 HotSpot VM 中，就有对 indexOf 的优化。

使用以下两行命令执行 Main.java，会得到不同的用时。

###Java

// Main.java
import java.util.*;
class Main {
    static String ss = "1900216589537958049456207450268985232242852754963049829410964867980510717200606495004259179775210762723370289106970649635773837906542900276476226929871813370344374628795427969854262816333971458418647697497933767559786473164055741512717436542961770628985635269208255141092673831132865";
    static String pp = "830411595466023844647269831101019568881117264597716557501027220546437084223034983361631430958163646150071031688420479928498493050624766427709034028819288384316713084883575266906600102801186671777455503932259958027055697399984336592981698127456301551509241";
    static int cnt = (int) 1e8;
    static public void main(String[] args) {
        long start = System.currentTimeMillis();
        while (cnt-- > 0) ss.contains(pp);
        System.out.println(System.currentTimeMillis() - start);
    }
}

环境说明：

###Shell

➜  java -version
java version "1.8.0_131"
Java(TM) SE Runtime Environment (build 1.8.0_131-b11)
Java HotSpot(TM) 64-Bit Server VM (build 25.131-b11, mixed mode)

先执行 javac Main.java 进行编译后：

1. 使用原始的 indexOf 实现进行匹配（执行多次，平均耗时为基准值 $X$）：

java -XX:+UnlockDiagnosticVMOptions -XX:DisableIntrinsic=_indexOf Main

2. 使用 HotSpot VM 优化的 indexOf 进行匹配（执行多次，平均耗时为基准值 $X$ 的 $[0.55, 0.65]$ 之间）：

java Main

因此实际运行的 contains 操作的复杂度为多少并不好确定，但可以确定是要优于 $O(n * k)$ 的。

加练

今日份加餐 :【面试高频题】难度 2/5，结合二分的序列 DP 运用题 🍭🍭🍭🍭

或是考虑加练如下「模拟」题 🍭🍭🍭

注：以上目录整理来自 wiki，任何形式的转载引用请保留出处。

最后

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

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

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

模拟

利用 $n$ 的范围为 $1e4$，我们可以直接检查 $[1, n]$ 的每个数。

由于每一个位数都需要翻转，因此如果当前枚举到的数值 x 中包含非有效翻转数字（非 0125689）则必然不是好数；而在每一位均为有效数字的前提下，若当前枚举到的数值 x 中包含翻转后能够发生数值上变化的数值（2569），则为好数。

代码：

###Java

class Solution {
    public int rotatedDigits(int n) {
        int ans = 0;
        out:for (int i = 1; i <= n; i++) {
            boolean ok = false;
            int x = i;
            while (x != 0) {
                int t = x % 10;
                x /= 10;
                if (t == 2 || t == 5 || t == 6 || t == 9) ok = true;
                else if (t != 0 && t != 1 && t != 8) continue out;
            }
            if (ok) ans++;
        }
        return ans;
    }
}

###TypeScript

function rotatedDigits(n: number): number {
    let ans = 0
    out:for (let i = 1; i <= n; i++) {
        let ok = false
        let x = i
        while (x != 0) {
            const t = x % 10
            x = Math.floor(x / 10)
            if (t == 2 || t == 5 || t == 6 || t == 9) ok = true
            else if (t != 0 && t != 1 && t != 8) continue out
        }
        if (ok) ans++
    }
    return ans
};

###Python3

class Solution:
    def rotatedDigits(self, n: int) -> int:
        ans = 0
        for i in range(1, n + 1):
            ok, x = False, i
            while x != 0:
                t = x % 10
                x = x // 10
                if t == 2 or t == 5 or t == 6 or t == 9:
                    ok = True
                elif t != 0 and t != 1 and t != 8:
                    ok = False
                    break
            ans = ans + 1 if ok else ans
        return ans

• 时间复杂度：共有 $n$ 个数需要枚举，检查一个数需要遍历其每个数字，复杂度为 $O(\log{n})$。整体复杂度为 $O(n\log{n})$
• 空间复杂度：$O(1)$

最后

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

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

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

前缀和 + 滑动窗口

为了方便，我们将 $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 哦 ~