[Algo]プログラマ124国/地域のデジタルin Java


質問する


124カ国あります124カ国では、数字は10進数ではなく、以下の独自のルールで表されています.
124カ国には自然水しか存在しない.
124カ国では、すべての数字を表すときに1,2,4しか使用されません.
Image for post
自然数nをパラメータとして指定した場合、解関数を完了し、nを124カ国で使用した数値に置き換えた値を返します.

に近づく


問題を見るとバイナリで近づけることがわかる.そして、数字が増えると、新しいルールがあることに気づきました.問題は,探索,BFS,DFSなどの資料構造形式へのアクセスではなく,ルールの発見と実施である.
まず数字を3に分けて、シェアと残数を見つけます.Mathを1部分ける床処理を行い,残りはモジュールで演算した.これで残りの人は0、1、2、0になると4、1、2が加算されます.
また、シェアが3より大きい場合は上記を繰り返しますが、剰余金が0の場合、次の数字は直ちに桁数を変更するため、新しいルールが生成されます.すなわち、次の計算では、使用するシェアから1を減算すべきである.
パスした答えコードは以下の通りです.効率計算のためにStringビルダーを使用した.
import java.util.*;
class Solution {
     public String solution(int n) {
        List<Integer> arr = new ArrayList<>();
        int q = n;
        int r = Integer.MAX_VALUE;
while(q >= 3){
            q = (int)Math.floor(q / 3);
            r = n % 3;
            System.out.println(q);
            System.out.println(r);
            if(r == 0){
                q-=1;
                arr.add(0, 4);
            }else{
                arr.add(0, r);
            }
            n = q;
        }
        if(q != 0){
            arr.add(0, q);
        }
        
        String[] answer = new String[arr.size()];
        for(int i=0; i<arr.size(); i++){
            answer[i] = arr.get(i).toString();
        }
         
        StringBuilder sb = new StringBuilder();
        for (String str : answer){
            sb.append(str);
        }
     return sb.substring(0, sb.length());
    }
}