荣耀 8.10 笔试一二题参考题解

第一题报文转换题解

通过用例100%

import java.util.ArrayList;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String str = sc.nextLine().trim();
        String[] arr = str.split(" ");
        int n = arr.length;
        ArrayList list = new ArrayList();
        for (int i = 1; i < n; i++) {
            if (arr[i].equals("A") || arr[i].equals("a")) {
                list.add("12");
                list.add("34");
            } else if (arr[i].equals("B") || arr[i].equals("b")) {
                list.add("AB");
                list.add("CD");
            } else {
                list.add(arr[i].toUpperCase());
            }
        }
        StringBuilder sb = new StringBuilder();
        // 此处要转16进制，且16进制要大写
        // 只通过20%用例的话，可能这里出问题了
        System.out.print(Integer.toHexString(list.size() + 1).toUpperCase());
        for (int i = 0; i < list.size(); i++) {
            System.out.print(" ");
            System.out.print(list.get(i));
        }
        System.out.println();
    }
}

第二题会议室题解

通过用例100%

先排序，再动态规划

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

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int t = in.nextInt();
        while (t-- > 0) {
            int n = in.nextInt();
            int[][] times = new int[n][2];
            for (int i = 0; i < n; i++) {
                times[i][0] = in.nextInt();
                times[i][1] = in.nextInt();
            }
            System.out.println(solution(times));
        }
    }
    static int solution(int[][] nums) {
        Arrays.sort(nums, Comparator.comparingInt(o -> o[0]));
        int[] dp = new int[24];
        for (int[] meeting : nums) {
            int start = meeting[0], end = meeting[1];
            for (int i = 23; i >= end; --i) {
                dp[i] = Math.max(dp[start] + end - start, dp[i]);
            }
        }
        return dp[23];
    }
}

第二题解法2：

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

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int t = in.nextInt();
        while (t-- > 0) {
            int n = in.nextInt();
            int[][] times = new int[n][2];
            for (int i = 0; i < n; i++) {
                times[i][0] = in.nextInt();
                times[i][1] = in.nextInt();
            }
            System.out.println(solution(times));
        }
    }

    static int solution(int[][] times) {
        Arrays.sort(times, Comparator.comparingInt(o -> o[1]));
        // System.out.println(Arrays.deepToString(times));
        int n = times.length;
        int[] prev = new int[n];
        Arrays.fill(prev, -1);
        // prev数组 维护的是 第i个区间前面与之不相交的最近的区间的下标
        for (int i = n - 1; i >= 1; i--) {
            int start = times[i][0];
            for (int j = i - 1; j >= 0; j--) {
                if (times[j][1] <= start) {
                    prev[i] = j;
                    break;
                }
            }
        }

        System.out.println(Arrays.toString(prev));
        int[] opt = new int[n];
        for (int i = 0; i < n; i++) {
            int start = times[i][0], end = times[i][1];
            // 当前区间 选 或 不选 两种情况，取最大值
            opt[i] = Math.max(end - start + getOPT(opt, prev[i]), getOPT(opt, i - 1));
        }

        return opt[n - 1];
    }

    static int getOPT(int[] opt, int idx) {
        if (idx == -1) return 0;
        return opt[idx];
    }
}

解法2的参考学习资料在这里