2

最近，我被要求设计一个函数，该函数将采用包含 1、0 和 ? 中任何一个的单个字符串（例如：“10?10?1”、“00???11”、“???? "等）作为输入，并返回一个字符串列表，其中包含输入字符串的所有唯一的零排列。

对于“10?1?”的输入，答案将是包含“10010”、“10110”、“10011”和“10111”的列表。

我能够设计一个执行此操作的函数，但它本质上是蛮力的，我对复杂度为 O(2^n) 的更简洁的函数感兴趣。提供算法和/或实现将不胜感激，谢谢！

4

7 回答 7

2

我认为你不能比“蛮力”实现做得更好。对于提供的包含 N 个问号的任何此类字符串，将有 2^N 个唯一排列。真的，您所能做的就是按照您喜欢的顺序尝试所有不同的字符串。至于算法：

  • 获取指向字符串中所有有问号的位置的指针并存储在数组中。
  • 获取一个比问号个数长的无符号整数变量（使用 long long 是安全的）；设置为 0。
  • 变量中的位代表问号的所有可能组合。因此，使用按位运算将 1 和 0 替换为问号，并且每次将变量加 1。
  • 重复 2^N 次。
于 2013-11-01T03:29:26.270 回答
2

你可以把它想象成一棵树，其中每个节点都有一点。每个问号产生 2 个节点：0 和 1。任何不是问号的都只是具有相同值的节点。例如，对于 的输入10?1?，树会像这样展开：

在此处输入图像描述

这是一个C实现：

void generate_str(char *str, int pos) {
    if (str[pos] == '\0') {
        printf("%s\n", str);
        return;
    }
    if (str[pos] == '?') {
        str[pos] = '0';
        generate_str(str, pos+1);
        str[pos] = '1';
        generate_str(str, pos+1);
        str[pos] = '?'; /* We can get back to this branch because of an earlier '?' */
    }
    else {
        generate_str(str, pos+1);
    }
}

请注意，您必须将位置设置回“？” 在探索了那个分支之后，因为你可能来自另一个分支，然后你需要再次认识到这个相同的位置有一个问号。

你可以像这样调用这个函数：

int main(void) {
    char test[] = "10?1?";
    generate_str(test, 0);
    return 0;
}

您不能做得比 更好O(2^n)，因为您至少必须打印输出。

于 2013-11-01T09:37:16.533 回答
1

它会安慰这样的字符串

 arr = "4646555?45656?564465?";
    function A(arr){var k = arr.indexOf("?");
    if(k != -1){
        R = arr.slice(0,k);
        L = arr.slice(k+1,arr.length);
        let M = R +"0"+ L;
        let N = R +"1"+ L;


        if(M.indexOf("?") != -1) A(M);
        else console.log(M)
        if(N.indexOf("?") != -1) A(N);
        else console.log(N)
    }
    }
    A(arr)
于 2017-04-06T01:22:31.317 回答
1

我对此有一个递归解决方案

input_str = "10??01"

# 100001
# 100101
# 101001
# 101101

def solution(res, a, n):
  if n == 1 and a[0] != "?":
    print(res+a[0])
    return

  elif n == 1 and a[0] == "?":
    print(res+"0")
    print(res+"1")
    return


  if a[0] != "?":
    solution(res+a[0], a[1: ], len(a[1: ]))

  elif a[0] == "?":
    solution(res+"0", a[1: ], len(a[1: ]))
    solution(res+"1", a[1: ], len(a[1: ]))


solution("", input_str, len(input_str))
于 2017-11-10T19:39:09.113 回答
0

总体思路：

  • 创建一个接受一个string或字符数组和一个位置的函数。

  • 从位置 0 开始。

  • 增加位置，直到我们?在string.

  • 如果我们在字符串的末尾，输出它并返回。

  • 否则将字符设置在该位置1并从下一个位置递归，然后再到0并递归。

复杂：O(size of string + 2^(number of question marks))

于 2013-11-01T08:32:58.193 回答
0

用 Java 编写，但可以轻松转换为 c++。

基础是将问号分隔?为单个值。然后在组合列表中放入一个值（0而不是 all ?）。然后迭代烤箱并遍历组合列表，每次乘以使用bitwise or分隔问号的 on保存的值的数量?。

我们正在做 d 次乘法，其中 d 是问号的数量。因此，我们运行它大约 2^d 时间，因此 O(2^d)。如果 n 是输入大小，则小于 O(2^n)。

空间复杂度是返回的数组 - O(n * 2^d)。2^d 个字符串。每个字符串与输入的大小 - n。

* 如果输入大于 64 位，我会忽略合并的计算。

public class BinaryCombinationsForQuestionMark {

    public static void main(String[] args) {
        System.out.println(Arrays.toString(getAllCombinations("1??")));
    }

    // TODO: If larger than 64 bit, separate to 64 and merge to original sizes
    public static int[] getAllCombinations(String input) {
        // TODO: Validate input
        // Doing up to 64 bits
        int numWithZerosAsQuestions = convertToNumWithQuestionsAsZeros(input);
        int[] separated = separateToOnesAsQuestions(input);

        List<Integer> combinations = new ArrayList<>();
        combinations.add(numWithZerosAsQuestions);
        for (int separate : separated) {
            // Prevents ConcurrentModificationException
            int size = combinations.size();
            for (int i = 0; i < size; i++) {
                int combination = combinations.get(i);
                combinations.add(combination | separate);
            }
        }
        return combinations.stream().mapToInt(i -> i).toArray();
    }

    private static int[] separateToOnesAsQuestions(String input) {
        ArrayList<Integer> separated = new ArrayList<>();
        for (int i = input.length() - 1; i >= 0; --i) {
            char c = input.charAt(i);
            if (c == '?') {
                separated.add(1 << input.length() - 1 - i);
            }
        }
        return separated.stream().mapToInt(i -> i).toArray();
    }

    private static int convertToNumWithQuestionsAsZeros(String input) {
        int num = 0;
        for (int i = 0; i < input.length(); ++i) {
            num <<= 1;
            char c = input.charAt(i);
            if (c == '1') num |= 1;
        }
        return num;
    }
}

干杯。

于 2017-11-01T21:21:32.230 回答
0 
var arr = "00?11?01";
var l = arr.match(/[?]/g).length; //no of question marks
var l1 = Math.pow(2, l); // 2^l
for (var i = 0; i < l1; i++) {
    var num = Number(i).toString(2); //convert to binary
    while (num.length < l) { num = '0' + num }; //append required zeros
    var j = -1;
    console.log(arr.replace(/[?]/g, function() {j++; return num[j];}));
}
于 2017-04-06T16:11:44.553 回答