Leetcode刷题 2021.01.19
Leetcode刷题 2021.01.19
- Leetcode1584 连接所有点的最小费用
- Leetcode1376 通知所有员工所需的时间
- Leetcode1637 两点之间不包含任何点的最宽垂直面积
Leetcode1584 连接所有点的最小费用
给你一个points 数组，表示 2D 平面上的一些点，其中 points[i] = [xi, yi] 。
连接点 [xi, yi] 和点 [xj, yj] 的费用为它们之间的 曼哈顿距离 ：|xi - xj| |yi - yj| ，其中 |val| 表示 val 的绝对值。
请你返回将所有点连接的最小总费用。只有任意两点之间 有且仅有 一条简单路径时，才认为所有点都已连接。
今天每日一题。依然是并查集，类似于最小生成树的Kruskal算法，比正常必查集多了一个排序的过程。也能用Prim，但是早就忘了，就先写个这个吧。
class Solution { public int minCostConnectPoints(int[][] points) { int n = points.length; UnionFind uf = new UnionFind(n); List<Edge> list = new ArrayList<>(); //计算所有边的长度，贪心地从最小的开始建树 for(int i = 0; i < n - 1; i ){ for(int j = i 1; j < n; j ){ //新建一个类Edge，一条边的两边表示两个点，如果合并的话就把这两个点进行合并 list.add(new Edge(i, j, Math.abs(points[i][0] - points[j][0]) Math.abs(points[i][1] - points[j][1]))); } } //对边进行排序 Collections.sort(list, (x, y) -> (x.val - y.val)); int res = 0; for(int i = 0; i < list.size(); i ){ //如果说两个点已经属于同一个连通分量了，就略过 if (uf.find(list.get(i).x) == uf.find(list.get(i).y)){ continue; } res = list.get(i).val; //合并两条边 uf.union(list.get(i).x, list.get(i). y); } return res; }//新建一个类，两个点加两个点之间的曼哈顿距离 class Edge{ int x; int y; int val; public Edge(int x, int y, int val){ this.x = x; this.y = y; this.val = val; } }//并查集模板 class UnionFind{ int[] parent; public UnionFind(int n){ parent = new int[n]; for(int i = 0; i < n; i ){ parent[i] = i; } } public int find(int i){ if (parent[i] == i){ return i; } return parent[i] = find(parent[i]); } public void union(int i, int j){ int root1 = find(i); int root2 = find(j); if (root1 == root2) return; parent[root1] = root2; } }}Leetcode1376 通知所有员工所需的时间
公司里有 n 名员工，每个员工的 ID 都是独一无二的，编号从 0 到 n - 1。公司的总负责人通过 headID 进行标识。
在 manager 数组中，每个员工都有一个直属负责人，其中 manager[i] 是第 i 名员工的直属负责人。对于总负责人，manager[headID] = -1。题目保证从属关系可以用树结构显示。
公司总负责人想要向公司所有员工通告一条紧急消息。他将会首先通知他的直属下属们，然后由这些下属通知他们的下属，直到所有的员工都得知这条紧急消息。
第 i 名员工需要 informTime[i] 分钟来通知它的所有直属下属（也就是说在 informTime[i] 分钟后，他的所有直属下属都可以开始传播这一消息）。
返回通知所有员工这一紧急消息所需要的 分钟数 。
图论的题目做多了，开始不管什么题目都想着先建图了。其实这题完全没必要建图，之间DFS或者BFS就行了。不过这种建图的做法看着比较好看吧。
class Solution { public int numOfMinutes(int n, int headID, int[] manager, int[] informTime) { //邻接表 List<List<Integer>> edge = new ArrayList<>(); for(int i = 0; i < n; i ){ edge.add(new ArrayList<Integer>()); } //建表 int[] res = new int[n]; for(int i = 0; i < n; i ){ if (manager[i] != -1){ edge.get(manager[i]).add(i); } } Queue<Integer> queue = new LinkedList<>(); queue.offer(headID); int sum = 0; //常规BFS，过程中记录一下到每一个点的时间 while (!queue.isEmpty()){ int temp = queue.poll(); for(int ele : edge.get(temp)){ res[ele] = res[temp] informTime[temp]; queue.offer(ele); } } int max = res[0]; //最后遍历一下，取最大值即可 for(int i = 1; i < n; i ){ max = Math.max(max, res[i]); } return max; }}Leetcode1637 两点之间不包含任何点的最宽垂直面积
给你 n 个二维平面上的点 points ，其中 points[i] = [xi, yi] ，请你返回两点之间内部不包含任何点的 最宽垂直面积 的宽度。
垂直面积 的定义是固定宽度，而 y 轴上无限延伸的一块区域（也就是高度为无穷大）。 最宽垂直面积 为宽度最大的一个垂直面积。
请注意，垂直区域 边上 的点 不在 区域内。
一开始看不懂这题，看懂了就觉得没什么意思。看了其他的解法，也是要排序，那就更没意思了。-_-||
class Solution { public int maxWidthOfVerticalArea(int[][] points) { Arrays.sort(points, (x, y) -> (x[0] - y[0])); int n = points.length, max = Integer.MIN_VALUE; int[] prev = points[0]; for(int i = 1; i < n; i ){ max = Math.max(max, points[i][0] - prev[0]); prev = points[i]; } return max; }}