C++实现LeetCode(89.格雷码)

[LeetCode] 89.Gray Code 格雷码

The gray code is a binary numeral system where two successive values differ in only one bit.

Given a non-negative integer n representing the total number of bits in the code, print the sequence of gray code. A gray code sequence must begin with 0.

For example, given n = 2, return [0,1,3,2]. Its gray code sequence is:

00 - 0
01 - 1
11 - 3
10 - 2

Note:
For a given n, a gray code sequence is not uniquely defined.

For example, [0,2,3,1] is also a valid gray code sequence according to the above definition.

For now, the judge is able to judge based on one instance of gray code sequence. Sorry about that.

这道题是关于格雷码的,猛地一看感觉完全没接触过格雷码,但是看了维基百科后,隐约的感觉原来好像哪门可提到过,哎全还给老师了。这道题如果不了解格雷码,还真不太好做,幸亏脑补了维基百科,上面说格雷码是一种循环二进制单位距离码,主要特点是两个相邻数的代码只有一位二进制数不同的编码,格雷码的处理主要是位操作 Bit Operation,LeetCode中关于位操作的题也挺常见,比如 Repeated DNA Sequences 求重复的DNA序列, Single Number 单独的数字, 和  Single Number II 单独的数字之二 等等。三位的格雷码和二进制数如下:

Int    Grey Code    Binary 

0      000        000
1      001        001
2      011        010
3      010        011
4      110        100
5      111        101
6      101        110
7      100        111

其实这道题还有多种解法。首先来看一种最简单的,是用到格雷码和二进制数之间的相互转化,明白了转换方法后,这道题完全没有难度,代码如下:

解法一:

// Binary to grey code
class Solution {
public:
    vector<int> grayCode(int n) {
        vector<int> res;
        for (int i = 0; i < pow(2,n); ++i) {
            res.push_back((i >> 1) ^ i);
        }
        return res;
    }
};

然后我们来看看其他的解法,参考维基百科上关于格雷码的性质,有一条是说镜面排列的,n位元的格雷码可以从n-1位元的格雷码以上下镜射后加上新位元的方式快速的得到,如下图所示一般。

有了这条性质,我们很容易的写出代码如下:

解法二:

// Mirror arrangement
class Solution {
public:
    vector<int> grayCode(int n) {
        vector<int> res{0};
        for (int i = 0; i < n; ++i) {
            int size = res.size();
            for (int j = size - 1; j >= 0; --j) {
                res.push_back(res[j] | (1 << i));
            }
        }
        return res;
    }
};

维基百科上还有一条格雷码的性质是直接排列,以二进制为0值的格雷码为第零项,第一项改变最右边的位元,第二项改变右起第一个为1的位元的左边位元,第三、四项方法同第一、二项,如此反复,即可排列出n个位元的格雷码。根据这条性质也可以写出代码,不过相比前面的略微复杂,代码如下:

0 0 0
0 0 1
0 1 1
0 1 0
1 1 0
1 1 1
1 0 1
1 0 0

解法三:

// Direct arrangement
class Solution {
public:
    vector<int> grayCode(int n) {
        vector<int> res{0};
        int len = pow(2, n);
        for (int i = 1; i < len; ++i) {
            int pre = res.back();
            if (i % 2 == 1) {
                pre = (pre & (len - 2)) | ((~pre) & 1);
            } else {
                int cnt = 1, t = pre;
                while ((t & 1) != 1) {
                    ++cnt;
                    t >>= 1;
                }
                if ((pre & (1 << cnt)) == 0) pre |= (1 << cnt);
                else pre &= ~(1 << cnt);
            }
            res.push_back(pre);
        }
        return res;
    }
};

上面三种解法都需要事先了解格雷码及其性质,假如我们之前并没有接触过格雷码,那么我们其实也可以用比较笨的方法来找出结果,比如下面这种方法用到了一个set来保存已经产生的结果,我们从0开始,遍历其二进制每一位,对其取反,然后看其是否在set中出现过,如果没有,我们将其加入set和结果res中,然后再对这个数的每一位进行遍历,以此类推就可以找出所有的格雷码了,参见代码如下:

解法四:

