一道阿里巴巴算法笔试题

Question

给定一个数t,以及n个数，在这n个数中找到加和为t的所有集合，例如t=4,n=6,这6个数为（4，3，2，2，1，1）这样输出就有4个不同的组合它们的加和为4: 4,3+1,2+2,and 2+1+1,请设计一个高效算法实现这个需求

Answer 1

先对 n 个数进行排序，然后找到 <= t 的数，然后做循环得出不同的组合

Answer 2

如果不用输出的话其实是很简单的
可以建个链表 保存数组内元素的所有可能和
那样可以在O(logn)内完成
如果要输出其实也可以变下方式 一样不是很难

Answer 3

不好意思 构造的时候还是慢
我说的 O(logn)是指后边的查找时间
这个题没什么好的方法
只能暴力搜索

Answer 4

主要是考算法的，应该不是几个简单的for就能够搞定的，暴力搜索应该不是别人主考官想要的答案

Answer 5

如本题最后能得到的结果是
{4，3，2，2，1，1}
取 4
链表里  4
取 3 
链表里 3 4
取 2 
链表里 2 3 4 5 6
...
...
...
最后 链表里有 1 2 3 4 5 6 7 8 9 10 11 12 13 这就是能组合到的结果
当然这个没记录组合过程
可以用 map 值做键 过程以 string 存起来
这个实现起来不难吧楼上有人怀疑
但不可否认这个是可行的吧
毕竟N 个数的取否状态有 2^n 种
构造的时候时间复杂度是O(2^n)最后找数的时候时间按复杂度是 O(log n)其他的高效方法目前貌似还没有也可能是我孤陋寡闻吧

Answer 6

这个题本来就是 NP 级的
高效的方法貌似目前还没人找到
只能在 n 不大的情况下 暴力搜索 配合 适当的剪支

Answer 7

补充条件: t为正整数，集合为n个正整数构成的集合，n足够大
算法简要说明：排序+循环迭代+剪枝
具体步骤：
1、将集合内的元素由大到小排序
2、对n进行循环，判断第n个元素a=n[a]与t的大小
   若a>t continue
   若a==t 取出元素 continue
   若a<t 则另t'=t-a a=n[a+1] 
3、迭代循环

Answer 8

大概写了下，勉强能实现，但是效率不大高。给大家做个参考，欢迎改进
import java.util.*;public class Test {
public static void main(String[] args) {
int number = 9;
int[] array = { -9,-8,-7,-6,-5,-4,-3,-2,-1,1, 2, 3, 4, 5, 6, 7, 8, 9 };
List<String> list = f(number, array);
for (String s : list)
System.out.println(s);
} static List<String> f(int number, int[] array) {
List<String> list = new ArrayList<String>();
                // 这里先排除掉数组中与要找的数字相同的数，否则后面递归里面一直都在第一个循环中返回。这里不太好
for (int i = 0; i < array.length; i++) 
if(array[i] == number){
list.add(number + "");
array[i] = 0;
}

for (int i = 0; i < array.length; i++) {
if (array[i] == number) {
list.add(number + "");
continue;
}
String s = g(i, number, array);
if (!s.endsWith("null"))
list.add(s);
}
return list;
} static String g(int startIndex, int number, int[] array) {
for (int i = startIndex; i < array.length; i++){
if(array[i] == 0)
continue;
if (array[i] == number)
return array[i] + "";
}

for (int i = startIndex; i < array.length; i++)
if (array[i] < number) {
number -= array[i];
return array[i] + " + " + g(i + 1, number, array);
}
return null;
}
}

Answer 9

package cn.gao.util.algorithm;
import java.util.ArrayList;
import java.util.Collection;
@SuppressWarnings("serial")
public class BagList extends ArrayList {
@SuppressWarnings("unchecked")
public BagList(int num)
{
super.add(num);
}
@SuppressWarnings("unchecked")
public BagList(Collection<Integer> collection,int num)
{
for(Integer o:collection)
{
this.add(o);
}
this.add(num);
}
@Override
public boolean equals(Object arg0) {
// TODO Auto-generated method stub
if(arg0==this)
{
return true;
}
if(arg0==null&&this!=null||this==null&&arg0!=null)
{
return false;
}
if(arg0.getClass()!=BagList.class)
{
return false;
}
else{
BagList b=(BagList)arg0;
if(this.size()!=b.size())
{
return false;

}
for(Object o:b)
{
if(!this.contains(o))
{
return false;
}
}
return true;
}
}
@Override
public int hashCode() {
int sum=0;
for(Object o:this)
{
sum+=(Integer)o;
}
return sum;
}
}
package cn.gao.util.algorithm;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;
import java.util.Map.Entry;
/*
 * 0-1背包问题，已知给定一个数组，里面存放N个数的重量，然后你自己选出所有的重量等于M的组合情况
 */
