【华为OD题库-018】AI面板识别-Java

题目

Al识别到面板上有N(1<N≤100)个指示灯，灯大小一样，任意两个之间无重叠。由于AI识别误差，每次识别到的指示灯位置可能有差异，以4个坐标值描述Al识别的指示灯的大小和位置(左上角x1,y1，右下角x2.y2)。请输出先行后列排序的指示灯的编号，排序规则:
每次在尚未排序的灯中挑选最高的灯作为基准灯
找出和基准灯属于同一行所有的灯进行排序。两个灯高低偏差不超过灯半径算同一行(即两个灯坐标的差<=灯高度的一半)。
输入描述
第一行为N，表示灯的个数
接下来N行，每行为1个灯的坐标信息，格式为:编号 x1 y1 x2 y2
1∶编号全局唯一
2:1<编号≤100
3: 0<=x1 < x2 ≤ 1000
4: 0<=y1 < y2 ≤ 1000
输出描述
排序后的编号列表，编号之间以空格分隔
示例1:
输入
5
1 0 0 2 2
2 6 1 8 3
3 3 2 5 4
5 5 4 7 6
4 0 4 2 6
输出
1 2 3 4 5

思路

本题描述比较复杂，不好理解，下面转化为好理解的版本。
先找到基准灯：所有灯中最高的，等高时，取最左边的
找到所有与基准灯为同一行的灯，按照从左到右的顺序排序
继续再剩余未排序的灯中找基准灯，重复上述过程。
在实现思路上，我们已经有灯的左上角及右下角坐标，那么我们可以算出每个灯的中心坐标以及半径，假设以(X，Y)表示中心坐标，以R表示半径。

1. 由于涉及到复杂对象的比较，我们可以新建一个灯对象（Lamp），它有三个属性，X代表中心点横坐标，Y代表中心点的纵坐标，R代表半径。
2. 将每行输入转为一个灯，并放入集合list中
3. 为了寻找基准灯，也就是最高和最左边的灯，可以对Lamp对象自定义比较方法，取Y最小的（Y相等时取X最小的）
4. 对list按照我们自定义规则进行排序（最高最左的在前）
5. 对排序后list的第一个灯，作为基准灯，找到和基准灯在同一行的灯。判断同一行的标准，两个灯纵坐标的差值的绝对值<=灯半径。这个比较方法可以直接写在我们新建的Lamp对象中。
6. 对与基准灯同一行的灯，加入到一个临时集合tmp，然后再对tmp排序，按从左到右排序即可（X越小排在越前）
7. 将本轮排序结果tmp加入最终的ans中
8. 继续寻找下一个基准灯（还未被加入到ans中的里面找最高最左的灯），重复4，5，6，7步骤。

题解

package hwod;import java.util.*;public class AIBoardRecognize {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt();int[][] matrix = new int[n][5];for (int i = 0; i < n; i++) {for (int j = 0; j < 5; j++) {matrix[i][j] = sc.nextInt();}}List<Lamp> res = aIBoardRecognize(matrix);for (int i = 0; i < res.size(); i++) {if (i != 0) System.out.print(" ");System.out.print(res.get(i).getId());}}private static List<Lamp> aIBoardRecognize(int[][] matrix) {int m = matrix.length;List<Lamp> lamps = new ArrayList<>(m);for (int i = 0; i < m; i++) {int id = matrix[i][0];int x = (matrix[i][1] + matrix[i][3]) >> 1;int y = (matrix[i][2] + matrix[i][4]) >> 1;int r = (matrix[i][3] - matrix[i][1]) >> 1;lamps.add(new Lamp(id, x, y, r));}Collections.sort(lamps);List<Lamp> ans = new ArrayList<>(m);int i = 0;while (i < m) {Lamp base = lamps.get(i);List<Lamp> tmp = new ArrayList<>();while (i < m && base.isSameHigh(lamps.get(i))) {tmp.add(lamps.get(i));i++;}Collections.sort(tmp, (o1, o2) -> o1.getX() - o2.getX());ans.addAll(tmp);}return ans;}
}class Lamp implements Comparable<Lamp> {private int id;private int x;private int y;private int r;public Lamp(int id, int x, int y, int r) {this.id = id;this.x = x;this.y = y;this.r = r;}public int getId() {return id;}public int getX() {return x;}public int getY() {return y;}public int getR() {return r;}public boolean isSameHigh(Lamp lamp) {return Math.abs(lamp.getY() - this.getY()) <= this.r;}@Overridepublic int compareTo(Lamp other) {return this.getY() == other.getY() ? this.getX() - other.getX() : this.getY() - other.getY();}
}

为了方便验证，这里再提供三组测试用例

用例1：
5
1 0 0 2 2
2 6 0 8 2
3 3 1 5 3
5 5 1 7 3
4 0 4 7 6
输出： 1 3 5 2 4
用例2：
5
1 0 0 2 2
2 6 0 8 2
3 3 1 5 3
5 5 2 7 4
4 0 4 7 6
输出： 1 3 2 5 4
用例3：
5
1 0 0 2 2
2 6 0 8 2
3 3 1 5 3
5 5 3 7 5
4 0 4 7 6
输出： 1 3 2 4 5