class Solution {
public:
    vector<int> grayCode(int n) {
        vector<int> res;
        unordered_set<int> s;
        helper(n, s, 0, res);
        return res;
    }
    void helper(int n, unordered_set<int>& s, int out, vector<int>& res) {
        if (!s.count(out)) {
            s.insert(out);
            res.push_back(out);
        }
        for (int i = 0; i < n; ++i) {
            int t = out;
            if ((t & (1 << i)) == 0) t |= (1 << i);
            else t &= ~(1 << i);
            if (s.count(t)) continue;
            helper(n, s, t, res);
            break;
        }
    }
};

既然递归方法可以实现,那么就有对应的迭代的写法,当然需要用stack来辅助,参见代码如下:

解法五:

class Solution {
public:
    vector<int> grayCode(int n) {
        vector<int> res{0};
        unordered_set<int> s;
        stack<int> st;
        st.push(0);
        s.insert(0);
        while (!st.empty()) {
            int t = st.top(); st.pop();
            for (int i = 0; i < n; ++i) {
                int k = t;
                if ((k & (1 << i)) == 0) k |= (1 << i);
                else k &= ~(1 << i);
                if (s.count(k)) continue;
                s.insert(k);
                st.push(k);
                res.push_back(k);
                break;
            }
        }
        return res;
    }
};

到此这篇关于C++实现LeetCode(89.格雷码)的文章就介绍到这了,更多相关C++实现格雷码内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

(0)

