【沉浸式求职学习day46】【华为5.7暑期机试题目讲解】

题目1

一个超大智能汽车测试场有多个充电桩，每个充电桩的位置由其在二维平面上的坐标(x,y)表示。给定一辆智能汽车的当前位置(car_x,car_y)，请设计一个高效的算法，找出给定智能汽车行驶到充电桩行驶距离最近的k个充电桩井输出相关充电桩信息(编号、坐标、行驶距离)，且按行驶距离升序排序(最近行驶距离的排在最前面)，如果存在行驶距离相等的充电桩则按照充电桩的编号从小到大输出。汽车到充电桩的行驶距离的计算方法为 abs(car_x1-car_x2)+ abs(car_y1-car_y2) 注意:abs 表示绝对值。
输入描述
1，第一行是2 个整数kn，空格间隔，第 1 个整数k 表示需要输出到的行驶距离最近的充电桩的数量 (0 <= k <=1000000)，第2个整数n表示充电的总数量(0<n<= 1000000)。
2，第 2 行是长度为 2 的整数数组 car_x，car_y，中间是空格间隔，表示智能汽车的当前位置坐标。
3，第 3 行到第 n + 2 行是编号为 1 到n 的充电桩的位置坐标
注意:坐标数值大小区间为:[-2^32,231-1]
输出描述
一个二维数组，每一行是一个长度为 4的数组: 编号 x y distance ,
编号表示充电桩的编号(介于1到n之间),x和y表示充电的坐标,distance 表示智能汽车到充电桩的行驶距离，从第1行开始往下是按距离从小到大排序的。如果存在行驶距离相等的充电桩则按照充电桩的编号从小到大输出。如果k为0或者 k 大于n ，输出字符串 null 。

示例1：
输入：
3 5
0 0
1 4
5 6
2 3
7 8
3 -1

输出：
5 3 -1 4
1 1 4 5
3 2 3 5

说明：
到汽车行驶距离最近的三个充电桩的编号分别为 5、1、3，充电桩的坐标分别是(3,-1)、(1,4)、(2,3)，到智能汽车坐标(0,0)的行驶距离分别为 4、5、5。距离都为5的充电桩1的编号小于编号3的充电桩，输出结果中编号小的在前。

