1. leetcode 题目：
//有一个由小写字母组成的字符串 s，和一个长度相同的整数数组 shifts。
//
// 我们将字母表中的下一个字母称为原字母的 移位 shift() （由于字母表是环绕的， 'z' 将会变成 'a'）。
//
//
// 例如，shift('a') = 'b', shift('t') = 'u', 以及 shift('z') = 'a'。
//
//
// 对于每个 shifts[i] = x ， 我们会将 s 中的前 i + 1 个字母移位 x 次。
//
// 返回 将所有这些移位都应用到 s 后最终得到的字符串 。
//
//
//
// 示例 1：
//
//
//输入：s = "abc", shifts = [3,5,9]
//输出："rpl"
//解释：
//我们以 "abc" 开始。
//将 S 中的第 1 个字母移位 3 次后，我们得到 "dbc"。
//再将 S 中的前 2 个字母移位 5 次后，我们得到 "igc"。
//最后将 S 中的这 3 个字母移位 9 次后，我们得到答案 "rpl"。
//
//
// 示例 2:
//
//
//输入: s = "aaa", shifts = [1,2,3]
//输出: "gfd"
//
// 提示:
// 1 <= s.length <= 10⁵
// s 由小写英文字母组成
// shifts.length == s.length
// 0 <= shifts[i] <= 10⁹
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
public String shiftingLetters(String s, int[] shifts) {
}
}
//leetcode submit region end(Prohibit modification and deletion)
2. 算法详解，给出java示例，并分析时间、空间复杂度
题目解析
这个问题要求对字符串中的字符进行一系列累积移位操作，并输出最终结果。题目中的移位操作是环绕字母表的，即 'z' 的下一个是 'a'。
解题思路
1. 累积移位：
• 对于 shifts[i]，需要将字符串前 i + 1 个字母移位 shifts[i] 次。
• 实际上，shifts[i] 的作用会叠加到其之前的所有位置，因此我们可以从后往前计算累积的移位量。
• 假设总移位量为 sum，从后向前遍历，每次将 shifts[i] 累加到 sum，并用这个 sum 计算字符的最终移位。
2. 环绕处理：
• 对于字母表移位，我们可以使用 (原字符 - 'a' + 累积移位) % 26 得到环绕移位后的字符。
3. 高效实现：
• 使用一个字符数组存储结果，避免字符串频繁拼接。
算法实现
class Solution {
public String shiftingLetters(String s, int[] shifts) {
// 字符串长度
int n = s.length();
// 存储累积的移位量
long sum = 0;
// 使用字符数组存储结果，避免频繁字符串拼接
char[] result = new char[n];
// 从后往前遍历
for (int i = n - 1; i >= 0; i--) {
// 更新累积移位量，注意可能溢出，用 long
sum += shifts[I];
// 移位后的新字符
int newChar = (s.charAt(i) - 'a' + (int)(sum % 26)) % 26;
// 转换回字符并存储
result[i] = (char) ('a' + newChar);
}
// 将字符数组转换为字符串
return new String(result);
}
}
示例
输入：
String s = "abc";
int[] shifts = {3, 5, 9};
计算过程：
1. 初始化 sum = 0，result = []。
2. 从后往前遍历：
• i = 2: sum += 9 = 9，newChar = ('c' - 'a' + 9) % 26 = 15，对应 'p'。
• i = 1: sum += 5 = 14，newChar = ('b' - 'a' + 14) % 26 = 15，对应 'l'。
• i = 0: sum += 3 = 17，newChar = ('a' - 'a' + 17) % 26 = 17，对应 'r'。
3. 最终结果为 "rpl"。
时间与空间复杂度分析
总结
该算法通过从后往前累加移位量，避免了直接对每个前缀计算移位操作的冗余，提升了效率，是一种高效的解决方案。
注：
一般都是想着从前向后遍历，这里却从后向前遍历，一下子少了很多操作。有时候思维模式很重要。
提高算法的一个主要思想是少操作！
changyou
