华为OD机试真题 Java 实现【AI面板识别】【2023 B卷 100分】，附详细解题思路

在这里插入图片描述

专栏导读

本专栏收录于《华为OD机试（JAVA）真题（A卷+B卷）》。

刷的越多，抽中的概率越大，每一题都有详细的答题思路、详细的代码注释、样例测试，发现新题目，随时更新，全天CSDN在线答疑。

一、题目描述

AI识别到面板上有N（1 ≤ N ≤ 100）个指示灯，灯大小一样，任意两个之间无重叠。

由于AI识别误差，每次别到的指示灯位置可能有差异，以4个坐标值描述AI识别的指示灯的大小和位置(左上角x1,y1，右下角x2,y2)，

请输出先行后列排序的指示灯的编号，排序规则：

每次在尚未排序的灯中挑选最高的灯作为的基准灯，
找出和基准灯属于同一行所有的灯进行排序。两个灯高低偏差不超过灯半径算同一行（即两个灯坐标的差 ≤ 灯高度的一半）。

二、输入描述

第一行为N，表示灯的个数
接下来N行，每行为1个灯的坐标信息，格式为：编号 x1 y1 2 y2

编号全局唯一
1 ≤ 编号 ≤ 100
0 ≤ x1 < x2 ≤ 1000
0 ≤ y1 < y2 ≤ 1000

三、输出描述

排序后的编号列表，编号之间以空格分隔。

四、解题思路

第一行输入灯的个数N；
接下来的N行输入灯的序号和坐标（左上角x1,y1，右下角x2,y2），比如1 1 1 3 3；
定义一个等的集合，将灯的序号和坐标以Light对象的形式加入其中；
循环灯集合lightList；
- 先行后列，找出未排序最大的灯；
- 找出同一行的灯；
- 按照先行后列进行排序；
输出先行后列排序的指示灯的编号。

五、Java算法源码

package com.guor.od;

import java.util.*;

public class OdTest {
    static List<Light> lightList = new ArrayList<>();

    /**
     * 请输出先行后列排序的指示灯的编号
     *
     * 找出和基准灯属于同一行所有的灯进行排序。
     * 两个灯高低偏差不超过灯半径算同一行
     */
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        // 灯的个数
        int N = Integer.parseInt(sc.nextLine());
        for (int i = 0; i < N; i++) {
            int[] nums = Arrays.stream(sc.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();
            int id = nums[0];
            int x1 = nums[1];
            int y1 = nums[2];
            int x2 = nums[3];
            int y2 = nums[4];
            Light light = new Light(id, x1, y1, x2, y2);
            lightList.add(light);
        }

        while (lightList.size() > 0) {
            Light maxLight = getMaxLight();
            System.out.print(maxLight.id + " ");
            List<Light> sameLineLights = getSameLineLights(maxLight);
            sameLineLights.sort(new Comparator<Light>() {
                @Override
                public int compare(Light l1, Light l2) {
                    if (l1.x1 < l2.x1)
                        return -1;
                    if (l1.x1 > l2.x1)
                        return 1;
                    return 0;
                }
            });
            for (Light l : sameLineLights) {
                System.out.print(l.id + " ");
            }
        }
    }

    // 找出未排序的最大的那个
    public static Light getMaxLight() {
        Light light = null;
        for (Light lt : lightList) {
            if (light == null) {
                light = lt;
            }
            if (lt.y1 < light.y1) {
                light = lt;
            }
            if (lt.y1 == light.y1) {
                if (lt.x1 < light.x1) {
                    light = lt;
                }
            }
        }
        lightList.remove(light);
        return light;
    }
    
    public static List<Light> getSameLineLights(Light light) {
        List<Light> lights = new ArrayList<>();
        for (Light lt : lightList) {
            if (lt.y1 == light.y1 || (light.y1 - lt.y1) >= (light.y1 - light.y2) / 2) {
                lights.add(lt);
            }
        }
        lightList.removeAll(lights);
        return lights;
    }

    static class Light {
        int id, x1, y1, x2, y2;

        public Light(int id, int x1, int y1, int x2, int y2) {
            super();
            this.id = id;
            this.x1 = x1;
            this.y1 = y1;
            this.x2 = x2;
            this.y2 = y2;
        }
    }
}