搜狗笔试第3题：新密码
听说这个题暴力只能过80%，考虑到中间的重复搜索，考虑记忆化搜索优化应该就能过了。具体思路如下：
设当前生成的新密码为arr，那么令dp[i][j]表示arr[i]=j时，生成的新密码的后缀arr[i,n)的可能种数。举个例子，假如说arr[i] = j，由于旧密码是固定的，那么从 arr[i]=j 开始生成的新密码后缀的种数必然是确定的。那么dfs时若第一次搜索这种情况，就把这个种数记下来保存到dp[i][j]中。若下次在搜索到这种情况，就无需再次搜索，直接取出dp[i][j]即可。
还有一个问题是如何判断生成的新密码中是否会出现旧密码呢？首先思考一下可以知道如果存在，那么必然只会生成1次。具体地，我们只需对旧密码进行一次遍历，判断根据旧密码能否生成一个相同的密码即可。更具体些，新密码想和旧密码相同，第一位必须取旧密码第一位，然后按照生成规则生成，生成出的下一位必须和旧密码对应位相同才能继续生成后面的位。最终可以总结出规律，由于向上和向下取整最多两种情况，那么旧密码任意相邻两位必须绝对值差<=1才能保证能生成相同的新密码。总体下来，判断是否重复只需O(n)的复杂度即可。总时间复杂度为O(n) + O(10*n)。
下面给出暴力和记忆化搜索的代码，程序里通过生成随机字符串来验证记忆化搜索的正确性。如果有错误希望大家能指正。
- 暴力dfs
public class Solution {
static boolean flag;
public static long dfs(String password,String cur,int num,int d,int n){
cur+=num;
if(d==n){
if(cur.equals(password)) flag = true;
return 1;
}
int curNum = password.charAt(d)-'0';
int sum = curNum+num;
if((sum&1)==0){
return dfs(password,cur,sum/2,d+1,n);
}else{
return dfs(password,cur,sum/2,d+1,n) + dfs(password,cur,sum/2+1,d+1,n);
}
}
public static long getPasswordCount1(String password){
long res = 0;
flag = false;
for(int i=0;i<10;i++){
res+=dfs(password,"",i,1,password.length());
}
return flag?res-1:res;
}
}
2. 记忆化搜索
public class Solution {
static long[][] dp;
//记忆化搜索
public static long dfs(String password,int num,int d,int n){
if(d==n) return 1;
if(dp[d][num]!=0) return dp[d][num];
int curNum = password.charAt(d)-'0';
int sum = curNum+num;
if((sum&1)==0){
return dp[d][num] = dfs(password,sum/2,d+1,n);
}else{
return dp[d][num] = dfs(password,sum/2,d+1,n) + dfs(password,sum/2+1,d+1,n);
}
}
public static long getPasswordCount(String password){
dp = new long[password.length()][10];
long res = 0;
for(int i=0;i<10;i++){
res+=dfs(password,i,1,password.length());
}
// 只有相邻两位相差<=1才有可能生成和初始串相同的串，否则不可能
for(int i=1;i<password.length();i++){
// 差>1，直接返回res
if(Math.abs(password.charAt(i)-password.charAt(i-1))>1) return res;
}
// 说明存在重复
return res-1;
}
}
3. 验证程序，随机生成数字字符串，两者输出结果全部相同说明正确
import java.util.Random;
public class mima {
static long[][] dp;
//记忆化搜索
public static long dfs(String password,int num,int d,int n){
if(d==n) return 1;
if(dp[d][num]!=0) return dp[d][num];
int curNum = password.charAt(d)-'0';
int sum = curNum+num;
if((sum&1)==0){
return dp[d][num] = dfs(password,sum/2,d+1,n);
}else{
return dp[d][num] = dfs(password,sum/2,d+1,n) + dfs(password,sum/2+1,d+1,n);
}
}
public static long getPasswordCount(String password){
dp = new long[password.length()][10];
long res = 0;
for(int i=0;i<10;i++){
res+=dfs(password,i,1,password.length());
}
// 只有相邻两位相差<=1才有可能生成和初始串相同的串，否则不可能
for(int i=1;i<password.length();i++){
// 差>1，直接返回res
if(Math.abs(password.charAt(i)-password.charAt(i-1))>1) return res;
}
// 说明存在重复
return res-1;
}
// 暴力dfs
public static long dfs1(String password,int num,int d,int n){
if(d==n) return 1;
int curNum = password.charAt(d)-'0';
int sum = curNum+num;
if((sum&1)==0){
return dfs1(password,sum/2,d+1,n);
}else{
return dfs1(password,sum/2,d+1,n) + dfs1(password,sum/2+1,d+1,n);
}
}
public static long getPasswordCount1(String password){
long res = 0;
for(int i=0;i<10;i++){
res+=dfs1(password,i,1,password.length());
}
// 只有相邻两位相差<=1才有可能生成和初始串相同的串，否则不可能
for(int i=1;i<password.length();i++){
// 差>1，直接返回res
if(Math.abs(password.charAt(i)-password.charAt(i-1))>1) return res;
}
// 说明存在重复
return res-1;
}
public static void main(String[] args) {
Random r = new Random(1);
int len = 10;
String[] passwordList = new String[len];
for(int i=0;i<len;i++){
StringBuilder password = new StringBuilder();
for(int j=0;j<30;j++){
password.append(Math.abs(r.nextInt())%10);
}
passwordList[i] = password.toString();
}
long[] res1 = new long[len];
long[] res2 = new long[len];
long start1 = System.currentTimeMillis();
for(int i=0;i<len;i++){
res1[i] = getPasswordCount(passwordList[i]);
}
long end1 = System.currentTimeMillis();
System.out.println("记忆化搜索运行时间为："+(end1-start1)+"ms");
for(int i=0;i<len;i++){
res2[i] = getPasswordCount1(passwordList[i]);
}
System.out.println("暴力运行时间为："+(System.currentTimeMillis()-end1)+"ms");
boolean isSame = true;
for(int i=0;i<len;i++){
if(res1[i]!=res2[i]){
System.out.println("数据：" + passwordList[i] + "两者结果不一致");
isSame = false;
}
}
if(isSame) System.out.println("结果一致");
}
}