我如何获得拥有<Integer>从 1 到 "n" 的所有数字所需的最小数组列表数？

Question

我正在寻找一个简单的解决方案，以获得从1到n的所有数字所需的最小数量"整数数组列表"，条件是：

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

"a"one_answers"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值的布尔数组可能会更简单。然后，每次构造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中(我将把布尔逻辑的计算留给您，但其想法只是根据需要将所有额外的元素设置为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个数组覆盖的项目，则丢弃它