侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 471 篇文章
  • 累计创建 108 个标签
  • 累计收到 9 条评论

目 录CONTENT

文章目录

【差分数组】字母移位 II

GabrielxD
2022-08-21 / 0 评论 / 0 点赞 / 80 阅读 / 888 字 / 正在检测是否收录...

题目

6158. 字母移位 II


给你一个小写英文字母组成的字符串 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 只包含小写英文字母。

解题

方法一:差分数组

思路

首先维护一个长为 s.length() + 1差分数组(diffs),遍历移位数组,对于 shift[i]

  • 如果当前区间为向后移位(shift[i][2] == 1),那么就是在 shift[i][0] ~ shift[i][1]增量,所以 diffs[shift[i][0]] 自增,diffs[shift[i][1] + 1] 自减。
  • 如果当前区间为向前移位(shift[i][2] == 0),那么就是在 shift[i][0] ~ shift[i][1]减量,所以 diffs[shift[i][0]] 自减,diffs[shift[i][1] + 1] 自增。

遍历完成后差分数组就维护好了,随后遍历字符串,对于每一个字符:

首先维护变化量(diff),然后把该字符移位 diff

注意:chs[i] = (char) (((curr + diff) % 26 + 26) % 26 + 'a') 这里第一次余 26 把变化后的字符所代表的数字限制在了[25,25][-25, 25] ,然后加上 26 再余 26 就限制在了 [0,25][0, 25] ,随后就可以把它加上字符 'a' 放回原字串中了。

代码

class Solution {
    public String shiftingLetters(String s, int[][] shifts) {
        int n = s.length();
        int[] diffs = new int[n + 1];
        for (int[] shift : shifts) {
            if (shift[2] == 1) {
                ++diffs[shift[0]];
                --diffs[shift[1] + 1];
            } else {
                --diffs[shift[0]];
                ++diffs[shift[1] + 1];
            }
        }
        char[] chs = s.toCharArray();
        for (int i = 0, diff = 0; i < n; ++i) {
            int curr = chs[i] - 'a';
            diff += diffs[i];
            chs[i] = (char) (((curr + diff) % 26 + 26) % 26 + 'a');
        }
        return String.valueOf(chs);
    }
}
class Solution {
public:
    string shiftingLetters(string s, vector<vector<int>>& shifts) {
        int n = s.length();
        vector<int> diffs(n + 1);
        for (auto& shift : shifts) {
            if (shift[2]) {
                ++diffs[shift[0]];
                --diffs[shift[1] + 1];
            } else {
                --diffs[shift[0]];
                ++diffs[shift[1] + 1];
            }
        }
        for (int i = 0, diff = 0; i < n; ++i) {
            int curr = s[i] - 'a';
            diff += diffs[i];
            s[i] = ((curr + diff) % 26 + 26) % 26 + 'a';
        }
        return s;
    }
};
0

评论区