89. 格雷编码 (Medium)
2024-09-08 18:18:06
问题描述
n 位格雷码序列 是一个由 2ⁿ
个整数组成的序列,其中:
- 每个整数都在范围
[0, 2ⁿ - 1]
内(含0
和2ⁿ - 1
) - 第一个整数是
0
- 一个整数在序列中出现 不超过一次
- 每对 相邻 整数的二进制表示 恰好一位不同 ,且
- 第一个 和 最后一个 整数的二进制表示 恰好一位不同
给你一个整数 n
,返回任一有效的 n 位格雷码序列 。
示例 1:
输入:n = 2
输出:[0,1,3,2]
解释:
[0,1,3,2] 的二进制表示是 [00,01,11,10] 。
- 00 和 01 有一位不同
- 01 和 11 有一位不同
- 11 和 10 有一位不同
- 10 和 00 有一位不同
[0,2,3,1] 也是一个有效的格雷码序列,其二进制表示是 [00,10,11,01] 。
- 00 和 10 有一位不同
- 10 和 11 有一位不同
- 11 和 01 有一位不同
- 01 和 00 有一位不同
示例 2:
输入:n = 1
输出:[0,1]
提示:
1 <= n <= 16
解题思路
格雷编码的公式为f[i] = i ^ (i / 2)
;
代码
class Solution {
public:
vector<int> grayCode(int n) {
int num = 1 << n;
vector<int> res(num, 0);
for (int i = 0; i < num; i++) {
res[i] = i ^ (i / 2);
}
return res;
}
};
最新文章
- SpringBoot IntelliJ创建简单的Restful接口
- Sublime Text 2配置文件详解
- 测试加载jquery
- 学习flex布局(弹性布局)
- [闲的蛋疼系列]从零开始用TypeScript写React的UI组件(0)-先写一个Button??
- 无刷新更新listview
- WiFi攻击中“核武器”
- 细说java系列之HashMap原理
- 纯javascript实现可拖住/大小的div
- mysql兼容emoji表情存取
- WBXML 1.3协议摘要
- Flask的使用
- 微擎框架下拉分页(使用js模板引擎)
- mybatis学习一 环境搭建
- DirectX - dds图片格式(DDSURFACEDESC2)
- UI设计 - 手机列表风格总结
- Beta阶段DAY2
- 中文chrome font-size 10px,11px,12px,rem只为12px解决办法
- Dos操作基础
- echart在jsp中使用另外的方法
热门文章
- Python 20个常用库
- ES之分析器(Analyzer)及拼音分词器
- AR设备使用Vuforia的优化
- Mybatis-plus中sql语句各查询条件含义
- pip安装psycopg2报错Could not find a version that satisfies the requirement psycopg2
- Linux网络第六章:PXE高效批量网络装机及kickstart无人值守安装
- Unity3D中实现按资源名称自动化命名打包AssetBundle
- 如果同时存在application.properties 和application.yml 文件的话,springboot会优先使用application.properties吗
- 文件监控利器-Jnotify
- Linux 第四节(shell脚本,IF,do,for)