LeetCode经典算法题：矩阵中省份数量经典题目+三角形最大周长java多种解法详解

LeetCode经典算法题：矩阵中省份数量经典题目+三角形最大周长java多种解法

1 省份数量

题目描述

有 n 个城市，其中一些彼此相连，另一些没有相连。如果城市 a 与城市 b 直接相连，且城市 b 与城市 c直接相连，那么城市 a 与城市 c 间接相连。

省份 是一组直接或间接相连的城市，组内不含其他没有相连的城市。

给你一个 n x n 的矩阵 isConnected ，其中 isConnected[i][j] = 1 表示第 i 个城市和第 j 个城市直接相连，而 isConnected[i][j] = 0 表示二者不直接相连。

返回矩阵中 省份 的数量。

解题思路与代码

解法一：深度优先

获取一个城市，通过递归找到离该城市最远的城市，标记为已访问，然后逐个向内进行标记

 	public int findCircleNum(int[][] isConnected) {int provinces = isConnected.length;boolean[] visited = new boolean[provinces];int circles = 0;for (int i = 0; i < provinces; i++) {if (!visited[i]) {dfs(isConnected, visited, provinces, i);circles++;}}return circles;}public void dfs(int[][] isConnected, boolean[] visited, int provinces, int i) {for (int j = 0; j < provinces; j++) {if (isConnected[i][j] == 1 && !visited[j]) {visited[j] = true;dfs(isConnected, visited, provinces, j);}}}

解法二：广度优先

获取一个城市，先标记与该城市直连的城市(最近的)，然后逐步向外扩散寻找

    public int bfs(int[][] isConnected) {int provinces = isConnected.length;boolean[] visited = new boolean[provinces];int circles = 0;Queue<Integer> queue = new LinkedList<Integer>();for (int i = 0; i < provinces; i++) {if (!visited[i]) {queue.offer(i);while (!queue.isEmpty()) {int j = queue.poll();visited[j] = true;for (int k = 0; k < provinces; k++) {if (isConnected[j][k] == 1 && !visited[k]) {queue.offer(k);}}}circles++;}}return circles;}

解法三：并查集

将每个城市看成一个节点，如果两个城市相连，则建立树关系，选出其中一个为head，如果两个树中的节点也相连，则将其中一个head设置为另一个树的head

两个方法 ：一个寻找head节点，一个合并树

    static int mergeFind(int[][] isConnected){int provinces = isConnected.length;int[] head = new int[provinces];int[] level = new int[provinces];for (int i = 0; i < provinces; i++) {head[i] = i;level[i] = 1;}for (int i = 0; i < provinces; i++) {for (int j = i + 1; j < provinces; j++) {if (isConnected[i][j] == 1) {merge(i, j,head,level);}}}int count = 0;//找出所有的headfor (int i = 0; i < provinces; i++) {if (head[i] == i) {count++;}}return count;}//查找head节点static int find(int x, int[] arr) {if(arr[x] == x)return x;elsearr[x] = find(arr[x],arr);//路径压缩，每一个节点直接能找到headreturn arr[x];}static void merge(int x, int y,int[] arr,int[] level) {int i = find(x,arr);int j = find(y,arr);//深度比较短的树的head往深度大的树上挂，使合并后的深度尽量小if(i == j){return;}if(level[i] <= level[j]){arr[i] = j;}else{arr[j] = i;}//深度加1level[j]++;}

2 三角形的最大周长

题目描述

给定由一些正数（代表长度）组成的数组 A ，返回由其中三个长度组成的、面积不为零的三角形的最大周长。

如果不能形成任何面积不为零的三角形，返回 0 。

解题思路与代码

贪心算法：

先小到大排序，假设最长边是最后下标，另外两条边是倒数第二和第三下标，则此时三角形周长最大

n < (n-1) + (n-2)，如果不成立，意味着该数组中不可能有另外两个值之和大于n，此时将n左移，重新计算

 public int largestPerimeter(int[] A) {Arrays.sort(A);for (int i = A.length - 1; i >= 2; --i) {if (A[i - 2] + A[i - 1] > A[i]) {return A[i - 2] + A[i - 1] + A[i];}}return 0;}