改造字符串

题目描述

对于给定的字符串s，将其进行k轮改造，第k轮改造的步骤如下：

• 对于每一个大写字母，将其修改为其字母表中前面的一位字母，特别的，A前面一位为Z;

• 对于每一个小写字母，将其修改为其字母表中后面的第i位字母(i从1开始)，特别的，z后面一位为a；

米小游想让你输出第k轮改造后的字符串。

输入描述

第一行输入一个长度为1≤len(s)<10^6，由大小写字母混合构成的字符串s

第二行输入一个整数k(1≤k≤10^6)代表需要改造的轮数

输出描述

输出第k轮改造后的字符串。

示例

示例1

输入：
WhilE2

输出：
Ukloc

解释：
第一轮改造，`WhilE`变为`VijmD`；第二轮改造，`VijmD`变为`Ukloc`。

解题思路

解法1

逐个转换

• 对于大写字母，总位移量为 mov1=(-k%26+26)%26
• 对于小写字母，总位移量为 mov2=(k(k+1)/2)%26
• 遍历每个字符进行转换就好

时间复杂度：O(n)，其中n为字符串长度，需要遍历每个字符一次 空间复杂度：O(n)，需要存储结果字符串

解法2

映射表

• 预先构建字符映射表，这样在处理长字符串时可以避免重复计算转换规则
• 直接查表就能得到转换后的字符。

时间复杂度：O(n+26)=O(n)，其中n为字符串长度，需要遍历每个字符一次，构建映射表需要26次操作 空间复杂度：O(n+26)=O(n)，需要存储结果字符串和两个映射表（各26个字符）

C++ 解法

解法1

// 逐个转换
#include <iostream>
#include <string>

int main()
{
    std::string s;
    std::cin >> s;
    int k;
    std::cin >> k;

    // 计算位移量
    int uppercase_shift = (-k % 26 + 26) % 26;               // 大写字母向前移动
    int lowercase_shift = ((long long)k * (k + 1) / 2) % 26; // 小写字母向后移动

    std::string result;
    // 处理每个字符
    for (auto c : s) {
        if (isupper(c)) {
            // 大写字母处理
            result += 'A' + (c - 'A' + uppercase_shift) % 26;
        } else {
            // 小写字母处理
            result += 'a' + (c - 'a' + lowercase_shift) % 26;
        }
    }

    std::cout << result << std::endl;

    return 0;
}

解法2

// 使用映射表
#include <iostream>
#include <string>
#include <vector>

int main()
{
    std::string s;
    std::cin >> s;
    int k;
    std::cin >> k;

    // 计算位移量
    int uppercase_shift = (-k % 26 + 26) % 26;               // 大写字母向前移动
    int lowercase_shift = ((long long)k * (k + 1) / 2) % 26; // 小写字母向后移动

    // 构建映射表
    std::vector<char> uppercase_map(26);
    std::vector<char> lowercase_map(26);

    for (int i = 0; i < 26; i++) {
        uppercase_map[i] = 'A' + (i + uppercase_shift) % 26;
        lowercase_map[i] = 'a' + (i + lowercase_shift) % 26;
    }

    std::string result;
    for (auto c : s) {
        if (isupper(c)) {
            result += uppercase_map[c - 'A'];
        }
        else {
            result += lowercase_map[c - 'a'];
        }
    }

    std::cout << result << std::endl;

    return 0;
}