グレイコード+微信のお年玉を生成

1680 ワード

一組の数の符号化において、いずれか2つの隣接する符号が1ビットのバイナリ数だけ異なる場合、この符号化をグレイコード(Gray Code)と呼び、1つの関数を記述し、再帰的な方法でNビットのグレイコードを生成してください.
整数nを指定すると、nビットのグレイコードを返し、0から順に返します.
テストサンプル:
 1
戻る:[[0]、[1]]
構想:2ビットグレイコードは「00」,「01」,「11」,「10」である.したがって,1ビットグレイ符号の前に0を加え,さらに1ビットグレイ符号に0を加える,すなわち2ビットグレイ符号を逆にする.
import java.util.*;
   
public class GrayCode {
    public String[] getGray(int n) {
        if(n<=0) return null;
        if(n==1) return new String[]{"0","1"};
        String[] tmpStr = getGray(n-1);
        String[] resultStr = new String[tmpStr.length*2];
        int i;
        for(i=0;i<tmpStr.length;i++){
            resultStr[i]="0"+tmpStr[i];
        }
        for(int j=tmpStr.length-1;j>=0;j--){
            resultStr[i++]="1"+tmpStr[j];
        }
        return resultStr;
    }
       
}

春節の間、明ちゃんは微信を使ってお年玉をたくさんもらって、とても楽しかったです.お年玉の受け取り記録を見ると、あるお年玉の金額がお年玉の総数の半分を超えていることがわかりました.明ちゃんにこのお年玉の金額を見つけてください.具体的なアルゴリズムの構想とコードの実現を書き出して、アルゴリズムができるだけ効率的であることを要求します.
お年玉の金額配列giftsとその大きさnを指定し、求めたお年玉の金額を返してください.
テストサンプル:
  [1,2,3,2,2],5
戻る:2
importjava.util.*;
 
publicclass Gift {
    publicint getValue(int[] gifts, intn) {
        // write code here
        Map<Integer,Integer> map=newHashMap();
        for(inti=0;i<gifts.length;i++){
        if(map.containsKey(gifts[i])){
            intk=map.get(gifts[i]);
            k++;
            map.put(gifts[i],k);
            if(k>n/2){
                returngifts[i];
            }
        }else{
            map.put(gifts[i],1);
        }
             
        }
        return0;
    }
}