LeetCode 848. 字母移位

2022-03-09 HGNULB 约 6 分钟

文章信息 7 个分类 3 个标签

分类

题目描述

✅ 848. 字母移位

题意分析

输入是长度 $n$ 的小写字母串 s 和等长数组 shifts，第 i 次操作要把 s 的前 i + 1 个字符各自向后循环移动 shifts[i] 位，求所有操作做完后的字符串。

关键在于每次操作都作用在一个前缀上，所以位置 i 的字符会被 shifts[i]、shifts[i + 1]、直到 shifts[n - 1] 全部影响，它承受的总位移正好是 shifts 的一段后缀之和。

约束里 $n$ 可达 $10^5$、单个 shifts[i] 可达 $10^9$，后缀和量级到 $10^{14}$，32 位整数装不下，必须在累加过程中就压住数值。

好在字母表只有 26 个且移位是循环的，任何位移量只有模 26 的余数有意义，这给了「随时取模」的合法性。题目还保证 shifts[i] 非负，不用考虑负数回绕。

解法：后缀偏移累加

核心思路

暴力做法是照着题意执行：对每个 i，把 s[0..i] 里每个字符都往后挪 shifts[i] 位。光是外层枚举加内层前缀就已经是 $O(n^2)$，若还傻乎乎地一位一位挪 $10^9$ 次则完全不可行。

瓶颈在于同一个字符被反复重写，而且完全没利用「移位可以先加再一次性施加」这一点。

观察到移位操作可交换、可叠加：位置 i 的最终字符只取决于总位移量 $\sum_{j \ge i} shifts[j]$，中间过程长什么样无关紧要。而后缀和从右往左扫时可以 $O(1)$ 递推，一次遍历就能把每个位置的总位移算出来。

于是维持这个不变量：从右往左扫描，在处理下标 i 的字符之前先更新 shift，使其恒等于 $\left(\sum_{j = i}^{n - 1} shifts[j]\right) \bmod 26$。有了它，新字符就是 'a' + (s[i] - 'a' + shift) % 26。

解题步骤

把 s 转成可变的字符数组。字符串在 Java、Go 里都不可变，原地改写才能保证整体 $O(n)$，用字符串拼接会退化成平方级。

shift 置 0，从下标 n - 1 往左扫。方向必须是从右往左，因为后缀和的递推关系是「当前后缀 = 右边后缀 + 自己」，反过来就无法一次成型。

每步先做 shift = (shift + shifts[i]) % 26。先更新再用，是为了让 shift 在使用时已经包含 shifts[i] 自己 —— 位置 i 受第 i 次操作影响。取模紧跟加法，把数值锁死在 26 以内，从根上杜绝溢出。

用 base = s[i] - 'a' 把字符换算成 0 到 25 的编号，再取 (base + shift) % 26 得到新编号，加回 'a' 写入数组。先减基准再取模是循环移位的标准写法，直接在 ASCII 值上取模会把字母映射到控制字符区。

扫完把数组转回字符串返回。

以 s = "abc"、shifts = [3, 5, 9] 走一遍：

i = 2：shift = (0 + 9) % 26 = 9。base = 'c' - 'a' = 2，新编号 (2 + 9) % 26 = 11，写入 'l'，数组变成 "abl"。

i = 1：shift = (9 + 5) % 26 = 14。base = 'b' - 'a' = 1，新编号 (1 + 14) % 26 = 15，写入 'p'，数组变成 "apl"。

i = 0：shift = (14 + 3) % 26 = 17。base = 'a' - 'a' = 0，新编号 (0 + 17) % 26 = 17，写入 'r'，数组变成 "rpl"。

返回 "rpl"。手工核对：'a' 被三次操作全部覆盖，总位移 $3 + 5 + 9 = 17$；'b' 被后两次覆盖，总位移 14；'c' 只被最后一次覆盖，总位移 9，与扫描结果一一对应。

代码实现

