2023-12-13：用 go 语言，密码是一串长度为 n 的小写字母，一则关于密码的线索纸条，
首先将字母 a 到 z 编号为 0 到 25 编号，
纸条上共有 n 个整数 ai，其中 a1 表示密码里第一个字母的编号，
若 i>1 的话就表示第 i 个字母和第 i-1 个字母编号的差值，
例如，a2 就代表密码中第 1 个字母和第 2 个字母编号的差值，
若密码是 acb，那么纸条上的数字就是[5, 2, 1]，
a b c d e f
0 1 2 3 4 5
返回可能的密码的个数，由于结果可能很大，
输出对 1000000007 取模的结果。
1 <= n <= 10^5，
0 <= ai <= 25。
来自字节。
答案 2023-12-13：
灵捷3.5
大体过程如下：
算法一（ways1）：
1.定义函数 ways1，传入一个整数数组 arr 作为参数。
2.在 process1 函数中，传入当前索引 i 和前一个字母的编号 pre 作为参数。
3.如果 pre 小于 0 或大于 25，则返回 0；否则，进入下一步。
4.若当前索引 i 等于数组长度，则说明已经遍历完所有字母，返回 1。
5.否则，定义变量 ans 初始化为 0。
6.递归调用 process1 函数，传入 i+1 和 pre-arr[i]作为参数，并将结果累加到 ans 上。
7.递归调用 process1 函数，传入 i+1 和 pre+arr[i]作为参数，并将结果累加到 ans 上。
8.返回 ans 作为结果。
算法二（ways2）：
1.定义函数 ways2，传入一个整数数组 arr 作为参数。
2.初始化变量 mod 为 1000000007 和 n 为数组长度。
3.创建二维切片 dp，大小为(n+1)×26，用于存储动态规划的结果。其中 dp[i][j]表示考虑第 i 个位置时，以 j 号字母结尾的可能密码的个数。
4.将最后一行 dp[n][j]全部初始化为 1，表示在最后一个位置时，每个字母都是合法的密码结尾位置。
5.倒序遍历数组 arr 中的元素：
5.1.对于每个字母对应的编号 j，遍历 0 到 25：
5.1.1.如果 j-arr[i]大于等于 0，则将 dp[i][j]的值更新为 dp[i+1][j-arr[i]]。
5.1.2.如果 j+arr[i]小于 26，则将 dp[i][j]的值与 dp[i+1][j+arr[i]]相加，并对 mod 取模。
6.返回 dp[1][arr[0]]作为结果。
算法一的时间复杂度是 O(2^n)，空间复杂度是 O(n)。
算法二的时间复杂度是 O(n)，空间复杂度是 O(n)。
go 完整代码如下：
package main
import "fmt"
func ways1(arr []int) int { return process1(arr, 1, arr[0])}
func process1(arr []int, i, pre int) int { if pre < 0 || pre > 25 { return 0 } else { if i == len(arr) { return 1 } else { ans := 0 ans += process1(arr, i+1, pre-arr[i]) ans += process1(arr, i+1, pre+arr[i])
return ans } }}
func ways2(arr []int) int { mod := 1000000007 n := len(arr) dp := make([][]int, n+1) for i := 0; i <= n; i++ { dp[i] = make([]int, 26) }
for j := 0; j < 26; j++ { dp[n][j] = 1 }
for i := n - 1; i >= 1; i-- { for j := 0; j < 26; j++ { if j-arr[i] >= 0 { dp[i][j] = dp[i+1][j-arr[i]] } if j+arr[i] < 26 { dp[i][j] = (dp[i][j] + dp[i+1][j+arr[i]]) % mod } } }
return dp[1][arr[0]]}
func main() { arr := []int{5, 2, 1} result1 := ways1(arr) result2 := ways2(arr)
fmt.Println("Result using ways1:", result1) fmt.Println("Result using ways2:", result2)}
复制代码
c++完整代码如下：
#include <iostream>#include <vector>
int process1(std::vector<int>& arr, int i, int pre) { if (pre < 0 || pre > 25) { return 0; } else { if (i == arr.size()) { return 1; } else { int ans = 0; ans += process1(arr, i + 1, pre - arr[i]); ans += process1(arr, i + 1, pre + arr[i]);
return ans; } }}
int ways1(std::vector<int>& arr) { return process1(arr, 1, arr[0]);}
int ways2(std::vector<int>& arr) { const int MOD = 1000000007; int n = arr.size(); std::vector<std::vector<int>> dp(n + 1, std::vector<int>(26));
for (int j = 0; j < 26; ++j) { dp[n][j] = 1; }
for (int i = n - 1; i >= 1; --i) { for (int j = 0; j < 26; ++j) { if (j - arr[i] >= 0) { dp[i][j] = dp[i + 1][j - arr[i]]; } if (j + arr[i] < 26) { dp[i][j] = (dp[i][j] + dp[i + 1][j + arr[i]]) % MOD; } } }
return dp[1][arr[0]];}
int main() { std::vector<int> arr{ 5, 2, 1 }; int result1 = ways1(arr); int result2 = ways2(arr);
std::cout << "Result using ways1: " << result1 << std::endl; std::cout << "Result using ways2: " << result2 << std::endl;
return 0;}
复制代码
c 完整代码如下：
#include <stdio.h>#include <stdlib.h>
int process1(int* arr, int i, int pre, int len) { if (pre < 0 || pre > 25) { return 0; } else { if (i == len) { return 1; } else { int ans = 0; ans += process1(arr, i + 1, pre - arr[i], len); ans += process1(arr, i + 1, pre + arr[i], len);
return ans; } }}
int ways1(int* arr, int len) { return process1(arr, 1, arr[0], len);}
int ways2(int* arr, int len) { const int MOD = 1000000007; int n = len; int** dp = (int**)malloc((n + 1) * sizeof(int*));
for (int i = 0; i <= n; ++i) { dp[i] = (int*)malloc(26 * sizeof(int)); }
for (int j = 0; j < 26; ++j) { dp[n][j] = 1; }
for (int i = n - 1; i >= 1; --i) { for (int j = 0; j < 26; ++j) { if (j - arr[i] >= 0) { dp[i][j] = dp[i + 1][j - arr[i]]; } if (j + arr[i] < 26) { dp[i][j] = (dp[i][j] + dp[i + 1][j + arr[i]]) % MOD; } } }
int result = dp[1][arr[0]];
for (int i = 0; i <= n; ++i) { free(dp[i]); }
free(dp);
return result;}
int main() { int arr[] = { 5, 2, 1 }; int len = sizeof(arr) / sizeof(arr[0]);
int result1 = ways1(arr, len); int result2 = ways2(arr, len);
printf("Result using ways1: %d\n", result1); printf("Result using ways2: %d\n", result2);
return 0;}
复制代码
评论