荣耀笔试机试 20220825 通用软开

2小时3题，共600分，感觉方法都有点绕2333不过都通过了

第一题大小端字节流解析

思路：模拟

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int k = 0;
        in.nextLine();
        String[] res = new String[n];
        String line = in.nextLine();
        char[] sc = line.toCharArray();
        int mode = sc[0] - '0';
        int st = 0;
        for (int i=0; i<=sc.length; ++i) {
            if (i == sc.length || i%9==0 && i != 0) {
                // st+1 .. i!
                String sub = new String(sc, st+1, i - st - 1);
                res[k++] = mode == 1 ? sub : new StringBuilder(sub).reverse().toString();
                if (i < sc.length) mode = sc[i] - '0';
                st = i;
            }
        }

        System.out.println(String.join(" ", res));

    }
}

第二题视频会议使用时长最大化

思路：DP，dp[i] 表示 8..i 区间内所有安排方案中，占用会议室时长的最大值。

import java.util.*;
public class Main {
    static int func(int[][] arr) {
        int n = arr.length;
        // 8 .. 23
        int[] dp = new int[24];
        for (int i=8; i<=23; ++i) {
            int max = 0;
            for (int j=n-1; j>=0; --j) {
                if (arr[j][1] <= i) {
                    int t = arr[j][1] - arr[j][0] + dp[arr[j][0]];
                    max = Math.max(max, t);
                }
            }
            dp[i] = max;
        }
        return dp[23];

    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        // 8..23
        int T = sc.nextInt();
        for (int _i=0; _i<T; ++_i) {
            int n = sc.nextInt();
            int[][] arr = new int[n][];
            for (int i=0; i<n; ++i) {
                arr[i] = new int[] {sc.nextInt(), sc.nextInt()};
            }
            int res = func(arr);
            System.out.println(res);
        }
    }
}

第三题仓库出租公司

思路：二分+DP，二分仓库容量k，然后用DP判断k是否可以满足条件。dp[i][j] 表示前 i 个数中是否存在和为 j 的组合，在遍历最后一层判断即可。

import java.util.*;
import java.io.*;
public class Main {

    static boolean chk(int k, int[] arr, int sum) {
        int n = arr.length;
        boolean[][] dp = new boolean[n+1][k+1]; // 前i个数中存在和为 j 的组合
        for (int i=0; i<=n; ++i) dp[i][0] = true;
        for (int i=1; i<=n; ++i) {
            for (int j=1; j<=k; ++j) {
                boolean t = dp[i-1][j];
                if (j-arr[i-1] >= 0) t = (t || dp[i-1][j-arr[i-1]]);
                dp[i][j] = t;
                if (t && j <= k && sum - j <=k) return true;
            }
        }
        return false;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n];
        int sum = 0;
        for (int i=0; i<n; ++i) {
            arr[i] = sc.nextInt();
            sum += arr[i];
        }
        int l = sum / 2, r = sum;
        while (l < r) {
            int mi = l + (r - l) / 2;
            if (chk(mi, arr, sum)) r = mi;
            else l = mi + 1;
        }

        System.out.println(l);
    }
}

#2023一起秋招吧#