360公司 2021.09.25 算法岗笔试题

1、流水潺潺

题目描述

最近，小七发现了一处干涸的河道。

河道不同的位置高度也不相同，从河道起点到终点有n个位置，这些位置编号为1~n。每一个位置i的高度可以表示为hi(1、n是河道的两端，因此1左边、n右边的高度可以视为无穷大)。

本着环保的精神，小七希望在恰好一个位置注入水源，使得这个位置是有水的。自然地，水会从高处向低处流动，但原来的位置仍然有水。具体地来说，如果当前一个位置i是有水的，并且有某一个相邻的格子j高度严格小于i(hj < hi)，那么j也会成为有水的，并且i仍然是有水的。对于j相邻的格子也是如此。

现在小七想知道，通过一次注入水源最多可以使得多少个位置变成有水的。

输入描述
第一行一个正整数n(1<=n<=5000)，表示河道有n个位置
第二行n个正整数，第i个表示位置i的高度hi(0<=hi<=1000000000)

分析设计

这道题实际上就是要我们求在哪一个下标处注水会使该下标周围的递减序列最长。类似于雨水问题。
所以，通过从左向右的前缀和计算当前下标处前边连续递减的序列长度，然后通过从右向左的前缀和计算当前下标处后边连续递减的序列长度，然后遍历各个下标，计算最长的长度（长度=左边长度+右边长度-重复计算的自身的长度1）。

代码实现

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        sc.nextLine();
        String[] s = sc.nextLine().split(" ");
        int[] h = new int[n];
        for(int i = 0; i < n; ++i){
            h[i] = Integer.parseInt(s[i]);
        }
        int[] left = new int[n];
        left[0] = 1;
        for(int i = 1; i < n; ++i){
            if(h[i] > h[i - 1]){
                left[i] = left[i - 1] + 1;
            }
            else{
                left[i] = 1;
            }
        }
        int[] right = new int[n];
        right[n - 1] = 1;
        for(int i = n - 2; i >= 0; --i){
            if(h[i] > h[i + 1]){
                right[i] = right[i + 1] + 1;
            }
            else{
                right[i] = 1;
            }
        }
        int maxCnt = 1;
        for(int i = 0; i < n; ++i){
            maxCnt = Math.max(maxCnt, left[i] + right[i] - 1);
        }
        System.out.println(maxCnt);
    }
}

2、Yeah数列

题目描述

若数列a1…an，对于任意1<i<n的位置满足：a[i+1]>a[i]或a[i-1]>a[i] ，那么称这个数列为yeah数列。（通俗的理解，yeah数列除两端外，对于任意一个位置，左右两边至少有一个比他大）。

比如4 1 8 或 1 2 3或 8 6 4 2就是yeah数列，而1 1 1和0 1 0就不是yeah数列

现在有一个数列b1…bn，每次操作你可以选择一个i，使得bi减1(操作过程中允许bi减为负数)，问最少经过多少次操作，可以使得bi变为一个yeah数列

输入描述
输入第一行包含一个正整数n（3<=n<=100000），表示数列b的长度
输入第二行包含n个空格隔开的整数，第i个整数表示bi(0<=bi<=1000000000)

输出描述
输出一行一个整数，表示最小操作次数。

分析设计

这道题和之前网易的一道圆桌分纸题很相似，这题不需要考虑环的存在。

由于需要考虑b[i] < b[i - 1]，这就需要从左向右遍历数组b，同时维护一个临时数组left，如果当前b[i] >= left[i - 1]，则需要使b[i]变为比left[i - 1]还要小1的值，所以left[i] = left[i - 1] - 1；如果当前b[i] < left[i - 1]，则b[i]不需要改变，所以left[i] = b[i]。

还需要考虑b[i] < b[i + 1]，这就需要从右向左遍历数组b，同时维护一个临时数组right，如果当前b[i] >= right[i + 1]，则需要使b[i]变为比right[i + 1]还要小1的值，所以right[i] = right[i + 1] - 1；如果当前b[i] < right[i + 1]，则b[i]不需要改变，所以right[i] = b[i]。

如此一来，我们得到了从左向右满足条件的数组left和从右向左满足条件的数组right，这两个数组中的各个元素都比原数组b的相应下标元素值要小，为了使我们所求的操作数最小，我们会选择满足条件的元素的最大值（这样，也就是满足条件的值越接近原值b[i]），所以定义数组ans[]用来表示最终我们所取的元素值， ans[i] = Math.max(left[i], right[i])。

操作次数就是从b[i]变为ans[i]的差值，cnt = ∑(b[i] - ans[i])。

PS：这里有个小彩蛋，就是因为bi(0<=bi<=1000000000)，所以如果cnt定义为int类型是有可能越界的，所以要使用long类型。我就是一开始用的int，结果只通过了36%，改成long之后就全通过了。

代码实现

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        sc.nextLine();
        String[] s = sc.nextLine().split(" ");
        int[] b = new int[n];
        for(int i = 0; i < n; ++i){
            b[i] = Integer.parseInt(s[i]);
        }
        int[] left = new int[n];
        left[0] = b[0];
        for(int i = 1; i < n; ++i){
            if(b[i] < left[i - 1]){
                left[i] = b[i];
            }
            else{
                left[i] = left[i - 1] - 1;
            }
        }
        int[] right = new int[n];
        right[n - 1] = b[n - 1];
        for(int i = n - 2; i >= 0; --i){
            if(b[i] < right[i + 1]){
                right[i] = b[i];
            }
            else{
                right[i] = right[i + 1] - 1;
            }
        }
        int[] ans = new int[n];
        for(int i = 0; i < n; ++i){
            ans[i] = Math.max(left[i], right[i]);
        }
        long cnt = 0;
        for(int i = 0; i < n; ++i){
            cnt += b[i] - ans[i];
        }
        System.out.println(cnt);
    }
}