n位格雷码Java递归实现输入n=4时运行逻辑异常求助

问题排查结果 #

你的代码能输出正确格雷码完全是巧合，核心错误如下：

• 误用indexOf方法替代get方法：
  标准递归生成格雷码的逻辑是：生成n-1位格雷码后，先正序遍历加入结果（最高位补0），再倒序遍历n-1位格雷码，每个元素加2^(n-1)后加入结果（最高位补1）。你代码中第二个循环的逻辑写反了功能：

  // 你的错误写法：indexOf是查找值等于i-1的元素的下标，完全不符合需求
  int sun = x+result.indexOf(i-1);
  // 正确写法：取下标为i-1的元素值，再加高位权值
  int sun = x + list.get(i-1);
  

  你现在能得到合法结果纯粹是n较小时，i-1作为值刚好存在于列表中，返回的下标对应值刚好满足格雷码相邻位差1位的规则，才出现输出符合预期但添加顺序和你预想不一致的情况。
• Math.pow存在精度风险：
  Math.pow返回double类型，n较大时强转int会出现精度丢失，建议用位运算替代：

  // 替换int x = (int)Math.pow(2, n-1);
  int x = 1 << (n-1);
  

修正后完整代码 #

public static List<Integer> grayCode(int n) {
    return callrecursion(n);
}

public static List<Integer> callrecursion(int n){
    if (n==1) {
        List<Integer> list = new ArrayList<>();
        list.add(0);
        list.add(1);
        return list;
    }
    List<Integer> result = new ArrayList<>();
    List<Integer> list = callrecursion(n-1);
    // 正序添加n-1位格雷码（最高位为0）
    for (Integer integer : list) {
        result.add(integer);
    }
    int x = 1 << (n-1);
    // 倒序添加n-1位格雷码加高位权值（最高位为1）
    for (int i = list.size() - 1; i >= 0; i--) {
        result.add(x + list.get(i));
    }
    return result;
}

修正后代码的元素添加顺序就会符合你的预期。

内容的提问来源于stack exchange，提问作者Prabhakar singh