Every day a Leetcode
题目来源:2381. 字母移位 II
解法1:差分数组
用差分数组 diff 表示一段区间上的更新,即在 starti 变化量增加了 x,在 endi+1 变化量减少了 x(类比导数的概念)。
这里 x=2*directioni−1,把 0 和 1 变成 −1 和 1。
然后从小到大遍历 diff,累加变化量为 shift(类比积分的概念),这样对于第 i 个字符,其移位值就是 shift。
注意:
代码:
/*
* @lc app=leetcode.cn id=2381 lang=cpp
*
* [2381] 字母移位 II
*/
// @lc code=start
class Solution
{
public:
string shiftingLetters(string s, vector<vector<int>> &shifts)
{
// 特判
if (shifts.empty())
return s;
int n = s.length();
// 构造差分数组
vector<int> diff(n + 1, 0);
for (vector<int> &shift : shifts)
{
int start = shift[0];
int end = shift[1];
int move = shift[2] ? 1 : -1;
diff[start] += move;
diff[end + 1] -= move;
}
int shift = 0;
// 计算最终字符串
for (int i = 0; i < n; i++)
{
shift += diff[i];
s[i] = (char)((s[i] - 'a' + (shift % 26) + 26) % 26 + 'a');
}
return s;
}
};
// @lc code=end
结果:
复杂度分析:
时间复杂度:O(n+m),其中 n 是字符串 s 的长度,m 是数组 shift 的元素个数。
空间复杂度:O(n),其中 n 是字符串 s 的长度。