class Solution {
    // 转换顺序从右向左时，右侧已确定的偏移可以累加到当前字符，得到它最终应受的总位移。
    public String shiftingLetters(String s, int[] shifts) {
        char[] chars = s.toCharArray();
        int shift = 0;

        for (int i = chars.length - 1; i >= 0; i--) {
            shift = (shift + shifts[i]) % 26;
            int base = chars[i] - 'a';
            chars[i] = (char) ('a' + (base + shift) % 26);
        }

        return new String(chars);
    }
}

func shiftingLetters(s string, shifts []int) string {
    // 转换顺序从右向左时，右侧已确定的偏移可以累加到当前字符，得到它最终应受的总位移。
    chars := []byte(s)
    shift := 0

    for i := len(chars) - 1; i >= 0; i-- {
        shift = (shift + shifts[i]) % 26
        chars[i] = byte('a' + (int(chars[i]-'a')+shift)%26)
    }

    return string(chars)
}

复杂度分析

时间复杂度：$O(n)$，从右到左只扫一遍，每个位置做一次加法、两次取模和一次赋值，都是常数级操作。

空间复杂度：$O(n)$，开销来自承载结果的字符数组；除它以外只多用了 shift 一个整数，属于返回值本身必需的空间。

关键点总结

「多次前缀操作」等价于「每个位置吃一段后缀」。看穿这层转换后，$n$ 次区间更新塌成一次后缀累加，这是前缀和、差分家族最核心的思维动作。

操作可交换、可叠加时，不必按题目给的顺序真的执行，只需算出每个位置的净效果。这条原则在移位、旋转、加法类题目上通用。

取模的位置决定了会不会溢出。把 % 26 紧贴在累加后面，shift 永远小于 26，即使 shifts[i] 到 $10^9$、$n$ 到 $10^5$ 也不会碰到 32 位上限。

循环字符运算固定套路是「减基准 → 算数 → 取模 → 加基准」，四步缺一不可，直接在 ASCII 码上取模必然落到非字母区。

面试视角：这题的标准追问是「如果操作不是前缀而是任意区间怎么办」，答案是差分数组加一次前缀和还原；能主动把本题归到差分体系里，比只答出倒序扫描更能体现体系感。

易错点总结

错误写法：从左往右累加 shifts。用 s = "abc"、shifts = [3, 5, 9] 试：位置 0 只拿到 3，输出 'd'，但它还应吃到后面的 5 和 9，正确字符是 'r'。

错误写法：把 shifts[i] 当成「位置 i 独有的位移」逐位赋值。同一组用例会得到 "dgl"，正确答案是 "rpl"，前缀叠加效应整个丢失。

错误写法：先用 int 把所有 shifts 加完再统一取模。n = 10^5 且每个 shifts[i] = 10^9 时总和约 $10^{14}$，int 溢出成负数，取模后映射出的字母全是错的。

错误写法：算新字符时忘了先减 'a'，写成 (char) ((s[i] + shift) % 26)。'a' 的码值是 97，(97 + 9) % 26 = 2，得到的是控制字符而不是字母。

错误写法：写成 chars[i] += shift 而不取模。shift 最大 25，'z' + 25 已经越出字母区，正确结果应是回绕后的 'y'。

错误写法：在 Go 里把还没取模的 shift 转成 byte 参与运算。byte 只有 8 位，$10^9$ 级别的值高位被截断，得到的偏移量与真实值毫无关系。

错误写法：用不可变字符串拼结果，循环里做 res = string(c) + res。逻辑没错，但每次拼接都复制整串，$n = 10^5$ 时退化成 $O(n^2)$，直接超时。

错误写法：照搬「允许负位移」的模板写 (x % 26 + 26) 却漏掉最后一次 % 26。当 x 为 0 时结果是 26，'a' + 26 越出字母表落到 '{'。

相似题目

题目	难度	考察点
303. 区域和检索 - 数组不可变	简单	预处理前缀和以支持多次区间求和查询
560. 和为 K 的子数组	中等	前缀和配哈希表统计满足条件的区间个数
724. 寻找数组的中心下标	简单	前缀和与后缀和同时使用，求分割点
1094. 拼车	中等	差分还原后还要逐时刻校验容量上限
1109. 航班预订统计	中等	更新落在任意区间上，需差分数组而非后缀累加