字母移位
难度:
标签:
题目描述
代码结果
运行时间: 100 ms, 内存: 26.7 MB
// Solution using Java Stream
// Here we use Streams to accumulate the total shifts and apply them to each character.
// We reverse the shifts array to make the calculation easier, then convert it back.
import java.util.stream.IntStream;
public class Solution {
public String shiftingLetters(String s, int[] shifts) {
char[] chars = s.toCharArray();
int n = s.length();
long[] totalShifts = new long[n];
totalShifts[n - 1] = shifts[n - 1];
// Calculate total shifts for each character starting from the end
IntStream.range(0, n - 1)
.mapToObj(i -> n - 2 - i)
.forEach(i -> totalShifts[i] = (totalShifts[i + 1] + shifts[i]) % 26);
// Apply the shifts to each character
IntStream.range(0, n).forEach(i ->
chars[i] = (char) ((chars[i] - 'a' + totalShifts[i]) % 26 + 'a')
);
return new String(chars);
}
}
解释
方法:
此题解使用了一种巧妙的方法来避免重复计算多次移位,从而实现高效的字符串转换。首先,计算所有移位的总和,并对26取模,因为字母表循环的周期为26。然后遍历字符串中的每个字符,对于每个字符,计算其应当移位后的新位置,使用ASCII码转换来实现。在每次遍历中,通过减去当前位置的移位数并再次对26取模,动态地更新移位总和,这样可以保证每个字符都移位正确的次数。这种方法有效利用了前缀和思想,减少了重复的计算。
时间复杂度:
O(n)
空间复杂度:
O(n)
代码细节讲解
🦆
为什么在计算所有移位总和时需要对26取模?
▷🦆
在更新字符位置时,为什么可以保证`(index + X) % 26`总是返回正确的新位置?
▷🦆
在逐个字符更新移位总和`X = (X - shifts[i]) % 26`时,是否考虑了负数取模的情况?
▷🦆
如果`shifts`数组中的某些元素非常大,对26取模后的影响是什么,是否还是有效的?
▷