LeetCode 848. 字母移位
题目描述
题意分析
第
i项操作把前i+1个小写字母都向后移动shifts[i]次，超过z后回到a。求所有操作完成后的字符串。若逐次修改整个前缀，同一个字符会被处理很多次。可以先算清每个位置一共受到多少次移位，再一次性得到它的最终字母。
解法：后缀偏移累加
核心思路
[!blue]
位置
i会受到哪些操作影响？下标为j的操作覆盖区间[0, j]，所以它包含位置i当且仅当j >= i。因此位置i的总偏移是shifts[i] + shifts[i+1] + ... + shifts[n-1]，正好是一个后缀和。从右向左扫描，用
shift保存已经累计的后缀偏移。处理位置i时，先把shifts[i]加进去，此时shift就对应当前字符承受的全部操作；处理完当前字符，再向左移动即可。字母每移动 26 次就回到原位，所以累计时可以每轮对 26 取模，不影响最终字符。把当前字母转换为
0...25的编号base，它的新编号为(base + shift) % 26，最后加上a恢复成字符。逐轮取模也避免保存可能很大的完整后缀和。每轮开始时
shift至多为 25，而题目中单次移位至多为10^9，两者相加仍在 32 位整数范围内，可以安全地再取模。
解题步骤
- 把字符串转换为可修改的字符或字节数组，将累计偏移
shift初始化为 0。- 从最后一个位置向前扫描，先更新
shift = (shift + shifts[i]) % 26。- 将当前字母减去
a得到零基编号，加上累计偏移后对 26 取模，再加回a并写回当前位置。- 所有位置处理完后，把缓冲数组转换为字符串返回。
代码实现
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)$，
n为字符串长度，每个位置只处理一次。- 空间复杂度：$O(n)$，用于可修改的字符缓冲和结果字符串，累计偏移本身只需常数空间。
关键点总结
[!green]
- 一个位置会受到它自身及右侧操作的影响，因此前缀修改转化为后缀累计。
- 先加入当前操作，再改写当前字符，避免漏掉
shifts[i]。- 移位以 26 为周期，只保留余数就能得到相同的最终字母。
易错点总结
[!yellow]
- 从左向右累计：得到的是前缀和，与当前字符实际承受的后缀操作不一致。
- 每个位置只应用
shifts[i]：会漏掉所有覆盖它的更长前缀操作。- 直接对字符编码取模：应先减去
a转换成0...25，移位后再加回a。- 先用 32 位整数求出全部移位和再取模：总和可能已经溢出，应在每轮累计后立即取模。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 2381. 字母移位 II | 中等 | 本题只对前缀加位移，原题支持任意区间正负位移，需要更一般的差分累计。 |
| 370. 区间加法 | 中等 | 同样把批量区间影响先合并再一次还原，本题额外对字母循环长度26取模。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！