Acwing---841. 字符串哈希

本文主要是介绍Acwing---841. 字符串哈希，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

字符串哈希

1.题目
2.基本思想
3.代码实现

1.题目

奶牛贝茜正在学习如何在不同进制之间转换数字。

但是她总是犯错误，因为她无法轻易的用两个前蹄握住笔。

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

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

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

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

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

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

输出格式
输出正确的 $N$ 的值。

数据范围
$0≤N≤10^9$ ，且存在唯一解。

输入样例1：

1010
212

输出样例1：

14

样例解释
14 在二进制下的正确表示为 1110，在三进制下的正确表示为 112。

2.基本思想

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

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

首先，需要枚举，改变二进制每一位对应的数假设给你的为 01001 十进制为 9

首先特殊判断第一位，如果为0，那么第一位可以改变为1：11001 十进制为 9+2^4=25 【如果为1，则

不能在改变了，正常的数没有前导零】然后看第二位如果为0，则改变1，如果为1 则改变为0，记录下

改变的结果，以此重复.

三进制也是类似的办法:只不过三进制可以改变为0，1，2三种

3.代码实现

import java.util.HashSet;
import java.util.Scanner;class Main {static char[] arr2 = new char[40];private static int qjs(char[] arr, int b) {//秦九绍算法计算此二进制的十进制位int ten = 0;for (int i = 0; i < arr.length; i++) ten = ten * b + arr[i] - '0';return ten;}public static void main(String[] args) {Scanner sc = new Scanner(System.in);arr2 = sc.next().toCharArray();//二进制char[] arr3 = sc.next().toCharArray();//三进制HashSet<Integer> set = new HashSet<>();//枚举每一位 二进制下 可能错误的可能for (int i = 0; i < arr2.length; i++) {arr2[i] ^= 1;//将每位 数字 异或相反数字set.add(qjs(arr2, 2));arr2[i] ^= 1;//将改变的位置 变回来 以便下次使用}//计算3进制的可能for (int i = 0; i < arr3.length; i++) {//存储本位char c = arr3[i];for (char j = '0'; j < '3'; j++) {if (arr3[i] == j ) continue;//如果c本位等于当前的值则跳过继续arr3[i] = j; //不是则给a赋予j值if (set.contains(qjs(arr3, 3))) {System.out.println(qjs(arr3, 3));return;}arr3[i] = c;}}}
}