程序员人生 网站导航

Gray Code [leetcode]

栏目:互联网时间:2014-10-04 08:00:01

第一种方法是直接排列

以二进制为0值的格雷码为第零项,第一项改变最右边的位元,第二项改变右起第一个为1的位元的左边位元,第三、四项方法同第一、二项,如此反复,即可排列出n个位元的格雷码。

vector<int> grayCode(int n) { vector<int> res; res.push_back(0); if (n == 0) return res; res.push_back(1); int total = 1 << n; for (int i = 2;i < total; i+=2) { int j = 1; while((res.back() & j) == 0) j <<= 1; j <<= 1; res.push_back(res.back() ^ j); res.push_back(res.back() ^ 1); } return res; }

第二种方法是镜射排列

vector<int> grayCode(int n) { vector<int> res; if (n == 0) { res.push_back(0); return res; } res.push_back(0); res.push_back(1); for (int i = 2; i <= n; i++) { int s = 1 << (i-1); for (int j = res.size() - 1; j >= 0; j--) { res.push_back(res[j] + s); } } return res; }


------分隔线----------------------------
------分隔线----------------------------

最新技术推荐