华为OD刷题C卷 - 每日刷题 21（按身高和体重排队，解密犯罪时间）

三段代码分别解决了三个不同的算法问题，下面是对它们的概述：

1、（按身高和体重排队）：

这段代码是解决“按身高和体重排队”的问题。它提供了一个Java类Main，其中包含main方法，用于根据学生的身高和体重对学生进行排序，并输出排序后的学生编号。

main方法首先读取学生数量n，然后读取每个学生的身高和体重，存储到HashMap中。接着，使用StringJoiner来构建最终的排序结果字符串。通过流排序，首先按身高升序排序，身高相同的情况下按体重升序排序，体重也相同的情况下按学生编号升序排序。

2、（按身高体重排序 - 优化版）：

这段代码是解决“按身高体重排序”问题的优化版本。它提供了一个Java类Main，其中包含main方法和一个内部类Student，用于对学生进行身高和体重的综合排序。

main方法首先读取学生数量n，然后读取所有学生的身高和体重，创建Student对象数组。接着，使用Arrays.sort对Student数组进行排序，排序规则是：优先按身高升序、身高相同按体重升序、体重也相同的情况下按学生编号升序。

3、（解密犯罪时间）：

这段代码是解决“解密犯罪时间”的问题。它提供了一个Java类Main，其中包含main方法和getResult方法，用于根据给定的时间字符串，找出所有可能的合法时间，并输出距离给定时间最近的下一个时间。

main方法首先读取原始时间字符串，然后调用getResult方法并打印解密后的时间。

getResult方法首先使用HashSet来存储时间字符串中出现过的所有数字，然后使用回溯法进行全排列，生成所有可能的合法时间字符串。使用正则表达式来验证排列结果是否为合法的时间格式。最后，将所有合法时间字符串排序，并找出距离给定时间最近的下一个时间。

三段代码都展示了基本的排序和搜索算法思想：第一段和第二段代码通过自定义排序规则来解决学生的排序问题，其中第二段代码提供了一个更面向对象的解决方案；第三段代码则通过全排列和正则表达式来解决时间解密问题。三者都通过精心设计的逻辑来优化性能和解决问题。

package OD301;

import java.util.*;

/**
 * @description 按身高和体重排队
 * @level 6
 */

/**
 * 题目描述
 * 某学校举行运动会，学生们按编号(1、2、3…n)进行标识，现需要按照身高由低到高排列，对身高相同的人，按体重由轻到重排列；对于身高体重都相同的人，维持原有的编号顺序关系。请输出排列后的学生编号。
 * <p>
 * 输入描述
 * 两个序列，每个序列由n个正整数组成（0 < n <= 100）。第一个序列中的数值代表身高，第二个序列中的数值代表体重。
 * <p>
 * 输出描述
 * 排列结果，每个数值都是原始序列中的学生编号，编号从1开始
 */
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        //学生数量
        int n = sc.nextInt();
        //身高 <学生编号，身高>
        Map<Integer, Integer> height = new HashMap<>();
        for (int i = 0; i < n; i++) {
            height.put(i + 1, sc.nextInt());
        }
        //体重 <学生编号，身高>
        Map<Integer, Integer> weight = new HashMap<>();
        for (int i = 0; i < n; i++) {
            weight.put(i + 1, sc.nextInt());
        }
        //先按身高排序，身高相同按体重，体重相同按编号，结果放进StringJoiner中
        StringJoiner sj = new StringJoiner(" ");
        height.keySet().stream().sorted((o1, o2) -> {
            int h1 = height.get(o1);
            int h2 = height.get(o2);
            int w1 = weight.get(o1);
            int w2 = weight.get(o2);
            if(h1 != h2){
                return h1 - h2;
            } else if (h1 == h2 && w1 != w2) {
                return w1 - w2;
            }else {
                return o1 - o2;
            }
        }).forEach(s -> {
            sj.add(Integer.toString(s));
        });

        //打印结果
        System.out.println(sj.toString());
    }
}




package OD301.better;

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

