题解 | #凯撒解密#

题目链接

凯撒解密

题目描述

这是又一个函数实现题。你需要实现一个 decodeWangzai 函数，来解密一个通过凯撒密码加密后的字符串。

函数接受两个参数：

password: 一个仅由小写字母组成的加密字符串。
n: 一个正整数，表示加密时每个字母向后错位的次数。

解密过程就是加密的逆过程：将每个字母向前移动 n 位。注意字母表的循环性，例如，'a' 向前移动 1 位会变成 'z'。

平台工作模式:

你只需要在给定的函数框架内编写核心逻辑。
评测系统会自动调用你的函数并验证结果。
你不应该编写 main 函数或任何输入/输出代码。

示例:

输入: "abcd", 1 (由平台处理)
你的函数被调用: decodeWangzai("abcd", 1)
你的函数应返回: "zabc"

解题思路

这道题是经典的凯撒密码解密问题，本质上是 noob56 凯撒加密的逆运算。核心在于处理字符的循环左移。

处理移位量: 加密时的移位次数 n 可能大于 26。由于字母表只有 26 个字母，移位 n 次和移位 n % 26 次的效果是相同的。因此，我们首先计算有效移位量：effective_shift = n % 26。
遍历与转换: 我们需要遍历输入字符串 password 中的每一个字符，并对其进行解密转换。
核心解密逻辑 (处理循环): 对于每个字符 c，解密就是将其向前（向左）移动 effective_shift 位。 a. 获取字符索引: 首先，计算字符 c 在字母表中的位置（0-indexed），即 idx = c - 'a'。 b. 计算新索引: 新的索引应该是 new_idx = idx - effective_shift。 c. 处理回绕 (Underflow): 如果 idx - effective_shift 是负数，就需要从字母表的末尾开始回绕。例如，'a' (索引0) - 1 应该得到 'z' (索引25)。一个通用且健壮的数学公式可以处理所有情况（包括正数和负数结果）： new_idx = (idx - effective_shift + 26) % 26; - 加上 26 可以确保即使 idx - effective_shift 为负，其结果也变为正数。 - 最后对 26 取模，将结果规范到 [0, 25] 的范围内。 d. 转换回字符: 将计算出的新索引 new_idx 转换回字符：'a' + new_idx。
构建结果: 将每个转换后的新字符拼接起来，形成最终的解密字符串并返回。在 C++ 中可以直接修改输入字符串的副本，在 Java 中使用 StringBuilder 或 char[]，在 Python 中构建一个新列表再 join 是比较高效的做法。

代码

注意：以下是你需要提交的全部内容，即在牛客网给定的模板中填写的代码。

c++
java
python

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 进行凯撒解密
     * @param password string字符串 旺仔哥哥的密码
     * @param n int整型 每个字符加密过程中错位的次数
     * @return string字符串
     */
    string decodeWangzai(string password, int n) {
        int effective_shift = n % 26;
        for (char &c : password) {
            int idx = c - 'a';
            int new_idx = (idx - effective_shift + 26) % 26;
            c = 'a' + new_idx;
        }
        return password;
    }
};

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 进行凯撒解密
     * @param password string字符串 旺仔哥哥的密码
     * @param n int整型 每个字符加密过程中错位的次数
     * @return string字符串
     */
    public String decodeWangzai(String password, int n) {
        int effective_shift = n % 26;
        StringBuilder sb = new StringBuilder();
        for (char c : password.toCharArray()) {
            int idx = c - 'a';
            int new_idx = (idx - effective_shift + 26) % 26;
            sb.append((char)('a' + new_idx));
        }
        return sb.toString();
    }
}

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 进行凯撒解密
# @param password string字符串 旺仔哥哥的密码
# @param n int整型 每个字符加密过程中错位的次数
# @return string字符串
#
class Solution:
    def decodeWangzai(self, password: str, n: int) -> str:
        effective_shift = n % 26
        res = []
        for char in password:
            idx = ord(char) - ord('a')
            new_idx = (idx - effective_shift + 26) % 26
            res.append(chr(ord('a') + new_idx))
        return "".join(res)

算法及复杂度

算法: 字符串处理、模运算。
时间复杂度: $\mathcal{O}(L)$ ，其中 $L$ 是字符串 password 的长度。我们只需要对字符串进行一次遍历。
空间复杂度: $\mathcal{O}(L)$ 。C++ 版本中虽然在形式上是原地修改，但 string 参数是按值传递的，所以函数调用时会创建一个副本，空间复杂度为 $\mathcal{O}(L)$ 。Java 和 Python 版本都明确创建了新的数据结构 (StringBuilder 或列表) 来存储结果，因此空间复杂度也是 $\mathcal{O}(L)$ 。