阿里内推实习生在线编程题

2019-11-06 06:20:24

字体：大中小

来源：转载

供稿：网友

阿里实习生内推在线编程题

考试后对这个题目很感兴趣所以花时间再做了一遍,相信阿里的在线编程题都是随机的.如果各位以后做刚好遇到这个题目..纯属巧合 : )

阿里实习生内推在线编程题题目思路代码疑问吐槽

题目

对于一个长度为N的整形数组A,数组里所有的数都是正数,用三个下标m1,m2,m3(满足条件 0<m1<m1+1<m2<m2+1<m3<N-1)将数组A分成(0,m1-1),(m1+1,m2-1),(m2+1,m3-1),(m3+1,N-1)四个切片;如果这四个切片中的正数求和相等,则为"四等分".编写一个函数,求一个给定的整形数组是否可以四等分,可以返回true,不可以返回false.限制条件: N<= 1000000;要求:空间复杂度最多为O(n);时间复杂度为O(n);例子:[2,5,1,1,1,1,4,1,7,3,7] true[10,2,11,13,1,1,1,1] false

思路

设数组首尾两端指针low和high, 切片1-4的和为sum1~sum4 , low和 high往中间靠拢, 如果有解, 必定在high>low的情况下出现sum1 == sum4 ; 那么此时我们记录下来即将去掉的断点i =low+1和j = low-1; 然后我们同样的方法来得到sum3 == sum4 ,如果刚好, 有可能 low+1 = high-1; 那么判断sum1==sum2就知道是否有解了. 那要没这么刚好,(我们设当前数组的状态为Status). 我们来做一个指针的平移, 将i往low的方向平移,然后sum1 += A[i], sum2-=A[++i], 如果sum1 < sum2 , 继续平移i指针, 如果sum1 > sum2 ,sum2+= A[low++], 直到sum1 == sum2 ; 同样的方法我们将指针j往high的方向平移,处理sum3和sum4, 直到sum3 == sum4; 这样,我们又回到了Status这种情况,如果low<high .直接重复刚刚的平移操作即可,如果相等那么判断sum1 == sum4就知道结果啦.

代码

import java.util.ArrayList;import java.util.Arrays;import java.util.Scanner;/** * @author Jiangjiaze * @version Id: AliExam .java, v 0.1 2017/3/7 22:34 FancyKong */public class AliExam { static boolean resolve(int[] A) { int low = 0; int high = A.length - 1; long sum1 = A[low]; long sum4 = A[high]; while (low != high) //从中间向两边靠拢 if (sum1 == sum4) { break; } else if (sum1 < sum4) { sum1 += A[++low]; } else { sum4 += A[--high]; } int i = low + 1; // 保存被切掉的元素的索引 int j = high - 1; low += 2; // 跳过被切掉的元素 high -= 2; if (low >= high) return false; //同理,从中间向两边靠拢 long sum2 = A[low]; long sum3 = A[high]; while (low != high) { if (sum2 == sum3) { break; } else if (sum2 < sum3) { sum2 += A[++low]; } else { sum3 += A[--high]; } } low++; high--; //如果high还是大于 low , 题目有无解还不知道 while (high > low) { while (high >= low) { //平移指针,sum1+ 而 sum2 -; 比较大小来移动low指针和i指针 sum1 += A[i]; sum2 -= A[++i]; while (sum1 > sum2) { sum2 += A[low++]; } if (sum1 == sum2) break; } while (high >= low) { //同理 sum4 += A[j]; sum3 -= A[--j]; while (sum4 > sum3) { sum3 += A[high--]; } if (sum3 == sum4){ //不能像上面那样直接break,因为不知道sum1和sum4的大小 //加多一层判断,如果sum1小于sum4 break ; 大于的话sum4需要继续加 if(sum1 == sum4 && low == high) return true; if(sum1 < sum4) break; } } } return low == high && sum1 == sum2 && sum1 == sum3; } public static void main(String[] args) { //考试上面的main函数不是我这样的. //单纯为了测试一下而已 mainTest(null); } public static void mainTest(String[] args) { ArrayList<Integer> inputs = new ArrayList<Integer>(); Scanner in = new Scanner(System.in); int n = in.nextInt(); //每小段多少个元素,总共4小段 int random[] = new int[n]; //生成随机数的一小段 for (int i = 0; i < n; i++) { random[i] = (int)(100*Math.random()); } int[] A = new int[4*n+3]; System.arraycopy(random,0,A,0,n); System.arraycopy(random,0,A,n+1,n); System.arraycopy(random,0,A,2*n+2,n); System.arraycopy(random,0,A,3*n+3,n); //下面注释掉的只是做点交换,破除原来数组的中心对称 /*int div = A[n+1]; A[2] -= div; A[n+3] +=div; A[n+1] = A[n]; A[n] = div;*/ System.out.PRintln(Arrays.toString(A)); Boolean res = resolve(A); System.out.println(String.valueOf(res)); }}