Re: [閒聊] 每日LeetCode已回收

看板Marginalman作者Rushia (みけねこ的鼻屎)時間2年前 (2023/06/04 22:12)推噓3(3推 0噓 0→)

留言3則, 3人參與討論串336/719 (看更多)

https://leetcode.com/problems/number-of-provinces/description/ 547. Number of Provinces 給你一個陣列isConnected[][]，isConnected[i][j] 表示第 i 個城市是否與第 j 個城市相連(1表示相連)，一個直接或間接相連的城市集合為一個省份，找出這個圖共有幾個省。 Example 1: https://assets.leetcode.com/uploads/2020/12/24/graph1.jpg

Input: isConnected = [[1,1,0],[1,1,0],[0,0,1]] Output: 2 Example 2: https://assets.leetcode.com/uploads/2020/12/24/graph2.jpg

Input: isConnected = [[1,0,0],[0,1,0],[0,0,1]] Output: 3 思路： 1.從隨便一個點出發並遍歷所有相鄰的點(DFS)，每次遇到沒走過的城市時省分數量+1，走過的城市用一個visited[]標記已經走過，下次遇到就跳過。 2.遍歷完整個陣列返回統計的省分數量。 Java Code： --------------------------------------------------- class Solution { public int findCircleNum(int[][] isConnected) { int n = isConnected.length; int count = 0; boolean[] visited = new boolean[n]; for (int i = 0; i < n; i++) { if (!visited[i]) { count++; dfs(i, isConnected, visited); } } return count; } private void dfs(int id, int[][] isConnected, boolean[] visited) { if (visited[id]) return; visited[id] = true; for (int i = 0; i < isConnected.length; i++) { if (isConnected[id][i] == 1) { dfs(i, isConnected, visited); } } } } --------------------------------------------------- -- https://i.imgur.com/CBMFmWk.jpg