9月6日字节教育笔试

前言

2020年9月6日上午10点-12点的笔试。

第一题

跳楼梯问题，不能连续跳两级。

如果只是跳楼梯那是很简单的，这里加了一个限制条件，不能连续跳2级的。

那么假设目前要跳7级的有多少种，那么所有跳6级的肯定可以，因为6级跳到7级只需要跳一级，必然是满足的。而5级不能直接加上去，因为5级跳到7级的是直接跳2级的，所以我们要多想一步，就是直接选4级的。

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        sc.close();
        if (n == 0) {
            System.out.println(0);
            return;
        }
        if (n == 1) {
            System.out.println(1);
            return;
        }
        if(n == 2){
            System.out.println(2);
            return;
        }
        long[] dp = new long[n+1];
        dp[0] = 1;
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 3;
        for (int i = 4; i < n+1; i++) {
            dp[i] = dp[i - 1] + dp[i - 3];
        }
        System.out.println(dp[n]);
    }
}

这里注意dp要用Long数组，否则会溢出。

第二题

给定一个数组，对于其中的每个数字，找到这个数字左边的比它大，且离他最近的一个数；同样找到一个在它右边，且比它大的数字，如果不存在则为0，求出这两个数字相乘，最大的那个。

最简单的就是暴力，对于每个数字，我都从该数字开始往两边找，但是这样时间复杂度是O(N²)。

然后稍微想想就知道可以利用单调栈来完成：

public static int[] findMaxRight(int[] array) {
    if (array == null) {
        return array;
    }
    int size = array.length;
    int[] result = new int[size];
    Stack<Integer> stack = new Stack<>();
    stack.push(0);
    int index = 1;
    while (index < size) {
        if (!stack.isEmpty() && array[index] > array[stack.peek()]) {
            result[stack.pop()] = index + 1;
        } else {
            stack.push(index);
            index++;
        }
    }
    if (!stack.isEmpty()) {
        result[stack.pop()] = 0;
    }
    return result;
}

但是这题我用了单调栈，理论上时间已经是O(n)了，不知道为什么还是只过了63%，迷。

第三题

给定一个长度为N的数组，和一个重复的数字M，意味着这个数组重复了M次，那么求出这个大数组中最大的子序列和。

最大子序列和很简单：

public static long maxSubSequence(long[] array) {
    long length = array.length;
    long res = 0;
    long temp = 0;
    for (long i = 0; i < length; i++) {
        temp += array[(int) i];
        if (temp > res) {
            res = temp;
        } else if (temp < 0) {
            temp = 0;
        }
    }
    return res;
}

要让数组重复M次也简单，但是显然这题如果你真这么做了，肯定只能通过一些数据。

其实只需要考虑三种情况，就可以推导出所有的情况了。

第一种，只有数组本身，那很简单，直接撸就完事了。

第二种，数组重复了一次，那么可能因为拼接的那部分，而导致结果发生变化。

第三种，数组重复了两次，此时我们已经可以能够得到每拼接一次数组，会让答案变大还是变小，根据这个就可以计算了。

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int M = sc.nextInt();
        long[] array = new long[N];
        for (int i = 0; i < N; i++) {
            array[i] = sc.nextInt();
        }
        sc.close();

        // 特殊情况判断，如果数组中每个数字都是负数，那么选择这些负数中最大的那个
        long minus = 0;
        long bigest = array[0];
        for (int i = 0; i < N; i++) {
            if (array[i] < 0) {
                minus++;
            }
            bigest = Math.max(bigest, array[i]);
        }
        if (minus == N) {
            System.out.println(bigest);
            return;
        }

        long oneSum = maxSubSequence(array);

        if (M == 1) {
            System.out.println(oneSum);
            return;
        }

        // 计算出两个的最大
        long[] array2 = new long[2 * N];
        for (int i = 0; i < N; i++) {
            array2[i] = array[i];
            array2[i + N] = array[i];
        }
        long twoMax = maxSubSequence(array2);

        // 计算出三个的最大
        long[] array3 = new long[3 * N];
        for (int i = 0; i < N; i++) {
            array3[i] = array[i];
            array3[i + N] = array[i];
            array3[i + N + N] = array[i];
        }
        long threeMax = maxSubSequence(array3);

        if (M == 2) {
            System.out.println(twoMax);
            return;
        }
        if (M == 3) {
            System.out.println(threeMax);
            return;
        }
        if (M > 3) {
            long sub = threeMax - twoMax;
            if (sub > 0) {
                System.out.println(twoMax + (M - 2) * sub);
            } else {
                long max = Math.max(oneSum, twoMax);
                max = Math.max(max, threeMax);
                System.out.println(max);
            }
        }
    }

    public static long maxSubSequence(long[] array) {

        long length = array.length;
        long res = 0;
        long temp = 0;
        for (long i = 0; i < length; i++) {
            temp += array[(int) i];
            if (temp > res) {
                res = temp;
            } else if (temp < 0) {
                temp = 0;
            }
        }
        return res;
    }
}

第四题

完全不会做。