阿里內(nèi)推實(shí)習(xí)生在線編程題

2019-11-06 06:20:24

字體：大中小

供稿：網(wǎng)友

阿里實(shí)習(xí)生內(nèi)推在線編程題

考試后對(duì)這個(gè)題目很感興趣所以花時(shí)間再做了一遍,相信阿里的在線編程題都是隨機(jī)的.如果各位以后做剛好遇到這個(gè)題目..純屬巧合 : )

阿里實(shí)習(xí)生內(nèi)推在線編程題題目思路代碼疑問(wèn)吐槽

題目

對(duì)于一個(gè)長(zhǎng)度為N的整形數(shù)組A,數(shù)組里所有的數(shù)都是正數(shù),用三個(gè)下標(biāo)m1,m2,m3(滿足條件 0<m1<m1+1<m2<m2+1<m3<N-1)將數(shù)組A分成(0,m1-1),(m1+1,m2-1),(m2+1,m3-1),(m3+1,N-1)四個(gè)切片;如果這四個(gè)切片中的正數(shù)求和相等,則為"四等分".編寫一個(gè)函數(shù),求一個(gè)給定的整形數(shù)組是否可以四等分,可以返回true,不可以返回false.限制條件: N<= 1000000;要求:空間復(fù)雜度最多為O(n);時(shí)間復(fù)雜度為O(n);例子:[2,5,1,1,1,1,4,1,7,3,7] true[10,2,11,13,1,1,1,1] false

思路

設(shè)數(shù)組首尾兩端指針low和high, 切片1-4的和為sum1~sum4 , low和 high往中間靠攏, 如果有解, 必定在high>low的情況下出現(xiàn)sum1 == sum4 ; 那么此時(shí)我們記錄下來(lái)即將去掉的斷點(diǎn)i =low+1和j = low-1; 然后我們同樣的方法來(lái)得到sum3 == sum4 ,如果剛好, 有可能 low+1 = high-1; 那么判斷sum1==sum2就知道是否有解了. 那要沒這么剛好,(我們?cè)O(shè)當(dāng)前數(shù)組的狀態(tài)為Status). 我們來(lái)做一個(gè)指針的平移, 將i往low的方向平移,然后sum1 += A[i], sum2-=A[++i], 如果sum1 < sum2 , 繼續(xù)平移i指針, 如果sum1 > sum2 ,sum2+= A[low++], 直到sum1 == sum2 ; 同樣的方法我們將指針j往high的方向平移,處理sum3和sum4, 直到sum3 == sum4; 這樣,我們又回到了Status這種情況,如果low<high .直接重復(fù)剛剛的平移操作即可,如果相等那么判斷sum1 == sum4就知道結(jié)果啦.

代碼

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; // 跳過(guò)被切掉的元素 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 , 題目有無(wú)解還不知道 while (high > low) { while (high >= low) { //平移指針,sum1+ 而 sum2 -; 比較大小來(lái)移動(dòng)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,因?yàn)椴恢纒um1和sum4的大小 //加多一層判斷,如果sum1小于sum4 break ; 大于的話sum4需要繼續(xù)加 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函數(shù)不是我這樣的. //單純?yōu)榱藴y(cè)試一下而已 mainTest(null); } public static void mainTest(String[] args) { ArrayList<Integer> inputs = new ArrayList<Integer>(); Scanner in = new Scanner(System.in); int n = in.nextInt(); //每小段多少個(gè)元素,總共4小段 int random[] = new int[n]; //生成隨機(jī)數(shù)的一小段 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); //下面注釋掉的只是做點(diǎn)交換,破除原來(lái)數(shù)組的中心對(duì)稱 /*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)); }}