当前位置：首页 > news >正文

力扣第89题格雷编码

news 来源：原创 2025/5/15 13:17:51

题目描述

格雷编码序列是一个二进制数字序列，其中的每两个相邻的数字只有一个二进制位不同。给定一个整数 n，表示格雷编码的位数，要求返回 n 位的格雷编码序列。

示例 1

输入：

n = 2

输出：

[0, 1, 3, 2]

解释：

对于 n = 2，对应的格雷编码序列为 [00, 01, 11, 10]，它们的十进制表示为 [0, 1, 3, 2]。

示例 2

输入：

n = 3

输出：

[0, 1, 3, 2, 6, 7, 5, 4]

解释：

对于 n = 3，对应的格雷编码序列为 [000, 001, 011, 010, 110, 111, 101, 100]，它们的十进制表示为 [0, 1, 3, 2, 6, 7, 5, 4]。

解题思路

格雷编码序列的生成有两种常见方法：

递归法
数学公式法

方法 1：递归法（构建反射法）

递归的核心思想是：

通过已有的 $n$ 位的格雷编码序列，构建 $n + 1$ 位的格雷编码序列。
假设已有 $n$ 位的格雷编码序列为 G(n)，我们可以通过以下方法得到 G(n+1)：
- G(n+1) 的前半部分是 G(n) 本身。
- G(n+1) 的后半部分是 G(n) 的每个元素前面加上一个 1，并且反转原序列的顺序。

举个例子：

对于 n = 1，格雷编码序列是 [0, 1]。
对于 n = 2，格雷编码序列是 [00, 01, 11, 10]。

方法 2：数学公式法

格雷编码的数学公式为：
$\oplus (k >> 1)$
其中， $k$ 是当前的数字， $k >> 1$ 是 $k$ 右移一位， $\oplus (k >> 1)$ 是 $k$ 与右移后的 $k$ 进行按位异或操作。

使用该公式可以快速生成格雷编码序列。

代码实现

方法 1：递归法

#include <stdio.h>
#include <stdlib.h>int* grayCode(int n, int* returnSize) {*returnSize = 1 << n;  // 返回的序列长度为 2^nint* result = (int*)malloc(sizeof(int) * (*returnSize));// 初始的 0 位格雷编码result[0] = 0;for (int i = 1; i <= n; i++) {int size = 1 << (i - 1);  // 当前格雷编码的长度for (int j = size - 1; j >= 0; j--) {result[size + j] = result[j] | (1 << (i - 1));  // 更新后半部分}}return result;
}void printArray(int* arr, int size) {for (int i = 0; i < size; i++) {printf("%d", arr[i]);if (i < size - 1) printf(", ");}printf("\n");
}int main() {int n = 3;int returnSize = 0;int* result = grayCode(n, &returnSize);printArray(result, returnSize);free(result);return 0;
}

方法 2：数学公式法

#include <stdio.h>
#include <stdlib.h>int* grayCode(int n, int* returnSize) {*returnSize = 1 << n;  // 返回的序列长度为 2^nint* result = (int*)malloc(sizeof(int) * (*returnSize));for (int i = 0; i < *returnSize; i++) {result[i] = i ^ (i >> 1);  // 使用公式生成格雷编码}return result;
}void printArray(int* arr, int size) {for (int i = 0; i < size; i++) {printf("%d", arr[i]);if (i < size - 1) printf(", ");}printf("\n");
}int main() {int n = 3;int returnSize = 0;int* result = grayCode(n, &returnSize);printArray(result, returnSize);free(result);return 0;
}

代码详解

1. 递归法实现

我们从最简单的格雷编码 [0] 开始，逐步扩展到 $n$ 位。
每次扩展时，通过反射法创建新的序列：
- 将已有的序列复制到前半部分。
- 将每个数值在前面加上 1，并将该部分的顺序反转，加入到后半部分。

2. 数学公式法实现

通过公式 $\oplus (k >> 1)$ 来计算每个数字的格雷编码。
通过位运算，我们可以在 $O (1)$ 的时间内生成每个数字的格雷编码。

时间与空间复杂度

时间复杂度

