h*******e
发帖数: 125 | 1 给一个由1， 0 和 ?组成的字符串，返回所有的matching strings， “
?” 可以 match 0 and 1, 比如说：
input : 1??
output: {100, 101, 110, 111}.
input: 100100?00?
output: {1001000000,1001000001,1001001000,1001001001} |
y*****9
发帖数: 149 | 2 void match_string(string s){
match_recursive("",s)
}
void match_recursive(string s_1, string s_2){
if (s_2.length() == 0) cout << s1 << endl;
if (s_2[0] == '?'){
match_recursive(s_1 + "0", s_2.substr(1));
match_recursive(s_1 + "1", s_2.substr(1));
}
else {
match_recursive(s_1 + str(s_2[0]), s_2.substr(1));
}
} |
l*****a
发帖数: 14598 | 3 1) recursion is not good, it will use extra memory and it will cause
stackoverflow
2) string + string is not recommend as well
【在 y*****9 的大作中提到】
: void match_string(string s){
: match_recursive("",s)
: }
: void match_recursive(string s_1, string s_2){
: if (s_2.length() == 0) cout << s1 << endl;
: if (s_2[0] == '?'){
: match_recursive(s_1 + "0", s_2.substr(1));
: match_recursive(s_1 + "1", s_2.substr(1));
: }
: else {
|
g*********e
发帖数: 14401 | 4 void gen(string in) {
vector res;
stack stk;
if(in[0]=='1')
stk.push("1");
else if(in[0]=='0')
stk.push("0");
else {
stk.push("1"); stk.push("0");
}
while(!stk.empty()) {
string one=stk.top(); stk.pop();
int idx=one.length();
if(idx == in.length()) {
res.push_back(one);
cout<
} else if(in[idx]=='1') {
one+='1';
stk.push(one);
} else if(in[idx]=='0') {
one+='0';
stk.push(one);
} else {
stk.push(one+'0'); stk.push(one+'1');
}
}
} |
l*****a
发帖数: 14598 | 5 这个题用stack还是第一次见到
【在 g*********e 的大作中提到】
: void gen(string in) {
: vector res;
: stack stk;
: if(in[0]=='1')
: stk.push("1");
: else if(in[0]=='0')
: stk.push("0");
: else {
: stk.push("1"); stk.push("0");
: }
|
g*********e
发帖数: 14401 | 6 recursion据说都可以改成stack
【在 l*****a 的大作中提到】
: 这个题用stack还是第一次见到
|
l*****a
发帖数: 14598 | 7 我想这么做,你看咋样
List list=new ArrayList();
List result=new ArrayList();
for(int i=0;i
if(input.charAt(i)=='?') list.add(0);
}
while(true) {
String cur=genString(input,list);
result.add(cur);
// if all 1 in list, break;
for(int i=list.size()-1;i>=0;i--) {
if(list.get(i)==0) {
list.set(i)=1;
break;
} else {
list.set(i)=0;
}
}
}
return result;
【在 g*********e 的大作中提到】
: recursion据说都可以改成stack
|
y*****9
发帖数: 149 | 8 Python:
list = []
for i in range(len(s)):
if (s[i] == ?):
list = [element + '0' for element in list].extend(
[element + '1' for element in list])
else:
list = [element + s[i] for element in list]
print list |
g*********e
发帖数: 14401 | 9
看不懂@@
【在 l*****a 的大作中提到】
: 我想这么做,你看咋样
: List list=new ArrayList();
: List result=new ArrayList();
: for(int i=0;i: if(input.charAt(i)=='?') list.add(0);
: }
: while(true) {
: String cur=genString(input,list);
: result.add(cur);
: // if all 1 in list, break;
|
l*****a
发帖数: 14598 | 10 those ?s can be replaced by
000
001
010
011
100
101
110
111
make sense?
【在 g*********e 的大作中提到】
:
: 看不懂@@
|
|
|
f******n
发帖数: 279 | |
d**e
发帖数: 6098 | 12 你的code似乎有个bug: while(true)没有条件退出,进入死循环.
我觉得你flip bit的那段code有些问题,它并没有正确地flip, list.get(i)是?的index
,用它来跟0/1比较应该是不正确的.
我把它改成这样,用shift bit来做,不知有没有更好的方法.
public static List genMatchers(String str) {
List results = new ArrayList();
if (str != null && str.length() != 0) {
List questionMarkPositions = new ArrayList();
for (int i = 0; i < str.length(); i++) {
char c = str.charAt(i);
if (c == '?') {
questionMarkPositions.add(i);
}
}
StringBuilder builder = new StringBuilder(str);
int numberOfQuestionMarks = questionMarkPositions.size();
for (int questionMarkValue = 0;
questionMarkValue < ((1 << numberOfQuestionMarks) - 1);
questionMarkValue++) {
for (int j = 0; j < numberOfQuestionMarks; j++) {
int shift = numberOfQuestionMarks - 1 - j;
char setValue =
(char) ('0' + ((questionMarkValue & (1 << shift)) >>
shift));
builder.setCharAt(questionMarkPositions.get(j), setValue
);
}
results.add(builder.toString());
}
}
return results;
}
【在 l*****a 的大作中提到】
: those ?s can be replaced by
: 000
: 001
: 010
: 011
: 100
: 101
: 110
: 111
: make sense?
|
g********e
发帖数: 1142 | 13
this is the clearest logic.
【在 l*****a 的大作中提到】
: those ?s can be replaced by
: 000
: 001
: 010
: 011
: 100
: 101
: 110
: 111
: make sense?
|
l*****a
发帖数: 14598 | 14
// if all 1 in list, break;
index
我存的就是0,1不是index
【在 d**e 的大作中提到】
: 你的code似乎有个bug: while(true)没有条件退出,进入死循环.
: 我觉得你flip bit的那段code有些问题,它并没有正确地flip, list.get(i)是?的index
: ,用它来跟0/1比较应该是不正确的.
: 我把它改成这样,用shift bit来做,不知有没有更好的方法.
: public static List genMatchers(String str) {
: List results = new ArrayList();
: if (str != null && str.length() != 0) {
: List questionMarkPositions = new ArrayList();
: for (int i = 0; i < str.length(); i++) {
: char c = str.charAt(i);
|
X*4
发帖数: 101 | 15 这方法太暴力了
比递归节省不了多少空间吧，
【在 g*********e 的大作中提到】
: void gen(string in) {
: vector res;
: stack stk;
: if(in[0]=='1')
: stk.push("1");
: else if(in[0]=='0')
: stk.push("0");
: else {
: stk.push("1"); stk.push("0");
: }
|
w****3
发帖数: 110 | 16 自己实现stack和递归的复杂度也是一样，不需要每一位都递归，只要碰到？的时候
copy一份递归就可以
或者计算出？的个数m算m^2的全排列再还原原来的数，复杂度也是一样的 |
d**e
发帖数: 6098 | 17 看明白了，但你的break比较confusing....
【在 l*****a 的大作中提到】
:
: // if all 1 in list, break;
: index
: 我存的就是0,1不是index
|
s******t
发帖数: 229 | 18 干脆大家就讨论怎么生成连续的binary数字算了！ |
m*****l
发帖数: 95 | 19 随便给个思路。
public static Set generateStrings(String input) {
Set stringSet = new HashSet();
if(input != null) {
List questionMarks = new ArrayList();
char[] chars = input.toCharArray();
for (int i = 0; i < chars.length; i++) {
if (chars[i] == '?') {
questionMarks.add(i);
} else if (chars[i] != '0' && chars[i] != '1') {
throw new IllegalArgumentException();
}
}
if(questionMarks.size() != 0) {
if(questionMarks.size() > 31) {
throw new IllegalArgumentException("Too many question
marks");
}
for(int i = 0; i < 1 << questionMarks.size(); i++) {
int x = i;
for(Integer position : questionMarks) {
int flag = x & 1;
chars[position] = ( flag == 0) ? '0' : '1';
x = x >> 1;
}
stringSet.add(new String(chars));
}
}else{
stringSet.add(input);
}
}
return stringSet;
}
【在 h*******e 的大作中提到】
: 给一个由1， 0 和 ?组成的字符串，返回所有的matching strings， “
: ?” 可以 match 0 and 1, 比如说：
: input : 1??
: output: {100, 101, 110, 111}.
: input: 100100?00?
: output: {1001000000,1001000001,1001001000,1001001001}
|
