ppt超链接到网站怎么做,wordpress文本框,上海好牛网站建设,wordpress 内网搭建题目链接
省份数量
题目描述 注意点
1 n 200isConnected[i][j] 为 1 或 0isConnected[i][i] 1isConnected[i][j] isConnected[j][i]
解答思路
最初想到的是广度优先遍历#xff0c;当某个城市不属于省份#xff0c;需要从该城市开始#xff0c;根据isConne…题目链接
省份数量
题目描述 注意点
1 n 200isConnected[i][j] 为 1 或 0isConnected[i][i] 1isConnected[i][j] isConnected[j][i]
解答思路
最初想到的是广度优先遍历当某个城市不属于省份需要从该城市开始根据isConnected找到所有与其相连的城市即可得到省份中有哪些城市保存城市所属省份的信息遍历完全部城市以后即可得到连通分量的总数即省份的总数另一个方法就是深度优先遍历找到相连的城市找到一个属于新的省份的城市后找到与之相连的城市再根据相连的城市找到与相连城市相连的城市…找到省份中所有的城市。遍历完全部城市找到所有省份
代码
方法一
class Solution {public int findCircleNum(int[][] isConnected) {int res 0;int n isConnected.length;int[] province new int[n];DequeInteger deque new ArrayDeque();for (int i 0; i n; i) {// 该城市已经属于某个省份if (province[i] ! 0) {continue;}res;deque.offerLast(i);// 找到与i相连的所有城市while (!deque.isEmpty()) {int row deque.pollFirst();for (int j 0; j n; j) {if (isConnected[row][j] 1 province[j] 0) {province[j] res;deque.offerLast(j);}}}}return res;}
}方法二
class Solution {public int findCircleNum(int[][] isConnected) {int res 0;int n isConnected.length;int[] province new int[n];for (int i 0; i n; i) {// 该城市已属于某个省份if (province[i] ! 0) {continue;}res;// 深度优先遍历找到属于该省份的城市dfs(isConnected, province, i);}return res;}public void dfs(int[][] isConnected, int[] province, int i) {if (province[i] ! 0) {return;}province[i] 1;for (int j 0; j province.length; j) {if (isConnected[i][j] 1) {dfs(isConnected, province, j);}}}
}关键点
深度优先遍历的思想广度优先遍历的思想需要保存城市属于某个省份的信息
