从Leetcode 每日一题练习继续讨论：
2381. 字母移位 II
2381. Shifting Letters II
题解
本题最直观的方法就是遍历shifts数组，根据shifts数组的内容来改变s中对应范围的字符。
但考虑如果shift中的范围有重叠，并且在前一个shift中方向为0，而在后一个shift中方向为1，则重叠范围内的字符实际上并未发生变化。因此为了避免在这种情况下来回变化字符，可以想办法记录每个位置处字符的变化量，这里以方向1的变化为+1，以方向0的变化为-1，这样只需根据最终记录的变化量的值直接变化对应字符即可。为了避免每次记录某个范围内的变化值时都要遍历该范围内的所有记录并改变数值，可以使用线段树，使用线段树可以只记录某个范围内的变化量而不用直接将范围内所有数字的具体值算出来，到shift全部遍历完成后再一边遍历s字符串一边计算每个位置具体的变化量并改变字符。
代码
class SegmentTree {
private:
vector<int> tree;
int n;
void build(int node, int start, int end) {
if (start == end) {
tree[node] = 0;
return;
}
int mid = (start + end) / 2;
build(2 * node + 1, start, mid);
build(2 * node + 2, mid + 1, end);
tree[node] = 0;
}
void update(int node, int start, int end, int l, int r, int val) {
if (r < start || l > end) return;
if (l <= start && end <= r) {
tree[node] += val;
return;
}
int mid = (start + end) / 2;
update(2 * node + 1, start, mid, l, r, val);
update(2 * node + 2, mid + 1, end, l, r, val);
}
int query(int node, int start, int end, int idx) {
if (start == end) return tree[node];
int mid = (start + end) / 2;
if (idx <= mid) {
return tree[node] + query(2 * node + 1, start, mid, idx);
} else {
return tree[node] + query(2 * node + 2, mid + 1, end, idx);
}
}
public:
SegmentTree(int size) {
n = size;
tree.resize(4 * n);
build(0, 0, n - 1);
}
void rangeUpdate(int l, int r, int val) {
update(0, 0, n - 1, l, r, val);
}
int pointQuery(int idx) {
return query(0, 0, n - 1, idx);
}
};
class Solution {
public:
string shiftingLetters(string s, vector<vector<int>>& shifts) {
int n = s.length();
SegmentTree st(n);
for (const auto& shift : shifts) {
int start = shift[0];
int end = shift[1];
int direction = shift[2];
int val = (direction == 1) ? 1 : -1; // 方向1为+1，方向0为-1
st.rangeUpdate(start, end, val); // 更新区间
}
// 遍历字符串，根据线段树中的变化量调整字符
for (int i = 0; i < n; ++i) {
int shiftAmount = st.pointQuery(i); // 查询当前字符的变化量
s[i] = shiftChar(s[i], shiftAmount); // 调整字符
}
return s;
}
private:
char shiftChar(char c, int shift) {
shift = shift % 26;
if (shift < 0) shift += 26;
int newChar = c - 'a' + shift;
newChar = newChar % 26;
if (newChar < 0) newChar += 26;
return 'a' + newChar;
}
};
总结
这种需要频繁处理区间变化的问题还可以使用差分数组，本题如果使用差分数组则效率要高得多，因为差分数组的实现和处理更简单。差分数组的思想建立在前缀和的基础上，我们构建一个差分数组diff，数组中每个位置的数字表示当前位置的数字比前一个位置大多少，如diff[i]=3表示i比i-1的数字大3，差分数组为什么可以很方便的用于处理区间变化问题呢，我们考虑一个简单情况，差分数组初始化为全0表示所有位置的数字都一样，此时假如将diff[i]变为3，那么i比i-1大3，此时我们可以发现，i后面的位置虽然在差分数组中的值仍然为0，但由于i发生了变化，则后面的数字在差分数组为0的情况下表示和i的大小相同也就自然跟随i发生了变化。这样就实现了大于等于i的全部位置都比i-1大3的效果。那么如果要只将中间某一段变为比i前面的数字大3应该怎么办呢。假如我们想让i~j的数字加3，j以后的数字不变，则在diff[i]加3的情况下，让j+1位置不加3，则只需让diff[j+1]减3，抵消掉前面的加3带来的效果即可（大于j+1的位置也就同样跟随着j+1自然产生了抵消效果）。最终计算每个位置的变化量时只需计算diff数组的前缀和即可，是非常巧妙的思路。
这里的思想是我们只需知道变化的路径就可以知道最终的值相当于初始值的总体变化量，在一些特定场景下，相对变化量变化频繁，可以不必每次都记下绝对变化量，仅将相对变化全部记录下来，最终再去计算出绝对变化量会大大增加计算效率。当然这需要有一个固定的初始值，比如本题其实默认在开始之前字符是没发生变化的，即初始为0。
class Solution {
public:
string shiftingLetters(string s, vector<vector<int>>& shifts) {
int n = s.length();
vector<int> prefix(n + 1, 0);
for (auto &shift : shifts) {
int a = shift[0];
int b = shift[1];
int c = shift[2];
prefix[a] += (2 * c - 1);
prefix[b + 1] -= (2 * c - 1);
}
int currentShift = 0;
for (int i = 0; i < n; i++) {
currentShift = (currentShift + prefix[i]) % 26;
s[i] = 'a' + (s[i] - 'a' + currentShift + 26) % 26;
}
return s;
}
};