leetcode
leetcode 2051 ~ 2100
字母移位 II

字母移位 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?
在差分数组中,初始化长度为n+1的目的是为了方便处理区间的结束位置。当我们对一个区间[start, end]进行操作时,为了使end位置之后的元素不受影响,我们在end+1位置进行一个相反的操作。如果数组只有长度n,那么当end等于n-1(即区间结束于数组末尾)时,end+1将是n,这将越界如果数组长度只是n。因此,为了安全地应用这种操作而不越界,数组长度设置为n+1。
🦆
差分数组的更新操作中,使用(-1, 1)[direct]是什么意思,它如何根据direction值决定加1还是减1?
表达式(-1, 1)[direct]是Python中的一个条件表达式,它根据direct的值选择-1或1。这里,direct是一个指示移动方向的标志,通常0代表向前移动(向左或逆时针),1代表向后移动(向右或顺时针)。如果direct为0,(-1, 1)[0]将结果为-1,表示字符需要向前移动;如果direct为1,(-1, 1)[1]将结果为1,表示字符需要向后移动。这是一个简洁的方法来根据方向设置增加或减少的值。
🦆
你提到将终点后一个位置的值进行相反操作,这是为了什么目的?
在差分数组中,终点后一个位置的相反操作是为了限定移位操作只影响区间[start, end]内的元素。通过在start位置增加一个值,并在end+1位置减去相同的值,我们创建了一个区间内的‘区间增量’。这样,当我们累加数组以应用这些变化时,只有在start到end的位置会受到影响,end之后的位置则不会累积这个特定的变化,从而保持了区间之外的数据稳定。
🦆
为什么可以直接用(chr(ord(ch) - 97 + cur) % 26 + 97)来计算移位后的字符?
这个表达式是基于ASCII码计算字符移位的通用方法。首先,ord(ch) - 97将字符ch(假设是小写字母)转换为0-25之间的整数,其中'a'变为0,'z'变为25。然后加上cur表示移位的数量,可以是正数或负数。使用模26操作确保结果再次落在0-25的范围内,这对应于字母表中的循环移位。最后,再加上97将数字转换回对应的ASCII字符。这种方法有效地处理了字母表循环和任意方向的移位。

相关问题