第一题
在一组数的编码中，若任意两个相邻的代码只有一位二进制数不同， 则称这种编码为格雷码(Gray Code)，请编写一个函数，使用递归的方法生成N位的格雷码。
给定一个整数n，请返回n位的格雷码，顺序为从0开始。
测试样例： 1 返回：["0","1"]题解：该题考察格雷码生成规则。具体思想参考我的另一篇博文。本题注意以下几点：
1、要求返回的是字符串数组，因为要用到Backtracking，程序中可以使用ArrayList作为中间件存储结果，最后转为数组。
2、题目要求返回长度为n的二进制串，因此对于长度不足的需要在左边补零。
参考代码：
import java.util.*; public class GrayCode { public String[] getGray(int n) { List<Integer> 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、设置两个临时变量k，j。k存储数组中某一元素，j代表该元素的指数。如果下一元素等于k，则j+1.如果下一元素不等于k，则j-1，当j等于0时，将k设置为当前遍历到的元素。遍历数组一遍以后查找元素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; } } }