对于递归法：生成每一位的格雷编码序列时，需要 $O(2^n)$ 的时间，因此时间复杂度是 $O(2^n)$ 。
对于数学公式法：直接计算每个数字的格雷编码，因此时间复杂度是 $O(2^n)$ 。

空间复杂度

对于两种方法：需要存储生成的格雷编码序列，空间复杂度是 $O(2^n)$ 。

测试用例

示例 1：

输入：

n = 2

输出：

[0, 1, 3, 2]

示例 2：

输入：

n = 3

输出：

[0, 1, 3, 2, 6, 7, 5, 4]

力扣第89题格雷编码

题目描述格雷编码序列是一个二进制数字序列，其中的每两个相邻的数字只有一个二进制位不同。给定一个整数 n，表示格雷编码的位数，要求返回 n 位的格雷编码序列。示例 1 输入： n 2输出： [0, 1, 3, 2]解释&#x…...

编程日记 2025/5/15 13:17:51

ros sensor_msgs::Imu详细介绍 Eigen::Vector3d 详细介绍

1.ros sensor_msgs::Imu详细介绍 sensor_msgs::Imu 是 ROS（Robot Operating System）中用于表示惯性测量单元（IMU）数据的消息类型。IMU 是一种传感器，通常用于测量物体的线性加速度、角速度和方向信息。以下是 sensor_…...

编程日记 2025/5/16 2:37:36

【ArcGIS微课1000例】0133：二维建筑物依据高度生成三维模型

拓展阅读：【ArcGIS Pro微课1000例】0032：创建具有指定高程Z值的矢量数据文章目录一、二维面要素拉伸实现三维显示二、依据高度实现要素转3D一、二维面要素拉伸实现三维显示打开ArcScene软件，加载实验配套数据0133.rar中的建筑物.shp数据，如下图：数据属性表中的Z为建筑…...

编程日记 2025/5/7 10:32:17

虚拟内存的意义

1.什么是虚拟内存虚拟内存的基本原理是将物理内存与磁盘空间组合使用，将正在执行的程序的部分数据和代码加载到物理内存中，而不是全部加载。当程序需要访问未加载到内存的部分时，操作系统会将相关数据从磁盘中加载到内存中 2.为了解决什么…...

编程日记 2025/5/13 5:54:14

h5 sqlite 操作封装

参考文档错误码 // 数据库名称 const namesjk "sl" // 存储路径 const path _doc/${name}.db/** 基本操作* 查询数据库连接状态 isOpenDatabase * 无参数* 返回 true false* * * 关闭数据库 closeDatabase* 无参数* Promise 成功/失败* * * …...

编程日记 2025/5/6 4:42:08

Git 详解

Git 详解 Git 是一个分布式版本控制系统，用于高效地管理项目代码的版本历史。它是目前最流行的版本控制工具之一，广泛应用于软件开发领域。Git 的分布式架构允许开发者在本地进行代码的版本管理，并与远程仓库同步，实现团队协作。…...

编程日记 2025/5/10 15:30:48

Redis设计与实现第17章 -- 集群总结3（ASK错误、复制与故障转移、消息）

17.5 ASK错误在进行重新分片期间，源节点向目标节点迁移一个槽的过程中，可能会出现这样一种情况：属于被迁移槽的一部分键值对保存在源节点里面，而另一部分键值对则保存在目标节点里面。当客户端向源节点发送一个与数据库键有关的…...

编程日记 2025/5/11 22:04:21

支持向量机（SVM）的解析与应用：从封闭解到时代演变（中英双语）

中文版支持向量机（SVM）的解析与应用：从封闭解到时代演变什么是支持向量机（SVM）？ 支持向量机（Support Vector Machine, SVM）是一种经典的监督学习算法，用于解决分类和…...

编程日记 2025/5/15 6:28:46

Linux 密码学的基本知识与应用技术

一、基本知识 （一）加密算法 • 对称加密算法 • 原理：对称加密使用相同的密钥进行加密和解密。例如，在Linux中常用的AES（高级加密标准）算法，发送方和接收方都需要持有相同的密钥。假设要加密…...

编程日记 2025/5/16 2:18:21

【力扣】2094.找出3为偶数

