阿里巴巴笔考试题进化版

2013-01-11

阿里巴巴笔试题进化版之前的题目如：已知一个整数数组a，给定一个整数x，判断x是否数组a中某两个数之和http:/

阿里巴巴笔试题进化版
之前的题目如：
已知一个整数数组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 ……

要输出的话可以把这个值以 key 组合方式以 value 存入 map里
不过实现起来还是顶繁琐的
速度可能也不怎么高
而且构造那个链表的时候时间复杂度还是顶高的
[解决办法]
求全解的话就是搜索配合剪枝，没什么太好的方法。求解的个数可以DP。
[解决办法]
变种01背包问题,如果x不太大就用DP
n的值很稀疏,x很大的话就搜索吧.
[解决办法]
递归可以实现，就是效率不高，应该是n*n，而且对于去重复没想到什么好的办法(bitmap?)，就没进行去重，下面是我的递归程序


#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#defineARRAY_LEN10

inta[ARRAY_LEN] = {5, 5, 4, 4, 3, 2, 2, 1, 1, 1};
inttrg = 10;
charoutput_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;
}

热点排行

软件架构设计

阿里巴巴笔考试题进化版