《藍橋杯每日一題》哈希·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;
    }

}
           

感謝你能看完， 如有錯誤歡迎評論指正，有好的思路可以交流一波，如果對你有幫助的話，點個贊支援下