解题思路

这是一个递归生成格雷码的问题。格雷码的特点是：

  1. 相邻的两个数字只有一位二进制数不同
  2. 第一个数字和最后一个数字也只有一位不同
  3. 位格雷码有 个数字

解决方案：

  1. 使用递归方法生成格雷码
  2. 位格雷码可以由 位格雷码生成：
    • 在 位格雷码前面添加
    • 逆序遍历 位格雷码，在前面添加
  3. 基础情况是 时，返回 ["0", "1"]

代码

class GrayCode {
public:
    vector<string> getGray(int n) {
        vector<string> res;
        generateGray(res, n);
        return res;
    }
    
private:
    void generateGray(vector<string>& res, int n) {
        // 基础情况：1位格雷码
        if(n == 1) {
            res.push_back("0");
            res.push_back("1");
            return;
        }
        
        // 递归生成n-1位格雷码
        generateGray(res, n-1);
        
        // 逆序遍历，添加1前缀
        int len = res.size();
        for(int i = len-1; i >= 0; i--) {
            res.push_back("1" + res[i]);
        }
        
        // 为原有编码添加0前缀
        for(int i = 0; i < len; i++) {
            res[i] = "0" + res[i];
        }
    }
};

import java.util.*;
public class GrayCode {
    public String[] getGray(int n) {
        List<String> res = new ArrayList<>();
        generateGray(res, n);
        return res.toArray(new String[0]);
    }
    
    private void generateGray(List<String> res, int n) {
        // 基础情况：1位格雷码
        if(n == 1) {
            res.add("0");
            res.add("1");
            return;
        }
        
        // 递归生成n-1位格雷码
        generateGray(res, n-1);
        
        // 逆序遍历，添加1前缀
        int len = res.size();
        for(int i = len-1; i >= 0; i--) {
            res.add("1" + res.get(i));
        }
        
        // 为原有编码添加0前缀
        for(int i = 0; i < len; i++) {
            res.set(i, "0" + res.get(i));
        }
    }
}

class GrayCode:
    def getGray(self, n: int) -> List[str]:
        def generateGray(n: int) -> List[str]:
            # 基础情况：1位格雷码
            if n == 1:
                return ["0", "1"]
            
            # 递归生成n-1位格雷码
            prev = generateGray(n-1)
            
            # 生成n位格雷码
            result = []
            # 添加0前缀
            for code in prev:
                result.append("0" + code)
            # 逆序添加1前缀
            for code in reversed(prev):
                result.append("1" + code)
                
            return result
            
        return generateGray(n)

算法及复杂度

  • 算法：递归生成
  • 时间复杂度： - 需要生成 个格雷码
  • 空间复杂度： - 需要存储所有格雷码