w****x
发帖数: 2483 | 1 做了无数recursion的题后花了两小时才整出gray code解, 大家鄙视我吧, 哈哈哈:
/*
The gray code is a binary numeral system where two successive values differ
in only one bit.
Given a non-negative integer n representing the total number of bits in the
code, print the sequence of gray code. A gray code sequence must begin with
0.
For example, given n = 2, return [0,1,3,2]. Its gray code sequence is:
00 - 0
01 - 1
11 - 3
10 - 2
*/
void _inner_sol(int& nCur, vector& vec, int nStopPos, int nPos)
{
if (nPos < 0)
{
vec.push_back(nCur);
return;
}
_inner_sol(nCur, vec, nStopPos, nPos-1);
if (nPos >= nStopPos)
return;
//flip nPos at nCur
nCur ^= (1 << nPos);
_inner_sol(nCur, vec, nStopPos, nPos-1);
}
vector grayCode(int n) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
vector vec;
if (0 == n)
vec.push_back(0);
else
{
int nCur = 0;
_inner_sol(nCur, vec, n, 31);
}
return vec;
} |
p*****2
发帖数: 21240 | |
p*****2
发帖数: 21240 | 3 这个真要鄙视你了。
我大概做了10分钟。
public ArrayList grayCode(int n)
{
ArrayList al = new ArrayList();
al.add(0);
for (int i = 1; i <= n; i++)
{
int a = 1 << (i - 1);
for (int j = al.size() - 1; j >= 0; j--)
{
al.add(al.get(j) | a);
}
}
return al;
} |
t**********h
发帖数: 2273 | |
p*****2
发帖数: 21240 | 5
你不是在梦游吧？
【在 t**********h 的大作中提到】
: 膜拜楼上的两位牛人，gray code是什么？
|
w****x
发帖数: 2483 | 6 啊, 一直没有弄出gray code的本质, 二爷简洁的代码真是一语惊醒梦中人.
现在对二爷的敬仰犹如滔滔江水连绵不绝,犹如黄河泛滥一发不可收拾 |
p*****2
发帖数: 21240 | 7
靠。别来了。其实这个规律zhangchi大神已经总结过了。你还记得吗？
【在 w****x 的大作中提到】
: 啊, 一直没有弄出gray code的本质, 二爷简洁的代码真是一语惊醒梦中人.
: 现在对二爷的敬仰犹如滔滔江水连绵不绝,犹如黄河泛滥一发不可收拾
|
w****x
发帖数: 2483 | 8 期末以后把板上漏下来的题再归纳一下写一遍, 完全不在状态啊~~ |
p*****2
发帖数: 21240 | 9
我看你已经总结到300题了。很牛呀。我最近才开始总结。也就是100题这样子。我觉得
至少得总结到200题才行。
【在 w****x 的大作中提到】
: 期末以后把板上漏下来的题再归纳一下写一遍, 完全不在状态啊~~
|
w****x
发帖数: 2483 | 10
我啥时候总结道300了, 你哪看的??
【在 p*****2 的大作中提到】
:
: 我看你已经总结到300题了。很牛呀。我最近才开始总结。也就是100题这样子。我觉得
: 至少得总结到200题才行。
|
|
|
p*****2
发帖数: 21240 | 11
一亩三分地吧。
【在 w****x 的大作中提到】
:
: 我啥时候总结道300了, 你哪看的??
|
w****x
发帖数: 2483 | 12
刚才又仔细看了一下, 这个规律太牛擦了, 由于太牛擦了, 所以就不研究了....
还是研究一下为什么递归做这么烂吧...
【在 p*****2 的大作中提到】
: 这个真要鄙视你了。
: 我大概做了10分钟。
: public ArrayList grayCode(int n)
: {
: ArrayList al = new ArrayList();
: al.add(0);
: for (int i = 1; i <= n; i++)
: {
: int a = 1 << (i - 1);
: for (int j = al.size() - 1; j >= 0; j--)
|
w****x
发帖数: 2483 | 13
那个丢的都是废题, careercup网站和csdn上没意义的题, 根本没用,
那个好像是10个月前丢的
【在 p*****2 的大作中提到】
:
: 一亩三分地吧。
|
r*****e
发帖数: 792 | 14 如果只是为了生成Gray code, 最简单的方法是：
grayCode = binary ^ (binary>>1); |
p*****2
发帖数: 21240 | 15
废题你还做了300道？你太牛X了。
【在 w****x 的大作中提到】
:
: 那个丢的都是废题, careercup网站和csdn上没意义的题, 根本没用,
: 那个好像是10个月前丢的
|
t**********h
发帖数: 2273 | 16 求一亩三分地的地址
一亩三分地吧。
★ Sent from iPhone App: iReader Mitbbs Lite 7.56
【在 p*****2 的大作中提到】
:
: 废题你还做了300道？你太牛X了。
|
C***U
发帖数: 2406 | 17 你们两太像我本科的几个同学了。。。
differ
the
with
【在 w****x 的大作中提到】
: 做了无数recursion的题后花了两小时才整出gray code解, 大家鄙视我吧, 哈哈哈:
: /*
: The gray code is a binary numeral system where two successive values differ
: in only one bit.
: Given a non-negative integer n representing the total number of bits in the
: code, print the sequence of gray code. A gray code sequence must begin with
: 0.
: For example, given n = 2, return [0,1,3,2]. Its gray code sequence is:
: 00 - 0
: 01 - 1
|
f****0
发帖数: 151 | 18
膜拜。。。。
【在 r*****e 的大作中提到】
: 如果只是为了生成Gray code, 最简单的方法是：
: grayCode = binary ^ (binary>>1);
|
C***U
发帖数: 2406 | 19 Wiki上的结论不错
http://en.wikipedia.org/wiki/Gray_code
做了无数recursion的题后花了两小时才整出gray code解, 大家鄙视我吧, 哈哈哈:/*
The gray code is a binary numeral syst........
★ Sent from iPhone App: iReader Mitbbs 7.56 - iPad Lite
【在 w****x 的大作中提到】
: 做了无数recursion的题后花了两小时才整出gray code解, 大家鄙视我吧, 哈哈哈:
: /*
: The gray code is a binary numeral system where two successive values differ
: in only one bit.
: Given a non-negative integer n representing the total number of bits in the
: code, print the sequence of gray code. A gray code sequence must begin with
: 0.
: For example, given n = 2, return [0,1,3,2]. Its gray code sequence is:
: 00 - 0
: 01 - 1
|
J*********r
发帖数: 5921 | 20 这个不对吧
【在 r*****e 的大作中提到】
: 如果只是为了生成Gray code, 最简单的方法是：
: grayCode = binary ^ (binary>>1);
|
|
|
r*****e
发帖数: 792 | 21 for what input binary number does not it work?
【在 J*********r 的大作中提到】
: 这个不对吧
|
x******9
发帖数: 473 | 22 提到的大神是买买提上的么？求总结。
【在 p*****2 的大作中提到】
:
: 废题你还做了300道？你太牛X了。
|
p*****2
发帖数: 21240 | 23
是呀。你去考考古。最近刚拿到F和G的双offer。
【在 x******9 的大作中提到】
: 提到的大神是买买提上的么？求总结。
|
l*****a
发帖数: 559 | 24 写了个递归版本的。
vector code(int n){
if(n == 0){
vector codes;
codes.push_back(0);
return codes;
}
vector oneless = code(n - 1);
int len = oneless.size();
for(int i = len - 1; i >= 0; i--){
oneless.push_back(oneless[i]);
}
for(int i = 0; i < len; i++){
int ele = oneless[i+len];
ele |= 1 << (n - 1);
oneless[i+len] = ele;
}
return oneless;
} |
I***C
发帖数: 765 | 25 This is the shortest code I have ever seen for gray code.
-------------------------
vector grayCode(int n) {
vector result;
int size = 1<
for (int i = 0; i < size; ++i)
result.push_back((i >> 1) ^ i);
return result;
}
-------------------------
But have not idea why this works.
Anyone can help answer why this works?
Thanks!
【在 f****0 的大作中提到】
:
: 膜拜。。。。
|
f*********y
发帖数: 376 | 26
【在 I***C 的大作中提到】
: This is the shortest code I have ever seen for gray code.
: -------------------------
: vector grayCode(int n) {
: vector result;
:
: int size = 1<:
: for (int i = 0; i < size; ++i)
: result.push_back((i >> 1) ^ i);
:
|
C***U
发帖数: 2406 | 27 所以做太多也会把脑子做乱了
有时候更应该冷静一下整理一下code
有点想高考啊！哈哈
differ
the
with
【在 w****x 的大作中提到】
: 做了无数recursion的题后花了两小时才整出gray code解, 大家鄙视我吧, 哈哈哈:
: /*
: The gray code is a binary numeral system where two successive values differ
: in only one bit.
: Given a non-negative integer n representing the total number of bits in the
: code, print the sequence of gray code. A gray code sequence must begin with
: 0.
: For example, given n = 2, return [0,1,3,2]. Its gray code sequence is:
: 00 - 0
: 01 - 1
|
e******o
发帖数: 757 | 28 it is easy to see that size = 1 << n.
but
can anyone explain why the ith number is ( i>>1 )^i ?
【在 I***C 的大作中提到】
: This is the shortest code I have ever seen for gray code.
: -------------------------
: vector grayCode(int n) {
: vector result;
:
: int size = 1<:
: for (int i = 0; i < size; ++i)
: result.push_back((i >> 1) ^ i);
:
|
l*****a
发帖数: 14598 | 29 1)why use Integer and int simultaneously?
2)most of the JAVA developers won't write like this
ArrayList al = new ArrayList();
【在 p*****2 的大作中提到】
: 这个真要鄙视你了。
: 我大概做了10分钟。
: public ArrayList grayCode(int n)
: {
: ArrayList al = new ArrayList();
: al.add(0);
: for (int i = 1; i <= n; i++)
: {
: int a = 1 << (i - 1);
: for (int j = al.size() - 1; j >= 0; j--)
|
g**e
发帖数: 6127 | 30 那怎么写
List al = new ArrayList();
这样？
【在 l*****a 的大作中提到】
: 1)why use Integer and int simultaneously?
: 2)most of the JAVA developers won't write like this
: ArrayList al = new ArrayList();
|
|
|
g**e
发帖数: 6127 | 31 我觉得这个题当电面不错，收藏之
【在 l*****a 的大作中提到】
: 1)why use Integer and int simultaneously?
: 2)most of the JAVA developers won't write like this
: ArrayList al = new ArrayList();
|
e***s
发帖数: 799 | |
b*****e
发帖数: 474 | 33 Ha, this is more like a math problem ...
Look at the table below:
bit_5 bit_4 bit_3 bit_2 bit_1
0 0 0 0 0
0 0 0 0 1
0 0 0 1
0 0 0 1
0 0 1
0 0 1
0 0 1
0 0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
For the missing entries, if you just repeat the bit pattern for lower bit
columns, then row N has the binary representation of N. However, if you
repeat the bit pattern in reverse (i.e. flipped), then switch back, and so
on ... then you get the Gray code for N.
Since you switch every 2^k rows, you just need to check the previous column
to see if the bits are to be reversed.
Thus, if ( N's bit k+1) == 0, bit k of Gray code = bit k of N;
else (i.e. N's k+1'th bit is 1), bit k of Gray code = flip (bit k of N)
That translates to (N>>1) ^ N. |
r*****e
发帖数: 792 | 34 it is correct because the equation is derived from digital logic which is
Gray code's origin.
Use K-Map on the truth table when the variables are not too many, otherwise
not easy to use
K-map even though it still works.
FYI, grayToBinary(unsigned int num)
unsigned int numBits = 8*sizeof(num); //here 8 means each byte has 8 bits
unsigned int shift;
for (shift=1; shift
num ^= num>>shift;
return num;
【在 I***C 的大作中提到】
: This is the shortest code I have ever seen for gray code.
: -------------------------
: vector grayCode(int n) {
: vector result;
:
: int size = 1<:
: for (int i = 0; i < size; ++i)
: result.push_back((i >> 1) ^ i);
:
|
f*******4
发帖数: 64 | 35 f(i)=(i>>1)^i, 只要比较一下f(i)和f(i-1)的关系就能看出来了
另外生成只相差一位不同的序列也不唯一,
比如已有长度为i-1的序列,在向长度i扩展时只需在i-1序列的后考虑添加1,接着再走一
遍i-1序列,是对称的.归纳法
【在 e******o 的大作中提到】
: it is easy to see that size = 1 << n.
: but
: can anyone explain why the ith number is ( i>>1 )^i ?
|
S******1
发帖数: 269 | 36 public class Solution {
public ArrayList grayCode(int n) {
ArrayList result =new ArrayList();
if(n<=0)
return result;
result.add(0);
result.add(1);
for(int i=2; i<=n; i++){
for(int j=result.size()-1;j>=0;j--){
result.add(result.get(j)+(1<<(i-1)));
}
}
return result;
}
} |
A******g
发帖数: 612 | 37 很弱的问一下，这个点解？
第一个数000
000^(000>>1) = 000^000 = 000?
【在 r*****e 的大作中提到】
: 如果只是为了生成Gray code, 最简单的方法是：
: grayCode = binary ^ (binary>>1);
|
h****n
发帖数: 2094 | 38 强烈的对称性。。。
differ
the
with
【在 w****x 的大作中提到】
: 做了无数recursion的题后花了两小时才整出gray code解, 大家鄙视我吧, 哈哈哈:
: /*
: The gray code is a binary numeral system where two successive values differ
: in only one bit.
: Given a non-negative integer n representing the total number of bits in the
: code, print the sequence of gray code. A gray code sequence must begin with
: 0.
: For example, given n = 2, return [0,1,3,2]. Its gray code sequence is:
: 00 - 0
: 01 - 1
|
A******g
发帖数: 612 | 39 看了两小时没看懂，二爷能讲讲这是啥子算法吗？
循环套循环里面array size 还变 ...
【在 p*****2 的大作中提到】
: 这个真要鄙视你了。
: 我大概做了10分钟。
: public ArrayList grayCode(int n)
: {
: ArrayList al = new ArrayList();
: al.add(0);
: for (int i = 1; i <= n; i++)
: {
: int a = 1 << (i - 1);
: for (int j = al.size() - 1; j >= 0; j--)
|
A******g
发帖数: 612 | 40 Trace 一下二爷的code
i=1, [000] | [001]
i=2, [000， 001] | [010]
i=3, [000, 001, 011, 010] | [100]
[000, 001, 011, 010, 110, 111, 101, 100]
我所知道的gray code,
1. 变最右一位
2. 变最右边开始第一个1的左边
repeat 1,2 直到没得变...
实在无法和这么精妙的算法联系起来啊, 求解释...
不然实在记不住啊 |
|
|
a********x
发帖数: 1502 | 41 研究了一下，确实code写得很简洁明了，下面wiki得解释也很帮助理解。
http://en.wikipedia.org/wiki/Gray_code#Constructing_an_n-bit_Gr
【在 p*****2 的大作中提到】
: 这个真要鄙视你了。
: 我大概做了10分钟。
: public ArrayList grayCode(int n)
: {
: ArrayList al = new ArrayList();
: al.add(0);
: for (int i = 1; i <= n; i++)
: {
: int a = 1 << (i - 1);
: for (int j = al.size() - 1; j >= 0; j--)
|
