n****r
发帖数: 279 | 1 45分钟，只把第一题做完，第二题没时间问了。太惨了。
题目其实很简单，写一个方程生成gray code并按顺序输出相应的数字。
比如grayCode(3) = {0,1,3,2,6,7,5,4}
我先是尝试用iteration，越写越乱，干脆打倒重来用recursion。
刚写完graycode数组生成，还没写转化成int的function，时间到了。
悲惨...
三哥口音不错，人挺nice，给了不少提示，可惜，dream job就这么没了。 |
d********t
发帖数: 9628 | 2 what's gray code?
【在 n****r 的大作中提到】
: 45分钟，只把第一题做完，第二题没时间问了。太惨了。
: 题目其实很简单，写一个方程生成gray code并按顺序输出相应的数字。
: 比如grayCode(3) = {0,1,3,2,6,7,5,4}
: 我先是尝试用iteration，越写越乱，干脆打倒重来用recursion。
: 刚写完graycode数组生成，还没写转化成int的function，时间到了。
: 悲惨...
: 三哥口音不错，人挺nice，给了不少提示，可惜，dream job就这么没了。
|
b******t
发帖数: 965 | 3 格雷码 连续的数一次flip一个bit
【在 d********t 的大作中提到】
: what's gray code?
|
a*****a
发帖数: 495 | 4 pat pat
【在 n****r 的大作中提到】
: 45分钟，只把第一题做完，第二题没时间问了。太惨了。
: 题目其实很简单，写一个方程生成gray code并按顺序输出相应的数字。
: 比如grayCode(3) = {0,1,3,2,6,7,5,4}
: 我先是尝试用iteration，越写越乱，干脆打倒重来用recursion。
: 刚写完graycode数组生成，还没写转化成int的function，时间到了。
: 悲惨...
: 三哥口音不错，人挺nice，给了不少提示，可惜，dream job就这么没了。
|
l*****a
发帖数: 14598 | 5 不简单吧？
【在 n****r 的大作中提到】
: 45分钟，只把第一题做完，第二题没时间问了。太惨了。
: 题目其实很简单，写一个方程生成gray code并按顺序输出相应的数字。
: 比如grayCode(3) = {0,1,3,2,6,7,5,4}
: 我先是尝试用iteration，越写越乱，干脆打倒重来用recursion。
: 刚写完graycode数组生成，还没写转化成int的function，时间到了。
: 悲惨...
: 三哥口音不错，人挺nice，给了不少提示，可惜，dream job就这么没了。
|
n****r
发帖数: 279 | 6 对于版上牛人来说很简单。我差点没做出来，觉得很难。
【在 l*****a 的大作中提到】
: 不简单吧？
|
v***a
发帖数: 365 | 7 多谢面经，很新颖的题目
GC(0) = []
GC(N) = '0' + GC(N - 1), '1' + reverse( GC(N - 1) ) |
p*****2
发帖数: 21240 | 8 没看太明白。谁能详细解释一下。
grayCode(3) = {0,1,3,2,6,7,5,4} |
n****r
发帖数: 279 | 9 000 = 0
001 = 1
011 = 3
010 = 2
110 = 6
111 = 7
101 = 5
100 = 4
就是先算出来gray code的二维数组，然后一行一行转换成十进制整形
【在 p*****2 的大作中提到】
: 没看太明白。谁能详细解释一下。
: grayCode(3) = {0,1,3,2,6,7,5,4}
|
S*******0
发帖数: 198 | 10 public static void getGrayCode(int bitNum){
for(int i = 0; i< (int)Math.pow(2, bitNum); i++){
int grayCode = (i >> 1) ^ i;
System.out.println(num2Binary(grayCode, bitNum));
}
}
public static String num2Binary(int num, int bitNum){
String ret = "";
for(int i=bitNum-1; i >=0; i--){
ret += (num >> i) & 1;
}
return ret;
} |
|
|
D***h
发帖数: 183 | 11 时间复杂度好像只能n^2?
【在 n****r 的大作中提到】
: 对于版上牛人来说很简单。我差点没做出来，觉得很难。
|
p*****2
发帖数: 21240 | 12
谢谢。感觉不算太简单。正在想。
【在 n****r 的大作中提到】
: 000 = 0
: 001 = 1
: 011 = 3
: 010 = 2
: 110 = 6
: 111 = 7
: 101 = 5
: 100 = 4
: 就是先算出来gray code的二维数组，然后一行一行转换成十进制整形
|
c*******2
发帖数: 173 | 13 赞，敢问一下思路怎么来的？很难看到这个规律吧
【在 S*******0 的大作中提到】
: public static void getGrayCode(int bitNum){
: for(int i = 0; i< (int)Math.pow(2, bitNum); i++){
: int grayCode = (i >> 1) ^ i;
: System.out.println(num2Binary(grayCode, bitNum));
: }
: }
: public static String num2Binary(int num, int bitNum){
: String ret = "";
: for(int i=bitNum-1; i >=0; i--){
: ret += (num >> i) & 1;
|
p*****2
发帖数: 21240 | 14 练了练。
static int Convert(string s)
{
int output=0;
for (int i = 0; i < s.Length; i++)
{
output *= 2;
if (s[i] == '1')
output += 1;
}
return output;
}
static string[] GrayCode(int n)
{
if (n <= 0)
throw new ArgumentNullException();
string[] output = new string[(int)Math.Pow(2, n)];
if (n == 1)
{
output[0] = "0";
output[1] = "1";
return output;
}
string[] last = GrayCode(n - 1);
for (int i = 0; i < last.Length; i++)
{
output[i] = "0" + last[i];
output[output.Length - 1 - i] = "1" + last[i];
}
return output;
}
static void GetGrayCode(int n)
{
if (n <= 0)
throw new ArgumentNullException();
string[] output = GrayCode(n);
for (int i = 0; i < output.Length; i++)
Console.WriteLine(Convert(output[i]));
} |
b******e
发帖数: 52 | 15 void gray(int N)
{
for (int i = 0; i < (1<
cout << i^(i>>1) << endl;
} |
p*****2
发帖数: 21240 | 16
赞 again.
【在 c*******2 的大作中提到】
: 赞，敢问一下思路怎么来的？很难看到这个规律吧
|
m*******p
发帖数: 141 | 17 thanks for sharing.
so sad. I even don't know what gray code is.
:-(
【在 n****r 的大作中提到】
: 45分钟，只把第一题做完，第二题没时间问了。太惨了。
: 题目其实很简单，写一个方程生成gray code并按顺序输出相应的数字。
: 比如grayCode(3) = {0,1,3,2,6,7,5,4}
: 我先是尝试用iteration，越写越乱，干脆打倒重来用recursion。
: 刚写完graycode数组生成，还没写转化成int的function，时间到了。
: 悲惨...
: 三哥口音不错，人挺nice，给了不少提示，可惜，dream job就这么没了。
|
f*******t
发帖数: 7549 | |
B*******1
发帖数: 2454 | 19 同感，太可恶了，出这样子的题。
【在 f*******t 的大作中提到】
: 三哥绝对是在坑你
|
m*******p
发帖数: 141 | 20 so talented.
【在 b******e 的大作中提到】
: void gray(int N)
: {
: for (int i = 0; i < (1<: cout << i^(i>>1) << endl;
: }
|
|
|
A**u
发帖数: 2458 | 21 我有笨办法
#include
#include
#include
#include
using namespace std;
vector P( int n );
vector R( int n );
vector P( int n )
{ vector code;
if ( n == 1 )
{
code.push_back(string("0"));
code.push_back(string("1"));
}
else
{
vector p_prev = P(n-1);
for(vector::iterator it = p_prev.
begin(); it != p_prev.end(); ++it)
{
code.push_back("0" + *it);
}
vector r_prev = R(n-1);
for(vector::iterator it = r_prev.
begin(); it != r_prev.end(); ++it)
code.push_back("1" + *it);
}
return code;
}
vector R( int n )
{ vector code;
if ( n == 1 )
{
code.push_back(string("1"));
code.push_back(string("0"));
}
else
{
vector p_prev = P(n-1);
for(vector::iterator it = p_prev.
begin(); it != p_prev.end(); ++it)
{
code.push_back("1" + *it);
}
vector r_prev = R(n-1);
for(vector::iterator it = r_prev.
begin(); it != r_prev.end(); ++it)
code.push_back("0" + *it);
}
return code;
}
【在 m*******p 的大作中提到】
: so talented.
|
a********m
发帖数: 15480 | 22 这个题目还好吧？
【在 f*******t 的大作中提到】
: 三哥绝对是在坑你
|
e********e
发帖数: 12 | 23 我这儿有另外一种，利用对称性：
numBit = 2 时，
00
01
－ 对称轴
11
10
vector grayCode(int numBit)
{
if (numBit == 0) return vector();
vector res;
res.push_back(string("0"));
res.push_back(string("1"));
for (int i=1; i < numBit; i++) {
int k = res.size();
while (--k >=0) {
string bits = res[k];
res[k].insert(0,1,'0');
res.push_back(bits.insert(0,1,'1'));
}
}
for (int i=0; i < res.size(); i++) {
cout << res[i] << endl;
}
return res;
}
【在 A**u 的大作中提到】
: 我有笨办法
: #include
: #include
: #include
: #include
: using namespace std;
: vector P( int n );
: vector R( int n );
: vector P( int n )
: { vector code;
|
H***e
发帖数: 476 | 24 妙
只是是怎么想起来的呢
【在 S*******0 的大作中提到】
: public static void getGrayCode(int bitNum){
: for(int i = 0; i< (int)Math.pow(2, bitNum); i++){
: int grayCode = (i >> 1) ^ i;
: System.out.println(num2Binary(grayCode, bitNum));
: }
: }
: public static String num2Binary(int num, int bitNum){
: String ret = "";
: for(int i=bitNum-1; i >=0; i--){
: ret += (num >> i) & 1;
|
s******n
发帖数: 3946 | 25 咋想出来的?
【在 b******e 的大作中提到】
: void gray(int N)
: {
: for (int i = 0; i < (1<: cout << i^(i>>1) << endl;
: }
|
B*******1
发帖数: 2454 | 26 这就是wiki上面写的方法吧。
【在 s******n 的大作中提到】
: 咋想出来的?
|
Y**B
发帖数: 144 | 27 这个二进制数的顺序是怎么确定的？
【在 n****r 的大作中提到】
: 000 = 0
: 001 = 1
: 011 = 3
: 010 = 2
: 110 = 6
: 111 = 7
: 101 = 5
: 100 = 4
: 就是先算出来gray code的二维数组，然后一行一行转换成十进制整形
|
Y**B
发帖数: 144 | 28 请问LZ面世的是跟硬件相关的职位么？ 还是软件？
【在 n****r 的大作中提到】
: 45分钟，只把第一题做完，第二题没时间问了。太惨了。
: 题目其实很简单，写一个方程生成gray code并按顺序输出相应的数字。
: 比如grayCode(3) = {0,1,3,2,6,7,5,4}
: 我先是尝试用iteration，越写越乱，干脆打倒重来用recursion。
: 刚写完graycode数组生成，还没写转化成int的function，时间到了。
: 悲惨...
: 三哥口音不错，人挺nice，给了不少提示，可惜，dream job就这么没了。
|
H***e
发帖数: 476 | 29 从中间对称
【在 Y**B 的大作中提到】
: 这个二进制数的顺序是怎么确定的？
|
k***t
发帖数: 276 | 30 两点想法：
1。本质上是边沿触发记录相邻信号变化，不变为零，变化为一。
2。按顺序输出GrayCode序列时，每次原数自增一时，进位到的最高位
的GaryCode bit flip，其它位不变，因为原数低于进位最高位的位全变了
（由全一变成全零），而原数高于进位最高位的位全不变。所以记录相邻位信
号变化的GrayCode，与自增前的原数的GaryCode相比，只有在最高进位位flip，
其它位不变。如果原数自增时没有进位，则退化成GaryCode末位flip的情况。
按这个思路，可以有一个NextGrayCode()函数返回下一个GrayCode。计算出应该flip的bit，然后flip保存的上一个GaryCode的相应bit即可。flip bit
的计算应该可以用类似计算全组合的回溯或递归的方法取得。
【在 n****r 的大作中提到】
: 45分钟，只把第一题做完，第二题没时间问了。太惨了。
: 题目其实很简单，写一个方程生成gray code并按顺序输出相应的数字。
: 比如grayCode(3) = {0,1,3,2,6,7,5,4}
: 我先是尝试用iteration，越写越乱，干脆打倒重来用recursion。
: 刚写完graycode数组生成，还没写转化成int的function，时间到了。
: 悲惨...
: 三哥口音不错，人挺nice，给了不少提示，可惜，dream job就这么没了。
|
|
|
c****p
发帖数: 6474 | 31 method 1: use a generic equation.
method 2: recursive way
GC(0) = 0, GC(1) = 1;
GC(2^k + n) = 2^k + GC(2^k-n-1), where 0<=n<=2^k-1
in other words, to get GC for 2^k to 2^(k+1)-1, flip the GC sequence of 0~2^
k-1, and set the kth bit(LSB is 0th bit).
000
001
--- k = 1, flip and set 1st bit
011
010
--- k = 2, flip and set 2nd bit
110
111
101
100
--- .....
【在 n****r 的大作中提到】
: 45分钟，只把第一题做完，第二题没时间问了。太惨了。
: 题目其实很简单，写一个方程生成gray code并按顺序输出相应的数字。
: 比如grayCode(3) = {0,1,3,2,6,7,5,4}
: 我先是尝试用iteration，越写越乱，干脆打倒重来用recursion。
: 刚写完graycode数组生成，还没写转化成int的function，时间到了。
: 悲惨...
: 三哥口音不错，人挺nice，给了不少提示，可惜，dream job就这么没了。
|
s**********e
发帖数: 326 | 32 recursion 代码：
public static void grayCode(int numOfBits) {
assert (numOfBits > 0);
int[] arr = new int[numOfBits];
for (int i : arr) i = 0;
doGrayCode(arr, 0);
}
public static void doGrayCode(int[] arr, int layer) {
int len = arr.length - 1;
if (layer == len) {
print(arr);
arr[layer] = 1 - arr[layer];
print(arr);
} else {
doGrayCode(arr, layer + 1);
arr[layer] = 1 - arr[layer];
doGrayCode(arr, layer + 1);
}
} |
b*****7
发帖数: 631 | 33 Your solution is so cool.
Here's what I came up with:
void gray(int bits)
{
int v = 0;
for(int i=1; i<= (1<
{
cout<
int t=0;
while((i & (1<
t++;
v = v^(1<
}
cout<
}
【在 b******e 的大作中提到】
: void gray(int N)
: {
: for (int i = 0; i < (1<: cout << i^(i>>1) << endl;
: }
|
t********0
发帖数: 118 | |