相关推荐

  • C++实现LeetCode(79.词语搜索)

    [LeetCode] 79. Word Search 词语搜索 Given a 2D board and a word, find if the word exists in the grid. The word can be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. Th

  • C++实现LeetCode(80.有序数组中去除重复项之二)

    [LeetCode] 80. Remove Duplicates from Sorted Array II 有序数组中去除重复项之二 Given a sorted array nums, remove the duplicates in-place such that duplicates appeared at most twice and return the new length. Do not allocate extra space for another array, you mus

  • C++实现LeetCode(73.矩阵赋零)

    [LeetCode] 73.Set Matrix Zeroes 矩阵赋零 Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in place. click to show follow up. Follow up: Did you use extra space? A straight forward solution using O(mn) space is probably

  • C++实现LeetCode(74.搜索一个二维矩阵)

    [LeetCode] 74. Search a 2D Matrix 搜索一个二维矩阵 Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties: Integers in each row are sorted from left to right. The first integer of each row is great

  • C++实现LeetCode(76.最小窗口子串)

    [LeetCode] 76. Minimum Window Substring 最小窗口子串 Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n). Example: Input: S = "ADOBECODEBANC", T = "ABC" Output: "BA

  • C++实现LeetCode(81.在旋转有序数组中搜索之二)

    [LeetCode] 81. Search in Rotated Sorted Array II 在旋转有序数组中搜索之二 Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand. (i.e., [0,0,1,2,2,5,6] might become [2,5,6,0,0,1,2]). You are given a target value to search.

  • C++实现LeetCode(75.颜色排序)

    [LeetCode] 75. Sort Colors 颜色排序 Given an array with n objects colored red, white or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white and blue. Here, we will use the integers 0, 1, and 2

  • C++实现LeetCode(82.移除有序链表中的重复项之二)

    [LeetCode] 82. Remove Duplicates from Sorted List II 移除有序链表中的重复项之二 Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list. Example 1: Input: 1->2->3->3->4->4->5 Outp

  • C++实现LeetCode(89.格雷码)

    [LeetCode] 89.Gray Code 格雷码 The gray code is a binary numeral system where two successive values differ in only one bit. Given a non-negative integer n representing the total number of bits in the code, print the sequence of gray code. A gray code se

  • Python实现的生成格雷码功能示例

    本文实例讲述了Python实现的生成格雷码功能.分享给大家供大家参考,具体如下: 问题 在一组数的编码中,若任意两个相邻的代码只有一位二进制数不同, 则称这种编码为格雷码(Gray Code),请编写一个函数,使用递归的方法生成N位的格雷码. 解决方法: 给定一个整数n,请返回n位的格雷码,顺序为从0开始. 测试样例: 返回:["0","1"] 题目很刁钻,题干很简洁,样例很高冷-- 其中有一些微妙的关系 发现了这个规律之后,代码自然就很好写了 # -*- codi

  • C++实现LeetCode(201.数字范围位相与)

    [LeetCode] 201.Bitwise AND of Numbers Range 数字范围位相与 Given a range [m, n] where 0 <= m <= n <= 2147483647, return the bitwise AND of all numbers in this range, inclusive. For example, given the range [5, 7], you should return 4. Credits: Special t

  • matlab遗传算法求解车间调度问题分析及实现源码

    目录 一.车间调度简介 1 车间调度定义 2 传统作业车间调度 二.遗传算法简介 1 遗传算法概述 2 遗传算法的特点和应用 3 遗传算法的基本流程及实现技术 3.1 遗传算法的基本流程 3.2 遗传算法的实现技术 4 遗传算法的基本原理 4.1 模式定理 4.2 积木块假设 三.部分源代码 四.运行结果 五.matlab版本及参考文献 一.车间调度简介 1 车间调度定义 车间调度是指根据产品制造的合理需求分配加工车间顺序,从而达到合理利用产品制造资源.提高企业经济效益的目的.车间调度问题从数学

  • Python之列表推导式最全汇总(下篇)

    目录 前言 列表推导式 语法规范: 进阶实例 乘法口诀表 求100以内的质数(或称素数) 求出字符串的所有字串(可推广到所有可切片数据类型) 根据方程式画出字符图 EXCEL表格列号字串转整数 打印Gray格雷码序列 高阶实例 杨辉三角形 斐波那契数列 曼德勃罗集(Mandelbrot Set)分形 附录 前言 网传的七天学Python的路线如下,我觉得可以在学过此表中前几天的内容后,就可以回头来学习一下 列表推导式:它综合了列表.for循环和条件语句. 第一天:基本概念(4小时) : prin

  • 在java poi导入Excel通用工具类示例详解

    前言 本文主要给大家介绍了关于java poi导入Excel通用工具类的相关内容,分享出来供大家参考学习,下面话不多说了,来一起看看详细的介绍吧. 问题引入和分析 提示:如果不想看罗嗦的文章,可以直接到最后点击源码下载运行即可 最近在做一个导入Excel的功能,在做之前在百度上面查找"java通用导入Excel工具类",没有查到,大多数都是java通用导出Excel.后来仔细想想,导出可以利用java的反射,做成通用的,放进相应的实体成员变量中,导入为什么不可以呢?也是可以的,不过在做

  • python生成n个元素的全组合方法

    利用二进制反格雷码(bynary reflected Gray code)的方式生成n个元素的全组合,Cn1+Cn2+...+Cnn, 如在利用穷举方法解决背包问题时,就需要找出物品的所有组合的子集.如有物品1,2,3.我们就可以生成3个位串的格雷码,0表示不选择该物品,1表示选择该物品. 算法如下所示: import copy def brgd(n): ''' 递归生成n位的二进制反格雷码 :param n: :return: ''' if n==1: return ["0",&qu

  • 在 Python 中进行 One-Hot 编码

    目录 1.介绍​ 2.什么是One-Hot编码? ​3.实现-Pandas​ ​4.实现-Scikit-Learn​ 5.​One-hot编码在机器学习领域的应用​ 1.介绍​ 在计算机科学中,数据可以用很多不同的方式表示,自然而然地,每一种方式在某些领域都有其优点和缺点.      由于计算机无法处理分类数据,因为这些类别对它们没有意义,如果我们希望计算机能够处理这些信息,就必须准备好这些信息.      此操作称为预处理. 预处理的很大一部分是编码 - 以计算机可以理解的方式表示每条数据(该

  • python遗传算法之geatpy的深入理解

    目录 1. geatpy的安装 2. geatpy的基础数据结构 2.1 种群染色体 2.2 种群表现型 2.3 目标函数值 2.4 个体适应度 2.5 违反约束程度矩阵 2.6 译码矩阵 2.7 进化追踪器 3. geatpy的种群结构 3.1 Population类 3.2 PsyPopulation类 4. 求解标准测试函数——McCormick函数 5.参考文章 今天我们来学习python中的遗传算法的使用,我们这里使用的是geatpy的包进行学习,本博客主要从geatpy中的各种数据结

  • Flex中TabNavigator设置Tabs样式思路及源码

    1.设计思路 (1)设计一个TabNavigator,其中包含两个Tabs: (2)设置Tabs样式 2.设计源码 Tabs.mxml: 复制代码 代码如下: <?xml version="1.0" encoding="utf-8"?> <s:Application xmlns:fx="http://ns.adobe.com/mxml/2009" xmlns:s="library://ns.adobe.com/flex

随机推荐