import java.util.*;
import java.io.*;
public class Main1 {public static void main(String[] args) throws IOException {BufferedReader br = new BufferedReader(new InputStreamReader(System.in));// 第一行：k 和 nString[] firstLine = br.readLine().split(" ");int k = Integer.parseInt(firstLine[0]);int n = Integer.parseInt(firstLine[1]);// 第二行：carX 和 carYString[] secondLine = br.readLine().split(" ");int carX = Integer.parseInt(secondLine[0]);int carY = Integer.parseInt(secondLine[1]);if (k == 0 || k > n) {System.out.println("null");return;}// 最大堆：按距离和编号PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> {if (a[0] != b[0]) return a[0] - b[0];return a[1] - b[1];});for (int i = 1; i <= n; i++) {String[] line = br.readLine().split(" ");int x = Integer.parseInt(line[0]);int y = Integer.parseInt(line[1]);int d = Math.abs(carX - x) + Math.abs(carY - y);heap.offer(new int[]{-d, -i, x, y});if (heap.size() > k) {heap.poll();}}List<int[]> result = new ArrayList<>();while (!heap.isEmpty()) {int[] item = heap.poll();result.add(new int[]{-item[0], -item[1], item[2], item[3]});}result.sort((a, b) -> {if (a[0] != b[0]) return a[0] - b[0];return a[1] - b[1];});for (int[] item : result) {System.out.println(item[1] + " " + item[2] + " " + item[3] + " " + item[0]);}}
}

题目讲解：
第一行输入的是k和n，n就是充电桩的位置，k就是前K个距离汽车位置最近的充电桩的个数。
输出要求是，按照距离最小的排序，然后如果距离小的放在前面，距离相等，按照编号小的放在前面，
首先是处理输入输出，它的输入要求是第一行是k和n，第二行是汽车的位置。
我运用一个最大堆的思想处理：
首先java中的priorityqueue，它是一个优先队列，也是最小堆，送进去一系列的数，它poll得时候是会把最小值先poll出来，但是我们要的反而是最小的几个数，所以我在把距离和编号offer进去得时候加了个符号，这样就转换成最大堆处理。
首先是创建最大堆，然后把这个你控制台读入的距离、编号、x\y坐标offer进最大堆。然后根据我们之前设置的K,poll出来不需要的值。
之后根据sort函数进行一个排序，然后在根据强化for输出我们想要的值。

题目2

有一棵二叉树，每个节点上都住了一户居民。现在要给这棵树上的居民建设基站，每个基站只能覆盖她所在与相邻的节点，请问信号覆盖这棵树最少需要建设多少个基站
输入描述
一个整数数组nums(1 <= num.length <= 3000)，用空格分隔，表示二叉树的节点值，正整数表示存在节点，N表示不存在节点，如[1 2 3 4 N 5 6]表示一颗如下所示的树，最少需要建设2个基站
输出描述
最少需要建设的基站个数
示例1：
输入：
1 2 3 4 N 5 6

输出：
2
说明：

示例2：
输入：
1 2 N 3 N N 4

输出：
2
————————————————
0：当前节点已被覆盖（不需要基站）
1：当前节点需要被覆盖（子节点没有基站）
2：当前节点放置了基站

import java.util.*;public class Solution {static class TreeNode {int val;TreeNode left;TreeNode right;boolean covered;TreeNode(int val) {this.val = val;this.covered = false;}}private int stations = 0;private TreeNode buildTree(String[] nums) {if (nums == null || nums.length == 0 || nums[0].equals("N")) {return null;}TreeNode root = new TreeNode(Integer.parseInt(nums[0]));Queue<TreeNode> queue = new LinkedList<>();queue.offer(root);int i = 1;while (!queue.isEmpty() && i < nums.length) {TreeNode node = queue.poll();if (i < nums.length && !nums[i].equals("N")) {node.left = new TreeNode(Integer.parseInt(nums[i]));queue.offer(node.left);}i++;if (i < nums.length && !nums[i].equals("N")) {node.right = new TreeNode(Integer.parseInt(nums[i]));queue.offer(node.right);}i++;}return root;}private int dfs(TreeNode node) {if (node == null) {return 0;}int leftStatus = dfs(node.left);int rightStatus = dfs(node.right);// 如果子节点需要覆盖，在当前节点放置基站if (leftStatus == 1 || rightStatus == 1) {stations++;node.covered = true;if (node.left != null) node.left.covered = true;if (node.right != null) node.right.covered = true;return 2;}// 如果子节点有基站，当前节点已被覆盖if (leftStatus == 2 || rightStatus == 2) {node.covered = true;return 0;}// 如果当前节点已被覆盖if (node.covered) {return 0;}// 当前节点需要被覆盖return 1;}public int minStationsNeeded(String[] nums) {TreeNode root = buildTree(nums);if (root == null) {return 0;}int finalStatus = dfs(root);if (finalStatus == 1) {stations++;}return stations;}public static void main(String[] args) {Scanner scanner = new Scanner(System.in);String[] nums = scanner.nextLine().trim().split(" ");Solution solution = new Solution();System.out.println(solution.minStationsNeeded(nums));scanner.close();}
}

思路：

1. 写一个关于树的类，这个类包含左子树右子树的索引，以及当前值，还有是否放置基站的状态
2. 层序遍历画树，我需要把给的这个数组转换成树，首先确认几个状态。0：不需要放置基站；1：需要放置基站；2：已经存在基站；放置基站的方式采用队列，队列是先进先出，我先把根节点给它放到队列中吗，然后通过一个while循环，分别给根节点配置左子树和右子树，然后配置好的送进队列，进入下一次循环就会给之前配置的节点进行再配置。最终返回的是root。
3. 后写了一个dfs,深度优先搜索的一个函数，它的作用就是放基站。所以我在函数中就能拿到左子树和右子树的一个状态，如果左或者右为1，那说明它们需要放置基站，返回2；如果左或者右为2，说明返回0；如本身就已经是基站，返回0；其它情况返回1；
4. 还有一个边界情况是需要注意处理的，就是根节点为null的话，直接返回0；如果对根进行一个dfs，然后它返回的最终结果是1的话，也需要增加一个基站。因为我们之前写的那些都是针对于父节点给子节点覆盖基站，那么根节点他没有父节点，但是如果返回1，说明它还是需要被覆盖，这种情况只能让父节点成为基站。
5. 就可以直接输出我们最终的一个station值。