250309阿里云后端暑期实习笔试Java题解

考试的时候做的很烂，后来学习了下解法，分享给大家。简单自测了下，不保证对

第1题-小苯排列数组

排列子序列的长度之和

排列子序列是指从1开始数的子序列，例如1，2，3

[1, 1, 2]的排列子序列包括[1], [1], [1, 2], [1, 2]，所以长度之和为6

[1, 3, 4]的排列子序列只有[1]

import java.util.*;
public class Main {
    public static void main(String[] args) throws InterruptedException {
        Scanner in = new Scanner(System.in);
        int T = in.nextInt();
        int MOD = (int)1e9+7;
        while (T-- > 0) {  // 特殊子序列dp
            int n = in.nextInt();
            int[] nums = new int[n];
            for (int i = 0; i < n; i++) {
                nums[i] = in.nextInt();
            }
            // f[i]: 以i结尾的排列个数
            long[] f = new long[(int)1e5+1];
            f[0] = 1;
            for (int x : nums) {
                f[x] = (f[x] + f[x-1]) % MOD;
            }
            long res = 0;
            for (int i = 0; i < f.length; i++) {
                res = (res + f[i] * i) % MOD;
            }
            System.out.println(res);
        }
    }
}

第2题-小红的好串

小红认为一个字符串是好字符串当且仅当这个字符串去重后按照相对顺序排列在字典序上是一个单调递增字符串。

例如: abcaa去重后为abc，满足字典序单调递增。

现在小红有一个长度为的字符串，请你帮助她计算有多少个非空子串是好字符串。

去重:每种字符只保留第一个出现的位置。

子串:子串是指一个字符串中的连续部分。

import java.util.*;
public class Main {
    public static void main(String[] args) throws InterruptedException {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        String s = in.next();
        char[] cs = s.toCharArray();
        int res = 0;
        int[] map = new int[26];  // 记录每个字母最后一次出现的位置
        Arrays.fill(map, -1);
        for (int left = n-1; left >= 0; left--) {
            int idx = cs[left]-'a';
            map[idx] = left;
            int min = n;  // 记录倒序遍历字母时，最后出现位置的最小值
            int right = n;  // 记录满足条件的窗口的右边界
            for (int c = 25; c >= 0; c--) {
                if (map[c] == -1) continue;
                if (min < map[c]) {  // 之前出现的更大字母的最后出现位置，比当前字母最后出现位置小，说明没有按照字典序，所以缩小右边界，刚好到不取当前字母的位置
                    right = Math.min(right, map[c]);
                }
                min = Math.min(min, map[c]);
            }
            res += right - left;
        }
        System.out.println(res);
    }
}

第3题-数组交换

给定三个长度为n的数组a,b,c，最多可以进行一次操作，交换数组中的两个数字的位置。定义s=(b1-a1)*c1 + ... + (bn-an)*cn，求最多一次操作后s的最大值是多少?

import java.util.*;
public class Main {
    public static void main(String[] args) throws InterruptedException {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] a = new int[n], b = new int[n], c = new int[n];
        for (int i = 0; i < n; i++) a[i] = in.nextInt();
        for (int i = 0; i < n; i++) b[i] = in.nextInt();
        for (int i = 0; i < n; i++) c[i] = in.nextInt();
        long res = 0;
        for (int i = 0; i < n; i++) {  // 计算不交换元素的结果
            res += (b[i]-a[i]) * c[i];
        }
        int maxDiff = -(int)1e9;  // 交换元素产生增益的最大值
        // a[i]*c[i] + a[j]*c[j] - a[i]*c[j] - a[j]*c[i]
        // a[i]*(c[i]-c[j]) + a[j]*(c[j]-c[i]) = (a[j]-a[i])*(c[j]-c[i])
        int MX = (int)1e3;
        int[] min = new int[MX+1], max = new int[MX+1];  // 按c[i]分组，记录每组中a[i]的最大值和最小值
        Arrays.fill(min, 1000);
        for (int i = 0; i < n; i++) {
            min[c[i]] = Math.min(min[c[i]], a[i]);
            max[c[i]] = Math.max(max[c[i]], a[i]);
        }
        for (int ci = 1; ci <= MX; ci++) {  // 遍历c数组的两个元素的可能取值，计算最大增益
            for (int cj = ci+1; cj <= MX; cj++) {
                maxDiff = Math.max(maxDiff, (max[cj]-min[ci])*(cj-ci));
            }
        }
        System.out.println(res + maxDiff);
    }
}