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

力扣第89题 格雷编码

题目描述

格雷编码序列是一个二进制数字序列,其中的每两个相邻的数字只有一个二进制位不同。给定一个整数 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. 递归法
  2. 数学公式法

方法 1:递归法(构建反射法)

递归的核心思想是:

  1. 通过已有的 n n n 位的格雷编码序列,构建 n + 1 n+1 n+1 位的格雷编码序列。
  2. 假设已有 n n 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:数学公式法

格雷编码的数学公式为:
G ( k ) = k ⊕ ( k > > 1 ) G(k) = k \oplus (k >> 1) G(k)=k(k>>1)
其中, k k k 是当前的数字, k > > 1 k >> 1 k>>1 k k k 右移一位, k ⊕ ( k > > 1 ) k \oplus (k >> 1) k(k>>1) k k k 与右移后的 k 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 n n 位。
  • 每次扩展时,通过反射法创建新的序列:
    • 将已有的序列复制到前半部分。
    • 将每个数值在前面加上 1,并将该部分的顺序反转,加入到后半部分。

2. 数学公式法实现

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

时间与空间复杂度

时间复杂度

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

空间复杂度

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

测试用例

示例 1:

输入

n = 2

输出

[0, 1, 3, 2]

示例 2:

输入

n = 3

输出

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

相关文章:

力扣第89题 格雷编码

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

Linux C/C++编程中的多线程编程基本概念

【图书推荐】《Linux C与C一线开发实践&#xff08;第2版&#xff09;》_linux c与c一线开发实践pdf-CSDN博客《Linux C与C一线开发实践&#xff08;第2版&#xff09;&#xff08;Linux技术丛书&#xff09;》(朱文伟&#xff0c;李建英)【摘要 书评 试读】- 京东图书 (jd.com…...

解决Tomcat运行时错误:“Address localhost:1099 is already in use”

目录 背景: 过程&#xff1a; 报错的原因&#xff1a; 解决的方法&#xff1a; 总结&#xff1a; 直接结束Java.exe进程&#xff1a; 使用neststat -aon | findstr 1099 命令&#xff1a; 选择建议&#xff1a; 背景: 准备运行Tomcat服务器调试项目时&#xff0c;程序下…...

C/C++中的调用约定

在C/C编程中&#xff0c;调用约定(calling conventions)是一组指定如何调用函数的规则。主要在你调用代码之外的函数(例如OS API&#xff0c;操作系统应用程序接口)或OS调用你(如WinMain的情况)时起作用。如果编译器不知道正确的调用约定&#xff0c;那么你很可能会遇到非常奇怪…...

微信创建小程序码 - 数量不受限制

获取小程序码&#xff1a;小程序码为圆图&#xff0c;且不受数量限制。 目录 文档 接口地址 请求方式 功能描述 注意事项 获取 scene 值 请求参数 返回参数 对接 请求方法 获取小程序码 调用获取小程序码 总结 文档 接口地址 https://api.weixin.qq.com/wxa/get…...

springboot/ssm美食分享系统Java代码web项目美食烹饪笔记分享交流

springboot/ssm美食分享系统ava美食烹饪笔记分享交流系统web美食源码 基于springboot(可改ssm)vue项目 开发语言&#xff1a;Java 框架&#xff1a;springboot/可改ssm vue JDK版本&#xff1a;JDK1.8&#xff08;或11&#xff09; 服务器&#xff1a;tomcat 数据库&#…...

【Redis篇】 List 列表

在 Redis 中&#xff0c;List 是一种非常常见的数据类型&#xff0c;用于表示一个有序的字符串集合。与传统的链表结构类似&#xff0c;Redis 的 List 支持在两端进行高效的插入和删除操作&#xff0c;因此非常适合实现队列&#xff08;Queue&#xff09;和栈&#xff08;Stack…...

多级IIR滤波效果(BIQUAD),system verilog验证

MATLAB生成IIR系数 采用率1k&#xff0c;截止频率30hz&#xff0c;Matlab生成6阶对应的biquad3级系数 Verilog测试代码 // fs1khz,fc30hz initial beginreal Sig_Orig, Noise_white, Mix_sig;real fs 1000;Int T 1; //周期int N T*fs; //1s的采样点数// 数组声明…...

【WPF中ControlTemplate 与 DataTemplate之间的区别?】

