侧边栏壁纸
博主头像
GabrielxD

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

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

目 录CONTENT

文章目录

【数组, 字符串, 后缀和】字母移位

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

题目

848. 字母移位


有一个由小写字母组成的字符串 s,和一个长度相同的整数数组 shifts

我们将字母表中的下一个字母称为原字母的 移位 shift() (由于字母表是环绕的, 'z' 将会变成 'a')。

  • 例如,shift('a') = 'b', shift('t') = 'u', 以及 shift('z') = 'a'

对于每个 shifts[i] = x , 我们会将 s 中的前 i + 1 个字母移位 x 次。

返回 将所有这些移位都应用到 s 后最终得到的字符串

示例 1:

输入:s = "abc", shifts = [3,5,9]
输出:"rpl"
解释: 
我们以 "abc" 开始。
将 S 中的第 1 个字母移位 3 次后,我们得到 "dbc"。
再将 S 中的前 2 个字母移位 5 次后,我们得到 "igc"。
最后将 S 中的这 3 个字母移位 9 次后,我们得到答案 "rpl"。

示例 2:

输入: s = "aaa", shifts = [1,2,3]
输出: "gfd"

提示:

  • 1 <= s.length <= 10^5
  • s 由小写英文字母组成
  • shifts.length == s.length
  • 0 <= shifts[i] <= 10^9

解题

方法一:倒序遍历 后缀和

思路

对于每个 shift[i] = x 会将 s 中的前 i + 1 个字母移位 x 次,也就是说每个 s[i] 会移位 j=in1shift[j]\sum\limits _{j=i}^{n - 1} shift[j] 次,如表格所示:

i 移位
0 shift[0] + shift[1] + shift[2] + … + shift[n - 1]
1 shift[1] + shift[2] + … + shift[n - 1]
2 shift[3] + … + shift[n - 1]
n-3 shift[n-3] + shift[n-2] + shift[n-1]
n-2 shift[n-2] + shift[n-1]
n-1 shift[n-1]

那么我们只需要先倒序遍历数组求后缀和然后再枚举字符串中每一个字符把它移位后缀和数组中对应的次数即可。

注意:由于 shifts[i] 最大可能是 109 所以求后缀和时可能会发生整形溢出,需要在每次对 26 取余后再累加。
代码中直接在原数组上进行了累加,没有新建后缀和数组。

代码

class Solution {
public:
    string shiftingLetters(string s, vector<int>& shifts) {
        for (auto it = shifts.rbegin() + 1; it != shifts.rend(); ++it) {
            *it += *(it - 1) % 26;
        }
        for (int i = 0; i < s.length(); ++i) {
            s[i] = (s[i] - 'a' + shifts[i]) % 26 + 'a';
        }
        return s;
    }
};

方法二:一次遍历

思路

通过上面的代码易发现:每位后缀和只会使用一次,所以完全没必要构造出整个后缀和数组,在倒序遍历的过程中维护一个累加(accum)每次累加完成后移位字符即可。

代码

class Solution {
    static final char[] toChar = {'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z'};

    public String shiftingLetters(String s, int[] shifts) {
        int accum = 0;
        char[] chs = s.toCharArray();
        for (int i = shifts.length - 1; i >= 0; --i) {
            accum = (accum + shifts[i]) % 26;
            chs[i] = toChar[(chs[i] - 'a' + accum) % 26];
        }
        return String.valueOf(chs);
    }
}
// 关闭同步流,与算法逻辑无关
int _ = []() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    return 0;
}();

class Solution {
    const static int N = 0x3f3f3f3f;
    const char* to_char = new char[]{'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z'};

public:
    string shiftingLetters(string s, vector<int>& shifts) {
        int accum = 0;
        for (int i = shifts.size() - 1; i >= 0; --i) {
            accum += shifts[i];
            if (accum > N) accum %= 26;
            s[i] = to_char[(s[i] - 'a' + accum) % 26];
        }
        return s;
    }
};
0

评论区