首页 > 搜狗笔试第3题:新密码
头像
Unlimited_Blade_Works
编辑于 2020-09-06 23:13
+ 关注

搜狗笔试第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)。
下面给出暴力和记忆化搜索的代码,程序里通过生成随机字符串来验证记忆化搜索的正确性。如果有错误希望大家能指正。
  1. 暴力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("结果一致");
	}
}

全部评论

(1) 回帖
加载中...
话题 回帖

相关热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

近期精华帖

热门推荐