gray-code

题目描述

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

给定一个代表编码总位数的非负整数 n，打印其格雷编码序列。格雷编码序列必须以 0 开头。

题解

设 n 阶格雷码集合为 G(n)，则 G(n+1) 阶格雷码为：
给 G(n) 阶格雷码每个元素二进制形式前面添加 0，得到 G’(n)；
设 G(n) 集合倒序（镜像）为 R(n)，给 R(n) 每个元素二进制形式前面添加 1，得到 R’(n)；
G(n+1) = G’(n) ∪ R’(n)拼接两个集合即可得到下一阶格雷码。
链接：https://leetcode-cn.com/problems/gray-code/solution/gray-code-jing-xiang-fan-she-fa-by-jyd/

vector<int> grayCode(int n) {
	if (!n)return { 0 };

	vector<string> v1;
	v1.push_back("");
	while (n--)
	{
		for (int i = v1.size() -1; i >=0;i--)
		{
			v1.push_back("1"+v1[i]);
			v1[i] = "0" + v1[i];
		}
	}
	vector<int> res;
	for (int i = 0; i < v1.size(); i++)
		res.push_back(stoi(v1[i], nullptr, 2));
	return res;
}