欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  互联网

Seeker的奇妙求职历险(阿里巴巴笔试)

程序员文章站 2022-07-10 19:18:40
恐龙下蛋给出一个降序数组,每一轮数组中的元素a[i]都会增加i,返回几轮之后数组中会出现相同的元素。输入描述:第一行为一个数字,表示数组的长度,第二行为数组中的元素。输出描述:几轮之后会出现相同的元素,如果不用变化则输出0。-输入:38 4 2输出:2分析,这道题看着比较复杂,想到了还是比较简单的。我一开始直接暴力模拟,只通过了50%,估计后面的超时了。对于数组中的元素a[i]和a[i+1]来说,每次后面一个元素比前面那个元素多增加1,所以经过a[i]-a[i+1]轮之后,两个元...

恐龙下蛋

给出一个降序数组,每一轮数组中的元素a[i]都会增加i,返回几轮之后数组中会出现相同的元素。
输入描述:第一行为一个数字,表示数组的长度,第二行为数组中的元素。
输出描述:几轮之后会出现相同的元素,如果不用变化则输出0。-

输入:

3
8 4 2

输出:

2

分析,这道题看着比较复杂,想到了还是比较简单的。我一开始直接暴力模拟,只通过了50%,估计后面的超时了。
对于数组中的元素a[i]和a[i+1]来说,每次后面一个元素比前面那个元素多增加1,所以经过a[i]-a[i+1]轮之后,两个元素持平,由此可以得出代码:

public static void main(String[] arg){
    Scanner scanner = new Scanner(System.in);
    int n = scanner.nextInt();
    int[] nums = new int[n];
    for(int i=0;i<nums.length;i++){
        nums[i] = scanner.nextInt();
    }
    //因为元素是降序排列的,所以可以断言最大差值为nums[0]
    int min = nums[0];
    for(int i=0;i<n-1;i++){
        min = Math.min(nums[i]-nums[i+1],min);
    }
    System.out.println(min);
}

驿站

n 个客栈依次排列,给出 n - 1 条路的权重。从任意一处出发,每走过一条路,该路的权重减 1,但得到1 点利益。不能走权重为 0 的路。求最大利益。

输入:

5
2 1 4 3

输出

9

说明

考虑满足条件的路径为2-1-2-3-4-5-4-3-4-5

清华大佬的题解:https://www.nowcoder.com/discuss/462000?type=post&order=time&pos=&page=1&channel=1012&source_id=search_post

public static void a02(int n,int[] nums){
    //从第k个客栈出发,在客栈左边获得的利益。
    int[] f_l = new int[n];
    //从第k个客栈出发,在客栈右边获得的利益。
    int[] f_r = new int[n];
    //从第k个客栈出发,并且在k个客栈结束,在客栈左边获得的利益。
    int[] g_l = new int[n];
    //从第k个客栈出发,并在第k个客栈结束,在R_k中获得的最大利益
    int[] g_r = new int[n];
    f_l[0] = 0;
    g_l[0] = 0;
    for(int i=1;i<n;i++){
        if(nums[i-1]%2 == 1){
            f_l[i] = f_l[i-1]+nums[i-1];
            //因为最后要回到出发点,所以只能遍历偶数次
            g_l[i] = g_l[i-1]+nums[i-1]-1;
        }else{
            g_l[i] = g_l[i-1]+nums[i-1];
            f_l[i] = Math.max(f_l[i-1]+nums[i-1]-1, g_l[i]);
        }
    }
    for(int i=n-2;i>=0;i--){
        if(nums[i]%2 == 1){
            f_r[i] = f_r[i+1]+nums[i];
            //因为最后要回到出发点,所以只能遍历偶数次
            g_r[i] = g_r[i+1]+nums[i]-1;
        }else{
            g_r[i] = g_r[i+1]+nums[i];
            f_r[i] = Math.max(f_r[i+1]+nums[i]-1, g_r[i]);
        }
    }
    int max = Integer.MIN_VALUE;
    for(int i=0;i<n;i++){
        max = Math.max(Math.max(f_l[i]+g_r[i],f_r[i]+g_l[i]),max);
    }
    System.out.println(max);
}
public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);
    int n = scanner.nextInt();
    int[] nums = new int[n-1];
    for(int i=0;i<n-1;i++)
        nums[i] = scanner.nextInt();
    a02(n,nums);
}

本文地址:https://blog.csdn.net/qq_33241802/article/details/107662004