|
今天没事，撸一道算法题
题目要求：
给出一个升序排序的可能重复值的数字数组和一个目标值
其中目标值大于数组中最小数，求数组中数字组合(可多值组合)相加最接近目标数的组合(可能多个)
不考虑空间复杂度，效率最优的算法;
样例:
数组为[3,4,8,6]，目标值为9，最接近组合为[8]和[4,6];
这道题我的解题思路是：
1.先得到数组的全部不重复不为空的子集
2.将子集的和作为key，子集的元素作为value存进map
3.将子集的和与给定值相减，然后取绝对值，最小的就是题目要的结果
比如：集合是arr={3，4，8}，目标值为9 集合的所有不为空的子集为{3}，{4}，{8}，{3,4}，{3,8}，{4,8}，{3,4,8} 六个集合的和分别为3，4，8，7，11，12，15，将这六个数作为key存进map中，value是对应的元素集合，然后把每一个数与目标值（9）相减并取绝对值。 可得到结果为|3-9|=6，|4-9|=5，|8-9=|1，|7-9|=2，|11-9|=3，|15-9|=6，可以看到|8-9|=1是最小的，也就是输出{8}这个子集符合题意。
不多比比，下面是求集合子集的代码
public static List getArr(List list) {
if(list.size()>0){//当数组长度大于0时才进行子集获取
List result = new ArrayList();
long n = (long) Math.pow(2, list.size());//集合的子集数量 2的数组长度次方
List temp;
for (long l = 0L; l
if ((l >>> i & 1) == 1) {
temp.add(list.get(i));//用一个List来装每个子集中的元素
}
}
if (!temp.isEmpty()) result.add(temp);//当获取到的子集不为空时就放入返回结果中
}
return result;
}
return null;
}
有兴趣可以复制到idea里跑一下
这部分代码的原理如下：
000 无符号右移0位 与1位与运算后 000 ！=1
000 无符号右移1位 与1位与运算后 000 ！=1
000 无符号右移2位 与1位与运算后 000 ！=1
001 无符号右移0位 与1位与运算后 001 =1 获得下标为0的元素 第一个子集
001无符号右移1位 与1位与运算后 000 ！=1
001无符号右移2位 与1位与运算后 000 ！=1
010 无符号右移0位 与1位与运算后 010 ！=1
010 无符号右移1位 与1位与运算后 001 =1 获得下标1的元素 第二个子集
010 无符号右移2位 与1位与运算后 000 ！=1
011 无符号右移0位 与1位与运算后 001 =1
011 无符号右移1位 与1位与运算后 001 =1 获取下标为0,1的元素 第三个子集
011 无符号右移2位 与1位与运算后 000 ！=1
100 无符号右移0位 与1位与运算后 000 ！=1
100 无符号右移1位 与1位与运算后 000 ！=1
100 无符号右移2位 与1位与运算后 001 =1 获取下标为2的元素 第四个子集
101 无符号右移0位 与1位与运算后 001 =1
101 无符号右移1位 与1位与运算后 000 ！=1 获取下标为0,2的元素 第五个子集
101 无符号右移2位 与1位与运算后 001 =1
110 无符号右移0位 与1位与运算后 000 ！=1
110 无符号右移1位 与1位与运算后 001 =1 获取下标为1,2的元素第六个子集
110 无符号右移2位 与1位与运算后 000 =1
111 无符号右移0位 与1位与运算后 001 =1
111 无符号右移1位 与1位与运算后 001 =1 获取下标为0,1,2的元素 第七个子集
111 无符号右移2位 与1位与运算后 001 =1
输入：
123
输出：
1
2
12
3
13
23
123
得到所有子集后，求和放入map，将子集的和与目标值相减取最小的绝对值对应的子集并输出，代码如下：
public static List back(List list,Integer x){
List lists = new ArrayList();
ArrayList objects = new ArrayList();
Integer sum=new Integer(0);
for (int i = 0; i
sum+=integers.get(i1);
objects.add(Math.abs(sum-x));
}
sum=0;
}
Integer min = Collections.min(objects);
for (int i = 0; i
sum+=integers.get(i1);
}
if(min==Math.abs(sum-x)){
lists.add(integers);
}
sum=0;
}
return lists;
}
最后测试一下：
public static void main(String[] args) {
List integers = new ArrayList();
integers.add(new Integer(6));
integers.add(new Integer(26));
integers.add(new Integer(37));
integers.add(new Integer(50));
integers.add(new Integer(50));
integers.add(new Integer(31));
integers.add(new Integer(16));
List arr = getArr(integers);
List back = back(arr, 100);
for (int i = 0; i
System.out.print(l1.get(i1)+" ");
}
System.out.println();
}
}
输出：
50 50
6 26 37 31
Process finished with exit code 0
6+26+37+31=100
完事
|