a****x
发帖数: 89 | 1 看到一NB的解法for Gray Code:
vector grayCode(int n)
{
vector ret;
int size = 1 << n;
for(int i = 0; i < size; ++i)
ret.push_back((i >> 1)^i);
return ret;
}
太神了，这怎么能想出来呢？还是我太弱了:( |
c********t
发帖数: 5706 | 2 太牛了，收藏！
刚拿到这题我也试图用过bit operation,完全没idea, 放弃了。这是(i>>1)^i怎么想出
的呢?
【在 a****x 的大作中提到】
: 看到一NB的解法for Gray Code:
: vector grayCode(int n)
: {
: vector ret;
: int size = 1 << n;
: for(int i = 0; i < size; ++i)
: ret.push_back((i >> 1)^i);
: return ret;
: }
: 太神了，这怎么能想出来呢？还是我太弱了:(
|
c********t
发帖数: 5706 | 3 仔细看了一下，原来在wiki里有代码。
【在 c********t 的大作中提到】
: 太牛了，收藏！
: 刚拿到这题我也试图用过bit operation,完全没idea, 放弃了。这是(i>>1)^i怎么想出
: 的呢?
|
g*********e
发帖数: 14401 | |
p*****2
发帖数: 21240 | 5 面试感觉这样写给人的印象就是背题了。因为你没有办法表达你的思路。而且这个不背
好像也记不住，我其实也写过一次，不过很快也就忘记了。 |
c****p
发帖数: 6474 | 6 我要做这题的思路就是用最高位翻转、其他位反序的办法。。。
这个实在理解不了。。。
【在 p*****2 的大作中提到】
: 面试感觉这样写给人的印象就是背题了。因为你没有办法表达你的思路。而且这个不背
: 好像也记不住，我其实也写过一次，不过很快也就忘记了。
|
Q*******e
发帖数: 939 | 7 版上多少面试题是出自wiki或者算法书啊
出这样的题目意义不大
没有分析过程, 只有答案和对答案的解释 |
p*****2
发帖数: 21240 | 8 我也是 这个思路很正常
【在 c****p 的大作中提到】
: 我要做这题的思路就是用最高位翻转、其他位反序的办法。。。
: 这个实在理解不了。。。
|
a****x
发帖数: 89 | 9 二爷可贴个答案不？
我也是 这个思路很正常
【在 p*****2 的大作中提到】
: 我也是 这个思路很正常
|
v*****k
发帖数: 7798 | |
h**6
发帖数: 4160 | 11 f(x) = x ⊕ (x/2)
好像数字电路课上学过的吧 |
f*****7
发帖数: 92 | 12 class Solution {
public:
vector grayCode(int n) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
vector gray;
gray.push_back(0);
for(int i = 1; i <= n; i++)
{
int pre = gray.size() - 1;
while (pre >= 0)
{
//great idea!
//prefix + mirror
gray.push_back((1 << (i - 1)) + gray[pre]);
pre--;
}
}
return gray;
}
};
这是我ac的代码
用mirror（把之前所有的格雷码镜面倒转过来）和prefix（把前一半补0，mirror过来
的最高位补1）
就可以了
这是格雷码的规律
不需要记住位操作的解法 |
a****x
发帖数: 89 | 13 多谢了，这很简洁的解法，而且面试时好解释。
【在 f*****7 的大作中提到】
: class Solution {
: public:
: vector grayCode(int n) {
: // Start typing your C/C++ solution below
: // DO NOT write int main() function
: vector gray;
: gray.push_back(0);
:
: for(int i = 1; i <= n; i++)
: {
|
l*******b
发帖数: 2586 | 14 嗯，看到题目第一个想法就是这个
vector grayCode(int n) {
vector r;
r.push_back(0);
for(int i = 0; i < n; ++i)
for(int j = r.size() - 1; j >= 0; --j)
r.push_back(r[j] | 1 << i);
return r;
}
【在 f*****7 的大作中提到】
: class Solution {
: public:
: vector grayCode(int n) {
: // Start typing your C/C++ solution below
: // DO NOT write int main() function
: vector gray;
: gray.push_back(0);
:
: for(int i = 1; i <= n; i++)
: {
|
