Re: [閒聊] 每日LeetCode

https://leetcode.com/problems/maximal-network-rank/description/ 1615. Maximal Network Rank 給你一個 n 表示城市的數量，一個陣列 roads[][] ，roads[i][j] 表示 城市 i 存在直達城市 j 的雙向道路，Network Rank 被定義為任意兩城市 的所有直連道路總和（若兩城市間存在道路則只算一個），求出最大 Network Rank。 Example 1: https://assets.leetcode.com/uploads/2020/09/21/ex1.png Input: n = 4, roads = [[0,1],[0,3],[1,2],[1,3]] Output: 4 Explanation: The network rank of cities 0 and 1 is 4 as there are 4 roads that are connected to either 0 or 1. The road between 0 and 1 is only counted once. Example 2: https://assets.leetcode.com/uploads/2020/09/21/ex2.png Input: n = 5, roads = [[0,1],[0,3],[1,2],[1,3],[2,3],[2,4]] Output: 5 Explanation: There are 5 roads that are connected to cities 1 or 2. Example 3: Input: n = 8, roads = [[0,1],[1,2],[2,3],[2,4],[5,6],[5,7]] Output: 5 Explanation: The network rank of 2 and 5 is 5. Notice that all the cities do not have to be connected. 思路： 1.按照題意，一個 Network Rank 是兩個城市的道路總和，我們把城市看成點道路看成 線，就是要我們求任意兩個點的最大 degree 和。 2.我們用一個陣列記住每個點向外的道路有幾個，一個Set紀錄任意兩點是否連通。 3.最後把每個城市兩兩配對，將道路數量相加（若兩城市相連減一），並取最大的 rank 即可。 Java Code： ------------------------------------------------- class Solution { public int maximalNetworkRank(int n, int[][] roads) { int[] degree = new int[n]; boolean[][] connect = new boolean[n][n]; for (int[] road : roads) { degree[road[0]]++; degree[road[1]]++; connect[road[0]][road[1]] = true; connect[road[1]][road[0]] = true; } int maxRank = 0; for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { int rank = degree[i] + degree[j] + (connect[i][j] ? -1 : 0); maxRank = Math.max(maxRank, rank); } } return maxRank; } } ------------------------------------------------- -- https://i.imgur.com/bFRiqA3.jpg --
※ 批踢踢實業坊(ptt.cc), 來自: 122.100.73.13 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1692382070.A.E44.html

推 JerryChungYC: 大師 08/19 02:35