2025年Leetcode 89 格雷编码

Leetcode 89 格雷编码题目 格雷编码是一个二进制数字系统 在该系统中 两个连续的数值仅有一个位数的差异 给定一个代表编码总位数的非负整数 n 打印其格雷编码序列 即使有多个不同答案 你也只需要返回其中一种 格雷编码序列必须以 0 开头 解题思路 格雷编码有个生成公式 跟数学相关的我不想管

大家好,我是讯享网,很高兴认识大家。
题目

格雷编码是一个二进制数字系统,在该系统中,两个连续的数值仅有一个位数的差异。

给定一个代表编码总位数的非负整数 n,打印其格雷编码序列。即使有多个不同答案,你也只需要返回其中一种。

格雷编码序列必须以 0 开头。


讯享网

解题思路

  格雷编码有个生成公式,跟数学相关的我不想管。由于每两个格雷码之间仅有一个二进制位的差别,所以可以用递归+回溯写。对于每一个节点的下一个状态,我们可以枚举改变每一个位得到下一个节点状态,再用一个标记数组记录生成过的数。整个过程是一个树状结构的前序遍历,所以得到的序列一定是两两之间仅相差一位。

  最开始的时候我用 now ^ (1 << i) 进行更新得到下一个数,这样做会造成重复判断,原因是每一位的初始状态是 0 ,从 0 到 1 后就没必要再回到 0 再判断一次。后来换成 now | (1 << i) ,限制了每一位每次都是从 0 更新到 1 ,不会再变成 0 。这样相当于剪枝了一半,前者执行用时14ms,后者执行用时7ms。

代码
class Solution { 
    public boolean[] flag; public void dfs(List<Integer> ans, int now, int n) { 
    if (flag[now]) return; else { 
    flag[now] = true; ans.add(now); } for (int i = 0; i < n; i++) { 
    int tmp = 1 << i; dfs(ans, now | tmp, n); } } public List<Integer> grayCode(int n) { 
    flag = new boolean[1 << n]; List<Integer> ans = new ArrayList<>(); dfs(ans, 0, n); return ans; } } 

讯享网

每日一题又遇到了,优化了一下,快一点,而且省内存。

讯享网class Solution { 
    public List<Integer> grayCode(int n) { 
    boolean[] flag = new boolean[1 << n]; List<Integer> ans = new ArrayList<>(); ans.add(0); dfs(ans, flag, 0, n); return ans; } private void dfs(List<Integer> ans, boolean[] flag, int now, int n) { 
    for (int i = 0; i < n; i++) { 
    int next = now | (1 << i); if (flag[next]) continue; else { 
    ans.add(next); flag[next] = true; dfs(ans, flag, next, n); } } } } 
小讯
上一篇 2025-04-08 08:35
下一篇 2025-02-07 08:18

相关推荐

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容,请联系我们,一经查实,本站将立刻删除。
如需转载请保留出处:https://51itzy.com/kjqy/132548.html