java - 如何获得包含从 1 到 "n"的所有数字所需的 ArrayList 的最小数量？

Question

我正在寻找一个简单的解决方案来获取包含从 1 到 n 的所有数字所需的最小数量“整数数组列表”，并满足以下条件:

每个 ArrayList 必须由 3 个参数(a、b 和 n)创建

“a”和“b”设置ArrayList中的数字

“n”是极限

条件是:

如果 a ≤ b ===> a ≤ j ≤ b

如果 a>b ===> 1 ≤ j ≤ b 且 a ≤ j ≤ n

注意:“j”是 ArrayList 上的数字。

这是我的代码:

public Integers(int a, int b, int n) {//constructor
    this.numbers = new ArrayList<Integer>();

    makeList(a, b, n);
}

public void makeList(int a, int b, int n) {
    if (a < b) {
        while (a <= b) {
            this.numbers.add(a);
            a++;
        }
    } else {

        int aux = 1;
        while (aux <= b) {
            this.numbers.add(aux);
            aux++;
        }

        int aux2 = a;
        while (aux2 <= n) {
            this.numbers.add(aux2);
            aux2++;
        }

    }
}

public void showNumbers() {
    for (int x = 0; x < this.numbers.size(); x++) {
        System.out.print(this.numbers.get(x) + "\t");
    }

}

这是 n=20 的示例:

public static void main(String[] args) {
    Integers first= new Integers(1, 10, 20);
    first.showNumbers();//1 2 3 ...8 9 10
    System.out.println();

    Integers second= new Integers(15, 5, 20);
    second.showNumbers();//1 2 3 4 5 15 16 17 18 19 20 
    System.out.println();

    Integers third= new Integers(15, 20, 20);
    third.showNumbers();//15 16 17 18 19 20
    System.out.println();

    Integers fourth= new Integers(4, 17, 20);
    fourth.showNumbers();//4 5 6 ... 15 16 17
    System.out.println();

    System.out.println("Solution expected is: 2 ====> <second and fourth>");
}

我期望的答案是 2(第二个和第四个)。

Answer 1

如果您从一开始就知道 n 是什么，那么存储 n 值的 boolean 数组可能会更简单。然后，每次构造 ArrayList 时，只需标记该值是否出现在 ArrayList 中即可。

除此之外，您几乎必须进行暴力破解(我认为这相当于顶点覆盖问题，因此您最多能够比暴力破解更快地进行近似)。

因此，我会尝试您的 Integer 类的实现:

public class Integer {
    private int a, b;
    private boolean flipped;

    public Integer(int _a, int _b){
        a = Math.min(_a, _b);
        b = Math.max(_a, _b);
        flipped = b < a;
    }

    public void markOff(boolean [] arr){
        for(int i = 0; i < arr.length; i++){
            if(a <= i && i <= b){
                arr[i] = arr[i] || !flipped;
            }else{
                arr[i] = arr[i] || flipped;
            }
        }
    }
}

因此，在上面，markOff 只是检查每个索引是否会出现在您创建的 ArrayList 中(我将让您自行计算 boolean 逻辑) ，但想法只是根据需要将所有额外元素设置为 true - 因此，如果数组覆盖了新索引，您可以将其标记为关闭，但不会取消标记已标记的元素。)您可以如果您愿意，可以对其进行优化，使其不遍历整个数组，并且看起来更像您的 makeList。

为了找到最多覆盖 n 的最小数组集，您必须执行如下操作:

public static int driveSoln(int n, Integer[] covers){
    return helper(covers, new boolean[n], 0, 0);
}

private static int helper(Integer[] covers, boolean[] marked, int idx, int used){
    boolean done;
    for(boolean d: marked) done = done && d;
    if(done) return used;

    if(idx >= covers.length) return -1;

    boolean [] markCopy = marked.clone();
    covers[i].markOff(marked);
    int dontUse = helper(covers, markCopy, idx + 1, used);
    int use = helper(covers, marked, idx + 1, used + 1);
    return Math.min(use, dontUse);
}

直观上，我在这里所做的就是针对每个输入的封面，选择是否使用它并继续查看其余部分。这里的递归“记住”我的选择。我保证(遗憾的是)检查所有的选择，所以这很慢，但绝对是正确的。一种优化可能是忽略子集:如果一个数组仅覆盖 1 个数组已覆盖的项目，则丢弃它。