字母位移II

Leetcode Link: 6158. 字母移位 II - 力扣（LeetCode）

题目

解法一

思路：

原题解链接

1. 先构建一个差分数组diff
2. 然后根据字符串s对差分数组diff进行初始化
3. 对差分数组进行区间变更
4. 将差分数组更改为前缀和
5. 对差分数组中的每个值变为对应的字符

题解：

class Solution:
    def shiftingLetters(self, s: str, shifts: List[List[int]]) -> str:
        # 差分数组
        n = len(s)
        diff = [0] * (n + 1)
        diff[0] = ord(s[0]) - ord('a')
        # 初始化差分数组
        for i in range(1, len(s)):
            diff[i] = ord(s[i]) - ord(s[i - 1])
 
        # 区间变更
        for shift in shifts:
            if shift[2]:
                diff[shift[0]] += 1
                diff[shift[1] + 1] -= 1
            else:
                diff[shift[0]] -= 1
                diff[shift[1] + 1] += 1
 
        # 前缀和
        for i in range(1, len(diff)):
            diff[i] += diff[i - 1]
 
        for i in range(len(diff)):
            # diff[i]可能为负数
            while diff[i] < 0:
                diff[i] += 26
            diff[i] %= 26
            diff[i] += ord('a')
            diff[i] = chr(diff[i])
 
        return ''.join(diff[:-1])

解法二

思路：

题解：

解法三

思路：

题解：

启发和联系