思路方法一：使用Set集合 1.首先是三层for循环，遍历，并且遇到不满足的情况，便跳过，继续计算。不如前导为0,以及遍历同一个数组下标的情况 2.使用Set集合来确保答案是唯一的，使用桶来标记也是可以的 3.但是…...

编程日记 2025/5/11 18:16:19

【信息系统项目管理师】【综合知识】【备考知识点】第十四章项目沟通管理

【移动端浏览】☞【信息系统项目管理师】第十四章项目沟通管理第十四章项目沟通管理 （项目沟通管理）定义项目沟通管理是确保及时、正确地产生、收集、分发、存储和最终处理项目信息所需的过程。 （项目沟通管理）组成部分 (…...

编程日记 2025/5/15 13:53:16

CTFshow黑盒测试刷题

web380 先扫目录打开报错了先用伪协议去查看源码之前扫到有flag.php 访问一下就得到flag了 web381 查看一下源码点击第三个css 藏在目录里面 web382 跟上题一样不过访问这个页面是一个登录框试一下弱口令最后是admin admin888 就进去了 web383 进入这个后台 …...

编程日记 2025/5/12 23:39:22

抖音矩阵系统快速部署指南/抖音矩阵系统源码分发，短视频矩阵账号管理系统开发部署—

抖音矩阵系统的源码分发与短视频账号管理平台的开发部署，要求通过对接官方API来实现功能的拓展。当前开发的账号矩阵管理系统专注于提供一键式管理多个账户的能力，支持定时发布内容、自动化关键词生成以实现搜索引擎优化（SEO）和霸…...

编程日记 2025/5/15 5:10:10

windows文件下换行, linux上不换行解决CR换行符替换为LF notepad++

html文件是用回车换行的，在windows电脑上，显示正常。文件上传到linux服务器后，文件不换行了。只有一行。而且相关js插件也没法正常运行。用notepad查看，显示尾部换行符，是CR，这就是原因。CR是不被识别的。…...

编程日记 2025/5/14 22:09:22

服务器数据恢复—硬盘掉线导致热备盘同步失败的RAID5阵列数据恢复案例

服务器存储数据恢复环境： 华为S5300存储中有12块FC硬盘，其中11块硬盘作为数据盘组建了一组RAID5阵列，剩下的1块硬盘作为热备盘使用。基于RAID的LUN分配给linux操作系统使用，存放的数据主要是Oracle数据库。服务器存储故障&#…...

编程日记 2025/5/15 3:23:25

活着就好20411205

5号亲爱的朋友们，大家早上好！🌞 今天是5号，星期四，2024年12月的第五天，同时也是第49周的第四天，农历甲辰[龙]年十一月初一日。在这晨曦初露的美好时刻，愿第一缕柔和的阳光悄悄探进你…...

编程日记 2025/5/12 17:38:12

JDK8 下载与安装

下载安装包官网下载官网找到适合的版本: 网盘下载网盘链接提取码: 6666 下载得到的安装包: 安装步骤双击安装包开始安装. 安装路径不要有中文或者特殊符号如空格等. 更改安装路径: 跳出一个页面, 安装公共 JRE: 安装完成: 安装目录: 安装的公共 JRE: JDK 里面的 JR…...

编程日记 2025/5/13 22:19:04

基于MATLAB的信号处理工具：信号分析器

信号（或时间序列）是与特定时间相关的一系列数字或测量值，不同的行业和学科将这一与时间相关的数字序列称为信号或时间序列。生物医学或电气工程师会将其称为信号，而统计学家或金融定量分析师会使用时间序列这一术语。例如&#xf…...

编程日记 2025/5/15 21:41:38

Docker Compose 和 Kubernetes 之间的区别？

一、简介🎀 1.1 Docker Compose Docker Compose 是 Docker 官方的开源项目，负责实现对 Docker 容器集群的快速编排，可以管理多个 Docker 容器组成一个应用。你只需定义一个 YAML 格式的配置文件 docker-compose.yml ，即可创建并…...

编程日记 2025/5/10 20:46:46

uniapp远程摄像头流界面上显示

用到的插件：dplayer、hls dplayer官网：dplayer 远程摄像头视频流格式：m3u8 可以用来测试的视频流（有的用不了，多试几个，找可以用的）：m3u8测试视频安装hls，任选其一 npm…...

编程日记 2025/5/9 9:11:11

写译 Essay | Translation

单词参考上篇总结写译热点单词 | 50篇文章整理 | 手敲自用-CSDN博客文化类词汇： 包括传统节日及相关活动，如春节(Spring Festival)、中秋节(Mid-Autumn Festival)等。涵盖中国特色艺术和工艺品，如京剧(Peking opera)、中国画(traditi…...

编程日记 2025/5/5 22:51:56

知乎大数据开发面试题及参考答案

Java 两个线程之间是怎么通信的，属于哪种机制？在 Java 中，线程间通信主要有以下几种方式：共享变量：线程可以通过访问共享变量来进行通信。例如，一个线程修改一个共享的成员变量，另一个线程读取这个变量的值。但是这种方式需要注意线程安全问题。如果多个线程同时访问和…...

编程日记 2025/5/14 14:06:33

C# 绘制GDI红绿灯控件 using System; using System.Windows.Forms; using System.Drawing;public class TrafficLightControl : Control {protected override void OnPaint(PaintEventArgs e){base.OnPaint(e);Graphics g e.Graphics;g.SmoothingMode System.Drawing.Drawin…...

编程日记 2025/5/11 18:06:45

网络安全-使用HTTP动词篡改的认证旁路

这个东西去年的安全扫描都没有，今天就扫出来了，非常奇怪的一个东西。好吧，找资料找原因。结果可能应为搜索名词的原因，这个问题在群友的帮助下解决了。在我理解中servlet只有post和get方法，然后结果怎么出来这么多奇…...

编程日记 2025/5/15 6:43:29

多种MyBatis写法（数据库操作）

MyBatis，这个从iBatis演变而来的Java持久层框架，凭借其强大的功能和性能，早已成为企业级应用的首选。本文展示几种MyBatis写法，保证数据库操作既高效又灵活。 1. 批量操作批量操作是提升数据库操作效率的重要手段。MyBatis提供…...

编程日记 2025/5/15 14:40:33

centos 手动安装libcurl4-openssl-dev库

下载源代码 curl downloadshttps://curl.se/download/ 选择需要下载的版本，我下载的是8.11.0 解压 tar -zxvf curl-8.11.0 查看安装命令查找INSTALL.md，一般在docs文件夹下 –prefix ：指定安装路径（默认安装在/usr/local&…...

编程日记 2025/5/12 22:54:33

C#中的模拟服务器与客户端建立连接

创建一个控制台项目，命名为Server，模拟服务器端。在同一个解决方案下，添加新项目，命名为Client，模拟客户端。在服务器端与客户端之间建立TCP连接，并在客户端发送消息，在服务器端输出。 Server项目具体要求： 1.在Server项目中，用本机端点建立TcpListener对象，进行监…...

编程日记 2025/5/10 13:42:19

论文阅读——Supervised Learning With Quantum-Inspired Tensor Networks

张量网络是高维张量的有效表示，在物理和数学应用中非常成功。我们展示了如何通过使用矩阵乘积状态（张量训练）来参数化用于对图像进行分类的模型，将优化此类网络的算法应用于监督学习任务。对于 MNIST 数据集，我们获得的…...

编程日记 2025/5/11 9:41:42

HTML5系列（11）-- Web 无障碍开发指南

前端技术探索系列：HTML5 Web 无障碍开发指南 ♿ 致读者：构建人人可用的网络 👋 前端开发者们， 今天我们将深入探讨 Web 无障碍开发，学习如何创建一个真正包容、人人可用的网站。让我们一起为更多用户提供更好的网络…...

编程日记 2025/5/9 14:59:57

信号和槽思维脑图+相关练习

将登录框中的取消按钮使用信号和槽的机制，关闭界面。将登录按钮使用信号和槽连接到自定义的槽函数中，在槽函数中判断ui界面上输入的账号是否为"admin"，密码是否为"123456",如果账号密码匹配成功，当前界面关…...

编程日记 2025/5/14 13:36:58

Scala编程基础：模式匹配、解构赋值与正则表达式

在Scala编程语言中，模式匹配、解构赋值和正则表达式是三个非常强大的特性，它们可以让我们以更简洁、更直观的方式处理数据。本文将通过三个示例，详细解释这些特性的使用方法和背后的原理。 1. 模式匹配与case class 模式匹配是Scala中处理数…...

编程日记 2025/5/11 17:42:03

【大数据技术基础】课程第1章大数据技术概述大数据基础编程、实验和案例教程（第2版）

第1章大数据技术概述 1.1 大数据时代这本书的标题是《大数据时代》，副标题为“生活、工作与思维的大变革”。这本书由维克托迈尔-舍恩伯格（Viktor Mayer-Schnberger）和肯尼斯库克耶（Kenneth Cukier）合著&#xff0c…...

编程日记 2025/5/14 5:54:26

【基础分析】——宏参数连接

示例1： #include<stdio.h>#define STR1(s) #s#define FUN1(a,b) (int)(a##e##b)int main(int argv, char* agrc[]) {printf(STR1(king...));printf("\n");printf("%d\n", FUN1(2, 3));return 0; } 结果： （注&…...

编程日记 2025/5/15 19:21:00

算法3--二分查找

二分查找原理经典例题[704. 二分查找](https://leetcode.cn/problems/binary-search/)[34. 在排序数组中查找元素的第一个和最后一个位置](https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/)[35. 搜索插入位置](https://leetcode.cn/p…...

编程日记 2025/5/12 17:40:11

【信息系统项目管理师】第7章：项目立项管理考点梳理

文章目录 7.1 项目建议与立项申请7.2 项目可行性研究7.2.1 可行性研究的内容7.2.2 初步可行性研究7.2.3 详细可行性研究（重点） 7.3 项目评估与决策【学习建议】本章大概考选择题2分左右，有可能考案例题。论文早年考过。本章知识点比较集中&a…...

编程日记 2025/5/14 11:55:44

帝可得-策略管理

策略管理需求说明策略管理主要涉及到二个功能模块，业务流程如下： 新增策略: 允许管理员定义新的策略，包括策略的具体内容和参数（如折扣率）策略分配: 将策略分配给一个或多个售货机。 #mermaid-svg-PSQOJMLJqVGn3W…...

编程日记 2025/5/10 17:01:25

opencv-android编译遇到的相关问题处理

1、opencv-android sdk下载下载地址：https://opencv.org/releases/ 下载安卓SDK即可 2、解压下载好的SDK 3、导入opencv的SDK到安卓项目中导入步骤在/OpenCV-android-sdk/sdk/build.gradle文件的注释中写的非常详细，大家可安装官方给出的步骤导入。…...

编程日记 2025/5/15 6:41:25

汽车IVI中控开发入门及进阶（三十六）：QML调用蓝牙sdk的架构

Qt/QML本身在做GUI界面工程时，除了各种界面上的按钮、图片、工具条等元素之外，最方便的就是可以通过C++实现界面各种复杂逻辑，而实现上不可避免就需要一些外部库的支持，不管是静态库.a还是动态库.so，比如蓝牙模块。而QML/C++启动一个蓝牙协议栈SDK作为一个进程，然后启动…...

编程日记 2025/5/11 10:57:33

C++设计模式之外观模式

动机下图中左边方案的问题在于组件的客户和组件中各种复杂的子系统有了过多的耦合，随着外部客户程序和各子系统的演化，这种过多的耦合面临很多变化的挑战。如何简化外部客户程序和系统间的交互接口？如何将外部客户程序的演化和内部子系统…...

编程日记 2025/5/10 23:35:13

前缀和篇——繁星斗斗数字交织中，觅得效率明月辉光（1）

前言在这片无边无际的数字海洋中，如何从中提取出有价值的讯息，成为了计算机科学中的一项重要课题。前缀和算法，作为一种巧妙的技术，恰如其名——通过计算序列中各个元素的前缀和，能够为我们提供一种高效的查询方式&a…...

编程日记 2025/5/12 23:54:26

【论文复现】隐式神经网络实现低光照图像增强

📝个人主页🌹：Eternity._ 🌹🌹期待您的关注 🌹🌹 ❀ 隐式神经网络实现低光照图像增强引言那么目前低光照图像增强还面临哪些挑战呢？ 挑战1. 不可预测的亮度降低和噪声挑战2.度量友好…...

编程日记 2025/5/9 20:07:29

Secured Finance 推出 TVL 激励计划以及基于 FIL 的稳定币

Secured Finance 是新一代 DeFi 2.0 协议，其正在推出基于 FIL 的稳定币、固定收益市场以及具有吸引力的 TVL 激励计划，以助力 Filecoin 构建更强大的去中心化金融生态体系，并为 2025 年初 Secured Finance 协议代币的推出铺平道路。Secure Fi…...

编程日记 2025/5/8 8:37:47

2024前端框架年度总结报告（二）：新生qwik+solid和次新生svelte+Astro对比 -各自盯着前端的哪些个痛点 - 前端的区域发展差异

引言 2024年，前端开发依然是技术领域的热点之一。随着 Web 应用的日益复杂，前端框架的更新换代也加速了。尽管 React、Vue 和 Angular 老牌框架年度总结等“老牌”框架仍然占据着主流市场，但一些新兴的框架在不断挑战这些“巨头”的地位&am…...

编程日记 2025/5/11 13:21:01

MySQL大小写敏感、MySQL设置字段大小写敏感

文章目录一、MySQL大小写敏感规则二、设置数据库及表名大小写敏感 2.1、查询库名及表名是否大小写敏感2.2、修改库名及表名大小写敏感三、MySQL列名大小写不敏感四、lower_case_table_name与校对规则 4.1、验证校对规则影响大小写敏感4.1、验证校对规则影响排序五、设置字段…...

编程日记 2025/5/14 17:20:19

每日速记10道java面试题13-MySQL篇

其他资料每日速记10道java面试题01-CSDN博客每日速记10道java面试题02-CSDN博客每日速记10道java面试题03-CSDN博客每日速记10道java面试题04-CSDN博客每日速记10道java面试题05-CSDN博客每日速记10道java面试题06-CSDN博客每日速记10道java面试题07-CSDN博客每…...

编程日记 2025/5/12 22:38:03

关于Chrome自动同步书签的解决办法

前言并不一定适用所有用户， 目前我在网上搜集了一些资料，也做了一些尝试。就我个人总结的经验来讲，分享大家以下几种办法： 1.书签同步插件点击如下🔗： Chrome书签同步https://bm.famend.cn/ …...

编程日记 2025/5/14 9:14:54

江南大学《2024年807自动控制原理真题》 (完整版）

本文内容，全部选自自动化考研联盟的：《江南大学807自控考研资料》的真题篇。后续会持续更新更多学校，更多年份的真题，记得关注哦~ 目录 2024年真题 Part1：2024年完整版真题 2024年真题...

编程日记 2025/5/3 16:54:17

在VSCode中搭建Python开发环境

在VSCode中搭建Python开发环境 1、安装首先确保电脑已经安装好Python和VSCode。 2、安装VSCode的Python插件 3、选择python解释器 ctrlshiftP打开VSCode的命令行，输入python: select Interpreter选择合适的python版本。 4、运行代码在windows下你可以直接使用…...

编程日记 2025/5/16 2:18:26

mac 安装python3和配置环境变量

mac 安装python3和配置环境变量前言怎样选择python3的版本python3的安装1、去官网下载安装包2、下载完成后直接解压,检查安装是否成功前言在学习python的第一步就是安装它和配置他的环境变量，那么选择哪个版本的python你可曾知道，下面就讲解怎样选择…...

编程日记 2025/5/14 6:23:57

微信小程序版小米商城的搭建流程详解！

很多初学微信小程序语法的同学，可能不知道如何布局和搭建一个项目，下面我将讲解初学者如何搭建项目和注意事项。一、 app.json的配置 {"pages": ["pages/index/index","pages/classification/classification","pag…...

编程日记 2025/5/15 17:28:32

题目描述

示例 1

示例 2

解题思路

方法 1：递归法（构建反射法）

方法 2：数学公式法

代码实现

方法 1：递归法

方法 2：数学公式法

代码详解

1. 递归法实现

2. 数学公式法实现

时间与空间复杂度

时间复杂度

空间复杂度

测试用例

示例 1：

示例 2：

相关文章：