2021-03-04 携程实习笔试算法题记录

携程实习笔试算法题记录

总共2道算法题120分钟

第一题

表达式求值这一类问题一直没有去做，知道要用Stack去做但是不会。。。后续需要加强补。

第二题

因为分割的数组是由连续子数组组成，所以可以用dfs来遍历所有情况

private static int res = Integer.MIN_VALUE;
static int maxAmount(int[] packets, int n) {
	dfs(packets,n,0,0,Integer.MAX_VALUE);
	return res;
}

private static void dfs(int[] packets, int n, int curIndex, int curSum, int curMin){
	// 如果不够分则直接返回
	if(packets.length-curIndex<n) return;
	if(n==0){
		for(int i = curIndex ; i < packets.length ; i++) curSum+=packets[i];
		curMin = Math.min(curMin,curSum);
		res = Math.max(curMin,res);
		return;
	}
	int nextIndex = curIndex+1;
	// 把红包纳入前一个红包
	int ccurSum = curSum+packets[curIndex];
	dfs(packets,n,nextIndex,ccurSum,curMin);
	// 开辟新的红包
	if(curSum!=0) {
		curMin = Math.min(curMin,curSum);
		n--;
	}
	curSum = packets[curIndex];
	dfs(packets,n,nextIndex,curSum,curMin);
}

过了两个测试用例
[1,2,3,4,5,6,7,8,9]
5
和
[1,2]
1