《蓝桥杯每日一题》哈希·AcWing 2058. 笨拙的手指

1.题目描述

每当贝茜将数字转换为一个新的进制并写下结果时，她总是将其中的某一位数字写错。

例如，如果她将数字 14 转换为二进制数，那么正确的结果应为 1110，但她可能会写下 0110 或 1111。

贝茜不会额外添加或删除数字，但是可能会由于写错数字的原因，写下包含前导 0 的数字。

给定贝茜将数字 N 转换为二进制数字以及三进制数字的结果，请确定 N 的正确初始值（十进制表示）。

输入格式

第一行包含 N 的二进制表示，其中一位是错误的。

第二行包含 N 的三进制表示，其中一位是错误的。

输出格式

输出正确的 N 的值。

数据范围

N 一定不超过 109，且存在唯一解。

输入样例

1010
212

输出样例

14

2.思路分析

有一个十分简单的思路，把二进制数，所有可能的数都计算出来，存下来。

再把三进制所以可能的数计算出来，存下来。

两者的交集，所共同拥有的数字，一定是正确答案。

首先，需要枚举，改变二进制每一位对应的数，直接异或取反即可，

然后将异或后的结果根据秦九韶算法转换成10进制数并保存到哈希数组中，

最后改变三进制每一位对应的数，转成10进制后判断其是否在哈希数组中存在

3.秦九韶算法

秦九绍算法是非常高效的转换为十进制数的算法，因为他可以计算多项式，我们便把他用于了其它进制向十进制的转换中，

4.Ac代码

import java.io.*;
import java.util.HashSet;public class Main {public static void main(String[] args) throws IOException {BufferedReader  br=new BufferedReader(new InputStreamReader(System.in));String s1=br.readLine();String s2=br.readLine();//转换成字符数组，字符串无法异或char []c1=s1.toCharArray();char []c2=s2.toCharArray();HashSet<Integer> hs=new HashSet<>();for (int i = 0; i < c1.length; i++) {//将每位数字异或取相反数字c1[i]^=1;//转换为10进制数后添加到哈希表中hs.add( change(c1,2));//然后转换回来，方便下一位转换c1[i]^=1;}for (int i = 0; i < c2.length; i++) {char t=c2[i];for(char j='0';j<'3';j++){//如果c本位等于当前的值则跳过继续，因为必定会错一位if(c2[i]==j)  continue;//如果不是则赋j值c2[i]=j;if(hs.contains(change(c2,3))){System.out.println(change(c2,3));return;}c2[i]=t;}}}//根据秦九韶算法将其他进制转换为10进制数private static Integer change(char c[], int t) {int re=0;for (int i = 0; i < c.length; i++) {re=re*t+c[i]-'0';}return re;}}

感谢你能看完， 如有错误欢迎评论指正，有好的思路可以交流一波，如果对你有帮助的话，点个赞支持下