テンセント2016研究開発エンジニアプログラミング問題(二題)

第一題
一組の数の符号化において、いずれか2つの隣接する符号が1ビットのバイナリ数だけ異なる場合、この符号化をグレイコード(Gray Code)と呼び、1つの関数を記述し、再帰的な方法でNビットのグレイコードを生成してください.
整数nを指定すると、nビットのグレイコードを返し、0から順に返します.
テストサンプル:

1

 ：["0","1"]

問題解:この問題はグレイコード生成規則を考察する.具体的な思想は私のもう一つの博文を参考にします.この問題は以下の点に注意してください.
1、バックトラックを使用するため、プログラムではArrayListをミドルウェアとして結果を格納し、最後に配列に移行する文字列配列を返す必要があります.
2、タイトルは長さnの2進列を返すことを要求するので、長さが足りない場合は左側でゼロを補う必要がある.
参照コード:

import java.util.*;

public class GrayCode {
    public String[] getGray(int n) {
        List result = new ArrayList<>();
        result.add(0);
        for (int i = 0; i < n; i++) {
            int x = 1 << i;
            for (int j = result.size() - 1; j >= 0; j--) {
                result.add(x + result.get(j));
            }
        }
        String[] results = new String[result.size()];
        for (int i = 0; i < results.length; i++) {
            results[i] = Integer.toBinaryString(result.get(i));
            int diff = n - results[i].length();
            for (int j = 0; j < diff; j++) {
                results[i] = "0" + results[i];
            }
        }

        return results;
    }
}

第二題
春節の間、明ちゃんは微信を使ってお年玉をたくさんもらって、とても楽しかったです.お年玉の受け取り記録を見ると、あるお年玉の金額がお年玉の総数の半分を超えていることがわかりました.明ちゃんにこのお年玉の金額を見つけてください.具体的なアルゴリズムの構想とコードの実現を書き出して、アルゴリズムができるだけ効率的であることを要求します.
お年玉の金額配列giftsとその大きさnを指定し、求めたお年玉の金額を返してください.
テストサンプル:

[1,2,3,2,2],5

 ：2

問題解:本題は正の整数配列を与えて、ある数xが存在するかどうかを探して、xが配列の中で現れる回数は配列の長さの半分より大きいです.
考え方:
1、配列を並べ替え、中間位置要素xを取り、配列中にxが現れる回数を統計し、配列長の半分より大きい場合はxを返し、そうでない場合は0を返す.
2、2つの一時変数k,jを設定する.kは配列中の要素を格納し、jはその要素の指数を表す.次の要素がkに等しい場合、j+1.次の要素がkに等しくない場合、j−1は、jが0に等しい場合、kを現在遍歴している要素に設定する.配列を1回巡った後に検索要素kが配列に現れる回数は、配列の長さの半分より大きい場合はkを返し、そうでない場合は0を返す.
参考コード(考え方2):

import java.util.*;

public class Gift {
    public int getValue(int[] gifts, int n) {
        int k = gifts[0];
        int j = 0;
        for (int i = 0; i < n; i++) {
            if (k == gifts[i]) {
                j++;
            }else{
                j--;
                if (j == 0) {
                    k = gifts[i];
                    j = 1;
                }
            }
        }
        int sum = 0;
        for (int i = 0; i < gifts.length; i++) {
            if (k == gifts[i]) {
                sum++;
            }
        }
        if (sum == n/2) {
            return 0;
        } else {
            return k;
        }
    }
}