阿里在线编程题

记录阿里的在线面试题。

数组切片题

题设

对于一个长度为N的整型数组A，数组里所有的数都是正整数，对于两个满足0<=X<=Y<N的整数，A[X], A[X+1]...A[Y]构成A的一个切片，记作(X, Y)。
用三个下标m1, m2, m3下标满足条件0<m1, m2+1<m2, m2+1<m3<N-1。
可以把这个整型数组分成(0, m1-1), (m1+1, m2-1), (m2+1, m3-1), (m3+1, N-1)四个切片。如果这四个切片中的整数求和相等，称作“四等分”。
编写一个函数，求一个给定的整型数组是否可以四等分看，如果可以，返回一个布尔类型的true，如果不可以返回一个布尔类型的false。

限制条件：数组A最多有1,000,000项，数组中的整数取值范围介于-1,000,000到1,000,000之间。
要求：函数的计算复杂度为O(N)，使用额外存储空间（除了输入的数组之外）最多为O(N)。
例子：
对于数组A=[1, 5, 1, 1, 1, 1, 4, 1, 7, 3, 7]存在下标2, 7, 9使得数组分成四个分片[2, 5], [1, 1, 1, 4], [7], [7]，这三个分片内整数之和相等，所以对于这个数组，函数应该返回true。
对于数组A=[10, 2, 11, 13, 1, 1, 1, 1, 1]，找不到能把数组四等分的下标，所以函数应该返回false。

解题过程

很遗憾，当时把题目看错了，因为室友前一天做了，所以以为下表元素是算在求和之内的。直到最后五分钟才意识到，已经晚了。

第一种思路当然是暴力求解，三个for循环，但是这显然是不行的。因为复杂度为O(N^3)。

我这里采用的方法，受到了很多排序算法的启发，步骤如下：

使用三个游标，先初始化游标，初始位置为1，3，5，计算四个子块的和。
然后进入while循环，判断子块和是否相等，如果相等返回true结束。
找出最小和的游标，然后将游标右移一位。
注意，游标移动的时候，可能会影响到后面的游标，因此要做出判断是否移动后续游标，更新其它游标位置和各子块的和。
重复2,3,4步骤，直到第四块和成为了最小块或三号游标到达了倒数第二个位置（底部），返回false结束。

我把这个方法叫做“暴力逻辑求解”，暂时没想到其他方法……

程序如下：

package cn.sjtunix.job;

import java.util.*;

public class sum3 {

/** 请完成下面这个函数，实现题目要求的功能 **/
 /** 当然，你也可以不按照这个模板来作答，完全按照自己的想法来 ^-^  **/
	
	static private int min(int[] a) {
		int N = a.length;
		int p = 0;
		for(int i=0; i<N; i++) {
			if(a[i] < a[p])
				p = i;
		}
		return p;
	}
	
    static boolean resolve(int[] A) {
        int N = A.length;
        if(N < 7) return false;
        // 准备三个游标
        int p1 = 1;
		int p2 = 3;
		int p3 = 5;
		// 存储区段和并初始化
		int[] sum = new int[4];
		sum[0] = A[0];
        sum[1] = A[2];
        sum[2] = A[4];
        sum[3] = 0;
        for(int i=6; i<N; i++)
        	sum[3] += A[i];
		// 核心算法
		while(p3<N-1) {
			if(sum[0]==sum[1] && sum[1]==sum[2] && sum[2]==sum[3]) 
				return true;
			switch(min(sum)) {
				case 0 :
					sum[0] += A[p1];
					sum[1] -= A[p1+1];
					p1++;
					if(p1+1==p2) {
						sum[1] += A[p2];
						sum[2] -= A[p2+1];
						p2++;
					}
					if(p2+1==p3) {
						sum[2] += A[p3];
						sum[3] -= A[p3+1];
						p3++;
					}
					break;
				case 1 :
					sum[1] += A[p2];
					sum[2] -= A[p2+1];
					p2++;
					if(p2+1==p3) {
						sum[2] += A[p3];
						sum[3] -= A[p3+1];
						p3++;
					}
					break;
				case 2 :
					sum[2] += A[p3];
					sum[3] -= A[p3+1];
					p3++;
					break;
				case 3 :
					return false;
			}
		}
		return false;
    }

    public static void main(String[] args){
        ArrayList<Integer> inputs = new ArrayList<Integer>();
        Scanner in = new Scanner(System.in);
        String line = in.nextLine();
        while(line != null && !line.isEmpty()) {
            int value = Integer.parseInt(line.trim());
            if(value == 0) break;
            inputs.add(value);
            line = in.nextLine();
        }
        int[] A = new int[inputs.size()];
        for(int i=0; i<inputs.size(); i++) {
            A[i] = inputs.get(i).intValue();
        }
        Boolean res = resolve(A);

        System.out.println(String.valueOf(res));
    }
}

程序复杂度满足O(N)要求。

阿里在线编程题

目录

数组切片题

题设

解题过程