2381. 字母移位 II

🟠   🔖  数组 字符串 前缀和  🔗 力扣 LeetCode

题目

You are given a string s of lowercase English letters and a 2D integer array shifts where shifts[i] = [starti, endi, directioni]. For every i, shift the characters in s from the index starti to the index endi (inclusive) forward if directioni = 1, or shift the characters backward if directioni = 0.

Shifting a character forward means replacing it with the next letter in the alphabet (wrapping around so that 'z' becomes 'a'). Similarly, shifting a character backward means replacing it with the previous letter in the alphabet (wrapping around so that 'a' becomes 'z').

Return the final string after all such shifts tos are applied.

Example 1:

Input: s = "abc", shifts = [[0,1,0],[1,2,1],[0,2,1]]

Output: "ace"

Explanation: Firstly, shift the characters from index 0 to index 1 backward. Now s = "zac".

Secondly, shift the characters from index 1 to index 2 forward. Now s = "zbd".

Finally, shift the characters from index 0 to index 2 forward. Now s = "ace".

Example 2:

Input: s = "dztz", shifts = [[0,0,0],[1,1,1]]

Output: "catz"

Explanation: Firstly, shift the characters from index 0 to index 0 backward. Now s = "cztz".

Finally, shift the characters from index 1 to index 1 forward. Now s = "catz".

Constraints:

• 1 <= s.length, shifts.length <= 5 * 10^4
• shifts[i].length == 3
• 0 <= starti <= endi < s.length
• 0 <= directioni <= 1
• s consists of lowercase English letters.

题目大意

给你一个小写英文字母组成的字符串 s 和一个二维整数数组 shifts ，其中 shifts[i] = [starti, endi, directioni] 。对于每个 i ，将 s 中从下标 starti 到下标 endi （两者都包含）所有字符都进行移位运算，如果 directioni = 1 将字符向后移位，如果 directioni = 0 将字符向前移位。

将一个字符 向后 移位的意思是将这个字符用字母表中 下一个 字母替换（字母表视为环绕的，所以 'z' 变成 'a'）。类似的，将一个字符 向前 移位的意思是将这个字符用字母表中 前一个 字母替换（字母表是环绕的，所以 'a' 变成 'z' ）。

请你返回对 s 进行所有移位操作以后得到的最终字符串。

示例 1：

输入： s = "abc", shifts = [[0,1,0],[1,2,1],[0,2,1]]

输出： "ace"

解释： 首先，将下标从 0 到 1 的字母向前移位，得到 s = "zac" 。

然后，将下标从 1 到 2 的字母向后移位，得到 s = "zbd" 。

最后，将下标从 0 到 2 的字符向后移位，得到 s = "ace" 。

示例 2:

输入： s = "dztz", shifts = [[0,0,0],[1,1,1]]

输出： "catz"

解释： 首先，将下标从 0 到 0 的字母向前移位，得到 s = "cztz" 。

最后，将下标从 1 到 1 的字符向后移位，得到 s = "catz" 。

提示：

• 1 <= s.length, shifts.length <= 5 * 10^4
• shifts[i].length == 3
• 0 <= starti <= endi < s.length
• 0 <= directioni <= 1
• s 只包含小写英文字母。

解题思路

为了高效处理多次区间操作，我们可以使用 差分数组 来记录每个位置的累积偏移量。

1. 构建差分数组：

   • 创建一个与字符串 s 长度相同的差分数组 diffArr。
   • 对于每次位移操作 [start, end, direction]：
     • 如果是右移（direction = 1），则：
       • diffArr[start] += 1
       • 如果 end + 1 在范围内，则 diffArr[end + 1] -= 1
     • 如果是左移（direction = 0），则：
       • diffArr[start] -= 1
       • 如果 end + 1 在范围内，则 diffArr[end + 1] += 1

2. 计算累积偏移量：

   • 使用前缀和将差分数组转化为累积偏移量数组 diff。

3. 应用偏移量并生成结果字符串：

   • 遍历字符串 s，计算每个字符的最终位置：
     • 将累积偏移量加到当前字符的 ASCII 值上，并进行模 26 运算以确保循环在 'a' 到 'z' 范围内。

4. 返回结果字符串。

复杂度分析

• 时间复杂度：O(n + m)
  • 构建差分数组：O(m)，其中 m 是位移操作的个数。
  • 计算累积偏移量：O(n)，其中 n 是字符串长度。
  • 应用偏移量：O(n)。
  • 总复杂度：O(n + m)。
• 空间复杂度：O(n)，存储差分数组和结果数组。

代码

/**
 * @param {string} s
 * @param {number[][]} shifts
 * @return {string}
 */
var shiftingLetters = function (s, shifts) {
	const n = s.length;
	const diffArr = new Array(n).fill(0);

	// 构建差分数组
	for (let [start, end, direction] of shifts) {
		if (direction === 1) {
			diffArr[start]++;
			if (end + 1 < n) diffArr[end + 1]--;
		} else {
			diffArr[start]--;
			if (end + 1 < n) diffArr[end + 1]++;
		}
	}

	// 计算累积偏移量并生成结果字符串
	let diff = 0;
	let res = [];
	for (let i = 0; i < n; i++) {
		diff = (diff + diffArr[i]) % 26;
		if (diff < 0) diff += 26; // 处理负偏移
		res.push(String.fromCharCode(97 + ((s.charCodeAt(i) - 97 + diff) % 26)));
	}

	return res.join('');
};

相关题目

题号	标题	题解	标签	难度	力扣
218	天际线问题		树状数组 线段树 数组 4+	🔴	🀄️ 🔗
307	区域和检索 - 数组可修改	[✓]	设计 树状数组 线段树 1+	🟠	🀄️ 🔗
370	区间加法 🔒		数组 前缀和	🟠	🀄️ 🔗
848	字母移位		数组 字符串 前缀和	🟠	🀄️ 🔗
1854	人口最多的年份	[✓]	数组 计数 前缀和	🟢	🀄️ 🔗
1943	描述绘画结果		数组 哈希表 前缀和 1+	🟠	🀄️ 🔗