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

本文主要是介绍华为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=4if (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();}}}