阿里巴巴笔考题进化版

阿里巴巴笔试题进化版
之前的题目如：
已知一个整数数组a，给定一个整数x，判断x是否数组a中某两个数之和
http://topic.csdn.net/u/20081031/00/df74da9b-795e-4ce8-b39f-27d8a744b59a.html
啥子先排序，然后查找，或者位图

但昨天的题目变了些，判断是否是数组a中任意几个数的之和
例如：
输入：x = 5；a[10] = {1,1,2,3,4,5}
输出：5 = 5； 5 = 4 + 1； 5 = 3 + 2； 5 = 3 + 1 + 1；
同学说先排序，再递归，求出组合。
各位的意见呢？

[解决办法]
这样的话也只有暴力法了，不知道还有没有好的办法。。
[解决办法]
分支限界吧！！！
[解决办法]
DFS+剪枝！

[解决办法]
先进行排序，再二分查找
[解决办法]
如果只是判断是否有 而不要得出是哪些的话
建个链表
{1,1,2,3,4,5}
 取 1
链表里有 1
 取 1
链表里有 1 2 
 取 2
链表里有 1 2 3 4
...
...
最后本题的链表里有
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
即这些数是可以取数组的某些数得到
[解决办法]
https://docs.google.com/viewer?url=http://crab.rutgers.edu/~guyk/ex/part.pdf
[解决办法]

探讨

要输出所有有可能的组合。。。。 并且要求用最高效的算法实现 我也交白卷了

引用:

如果只是判断是否有 而不要得出是哪些的话
建个链表
{1,1,2,3,4,5}
取 1
链表里有 1
取 1
链表里有 1 2
取 2
链表里有 1 2 3 4
...
...
最后本题的链表里有
1 2 3 4 5 6 7 8 9 10 11 ……

[解决办法]
求全解的话就是搜索配合剪枝，没什么太好的方法。求解的个数可以DP。
[解决办法]
变种01背包问题,如果x不太大就用DP
n的值很稀疏,x很大的话就搜索吧.
[解决办法]
递归可以实现，就是效率不高，应该是n*n，而且对于去重复没想到什么好的办法(bitmap?)，就没进行去重，下面是我的递归程序

C/C++ code

#include <stdio.h>#include <stdlib.h>#include <string.h>#define        ARRAY_LEN            10int            a[ARRAY_LEN] = {5, 5, 4, 4, 3, 2, 2, 1, 1, 1};int            trg = 10;char        output_flag[ARRAY_LEN];/**<p>按控制位进行输出</p>*/void my_output(){    int         i;    for (i = 0; i < ARRAY_LEN; i++)    {        if (output_flag[i] == 1)        {            printf("%d\t", a[i]);        }    }    printf("\n");}/**<p>flag标志置位，n=1时判断结果是否匹配</p>*/void get_sum_recursive_low(int *a, int n, int trg, int out, int flag){    output_flag[ARRAY_LEN -n -1] = flag;        if (n == 1)    {        /**<p>只有如下两种情况才进行输出</p>*/        if (trg == 0)        {            output_flag[ARRAY_LEN -1] = 0;            my_output();        }        else if (trg == a[0])        {            output_flag[ARRAY_LEN -1] = 1;            my_output();        }    }    else    {        get_sum_recursive_low(a +1, n-1, trg-a[0], a[0], 1);        get_sum_recursive_low(a +1, n-1, trg, a[0], 0);    }}/**<p> 递归获取结果，对数组中的每个值，只有两种情况，取舍</p>*/void get_sum_recursive(int *a, int n, int trg){        get_sum_recursive_low(a+1, n-1, trg - a[0], a[0], 1);        get_sum_recursive_low(a+1, n-1, trg, a[0], 0);}int main(void){    get_sum_recursive(a, ARRAY_LEN, trg);    return 0;} 

 

查看更多 下一篇