题解 | #凯撒密码#

题意 给定一段密文str和偏移量d，求对应的明文（即明文的每个字符+偏移量=密文的每个字符）。 字符包含0-9、A-Z、a-z，且排列顺序为数字、大写字母、小写字母。

思路：遍历密文str的每一个字符，减去偏移量，等于所求明文的每个字符。

方法一 数组模拟

首先用一个字符串s存储排列顺序为0-9、A-Z、a-z的常量字符串。 遍历输入字符串str的每一个字符，跟常量字符串比较并寻找下标，再通过下标减去偏移量得到对应的明文字符。

class Solution {
public:
    string s="0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";//常量字符串
    string decode(string str, int d) {
        int n=str.size();
        for(int i=0;i<n;i++){//遍历密文字符串
            for(int j=0;j<62;j++){
                if(str[i]==s[j]){
                    str[i]=s[(j-d+62)%62];//(j-d+62)%62考虑下标越界
                    break;
                }
            }
        }
        return str;
    }
};

时间复杂度： ,第二重循环是常量级别，可以忽略，n是字符串长度。 空间复杂度：

方法二 模拟+MAP查找

首先用一个字符串s存储排列顺序为0-9、A-Z、a-z的常量字符串,和构造mapshixi 遍历输入字符串str的每一个字符，通过map映射寻找下标，再在常量字符串s通过下标减去偏移量得到对应的明文字符。

class Solution {
public:
    string s="0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";//常量字符串
    unordered_map<char,int> m;//字符到下标的映射
    string decode(string str, int d) {
        for(int i=0;i<10;i++){//初始化map
            m['0'+i]=i;
        }
        for(int i=10;i<36;i++){
            m['A'+i-10]=i;
        }
        for(int i=36;i<62;i++){
            m['a'+i-36]=i;
        }
        int n=str.size();
        for(int i=0;i<n;i++){//遍历密文字符串
            int x=m[str[i]];
            str[i]=s[(x-d+62)%62];//(j-d+62)%62考虑下标越界
        }
        return str;
    }
};

时间复杂度： 空间复杂度：