今日题目

https://leetcode.com/problems/shifting-letters-ii/description/

解题思路

我们需要构建一种数据结构，支持多次区间加法操作和一次性查询。因此，可以使用差分数组与前缀和来解决。

解题方法

在差分数组中，我们只记录变化区间边界处的差值。例如，对区间 $[l,r]$ 整体加 $k$，只需关注 $l$ 和 $r$ 两个端点：将差分数组 $diff[l]$ 加 $k$，再将 $diff[r+1]$ 加 $-k$。这样，对差分数组求前缀和 $s$ 后，加 $k$ 的效果只会体现在 $[l,r]$ 范围内。因此，利用差分数组与前缀和，每次区间修改的时间复杂度为 $O(1)$。

在处理字符移位时，先将字符转换为 ASCII 码，减去字符 ‘a’ 的 ASCII 码，再对 26 取模，即可实现字符的"循环移位"效果。

复杂度分析

  • 时间复杂度：$O(N + C)$，其中 N 为字符串长度，C 为操作次数。

  • 空间复杂度：$O(N)$，需要存储差分数组。

代码

class Solution:
    def shiftingLetters(self, s: str, shifts: List[List[int]]) -> str:
        dif = [0] * (len(s) + 1)
        for l,r,delta in shifts:
            if delta == 0:
                dif[l] -= 1
                dif[r + 1] += 1
            else:
                dif[l] += 1
                dif[r + 1] -= 1
        
        a = ord('a')
        cnt = 0
        ans = ""
        
        for i in range(len(s)):
            cnt += dif[i]
            ans += chr((ord(s[i]) - a + cnt) % 26 + a)

        return ans