/**
 * @description 按身高体重排序
 * @level
 * @score
 * @url
 */
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        //学生个数
        int n = Integer.parseInt(sc.nextLine());
        Student[] students = new Student[n];

        //身高
        int[] heights = Arrays.stream(sc.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();

        //体重
        int[] weights = Arrays.stream(sc.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        ;

        for (int i = 0; i < n; i++) {
            //编号从1开始
            students[i] = new Student(i + 1, heights[i], weights[i]);
        }

        //排序：优先身高升序、身高相同按体重升序、都相同按编号升序

        Arrays.sort(students, (s1, s2) -> {
            if (s1.height != s2.height) {
                return s1.height - s2.height;
            }
            if (s1.weight != s2.weight) {
                return s1.weight - s2.weight;
            }
            return s1.id - s2.id;
        });

        //输出
        for (Student student : students) {
            System.out.print(student.id + " ");
        }
    }

    static class Student {
        //学生编号
        int id;
        //身高
        int height;
        //体重
        int weight;

        public Student(int id, int height, int weight) {
            this.id = id;
            this.height = height;
            this.weight = weight;
        }
    }

}

package OD314;

import java.util.*;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

/**
 * @description 解密犯罪时间
 * @level 5
 * @score 100
 */

/**
 * 题目描述
 * 警察在侦破一个案件时，得到了线人给出的可能犯罪时间，形如 “HH:MM” 表示的时刻。
 * <p>
 * 根据警察和线人的约定，为了隐蔽，该时间是修改过的，
 * <p>
 * 解密规则为：利用当前出现过的数字，构造下一个距离当前时间最近的时刻，则该时间为可能的犯罪时间。
 * <p>
 * 每个出现数字都可以被无限次使用。
 * <p>
 * 输入描述
 * 形如HH:SS字符串，表示原始输入。
 * <p>
 * 输出描述
 * 形如HH:SS的字符串，表示推理处理的犯罪时间。
 * <p>
 * 备注
 * 1.可以保证现任给定的字符串一定是合法的。
 * <p>
 * 例如，“01:35”和“11:08”是合法的，“1:35”和“11:8”是不合法的。
 * <p>
 * 2.最近的时刻可能在第二天。
 */
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String[] times = sc.nextLine().split(":");
        String hour = times[0];
        String minute = times[1];
        System.out.println(getResult(hour, minute));

    }

    //返回下一个距离最近的时间
    public static String getResult(String hour, String minute) {
        //存放时间字符，去重
        Set<Character> set = new HashSet<>();
        for (int i = 0; i < hour.length(); i++) {
            set.add(hour.charAt(i));
        }
        for (int i = 0; i < minute.length(); i++) {
            set.add(minute.charAt(i));
        }
        //把字符转为char[]
        Character[] arr = set.toArray(new Character[0]);
        //存放满足时间格式的结果
        ArrayList<String> res = new ArrayList<>();
        //存放当前排列结果
        LinkedList<Character> path = new LinkedList<>();

        dfs(arr, path, res);

        //把满足时间格式的结果升序排列
        res.sort(String::compareTo);
        //找到当前时间 在res里面的下标
        int index = res.indexOf(hour + minute);
        String recentTime = "";
        //如果当前的时间是当前组合的最后一个，则下一个时间是第二天的开头
        if (index == res.size() - 1) {
            recentTime = res.get(0);
        } else {
            recentTime = res.get(index + 1);
        }
        //插入 ：
        recentTime = recentTime.substring(0, 2) + ":" + recentTime.substring(2);
        return recentTime;
    }

    //递归，求当前时间的全排列，每个数字可以无限次使用

    /**
     * 返回当前时间的全排列
     *
     * @param arr  组成当前时间的字符列表
     * @param path 当前的排列
     * @param res  结构的排列
     * @return void
     * @create 2024/3/21 19:24
     */
    public static void dfs(Character[] arr, LinkedList<Character> path, ArrayList<String> res) {
        //返回上一层标志 path.length=4
        if (path.size() == 4) {
            StringBuilder sb = new StringBuilder();
            for (Character c : path) {
                sb.append(c);
            }
            String timeStr = sb.toString();
            //判断该排列是否是合法时间
            Pattern p = Pattern.compile("([01][0-9]|2[0-3])([0-5][0-9])");
            Matcher m = p.matcher(timeStr);
            if (m.find()) {
                res.add(timeStr);
            }
            //返回上一层
            return;
        }

        //全排列
        for (Character c : arr) {
            //第i个字符开头，后面全排列，字符可以重复使用
            path.add(c);
            dfs(arr, path, res);
            //因为数字可以无限次使用，所有开始下一个字符的时候，需要清除上一个
            path.removeLast();
        }


    }

}