前言 WPF中ControlTemplate 与 DataTemplate之间的区别&#xff1f; 1. 定义&#xff1a; ControlTemplate 是用于定义 WPF 控件的外观和结构的模板。它允许您重新定义控件的视觉表现&#xff0c;而不改变控件的行为。 DataTemplate 是用于定义如何呈现数据对象的模板。它通…...

Keil5配色方案修改为类似VSCode配色

1. 为什么修改Keil5配色方案 视觉习惯&#xff1a;如果你已经习惯了VSCode的配色方案&#xff0c;尤其是在使用ESP-IDF开发ESP32时&#xff0c;Keil5的默认配色可能会让你感到不习惯。减少视觉疲劳&#xff1a;Keil5的默认背景可能过于明亮&#xff0c;长时间使用可能会导致视…...

ndp协议简介

在IPv6中&#xff0c;ARP&#xff08;地址解析协议&#xff09;被替代为邻居发现协议&#xff08;Neighbor Discovery Protocol&#xff0c;NDP&#xff09;。NDP是IPv6网络中用于发现邻居节点&#xff08;相邻设备&#xff09;的协议&#xff0c;类似于IPv4中的ARP。但与ARP不…...

stable diffusion实践操作-大模型介绍:SD的发展历史,SD1.5和SDXL之间的差别

大家有没有这样的困惑&#xff1a;在找模型时&#xff0c;老是会出现一些奇怪的标签&#xff0c;像 sd1.5、sdxl 之类的模型后缀&#xff0c;真让人摸不着头脑&#xff0c;一会儿 1.0&#xff0c;一会儿 1.5&#xff0c;一会儿 XL&#xff0c;完全搞不清楚状况。今天就来给大家…...

系统无法运行提示:sqlsut.dll初始化错误怎么解决?多种解决方法汇总一览

遇到 sqlsut.dll 初始化错误&#xff0c;这通常意味着 SQL Server 的某些组件未能正确加载或初始化。以下是一些可能的解决方法汇总&#xff0c;旨在帮助您排查和解决问题&#xff1a; 解决方法 1. 检查SQL Server服务状态•确认所有相关的SQL Server服务&#xff08;如SQL Se…...

通过waitress启动flask应用

假设你有一个名为 app.py 的文件&#xff0c;app 是指你的 Flask 应用实例。并且在这个文件中创建了一个 Flask 应用实例&#xff0c;那么你可以这样导入和使用它。 示例结构 假设你的项目结构如下&#xff1a; my_flask_app/ │ ├── app.py ├── waitress_server.py └─…...

Redis高阶之容错切换

当一台主机master宕掉之后&#xff0c;他的从机会取代主机么&#xff1f; 查看集群状态 127.0.0.1:6385> cluster nodes c8ff33e8da5fd8ef821c65974dda304d2e3327f9 192.168.58.129:638216382 slave f6b1fd5e58df90782f602b484c2011d52fc3482d 0 1733220836918 1 connecte…...

蓝桥杯准备训练(lesson2 ,c++)

3.1 字符型 char //character的缩写在键盘上可以敲出各种字符&#xff0c;如&#xff1a; a &#xff0c; q &#xff0c; &#xff0c; # 等&#xff0c;这些符号都被称为字符&#xff0c;字符是⽤单引号括 起来的&#xff0c;如&#xff1a; ‘a’ &#xff0c; ‘b’ &…...

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

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

利用红黑树封装map,和set,实现主要功能

如果不知道红黑树是什么的时候可以去看看这个红黑树 思路 首先我们可以把封装分为两个层面理解&#xff0c;上层代码就是set,和map&#xff0c;底层就是红黑树 就相当于根据红黑树上面套了两个map,set的壳子&#xff0c;像下面这张图一样 对于map和set&#xff0c;map里面存…...

网络(TCP)

目录 TCP socket API 详解 套接字有哪些类型&#xff1f;socket有哪些类型&#xff1f; 图解TCP四次握手断开连接 图解TCP数据报结构以及三次握手&#xff08;非常详细&#xff09; socket缓冲区以及阻塞模式详解 再谈UDP和TCP bind(): 我们的程序中对myaddr参数是这样…...

CSS 选择器的优先级

一、基本概念 CSS 选择器的优先级决定了在样式冲突时&#xff0c;哪个样式规则将被应用到 HTML 元素上。通过理解 CSS 选择器的优先级&#xff0c;可以更好地控制网页元素的样式&#xff0c;避免样式冲突。 二、优先级计算规则 1. 内联样式 内联样式具有最高的优先级。 &l…...