public class ZeroOneBagTest {
private Map<Integer, Set<BagList>> bagMap=new HashMap<Integer, Set<BagList>>();//保存排列组合信息
private Set<BagList> newBagSet=new HashSet<BagList>();//临时Set，用于构建上面的Map
private int count=1;
private int[] a;
private int target;
public ZeroOneBagTest(int[] a,int target)
{
this.a=a;
this.target=target;
}
public void printZuHe()
{
ArrayList<BagList> newBagList=new ArrayList<BagList>();
f();
Set<Entry<Integer, Set<BagList>>> s=bagMap.entrySet();
for(Entry<Integer, Set<BagList>> ss:s)
{
System.out.println(ss.getKey()+"个数的组合有：");
for(BagList bg:ss.getValue())
{
System.out.println(bg);
if(sum(bg)==target)
{
newBagList.add(bg);
}
}
}
System.out.println("和值等于"+target+"组合一共有"+newBagList.size()+"种！");
for(BagList bs:newBagList)
{
System.out.println(bs);
}
}
public int sum(BagList bb)
{
int sum=0;
   for(Object o:bb)
   {    
   sum+=(Integer)o;
   }
   return sum;
}
public void f()
{
while(true)
{
if(count==1)
{
for(int k:a)
{
newBagSet.add(new BagList(k));
bagMap.put(1, newBagSet);
}
count++;
}
if(count==a.length+1)
{
break;
}
g();
bagMap.put(count, newBagSet);
count++;
}
}
public void g()
{
Set<BagList> newBagSet1=new HashSet<BagList>();
for(int k:a)
{
for(BagList bg:newBagSet)
{
if(!bg.contains(k))
{
newBagSet1.add(new BagList(bg,k));
}
}
}
newBagSet=newBagSet1;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
int a[]={4,3,2,2,1,1};
long x=System.currentTimeMillis();
ZeroOneBagTest zz=new ZeroOneBagTest(a,4);
zz.printZuHe();
System.out.println(System.currentTimeMillis()-x);
}
}写了一个实现算法，（自己实现了一个特殊的LIST）,不过中间用了大量的内存，不过索性的是执行的时间还算比较快。

Answer 10

汗，一大早上来解题。这是0-1背包的变形，如果按0-1背包处理会出现打印相同组合多次的情况，比如1重复了2次，那么，可能1+3打印出两次。为了消除这个重复，可一开始计算出重复次数，在规划的时候，依次看加入当前元素1，2，3，。。M次的子问题。令result[v][i]表示，前1,2,..i个元素可构成和等于v的可能数。
那么result[v][i]的可能方案中可能包含a[i],也可能不包含，不包含的总数有result[v][i-1].
包含的情况有多种，可能包含一次，也可能包含2，3，。。n次。另外还可能只包含该元素，这时方案数要加1.result[v][i]=∑(result[v-a[i]*k][i-1])+result[v][i-1]+((v%a[i])==0?1:0)
方案数算出来后，构建路径比较麻烦点，但是思路还是一样。
从result[N][M]开始逆推，分别考虑是否包含了最后元素和不包含，一直逆推到只包含第一个元素，就可以打印出该路径。
代码：/**
 * 
 *//**
 * <pre>
 * 给定一个数t,以及n个数，在这n个数中找到加和为t的所有集合，
 * 例如t=4,n=6,这6个数为（4，3，2，2，1，1）
 * 这样输出就有4个不同的组合它们的加和为4: 4,3+1,2+2,and 2+1+1,
 * 请设计一个高效算法实现这个需求
 * </pre>
 * @author yvon 可重复一定次数的背包问题，不是一般的0-1背包,因为不能打印出重复的组合
 * 重建路径麻烦点
 */
