【大厂机试题解法笔记】字符串加密
给出原文字符串 str，通过对字符串的每个字母进行改变来实现加密，加密方式是在每一个字母str[i] 偏移特定数组元素 a[i] 的量。
数组 a 的前三位已经赋值：a[0]=1，a[1]=2，a[2]=4，当 i>=3 时，数组元素 a[i]=a[i-1]+a[i-2]+a[i-3]。
例如：原文abcde加密后bdgkr，其中偏移量分别是1，2，4，7，13。
输入描述
输入描述：第一行是整数n，表示n组测试数据。 每组数据包含一行，原文str(只含有小写字母，长度大于 0 小于 50)。
输出描述：每组测试数据输出一行，表示密文。
用例
| 输入 | 输出 |
|---|---|
| 1 xy | ya |
| 2 xy abcde | ya bdgkr |
思考
题目给出了偏移数组的计算方式，这个就是动态规划数组的状态转移方程。只要根据这个方程计算字符串中的每个字符的偏移量，然后用字符对应的 ASCII 码或者字符在字母表中的索引计算新的字符。无论选择哪种计算方式都会遇到索引超出26个字母的索引范围，因此需要判断索引超出范围要进行取模使其正确在字母表中循环。这里用字符的ASCII 码计算索引，通过 aCode +（code - zCode -1) % 26 获得字符在 26 个小写字母中的索引。 aCode = 'a'.charAtCode(0) = 97，zCode = 'z'.charCodeAt(0) = 122。当 code = 125 时， (code - zCode -1 ) % 26 = (125 - 122 - 1) % 26 = 2; 实际是偏移了 3 个位置，减 1 是因为从初始位置 a = 97 开始偏移，故 97 + 2 = 99，结果是 c。
算法过程
-
输入读取：读取测试用例数量
n，依次处理每组测试用例的输入字符串。 -
生成偏移量：对每个输入字符串，生成对应的偏移量数组。偏移量生成规则为：
-
初始值：
a[0]=1, a[1]=2, a[2]=4。 -
递推公式：
a[i] = a[i-1] + a[i-2] + a[i-3]（当i≥3时）。
-
-
字符加密：对字符串中每个字符
s[i]，将其 ASCII 码加上对应偏移量a[i]。若结果超过'z'的 ASCII 码（122），则通过模运算循环回小写字母范围。 -
输出结果：将加密后的字符拼接为字符串并输出。
-
时间复杂度：\(O(n \times m)\)
-
n为测试用例数量，m为输入字符串的最大长度。 -
每个字符串需遍历一次，每次遍历中生成偏移量和字符加密的操作均为\(O(1)\)。
-
-
空间复杂度：
-
原实现：\(O(m)\) 需存储长度为
m的偏移量数组。 -
优化后：\(O(1)\) 通过滚动变量维护前三个偏移量，无需存储完整数组。
-
参考代码
function solution() {const n = parseInt(readline());const encryptStr = function(str) {const size = str.length;// const dp = Array(size);// dp[0] = 1;// dp[1] = 2;// dp[2] = 4;let a = 1, b = 2, c = 4; // 使用滚动数组优化let result = [];const zCode ='z'.charCodeAt(0);for (let i = 0; i < size; i++) {let currentOffset;if (i === 0) {currentOffset = 1;} else if (i === 1) {currentOffset = 2;} else if (i === 2) {currentOffset = 4;} if (i >= 3) {// dp[i] = dp[i-1] + dp[i-2] + dp[i-3];currentOffset = a + b + c;a = b;b = c;c = currentOffset;}let code = str[i].charCodeAt(0) + currentOffset; // dp[i];if (code > zCode) {code = (code - zCode - 1) % 26 + 97;}const s = String.fromCharCode( code );result.push(s);}return result.join('');};for (let i = 0; i < n; i++) {console.log(encryptStr(readline()));}
}const cases = [`1xy`,`2xyabcde`
];let caseIndex = 0;
let lineIndex = 0;const readline = (function () {let lines = [];return function () {if (lineIndex === 0) {lines = cases[caseIndex].trim().split("\n").map((line) => line.trim());}return lines[lineIndex++];};
})();cases.forEach((_, i) => {caseIndex = i;lineIndex = 0;solution();
});