时间戳

首页 > 解决方案 > 生成给定长度并带有约束的二进制字符串

java - 生成给定长度并带有约束的二进制字符串

问题描述

我正在尝试编写一个逻辑，我想在其中生成给定大小的二进制字符串列表，n并且该字符串的最大k位数应设置为1.

例子：

If n = 3, k = 1 ==> the number of 1's can be 0 or 1.
Then the output should be 000, 001, 010, 100

以下是我在此链接的帮助下使用的逻辑作为参考：

这里n与 相同arr.length。

static void generateAllBinaryStrings(int n, int arr[], int i, List<String> res, int k) {
    if (i == n) {
        StringBuilder sb = new StringBuilder();
        int count = 0;
        for (int j = 0; j < arr.length; j++) {
            int val = arr[j];
            if (val == 1) {
                count++;
            }
            sb.append(val);
        }
        if (count <= k) {
            res.add(sb.toString());
        }

        return;
    }

    arr[i] = 0;
    generateAllBinaryStrings(n, arr, i + 1, res, k);

    arr[i] = 1;
    generateAllBinaryStrings(n, arr, i + 1, res, k);
}

public static void main(String args[]) {
    int n = 3;
    int[] arr = new int[n];
    int k = 1;
    int i = 0;
    List<String> res = new ArrayList<>();
    generateAllBinaryStrings(n, arr, i, res, k);
    System.out.println(res);// Prints [000, 001, 010, 100]
}

此代码工作正常，但此逻辑生成所有可能的二进制字符串，然后根据字符串中 1 的数量进行过滤。

有没有针对这个问题的时间复杂度更低的算法。

标签： javabinary

解决方案

我想出了这个：

static void generateAllBinaryStrings(StringBuilder sb, int n, Set<String> res, int k) {
    int len = sb.length();
    if (k == 0) {
        repeat(sb, '0', n);
        res.add(sb.toString());
        sb.setLength(len);
    } else {
        for (int i = 0; i <= n; ++i) {
            repeat(sb, '0', i);
            if (i < n) {
                sb.append('1');
                generateAllBinaryStrings(sb, n-i-1, res, k-1);
            } else {
                res.add(sb.toString());
            }
            sb.setLength(len);
        }
    }
}

private static void repeat(StringBuilder sb, char c, int n) {
    for (int j = 0; j < n; ++j) {
        sb.append('0');
    }
}

这个想法是你有k一个可以放在一个长度的字符串中n；所以如果k == 0，唯一可能的值是n零。如果k > 0，您可以添加n零或i零，i介于 0 和 n-1 之间的任意位置，然后是 a 1，递归剩余空间和k-1。

推荐阅读