d********i
发帖数: 582 | 1 题目：给一个只包含0,1,*的 String，将所有的*替换成0或者1,返回所有的可能。
For example, “00*1*0” => {“001100”, “001110”, “000110”, “
000100”｝
我的代码只输出： [“000100”, “000110”, “001110”], 但是少了“001100”.
我找不出原因。 谢谢。。
我的代码如下：
public static int depth;
public ArrayList combinationStarts(String s) {
int n = s.length();
char[] sc = s.toCharArray();
int starCount = 0;
for (int i = 0; i < n; i++) {
if (sc[i] == '*') {
starCount++;
}
}
depth = 0;
ArrayList res = new ArrayList();
dfs(sc, res, starCount);
return res;
}
public void dfs(char[] sc, ArrayList res, int starCount) {
if (depth == starCount) {
res.add(Arrays.toString(sc));
} else {
for (int i = 0; i < sc.length; i++) {
if (sc[i] == '*') {
depth = depth + 1;
sc[i] = 0 + '0';
dfs(sc, res, starCount);
sc[i] = 1 + '0';
dfs(sc, res, starCount);
}
}
}
} | d********i
发帖数: 582 | 2 我对recursion下的static的应用不太理解。。请教下什么时候该用static？ | d********i
发帖数: 582 | 3 请问recursion下什么时候要用static? 谢谢。。
代码run还是不对，什么都没有。。。。
public static ArrayList combinationStarts(String s) {
ArrayList res = new ArrayList();
dfs(s.toCharArray(), res, 0);
return res;
}
public static void dfs(char[] sc, ArrayList res, int depth) {
if (depth == sc.length) {
res.add(new String(sc));
} else {
for (int i = depth; i < sc.length; i++) {
if (sc[i] == '*') {
sc[i] = '0';
dfs(sc, res, i + 1);
sc[i] = '1';
dfs(sc, res, i + 1);
}
}
}
} | c**********y
发帖数: 38 | 4 小弟也是刚毕业在找工作刷题，学识浅薄，说的不对的请斧正。
1.不建议转换成chararray，因为你到后面还要转换回String，用stringbuilder可能会
更方便
2.这道题dfs里面不应该用for loop，虽然一样能出结果，但是compare非*字符的操作
在for里面会重复，会浪费很多时间，用for loop的时间复杂度是2^n,不用的是2^k,k
refers to number of * in string.
3.dfs在把字符分别设为0和1之后，要把字符还原成*，这是为什么大哥的结果里面没有
001100，因为在第二层设为1之后返回上一层，上一层在第二层原本是*的地方现在是1
了，于是结果只有00,01,11，若在第二层分别置0和1之后将该位置还原成*再返回上一
层，上一层再跑到这个位置的时候就会分出两个结果。
原代码里面只需要在dfs函数的for loop里面第二个dfs(sc, res, starCount);下面加
一句sc[i]='*'，代码应该就能出正确结果，这是小弟的代码，仅供参考：
public static ArrayList combinationStarts(String s) {
ArrayList res = new ArrayList();
dfs(new StringBuilder(s),0,res);
return res;
}
public static void dfs(StringBuilder s,int p,ArrayList res) {
if (p == s.length()) {
res.add(s.toString());
return;
}
if(s.charAt(p)=='*'){
s.setCharAt(p, '0');
dfs(s, p+1, res);
s.setCharAt(p, '1');
dfs(s, p+1, res);
s.setCharAt(p, '*');
}else{
dfs(s, p+1, res);
}
}
有推荐工作机会的大哥大姐们欢迎联系，谢谢~ | y**********u
发帖数: 6366 | | l*****a
发帖数: 14598 | 6 en.
被static搞晕了 ：（
【在 y**********u 的大作中提到】
: 这个代码看着就不对啊
| d********i
发帖数: 582 | 7 前辈，多谢你指点。。
1
【在 c**********y 的大作中提到】
: 小弟也是刚毕业在找工作刷题，学识浅薄，说的不对的请斧正。
: 1.不建议转换成chararray，因为你到后面还要转换回String，用stringbuilder可能会
: 更方便
: 2.这道题dfs里面不应该用for loop，虽然一样能出结果，但是compare非*字符的操作
: 在for里面会重复，会浪费很多时间，用for loop的时间复杂度是2^n,不用的是2^k,k
: refers to number of * in string.
: 3.dfs在把字符分别设为0和1之后，要把字符还原成*，这是为什么大哥的结果里面没有
: 001100，因为在第二层设为1之后返回上一层，上一层在第二层原本是*的地方现在是1
: 了，于是结果只有00,01,11，若在第二层分别置0和1之后将该位置还原成*再返回上一
: 层，上一层再跑到这个位置的时候就会分出两个结果。
| r****7
发帖数: 2282 | 8 Java里边默认是传引用吧
C++写了个，看了下和你的逻辑应该一样的，不过我觉得这个叫DFS是不是牵强了点儿。
。。
#include
#include
using namespace std;
int size;
void print(vector arr)
{
for (int i = 0; i < arr.size(); i++) {
printf("%c ", arr[i]);
}
printf("n");
}
void backtracking(vector arr, int len)
{
if (len == size) {
print(arr);
return;
}
int currLen = len;
len ++;
if (arr[currLen - 1] == '*') {
arr[currLen - 1] = '0';
backtracking(arr, len);
arr[currLen - 1] = '1';
backtracking(arr, len);
} else {
backtracking(arr, len);
}
}
int main()
{
char tmp[] = {'0', '0', '*', '1', '*', '0'};
vector arr(tmp, tmp + sizeof(tmp) / sizeof(char));
print(arr);
size = arr.size();
backtracking(arr, 1);
return 0;
}
【在 d********i 的大作中提到】
: 题目：给一个只包含0,1,*的 String，将所有的*替换成0或者1,返回所有的可能。
: For example, “00*1*0” => {“001100”, “001110”, “000110”, “
: 000100”｝
: 我的代码只输出： [“000100”, “000110”, “001110”], 但是少了“001100”.
: 我找不出原因。 谢谢。。
: 我的代码如下：
: public static int depth;
: public ArrayList combinationStarts(String s) {
: int n = s.length();
: char[] sc = s.toCharArray();
| x****7
发帖数: 86 | 9 C++:
#include
void replaceWildCard (std::string str, size_t pos)
{
if (pos >= str.size()) {
std::cout << str << std::endl;
return;
}
if (str[pos] == '*') {
str[pos] = '0';
replaceWildCard (str, pos + 1);
str[pos] = '1';
replaceWildCard (str, pos + 1);
}
else {
replaceWildCard(str, pos + 1);
}
}
int main (int argc, char ** argv)
{
replaceWildCard (std::string(argv[1]), 0);
return 0;
} | a****r
发帖数: 87 | 10 其实和permutation问题一样。
void transform_str_helper(vector &result, string sofar, string rest){
if(rest == "") {
result.push_back(sofar);
return;
}
size_t k = rest.find('*');
if(k == string::npos){
transform_str_helper(result, sofar+rest, "");
}else{
transform_str_helper(result, sofar+ rest.substr(0, k) + '0', rest.
substr(k+1));
transform_str_helper(result, sofar+ rest.substr(0, k) + '1', rest.
substr(k+1));
}
}
vector transform_str(string &st){
if(st == "") return vector();
vector result;
transform_str_helper(result, "", st);
return result;
} | f********6
发帖数: 9 | 11 dfs(sc, res, starCount);
后面加上sc[i] = '*';应该就好用了吧 | c**********y
发帖数: 38 | 12 不客气~~ 一起加油！！
【在 d********i 的大作中提到】
: 前辈，多谢你指点。。
:
: 1
| f******t
发帖数: 18 | 13 为什么都说还原＊号~我看楼主代码，每次循环是从0开始，如果加上还原星号会导致死
循环吧？应该还原是depth变量，楼主用static却从来不见depth有减的时候，这样当第
一次depth符合return条件之后，每次一进去递归就会返回 |
|