Cesium1.95中高性能加载1500个点

一、基本方式&#xff1a; 图标使用.png比.svg性能要好 <template><div id"cesiumContainer"></div><div class"toolbar"><button id"resetButton">重新生成点</button><span id"countDisplay&qu…...

全志A40i android7.1 调试信息打印串口由uart0改为uart3

一&#xff0c;概述 1. 目的 将调试信息打印串口由uart0改为uart3。 2. 版本信息 Uboot版本&#xff1a;2014.07&#xff1b; Kernel版本&#xff1a;Linux-3.10&#xff1b; 二&#xff0c;Uboot 1. sys_config.fex改动 使能uart3(TX:PH00 RX:PH01)&#xff0c;并让boo…...

【MATLAB代码】基于最大相关熵准则(MCC)的三维鲁棒卡尔曼滤波算法(MCC-KF),附源代码|订阅专栏后可直接查看

文章所述的代码实现了基于最大相关熵准则(MCC)的三维鲁棒卡尔曼滤波算法(MCC-KF),针对传感器观测数据中存在的脉冲型异常噪声问题,通过非线性加权机制提升滤波器的抗干扰能力。代码通过对比传统KF与MCC-KF在含异常值场景下的表现,验证了后者在状态估计鲁棒性方面的显著优…...

【Elasticsearch】Elasticsearch 在大数据生态圈的地位 实践经验

Elasticsearch 在大数据生态圈的地位 & 实践经验 1.Elasticsearch 的优势1.1 Elasticsearch 解决的核心问题1.1.1 传统方案的短板1.1.2 Elasticsearch 的解决方案 1.2 与大数据组件的对比优势1.3 关键优势技术支撑1.4 Elasticsearch 的竞品1.4.1 全文搜索领域1.4.2 日志分析…...

Python竞赛环境搭建全攻略

Python环境搭建竞赛技术文章大纲 竞赛背景与意义 竞赛的目的与价值Python在竞赛中的应用场景环境搭建对竞赛效率的影响 竞赛环境需求分析 常见竞赛类型&#xff08;算法、数据分析、机器学习等&#xff09;不同竞赛对Python版本及库的要求硬件与操作系统的兼容性问题 Pyth…...

五子棋测试用例

一.项目背景 1.1 项目简介 传统棋类文化的推广 五子棋是一种古老的棋类游戏&#xff0c;有着深厚的文化底蕴。通过将五子棋制作成网页游戏&#xff0c;可以让更多的人了解和接触到这一传统棋类文化。无论是国内还是国外的玩家&#xff0c;都可以通过网页五子棋感受到东方棋类…...

阿里云Ubuntu 22.04 64位搭建Flask流程(亲测)

cd /home 进入home盘 安装虚拟环境&#xff1a; 1、安装virtualenv pip install virtualenv 2.创建新的虚拟环境&#xff1a; virtualenv myenv 3、激活虚拟环境&#xff08;激活环境可以在当前环境下安装包&#xff09; source myenv/bin/activate 此时&#xff0c;终端…...

人工智能 - 在Dify、Coze、n8n、FastGPT和RAGFlow之间做出技术选型

在Dify、Coze、n8n、FastGPT和RAGFlow之间做出技术选型。这些平台各有侧重&#xff0c;适用场景差异显著。下面我将从核心功能定位、典型应用场景、真实体验痛点、选型决策关键点进行拆解&#xff0c;并提供具体场景下的推荐方案。 一、核心功能定位速览 平台核心定位技术栈亮…...

CSS3相关知识点

CSS3相关知识点 CSS3私有前缀私有前缀私有前缀存在的意义常见浏览器的私有前缀 CSS3基本语法CSS3 新增长度单位CSS3 新增颜色设置方式CSS3 新增选择器CSS3 新增盒模型相关属性box-sizing 怪异盒模型resize调整盒子大小box-shadow 盒子阴影opacity 不透明度 CSS3 新增背景属性ba…...

【大模型】RankRAG:基于大模型的上下文排序与检索增强生成的统一框架

文章目录 A 论文出处B 背景B.1 背景介绍B.2 问题提出B.3 创新点 C 模型结构C.1 指令微调阶段C.2 排名与生成的总和指令微调阶段C.3 RankRAG推理&#xff1a;检索-重排-生成 D 实验设计E 个人总结 A 论文出处 论文题目&#xff1a;RankRAG&#xff1a;Unifying Context Ranking…...