字母移位 II
难度:
标签:
题目描述
代码结果
运行时间: 104 ms, 内存: 38.9 MB
/*
思路:
1. 使用Java Stream API简化代码,尤其是在遍历shifts数组时。
2. 使用Stream.forEach遍历shifts数组,并对字符数组进行移位操作。
3. 使用一个字符数组存储字符串s,方便进行字符替换操作。
*/
import java.util.Arrays;
public class Solution {
public String shiftingLetters(String s, int[][] shifts) {
char[] arr = s.toCharArray();
Arrays.stream(shifts).forEach(shift -> {
int start = shift[0];
int end = shift[1];
int direction = shift[2];
for (int i = start; i <= end; i++) {
if (direction == 1) { // 向后移位
arr[i] = (char)((arr[i] - 'a' + 1) % 26 + 'a');
} else { // 向前移位
arr[i] = (char)((arr[i] - 'a' - 1 + 26) % 26 + 'a');
}
}
});
return new String(arr);
}
}
解释
方法:
该题解使用了差分数组的方法来优化连续区间的更新。对于每个shift操作,而不是直接更新字符串s的每个字符,我们在辅助数组lst中标记起始点和终点的变化。如果directioni是1(向后移位),在起始位置增加1,在终点的下一个位置减少1;如果是0(向前移位),则在起始位置减少1,在终点的下一个位置增加1。这样,我们只需要在lst上做两次操作即可标记一个区间的移位。之后,我们通过累加lst来计算实际的移位次数,并应用到字符串s上,计算最终的字符位置。
时间复杂度:
O(m + n)
空间复杂度:
O(n)
代码细节讲解
🦆
在差分数组中,为什么要初始化长度为n+1而不是n?
▷🦆
差分数组的更新操作中,使用(-1, 1)[direct]是什么意思,它如何根据direction值决定加1还是减1?
▷🦆
你提到将终点后一个位置的值进行相反操作,这是为了什么目的?
▷🦆
为什么可以直接用(chr(ord(ch) - 97 + cur) % 26 + 97)来计算移位后的字符?
▷