我是一名有用的助手,可以帮您进行文本翻译。
我有一个问题,不知道该如何解决。
我的问题是:我有一个二进制字符串,想生成所有可能的二进制子字符串。
例如:
input : 10111
output: 10000, 10100,00111,00001,10110 ...
我该如何快速而聪明地完成这项任务?
我是一名有用的助手,可以帮您进行文本翻译。
我有一个问题,不知道该如何解决。
我的问题是:我有一个二进制字符串,想生成所有可能的二进制子字符串。
例如:
input : 10111
output: 10000, 10100,00111,00001,10110 ...
Magic - 假定位掩码:
subset( int x )
list = ()
for ( int i = x; i >= 0; i = ( ( i - 1 ) & x ) )
list.append( i )
return list
不用在意——我忘了你的数据是字符串形式而不是整型/长整型等。不过你仍然可以使用相同的逻辑……只需按二进制计数,但仅使用包含1的位置。
只是随口一想。
我们来看看字符串1001。
我认为你想要的是四个数字:1001、1000、0001和0000,对吗?
如果是这样,你正在计算“1”的位置。
其中一种方法是存储原始数字。
orig = n;
然后开始对此进行迭代,并遍历每一个较小的数字。
while(n--)
但是,在每次迭代中,忽略试图将1放在0的位置的情况:
if(n & !orig)
continue;
printsubsets(const string &in, const string &out)
{
if(in.empty())
{
cout<<out<<"\n";
return;
}
if(in[0]=='1')
printsubsets(in.substr(1), out+"1");
printsubsets(in.substr(1), out+"0");
}
这就是它:
vector<string> submasks(string in)
{
vector<string> out;
out.push_back(string(in.size(), '0'));
for (int i = 0; i < in.size(); ++i)
{
if (in[i] == '0') continue;
int n = out.size();
for (int j = 0; j < n; ++j)
{
string s = out[j];
s[i] = '1';
out.push_back(s);
}
}
return out;
}
我认为这几乎是最优解了。