首页 > 阿里笔试记录
头像
myorange
编辑于 2021-08-14 13:14
+ 关注

阿里笔试记录

1题 数组分割成左右两部分,两端和的乘积尽量大,转化为两端和的差值尽量小。因为和为定值,两个数相差越小积越大。高中时学的不等式。不用用double
题意:有个数组arr[0..n-1],从某个位置x将数组分成左右两部分,返回左侧数组和 乘以 右侧数组和 的 积值最大时的切割位置x。例如[1,2,3],可分割为[1,2] [3] 和 [1] [2,3]两种情况。积值分别为9、5
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n];
        for(int i = 0; i < n; ++i) {
            arr[i] = sc.nextInt();
        }
        long[] preSum = new long[n + 1];
        for (int i = 0; i < n; ++i) {
            preSum[i + 1] = preSum[i] + arr[i];
        }  // sum[i..j] = preSum[j+1] - preSum[i]
        long delta = Long.MAX_VALUE;
        int target = 0;
        for (int i = 1; i < n; ++i) {
            long right = preSum[n] - preSum[i];
            long left = preSum[i];
            long tmp = Math.abs(right - left);
            if (tmp < delta) {
                delta = tmp;
                target = i;
            }
        }
        System.out.println(target);
    }

}
2题 不会。暴力打表找规律
[1..n/2 + 1]左边结果为0
当r <= n/2+1时,结果全为0。这样提交只能过3%
题意:前n个自然数1,2,..,n,连续的x个元素一组,剩余的不够x的元素计数加加。x从1取到n,可以得到[1..n]的总剩余计数次数。返回[l,r]的每个元素的总剩余次数。
例如n = 4, x = 1时无剩余数,x=2时无余数,x=3时剩余一个4,x=4时无剩余数。所以[1,4]总剩余次数[0,0,0,1]


全部评论

(8) 回帖
加载中...
话题 回帖

相关热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

近期精华帖

热门推荐