给定一个数组,求和为定值的所有组合, 这道算法题在leetcode应该算是中等偏下难度, 对三到五年工作经验主要做业务开发的同学来说, 一般较难的也就是这种程度了.
简述经过:
不算hr面,总计四面,第一天前三面, 然后过了一个多星期第四面(领导一般都比较忙~)
平均每一面都是一小时,面完前三面已经很辛苦了.
我之前去美团面试从一面到hr面,总计四面 面了一下午将近四个小时...还不包括来回路程,所以面试是项体力+脑力的活,准备的充分了,面试成功率高少跑几次了~就会轻松不少~大部分同学面试面上几家之后都懒得再跑了.
言归正传,
百度一面没有怎么问技术,主要问了工作内容,一面的面试官可能是负责日志接收相关的工作,问了许多关于日志打点,布码,字段格式,日志测试校验等方面的问题.在之前的工作中都涉及到了,面的不错,而且面试官一点架子没有,面试过程更像一个经验沟通了.
二面应该是个小leader,问了一些java开发必问的基础题:比如: jvm,gc,手写二分查找等.(以后有时间我会详细整理下java基础相关的东西)
三面应该是个大leader,问的问题挺多的,不止是技术上的问题, 算法题问了两道,第一道想不起来了... 第二道是:给定一个数组,求和为定值的所有组合.下文解答. 对了,三面还问了spark相关的问题并且介绍了一下他们组的工作,包括离线数据计算,实时数据计算和数据挖掘等.
三面都已经介绍自己组内的业务了,那肯定是过了,关键看四面了,四面是个经理,(经理思考问题的角度比咱们一般小兵要高~),主要聊了下业务上的东西,和一些遇到的不好解决的问题. 因为都是做数据开发并且都是媒体相关数据所以业务上的共同点还是比较多的,面试者思路较清晰,和经理聊得也不错,最终如愿拿到offer.
给定一个数组,求和为定值的所有组合--思路
这种题首先忽略掉效率最低的穷举法.
给定一个数组arr,求和为定值SUM的所有组合,所有组合并不确定组合里元素的个数,所以可以考虑化繁为简,一步步减少组合的元素个数.递归方式.
例如,去掉第一个元素,求剩下元素中和为SUM-第一个元素的值的所有组合.
剩下的元素中再去掉其中的第一个,求去掉第一个元素的值的所有组合.
依次类推直到剩下元素中的和为0,则之前去掉的元素的组合即为满足条件的一个组合.
java实现代码:
static int[] flag = new int[100];
static int index = 0;// 记录当前
/**
* @param arr 给定的数组
* @param start 开始位置
* @param length 数组长度
* @param sum 给定的值
*/
public static void numGroupAll(int[] arr, int start, int length, int sum) {
if (sum == 0) {
for (int j = 0; j < index; j++) {
System.out.print(flag[j]);
}
System.out.println();
}
else if(sum>0) {
for (int i = start; i < length; i++) {
flag[index++] = arr[i];
//去掉第i个元素,求剩下元素中和为`SUM-第一个元素的值`的所有组合.
SolveProb.numGroupAll(arr, i + 1, length-1, sum - arr[i]);
}
}
index--; //若sum<0 则表示该数不满足条件，需要index--, 因为之前假设该数满足条件 index++找该数下一个数
}
算法改进:
当判断sum - arr[i]是否大于0的时候,如果(sum-arr[i])<0
并且数组中,arr[i+1]及其之后的值都比arr[i]大,(sum-arr[i+1]那么也肯定<0, 就不需要再继续判断了!节省了大量的效率.
所以改进的方法是,在查找之前先排序,判断的时候如果(sum-arr[i])<0就可以停止此次循环了!
改进代码:
public static void numGroup(int[] arr, int start, int length, int sum) {
if (sum == 0) {
for (int j = 0; j < index; j++) {
System.out.print(flag[j]);
}
System.out.println();
}
else if(sum>0) {
for (int i = start; i < length; i++) {
int temp_sum=sum - arr[i];
if(temp_sum>=0)
{
flag[index++] = arr[i];
SolveProb.numGroup(arr, i + 1, length-1, sum - arr[i]);
}
else //****因为后面的数比这个大，若此时temp_sum小于0，则后面的数更不满足条件，不用再进行循环****
break;
}
}
index--;
// System.out.println(index);
}
测试代码,如下图:

在int[] arr = { 1, 3, 2, 4, 5, 6, 7, 8, 9 };这个例子中,改进算中递归的调用次数是不改进之前的三分之一.大大提高了效率.