w******e
发帖数: 81 | 1 suppose用二进制来表达一个整数,10=‘1010'.现在除了0和1，也允许用2，例如 4=‘
100’=‘20’。任给一个数，找出所有类似表达式。例如 10=‘1010’=‘1002’=‘
210’=‘122’。不知道还有没有别的可能性。。。太难了，死活没想出来。。。 |
y**i
发帖数: 1112 | 2 就是说所有的"10"都可以用"2"来表示？那就是相当于找"10"的组合，是么？
那题目能不能等价于，一个给定字符串（题目中的二进制数），找其中一个子字符串（
"10"）的组合？
【在 w******e 的大作中提到】
: suppose用二进制来表达一个整数,10=‘1010'.现在除了0和1，也允许用2，例如 4=‘
: 100’=‘20’。任给一个数，找出所有类似表达式。例如 10=‘1010’=‘1002’=‘
: 210’=‘122’。不知道还有没有别的可能性。。。太难了，死活没想出来。。。
|
l******c
发帖数: 2555 | 3 Number is N
brute force method:
2** n <= N
get the n
then
select 2, 2**2, 2**3, 2**4.....2**n,
when 2**k is selected, 2**(k-1) till 2 can be selected also, but 2**(k + 1)
is not allowed
N = 10;
select 2:
1002
select 2**2
122 (2 is also selected)
select 2**3
210, 202, (2 is also selected)
then program....
【在 w******e 的大作中提到】
: suppose用二进制来表达一个整数,10=‘1010'.现在除了0和1，也允许用2，例如 4=‘
: 100’=‘20’。任给一个数，找出所有类似表达式。例如 10=‘1010’=‘1002’=‘
: 210’=‘122’。不知道还有没有别的可能性。。。太难了，死活没想出来。。。
|
m*****g
发帖数: 226 | |
l******c
发帖数: 2555 | 5 In programming,
bit/digit operation seems easy:
number is
b1b2b3b4b5..bi...bn
bi = 0, 1, 2
if(b(i+1) == 0)
{
if(bi == 1)
{
bi= 0;
b(i+1) = 2
}
else if(bi == 2)
{
bi = 1;
b(i + 1) = 2
}
}
)
【在 l******c 的大作中提到】
: Number is N
: brute force method:
: 2** n <= N
: get the n
: then
: select 2, 2**2, 2**3, 2**4.....2**n,
: when 2**k is selected, 2**(k-1) till 2 can be selected also, but 2**(k + 1)
: is not allowed
: N = 10;
: select 2:
|
w******e
发帖数: 81 | 6 what if the number's binary expression are all '1's, without 0? for example,
7='111', how will this algorithm work? Sorry cannot type chinese now
)
【在 l******c 的大作中提到】
: Number is N
: brute force method:
: 2** n <= N
: get the n
: then
: select 2, 2**2, 2**3, 2**4.....2**n,
: when 2**k is selected, 2**(k-1) till 2 can be selected also, but 2**(k + 1)
: is not allowed
: N = 10;
: select 2:
|
l******c
发帖数: 2555 | 7 7 has no 2's expression, that means all selections fail.
bit scan from right is more easy, see above post
check the 0 first,
if (0)
{
if(left bit is 1)
{
02
}
if(left bit is 2)
{
12
}
else do nothing
}
else do nothing
example,
【在 w******e 的大作中提到】
: what if the number's binary expression are all '1's, without 0? for example,
: 7='111', how will this algorithm work? Sorry cannot type chinese now
:
: )
|
w******e
发帖数: 81 | 8 Super zan! Yes, I thought the key point is the '0' in the bin expression,
and this is probably the solution the interviewer was looking for. I only
proposed an idea using the brute force and the interviewer was not satisfied
with it.....
【在 l******c 的大作中提到】
: In programming,
: bit/digit operation seems easy:
: number is
: b1b2b3b4b5..bi...bn
: bi = 0, 1, 2
: if(b(i+1) == 0)
: {
: if(bi == 1)
: {
: bi= 0;
|
c******f
发帖数: 2144 | |
b******v
发帖数: 1493 | 10 第一遍，先找出该数的二进制表示，这时只含0,1
第二遍，每个10都可以等价于02
第三遍，每个20都可以等价于12
经过这三遍，应该所有可能都有了
例如x=10
第一遍，1010
第二遍，1002, 210, 202
第三遍， 122
【在 w******e 的大作中提到】
: suppose用二进制来表达一个整数,10=‘1010'.现在除了0和1，也允许用2，例如 4=‘
: 100’=‘20’。任给一个数，找出所有类似表达式。例如 10=‘1010’=‘1002’=‘
: 210’=‘122’。不知道还有没有别的可能性。。。太难了，死活没想出来。。。
|
|
|
l******c
发帖数: 2555 | 11 apparently not right
how about 100000000000000000000000000000000000 (binary)
this is not a simple question.
it is a recursive plus question
I tried a runable code, it took me several hours to finish it, so I will not
apply for google now.
【在 b******v 的大作中提到】
: 第一遍，先找出该数的二进制表示，这时只含0,1
: 第二遍，每个10都可以等价于02
: 第三遍，每个20都可以等价于12
: 经过这三遍，应该所有可能都有了
: 例如x=10
: 第一遍，1010
: 第二遍，1002, 210, 202
: 第三遍， 122
|
B*****t
发帖数: 335 | 12 找出最大的2^k<=n的k， 然后backtrack， 复杂度O(2^k), 也许可以剪枝
4=‘
【在 w******e 的大作中提到】
: suppose用二进制来表达一个整数,10=‘1010'.现在除了0和1，也允许用2，例如 4=‘
: 100’=‘20’。任给一个数，找出所有类似表达式。例如 10=‘1010’=‘1002’=‘
: 210’=‘122’。不知道还有没有别的可能性。。。太难了，死活没想出来。。。
|
b******v
发帖数: 1493 | 13 每遍当然对新出现的数也要处理
not
【在 l******c 的大作中提到】
: apparently not right
: how about 100000000000000000000000000000000000 (binary)
: this is not a simple question.
: it is a recursive plus question
: I tried a runable code, it took me several hours to finish it, so I will not
: apply for google now.
|
b******v
发帖数: 1493 | 14 而且这程序有啥难编的
每遍加个循环判断一下是否还有10和20就可以了
not
【在 l******c 的大作中提到】
: apparently not right
: how about 100000000000000000000000000000000000 (binary)
: this is not a simple question.
: it is a recursive plus question
: I tried a runable code, it took me several hours to finish it, so I will not
: apply for google now.
|
B*****t
发帖数: 335 | 15 程序不难，但是有两个缺点，1）需要判断重复出现的数。2）你这个方法象BFS，内存会
很快不够用。
【在 b******v 的大作中提到】
: 而且这程序有啥难编的
: 每遍加个循环判断一下是否还有10和20就可以了
:
: not
|
l******c
发帖数: 2555 | 16 post your runable code please
【在 b******v 的大作中提到】
: 而且这程序有啥难编的
: 每遍加个循环判断一下是否还有10和20就可以了
:
: not
|
w******1
发帖数: 520 | 17 这个题目是不是被想复杂了啊
直接找有多少对 10 ， 不就可以了么？
如果1010， 用0 1 2 表示， 应该是 22，102 210， 而不是202， 1002， 这种表示方
法， 是篡改了本来的表示方法了。 在2的前面，多加了0 . |
B*****t
发帖数: 335 | 18 如果像你这样解释的话，会简单一些，不过方法都差不多，DFS。
表示方
【在 w******1 的大作中提到】
: 这个题目是不是被想复杂了啊
: 直接找有多少对 10 ， 不就可以了么？
: 如果1010， 用0 1 2 表示， 应该是 22，102 210， 而不是202， 1002， 这种表示方
: 法， 是篡改了本来的表示方法了。 在2的前面，多加了0 .
|
b******v
发帖数: 1493 | 19 #include
#include
#include
#include
using namespace std;
string findbin(unsigned int x)
{
string result;
char tmp[2];
tmp[1]='\0';
if(x==0)
return string("0");
while(x!=0) {
int r = x%2;
tmp[0] = r+48;
result = string(tmp) + result;
x = (x-r)/2;
}
return result;
}
int find012(string& s, set& result)
{
【在 l******c 的大作中提到】
: post your runable code please
|
B*****t
发帖数: 335 | 20 呵呵， 你试试这个数8327168
【在 b******v 的大作中提到】
: #include
: #include
: #include
: #include
: using namespace std;
: string findbin(unsigned int x)
: {
: string result;
: char tmp[2];
: tmp[1]='\0';
|
|
|
r****o
发帖数: 1950 | 21 请问1002和122是怎么出来的呢？没看明白。
【在 w******e 的大作中提到】
: suppose用二进制来表达一个整数,10=‘1010'.现在除了0和1，也允许用2，例如 4=‘
: 100’=‘20’。任给一个数，找出所有类似表达式。例如 10=‘1010’=‘1002’=‘
: 210’=‘122’。不知道还有没有别的可能性。。。太难了，死活没想出来。。。
|
b******v
发帖数: 1493 | 22 改进了一下，不用queue，全用set，减少了重复运算
#include
#include
#include
using namespace std;
string findbin(unsigned int x)
{
string result;
char tmp[2];
tmp[1]='\0';
if(x==0)
return string("0");
while(x!=0) {
int r = x%2;
tmp[0] = r+48;
result = string(tmp) + result;
x = (x-r)/2;
}
return result;
}
int find012(string& s, set& re |
b******v
发帖数: 1493 | 23 这个数除了大一点，有什么特殊？
我运行了，除了时间长一点，并没有出现内存不够用的情况。
待会把结果贴上来
【在 B*****t 的大作中提到】
: 呵呵， 你试试这个数8327168
|
y**i
发帖数: 1112 | 24 看来原题中的意思是10可以写成02，20可以写成12，主要是第二种情况加入导致复杂了
很多
【在 r****o 的大作中提到】
: 请问1002和122是怎么出来的呢？没看明白。
|
b******v
发帖数: 1493 | 25 the binary representation of 8327168 is 11111110001000000000000
it has 370 different representations
2222221112111111111112
2222221112111111111120
2222221112111111111200
2222221112111111112000
2222221112111111120000
2222221112111111200000
2222221112111112000000
2222221112111120000000
2222221112111200000000
2222221112112000000000
2222221112120000000000
2222221112200000000000
2222221120111111111112
2222221120111111111120
2222221120111111111200
2222221120111111112000
2222221120111111120000
22222211
【在 b******v 的大作中提到】
: 这个数除了大一点，有什么特殊？
: 我运行了，除了时间长一点，并没有出现内存不够用的情况。
: 待会把结果贴上来
|
B*****t
发帖数: 335 | 26 我的意思是你的这个程序对稍微大一点儿的数就跑不动了，前面的帖子我已经说过了
这种题用BSF的方法有两个不足，1）需要判断重复出现的数，效率不好。2）随着数x的增
大，BFS树的深度也逐渐增加，树的节点成指数级增长，占用太多内存，进一步导致搜
索的
效率降低。
【在 b******v 的大作中提到】
: 这个数除了大一点，有什么特殊？
: 我运行了，除了时间长一点，并没有出现内存不够用的情况。
: 待会把结果贴上来
|
b******v
发帖数: 1493 | 27 那你有什么好方法？
的增
【在 B*****t 的大作中提到】
: 我的意思是你的这个程序对稍微大一点儿的数就跑不动了，前面的帖子我已经说过了
: 这种题用BSF的方法有两个不足，1）需要判断重复出现的数，效率不好。2）随着数x的增
: 大，BFS树的深度也逐渐增加，树的节点成指数级增长，占用太多内存，进一步导致搜
: 索的
: 效率降低。
|
r****o
发帖数: 1950 | 28 为啥20可以写成12，有什么道理么?
【在 y**i 的大作中提到】
: 看来原题中的意思是10可以写成02，20可以写成12，主要是第二种情况加入导致复杂了
: 很多
|
l******c
发帖数: 2555 | 29 for small number, correct; for big number, horrible
的增
【在 B*****t 的大作中提到】
: 我的意思是你的这个程序对稍微大一点儿的数就跑不动了，前面的帖子我已经说过了
: 这种题用BSF的方法有两个不足，1）需要判断重复出现的数，效率不好。2）随着数x的增
: 大，BFS树的深度也逐渐增加，树的节点成指数级增长，占用太多内存，进一步导致搜
: 索的
: 效率降低。
|
m*****n
发帖数: 5245 | 30
4 = 100 = 20 = 12
【在 r****o 的大作中提到】
: 为啥20可以写成12，有什么道理么?
|
|
|
b******v
发帖数: 1493 | 31 二进制10 = 2 = 二进制02
二进制20 = 4 = 二进制12
【在 r****o 的大作中提到】
: 为啥20可以写成12，有什么道理么?
|
b******v
发帖数: 1493 | 32 我的程序确实对大数跑得很慢，BlueAnt那个例子差不多要跑5分钟
不知道谁有好的办法对大数也很快？
I'll be very interested to learn
【在 l******c 的大作中提到】
: for small number, correct; for big number, horrible
:
: 的增
|
B*****t
发帖数: 335 | 33 我前面帖子说过了，就是DFS的思想。好处：1，不用判重。 2，内存使用只和递归深度有
关，所以内存使用非常少。递归的深度为k, k为使2^k<=n的最大整数。
这样分析的话2^1000的数都不是什么问题，至少堆栈和内存不会溢出。
BTW，我用刚才那个数8327168运行你的程序，现在结果还没有出来，不过我的电脑确实
很慢。
【在 b******v 的大作中提到】
: 那你有什么好方法？
:
: 的增
|
l******c
发帖数: 2555 | 34 RPRPRPRP
welcome to optimize
//012 string to represent binary value
#include
#include
set st;
void bin21(string str, int start)
{
int end = str.length() -1 ;
if(start >= end)
return;
while((str[start] == '0') && (start < end)) start++;
if((str[start +1] == '0') && (start < end))
{
//not change
bin21(str, start + 1);
//change
if(str[start] == '1')
{
str[start] = '0';
str[start + 1] =
【在 b******v 的大作中提到】
: 我的程序确实对大数跑得很慢，BlueAnt那个例子差不多要跑5分钟
: 不知道谁有好的办法对大数也很快？
: I'll be very interested to learn
|
b******v
发帖数: 1493 | 35 多谢
我的电脑是Q***[email protected]，后面那个全用set的版本差不多跑5分钟
度有
【在 B*****t 的大作中提到】
: 我前面帖子说过了，就是DFS的思想。好处：1，不用判重。 2，内存使用只和递归深度有
: 关，所以内存使用非常少。递归的深度为k, k为使2^k<=n的最大整数。
: 这样分析的话2^1000的数都不是什么问题，至少堆栈和内存不会溢出。
: BTW，我用刚才那个数8327168运行你的程序，现在结果还没有出来，不过我的电脑确实
: 很慢。
|
l******c
发帖数: 2555 | 36 my code is 3 seconds
【在 b******v 的大作中提到】
: 多谢
: 我的电脑是Q***[email protected]，后面那个全用set的版本差不多跑5分钟
:
: 度有
|
b******v
发帖数: 1493 | 37 看到了，果然很牛
【在 l******c 的大作中提到】
: my code is 3 seconds
|
B*****t
发帖数: 335 | 38 我觉得还可以优化，用set没什么必要
”2“的个数一定的话，不需要判断重复。
直接dfs就行了
【在 l******c 的大作中提到】
: RPRPRPRP
: welcome to optimize
: //012 string to represent binary value
: #include
: #include
: set st;
: void bin21(string str, int start)
: {
: int end = str.length() -1 ;
: if(start >= end)
|
l******c
发帖数: 2555 | 39 set is a lazy way to avoid repeat caculation, if no set, very slow.
I was trying to optimize with code, not set, but failed.
Basically, it is a recurisve tree, we need avoid caculating same node
Any optimization is welcome
【在 B*****t 的大作中提到】
: 我觉得还可以优化，用set没什么必要
: ”2“的个数一定的话，不需要判断重复。
: 直接dfs就行了
|
B*****t
发帖数: 335 | 40 你可能没有明白我的意思，这里根本就不需要判断repeat calculation
slow.
node
【在 l******c 的大作中提到】
: set is a lazy way to avoid repeat caculation, if no set, very slow.
: I was trying to optimize with code, not set, but failed.
: Basically, it is a recurisve tree, we need avoid caculating same node
: Any optimization is welcome
|
|
|
l******c
发帖数: 2555 | 41 please try your idea, post here or send to me.
【在 B*****t 的大作中提到】
: 你可能没有明白我的意思，这里根本就不需要判断repeat calculation
:
: slow.
: node
|
B*****t
发帖数: 335 | 42 写了个程序， x=8327168时， 我的老破机器0秒就可以出结果了
#include
#include
#include
#include
using namespace std;
int x = 8327168, k;
int d[1000];
char buf[100000];
inline bool check(int val, int ix) {
int i;
for(i=0; i<=ix; i++){
if(val%2==1&&d[i]==2) return false;
val >>=1;
}
return true;
}
void dfsFind21Str(int ix, int tot) {
if(tot>x) return;
if(ix==k) {
int i, reminder = 0;
i = 0;
reminder = x;
while(remind
【在 l******c 的大作中提到】
: please try your idea, post here or send to me.
|
a***9
发帖数: 364 | 43 呵呵，也写了一个，也是0秒
#include
#include
using namespace std;
int counter= 1;
int end = 0;
void bin21(string str, int start)
{
if(start >= end)
return;
if (start < 0) start = 0;
while((str[start] == '0') && (start < end)) start++;
while((str[start+1] != '0') && (start < end)) start++;
if((str[start +1] == '0') && (start < end))
{
if(str[start] == '1')
{
str[start] = '0';
str[start + 1] = '2';
++counter;
【在 B*****t 的大作中提到】
: 写了个程序， x=8327168时， 我的老破机器0秒就可以出结果了
: #include
: #include
: #include
: #include
: using namespace std;
: int x = 8327168, k;
: int d[1000];
: char buf[100000];
: inline bool check(int val, int ix) {
|
B*****t
发帖数: 335 | 44 while((str[start+1] != '0') && (start < end)) start++;
这里有可能越界，应该交换判断顺序一下顺序
【在 a***9 的大作中提到】
: 呵呵，也写了一个，也是0秒
: #include
: #include
: using namespace std;
: int counter= 1;
: int end = 0;
: void bin21(string str, int start)
: {
: if(start >= end)
: return;
|
a***9
发帖数: 364 | 45 我把楼上老兄的代码粘贴重组的，这里刚好也没事
最好换一下
【在 B*****t 的大作中提到】
: while((str[start+1] != '0') && (start < end)) start++;
: 这里有可能越界，应该交换判断顺序一下顺序
|
B*****t
发帖数: 335 | 46 ss = "11"的时候会越界。没有segmentation fault可能是stl string的数组预留
的空间比较大。
【在 a***9 的大作中提到】
: 我把楼上老兄的代码粘贴重组的，这里刚好也没事
: 最好换一下
|
b******v
发帖数: 1493 | 47 赞！老大人品水平都显然更胜一筹
【在 B*****t 的大作中提到】
: 写了个程序， x=8327168时， 我的老破机器0秒就可以出结果了
: #include
: #include
: #include
: #include
: using namespace std;
: int x = 8327168, k;
: int d[1000];
: char buf[100000];
: inline bool check(int val, int ix) {
|
H****r
发帖数: 2801 | 48 Could this number be negative?
【在 w******e 的大作中提到】
: suppose用二进制来表达一个整数,10=‘1010'.现在除了0和1，也允许用2，例如 4=‘
: 100’=‘20’。任给一个数，找出所有类似表达式。例如 10=‘1010’=‘1002’=‘
: 210’=‘122’。不知道还有没有别的可能性。。。太难了，死活没想出来。。。
|
y*c
发帖数: 904 | 49 你们是自己DFS，没用递归么？我这个递归的 num=8327168 也很快啊，我的输出需要
reverse string一下。先写递归表达
f(n) = f((n-1)/2) if n&1=1
f(n) = f((n-2)/2) + f(n/2) if n&1=0
后程序，
void FindAll210(int num, char res[], int index)
{
if(num==0){
res[index] = 0;
cout<
return;
}
if(num&1){
res[index] = '1';
FindAll210((num-1)>>1, res, index+1);
}else{
res[index] = '0';
FindAll210(num>>1, res, index+1);
res[index] = '2';
FindAll210((num-2)>>1, re |
p********7
发帖数: 549 | 50 优化了下你的算法，不用遍历2次，如果可以再搞个struct，来一个char 记录下上次位
置，速度更快
int find012(string& s, set& result)
{
string tmp1, tmp2;
queue qs;
qs.push(s);
while(!qs.empty()) {
tmp1 = qs.front();
// first scan for '10'
for(unsigned int i=0; i
if(tmp1[i]=='1' && tmp1[i+1]=='0') {
tmp2 = tmp1;
tmp2[i]='0';
【在 b******v 的大作中提到】
: 改进了一下，不用queue，全用set，减少了重复运算
: #include
: #include
: #include
: using namespace std;
: string findbin(unsigned int x)
: {
: string result;
: char tmp[2];
: tmp[1]='\0';
|
|
|
a***9
发帖数: 364 | 51 这个程序很神仙，nb!
【在 y*c 的大作中提到】
: 你们是自己DFS，没用递归么？我这个递归的 num=8327168 也很快啊，我的输出需要
: reverse string一下。先写递归表达
: f(n) = f((n-1)/2) if n&1=1
: f(n) = f((n-2)/2) + f(n/2) if n&1=0
: 后程序，
: void FindAll210(int num, char res[], int index)
: {
: if(num==0){
: res[index] = 0;
: cout<
|
a***9
发帖数: 364 | 52 估计是面试者想要的解答，从递推公式的角度想很简洁，
如果能想到，程序还是可能在规定时间内写出来的，很牛！
【在 y*c 的大作中提到】
: 你们是自己DFS，没用递归么？我这个递归的 num=8327168 也很快啊，我的输出需要
: reverse string一下。先写递归表达
: f(n) = f((n-1)/2) if n&1=1
: f(n) = f((n-2)/2) + f(n/2) if n&1=0
: 后程序，
: void FindAll210(int num, char res[], int index)
: {
: if(num==0){
: res[index] = 0;
: cout<
|
w******e
发帖数: 81 | 53 上来膜拜一下各位大仙，看来自己要继续修炼。。。
【在 y*c 的大作中提到】
: 你们是自己DFS，没用递归么？我这个递归的 num=8327168 也很快啊，我的输出需要
: reverse string一下。先写递归表达
: f(n) = f((n-1)/2) if n&1=1
: f(n) = f((n-2)/2) + f(n/2) if n&1=0
: 后程序，
: void FindAll210(int num, char res[], int index)
: {
: if(num==0){
: res[index] = 0;
: cout<
|
l******c
发帖数: 2555 | 54 I'm scared, too many 大仙.
【在 w******e 的大作中提到】
: 上来膜拜一下各位大仙，看来自己要继续修炼。。。
|
b******v
发帖数: 1493 | 55 这个程序超级赞，思路清晰，容易编写，而且速度很快
【在 y*c 的大作中提到】
: 你们是自己DFS，没用递归么？我这个递归的 num=8327168 也很快啊，我的输出需要
: reverse string一下。先写递归表达
: f(n) = f((n-1)/2) if n&1=1
: f(n) = f((n-2)/2) + f(n/2) if n&1=0
: 后程序，
: void FindAll210(int num, char res[], int index)
: {
: if(num==0){
: res[index] = 0;
: cout<
|
y*c
发帖数: 904 | 56
哇塞，第一次写程序被称赞，多谢各位！
【在 b******v 的大作中提到】
: 这个程序超级赞，思路清晰，容易编写，而且速度很快
|
B*****t
发帖数: 335 | 57 这个方法太好了！
【在 y*c 的大作中提到】
: 你们是自己DFS，没用递归么？我这个递归的 num=8327168 也很快啊，我的输出需要
: reverse string一下。先写递归表达
: f(n) = f((n-1)/2) if n&1=1
: f(n) = f((n-2)/2) + f(n/2) if n&1=0
: 后程序，
: void FindAll210(int num, char res[], int index)
: {
: if(num==0){
: res[index] = 0;
: cout<
|
B*****t
发帖数: 335 | 58 呵呵， 不敢当！
【在 b******v 的大作中提到】
: 赞！老大人品水平都显然更胜一筹
|
b******v
发帖数: 1493 | 59 这样修改一下就是正序输出了
void FindAll210(int num, char res[], int index)
{
if(num==0){
res[index] = 0;
// begin reverse the string
char c;
for(int i=0; i<=(int)((index-1)/2); i++) {
c = res[i];
res[i] = res[index-1-i];
res[index-1-i] = c;
}
//end reverse the string
cout<
return;
}
if(num&1){
res[index] = '1';
FindAll210((num-1)>>1, res, index+1);
}else{
res
【在 y*c 的大作中提到】
: 你们是自己DFS，没用递归么？我这个递归的 num=8327168 也很快啊，我的输出需要
: reverse string一下。先写递归表达
: f(n) = f((n-1)/2) if n&1=1
: f(n) = f((n-2)/2) + f(n/2) if n&1=0
: 后程序，
: void FindAll210(int num, char res[], int index)
: {
: if(num==0){
: res[index] = 0;
: cout<
|
t****t
发帖数: 6806 | 60 你这个思路跟我的类似, 不过我是从大向小搜索的, 不需要reverse string, 但是没有
利用最后一位是0,2/1的性质
顺手写了一个
#include
#include
using namespace std;
void FindAll210(int num, char res[], int index, int weight)
{
if (weight==0 && num==0) {
cout<
return;
}
if (num>(2*weight-1)*2) return;
res[index]='0';
FindAll210(num, res, index+1, weight>>1);
num-=weight;
if (num<0) return;
res[index]='1';
FindAll210(num, res, index+1, weight>>1);
num-=weight;
if (n
【在 y*c 的大作中提到】
: 你们是自己DFS，没用递归么？我这个递归的 num=8327168 也很快啊，我的输出需要
: reverse string一下。先写递归表达
: f(n) = f((n-1)/2) if n&1=1
: f(n) = f((n-2)/2) + f(n/2) if n&1=0
: 后程序，
: void FindAll210(int num, char res[], int index)
: {
: if(num==0){
: res[index] = 0;
: cout<
|
