题意

给定字符串s,长度不大于1000

给定偏移量$dd$d，把$ss$s中每个字符转换成按照0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz顺序，字符前面$dd$d个的字符

例如:

A前面$22$2个是8

而0前面$33$3个是x

方法

实现题意

这道题没特殊的算法，主要是把题意翻译成代码即可

在实现过程中，我们建立了两个映射关系

字符到对应下标 ch2idx[字符] = 下标

下标到对应字符 idx2ch[下标] = 字符

这两个关系建立以后可以简化我们的逻辑实现目标字符 = idx2ch[ch2idx[当前字符]-偏移量]

其中对于下标小于零的情况

我们可以通过 +总长度 去计算，为了简化不去写if判断是否小于零,可以通过(值+总长度)%总长度 来完成

代码

class Solution {
public:
    /**
     * 解密密文
     * @param str string字符串 密文
     * @param d int整型 偏移量
     * @return string字符串
     */
    string decode(string str, int d) {
        // write code here
        const int cnt = 10+26+26;
        char ch2idx[1000];
        char idx2ch[cnt+10];
        int idx = 0;
        for(int i = 0;i<10;i++,idx++){ // 初始化数字部分
            char ch = '0'+i;
            ch2idx[ch] = idx;
            idx2ch[idx] = ch;
        }
        for(int i = 0;i<26;i++,idx++){ // 初始化大写部分
            char ch = 'A'+i;
            ch2idx[ch] = idx;
            idx2ch[idx] = ch;
        }
        for(int i = 0;i<26;i++,idx++){ // 初始化小写部分
            char ch = 'a'+i;
            ch2idx[ch] = idx;
            idx2ch[idx] = ch;
        }
        int n = str.length();
        for(int i = 0;i<n;i++){
            str[i] = idx2ch[(ch2idx[str[i]]+cnt-d)%cnt];
        }
        return str;
    }
};

复杂度分析

时间复杂度: 建立表，时间复杂度为常数, 就是要用到的字符的个数,可以看做$O\left(1\right)O(1)$O(1)

每个字符的转化是通过几次内存寻址和数***算，也是常数时间$O\left(1\right)O(1)$O(1)，所有字符需要转化，所以总的时间复杂度为$O\left(n\right)O(n)$O(n)

空间复杂度: 这里我们直接使用str对其进行修改,所以额外空间仅是常量和映射表,而映射表的大小是要映射的字符数与$nn$n无关,所以空间复杂度是$O\left(1\right)O(1)$O(1)

知识点

0. 英文字母有26个，或者利用char运算'z'-'a'+1
1. Ascii 里的 a-z,0-9,A-Z 的char值是连续的，同时char和int 可以做计算, 因此可以通过for 来产生，一定程度上如果你手动输入可能发生漏输入或者多输入或者顺序错的情况，通过for产生，只要字母个数不错就减少了出错的可能
2. 映射表的建立，建立一次，多次使用，总代价更小，也简化了逻辑判断，减少了出错可能
3. 对于负数需要对取模特殊处理的情况可以用(v+mod)%mod来完成，这样整数无影响，负数完成了非负转换，减少了逻辑判断，减少了出错可能