题解 | #凯撒加密#

题目链接

凯撒加密

题目描述

实现一个凯撒密码算法。给定一个由小写英文字母组成的字符串和一个整数 k，需要将字符串中的每个字母向后循环移动 k 位。'a' 移动一位后是 'b'，'z' 移动一位后是 'a'。

输入描述:

第一行输入一个整数 k，表示错位次数。
第二行输入一个由小写英文字母组成的字符串 s。

输出描述:

输出对 s 中每个字符向后错位 k 次后得到的密码字符串。

示例:

输入:
```
1
abcdefg
```
输出: bcdefgh
输入:
```
2
xyz
```
输出: zab (x->y->z, y->z->a, z->a->b)

解题思路

这个问题的核心是字符的循环位移，可以通过数学中的模运算（取余）来优雅地解决。

读取输入: 首先，程序需要读取位移量 k 和原始字符串 s。
字符到数字的映射: 计算机中，字符是以数字（ASCII/Unicode码）形式存储的。'a' 到 'z' 是一段连续的编码。我们可以利用这一点，将每个字母映射到 0-25 的范围内，方便进行数学运算。
- 'a' 映射为 0
- 'b' 映射为 1
- ...
- 'z' 映射为 25 这个映射可以通过 (当前字符 - 'a') 来实现。
应用循环位移: 对于每个映射后的数字 pos（范围 0-25），我们将其加上位移量 k。为了处理循环，我们将结果对 26 取模。
- 新位置 = (pos + k) % 26
- 例如，对于 'y' (pos=24) 和 k=2，新位置是 (24 + 2) % 26 = 26 % 26 = 0。
- 对于 'z' (pos=25) 和 k=2，新位置是 (25 + 2) % 26 = 27 % 26 = 1。
数字到字符的映射: 计算出新位置后，再将其映射回字符。
- 这可以通过 ('a' + 新位置) 来实现。
- 新字符 = 'a' + (当前字符 - 'a' + k) % 26
构建结果: 遍历输入字符串的每一个字符，对每个字符执行上述转换，并将得到的新字符拼接起来，形成最终的密码字符串。

这个方法简洁且高效，完美地处理了字母表的循环特性。

代码

c++
java
python

#include <iostream>
#include <string>

using namespace std;

int main() {
    int k;
    cin >> k;
    string s;
    cin >> s;
    
    // 对 k 取模可以处理 k >= 26 的情况，虽然本题可能不需要
    k %= 26;
    
    for (char &c : s) {
        // 将字符 c 转换为 0-25 的数字，加上 k，然后对 26 取模，再转换回字符
        c = 'a' + (c - 'a' + k) % 26;
    }
    
    cout << s << endl;
    
    return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int k = sc.nextInt();
        String s = sc.next();
        
        // 对 k 取模以优化
        k %= 26;
        
        StringBuilder result = new StringBuilder();
        
        for (char c : s.toCharArray()) {
            int originalPos = c - 'a';
            int newPos = (originalPos + k) % 26;
            char newChar = (char) ('a' + newPos);
            result.append(newChar);
        }
        
        System.out.println(result.toString());
    }
}

# 读取输入
k = int(input())
s = input()

# 对 k 取模
k %= 26

result = []
for char_code in s.encode('ascii'):
    # char_code 是字符的 ASCII 值
    # ord('a') 是 'a' 的 ASCII 值
    original_pos = char_code - ord('a')
    new_pos = (original_pos + k) % 26
    new_char_code = ord('a') + new_pos
    result.append(chr(new_char_code))

print("".join(result))

算法及复杂度

算法: 模运算、字符串遍历。
时间复杂度: $\mathcal{O}(L)$ ，其中 L 是输入字符串的长度。因为我们需要遍历字符串中的每一个字符一次。
空间复杂度: $\mathcal{O}(L)$ 。在Java和Python中，需要一个额外的空间（如 StringBuilder 或列表）来构建和存储新的字符串。在C++中，虽然可以原地修改，但结果字符串本身也占用 $\mathcal{O}(L)$ 的空间，因此总体空间复杂度与输入规模成线性关系。