public class AliTest {
void solve(int N, int[] arr) {
int iLen = 0;
int m[] = new int[arr.length];
iLen = calcMultiplicy(arr, m);
int result[][] = new int[N + 1][iLen];
dpCalc(N, arr, m, iLen,result);
System.out.println("Totally:"+result[N][iLen-1]);
int path[]=new int[arr.length];
recurDisplay(result,arr,m,iLen,N,iLen-1,path,0);
        
}

/**
 * 动态规划计算可能的组合个数。
 * result[v][i]表示前i个数加起来等于v 的方案数
 * 则result[v][i]=∑(result[v-a[i]*k][i-1])+result[v][i-1]+((v%a[i])==0?1:0)
 * @param N 
 * @param arr
 * @param m
 * @param len
 * @param result
 */
private void dpCalc(int N, int[] arr,  int[] m,int len, int[][] result) {
for (int k = 0, t = 0; k < m[0] && t <= N; k++) {
t += arr[0];
result[t][0] = 1;
}
for (int i = 1; i < len; i++) {
for (int j = 0; j <= N; j++) {
result[j][i] = result[j][i - 1];
for (int k = 0, t = 0; k < m[i]; k++) {
t += arr[i];
if(j==t)result[j][i]+=1;
if (j > t) {
result[j][i] += result[j - t][i - 1];
}
}

}
}
}
/**
 * 反向重建动态规划的路径
 * @param result
 * @param arr
 * @param m
 * @param len
 * @param n
 * @param toI
 * @param path
 * @param pathCount
 */
private void recurDisplay(int[][] result, int[] arr, int[] m, int len,
int n, int toI, int[] path, int pathCount) {

if(toI==0){
if(result[n][toI]>0){
path[pathCount]=arr[0];
printfArr(path,pathCount+1);
}
}else{
if(result[n][toI-1]>0){
recurDisplay(result,arr,m,len,n,toI-1,path,pathCount);
}

for (int k = 0, t = 0; k < m[toI]; k++) {
t += arr[toI];
path[pathCount++]=arr[toI];
if (n > t) {
if(result[n-t][toI-1]>0){
recurDisplay(result,arr,m,len,n-t,toI-1,path,pathCount);

}
}else if(n==t){
printfArr(path,pathCount);
}
}
}

} /**
 * 打印数组
 * @param path
 * @param pc
 */
private void printfArr(int[] path, int pc) {
if(pc==0)return;
System.out.print("{");
for(int i=0;i<pc;i++){
System.out.print(path[i]);
if(i<pc-1){
System.out.print(",");
}
}
System.out.println("}");

} /**
 * 计算重复性，把每个元素的重复次数保存到数组m中，并返回不重复的元素个数
 * @param arr
 * @param m
 * @return
 */
private int calcMultiplicy(int[] arr, int[] m) {
int vn = 0;
for (int i = 0, j; i < arr.length; i++) {
for (j = 0; j < vn; j++) {
if (arr[i] == arr[j]) {
m[j]++;
break;
}
}
if (j == vn) {
m[vn] = 1;
arr[vn++] = arr[i];
}
}
return vn;
} /**
 * @param args
 */
public static void main(String[] args) {
int arr[] = new int[] {5, 4,3,2,2,1,1 };
new AliTest().solve(8, arr); }}

Answer 11

计算重复性可选任意一种排序算法，然后再去重复，O（N*log(N)),我没有用排序的，简单一个O(N^2)的算法即可。

Answer 12

回溯法import java.util.LinkedList;public class SetSum {
    int[] a;
    int t;
    
    SetSum(int[] a, int t) { this.a = a; this.t = t; }
    
    void huisu(LinkedList<Integer> list, int i) {
        int sum = 0;
        for(Integer x : list) sum += x;
        if(sum >= t) {
            if(sum==t) System.out.println(list);
            return;
        }
        for(int j=i; j<a.length; j++) {
            list.add(a[j]);
            huisu(list, j+1);
            list.removeLast();
        }
    }
    
    public static void main(String[] args) {
        SetSum s = new SetSum(new int[]{1,1,2,2,3,4}, 4);
        LinkedList<Integer> list = new LinkedList<Integer>();
        s.huisu(list, 0);
    }
}
输出：
[1, 1, 2]
[1, 1, 2]
[1, 3]
[1, 3]
[2, 2]
[4]把重复的去掉就行了

Answer 13

很简单,设f[i][j]表示，前i个数里面，和为j的集合个数，于是有状态转移方程f[i][j] = f[i-1][j] + f[i-1][j-a[i]] 其中a[i]表示第i个数。
其实就是一个背包问题了，还可以在空间上用滚动数组进行优化，时间上用不知道可不可以。唉，基础不扎实啊。

Answer 14

void  FindSetSumT(int t,int a[],int start,int n,int b[],int endPos)
{
if(start>=n)
return;
if(a[start]==t)
{
b[endPos++]=a[start];
for(int i=0;i<endPos;i++)
printf("%6d",b[i]);
printf("\n");
while(a[start+1]==a[start])
{
start++;
}
endPos--;
FindSetSumT(t,a,start+1,n,b,endPos);
}
else if(a[start]<t)
{
b[endPos++]=a[start];
FindSetSumT(t-a[start],a,start+1,n,b,endPos);
while(a[start+1]==a[start])
{
start++;
}
endPos--;
FindSetSumT(t,a,start+1,n,b,endPos);
}
else
{
FindSetSumT(t,a,start+1,n,b,endPos);
}
return;
}int main()
{

        int a[6]={4,3,2,2,1,1};
int t=4;
int b[6];
FindSetSumT(t,a,0,6,b,0);
return 0;
}输出：
     4
     3     1
     2     2
     2     1     1