阿里巴巴集团2017暑期实习生在线编程测试题分析-Java研发工程师

问题描述

题目：一个整型数组，将其划分为和相同的4个切片，例如：{ 2, 3, 5, 1, 2, 2, 1, 1, 3 }，切片操作后划分为：{2,3}，{5}，{1,2,2}，{1,1,3}，也就找到所谓的四等分点。只不过输出结果为true或者false（是否能得到这样的4个切片）。同时要求时间复杂度和空间复杂度为o(n)。

编程实现

下面是本人的两种种实现方法：
第一种方法（推荐，可靠）

    static boolean resolve(int[] A) {// 第一步，对数组进行求和int sum = 0;for (int i : A) {sum = sum + i;}// 确定是否可以化为4个切片int sliceSum = sum / 4;if (sliceSum * 4 != sum) {return false;}// 用于保存每个切片的结束索引int[] sliceIndex = new int[4];int sliceCount = 0;int tmpSum = 0;for (int i = 0; i < A.length; i++) {tmpSum = tmpSum + A[i];if (tmpSum == sliceSum) {sliceIndex[sliceCount] = i;sliceCount++;tmpSum = 0;}}if (sliceIndex[3] == A.length - 1) {return true;}return false;}

第二种方法（有些情况下不可靠）

    static boolean resolve(int[] A) {int slice1Index = 0;int slice2Index = A.length - 1;int slice3Index = 0;int slice1Sum = A[slice1Index];int tmpSum = A[slice2Index];// 先从两端获取和相等的两个切片while (slice1Sum != tmpSum) {if (slice1Sum < tmpSum) {slice1Index++;slice1Sum = slice1Sum + A[slice1Index];} else {slice2Index--;tmpSum = tmpSum + A[slice2Index];}// 如果不满足这个就已经无法得到4个切片这个基本的要求if (slice2Index - slice1Index < 3) {return false;}}tmpSum=0;// 如果两端存在和相等的切片,看是否能得到四个和相等的切片for (int i = slice1Index + 1; i < slice2Index - 1; i++) {tmpSum = tmpSum + A[i];slice3Index = i;if (tmpSum == slice1Sum) {break;}}//是否得到和相同的第三个切片if (tmpSum != slice1Sum) {return false;}tmpSum=0;for (int i = slice3Index + 1; i < slice2Index; i++) {tmpSum = tmpSum + A[i];}if (tmpSum == slice1Sum) {return true;}return false;}

楼主太渣，在线测试的时候，心里太着急，虽然也是现在这个思路，但是好多细节东西出现了错误，导致在线测试运行检测没有通过，所以时间到了无奈提交结束之后，楼主就立马理清了一下思绪，认真修改了一下细节，使得它能够正常运行并且结果也是对的，供广大同届找工作的童靴参考！

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！