为何基于队列迭代生成二进制字符串的函数出现无限输出？

嘿，我一眼就发现你代码里的bug啦！你这无限输出的问题，根源是修改s2的时候用错了对象，咱们一步步拆解来看：

问题分析 #

你创建了s2这个新的StringBuilder对象，但在替换?为1的时候，居然写成了s1.setCharAt(pos,'1')，而不是s2.setCharAt(pos,'1')。这就导致s2完全没被修改，还是带着?的原始字符串，每次入队后，循环又会处理这个未替换完?的字符串，队列永远不会空，自然就陷入无限输出的死循环了。

修正后的代码 #

static void fill(StringBuilder s) {
    Queue<StringBuilder> q = new LinkedList<>();
    q.add(s);
    while(!q.isEmpty()) {
        s = q.peek();
        int pos = s.indexOf("?");
        if(pos >= 0) {
            StringBuilder s1 = new StringBuilder(s);
            s1.setCharAt(pos, '0');
            q.add(s1);
            StringBuilder s2 = new StringBuilder(s);
            // 这里改成s2调用setCharAt，才是修改新创建的s2对象！
            s2.setCharAt(pos, '1');
            q.add(s2);
        } else {
            System.out.println(s);
        }
        q.poll();
    }
}

验证效果 #

当你传入new StringBuilder("1?1?")时，输出会完全符合预期：

1010
1011
1110
1111

额外小提示 #

如果想让代码逻辑更清晰，可以考虑把q.poll()的位置提前到循环开头（先取出元素再处理），不过你当前的逻辑只要修正了s2的调用就完全没问题啦。

内容的提问来源于stack exchange，提问作者akisonlyforu