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

## 1 省份数量

### 题目描述

c直接相连，那么城市 a 与城市 c 间接相连。

### 解题思路与代码

#### 解法一：深度优先

  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;
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;
}


#### 解法三：并查集

    static int mergeFind(int[][] isConnected){
int provinces = isConnected.length;
int[] level = new int[provinces];
for (int i = 0; i < provinces; i++) {
level[i] = 1;
}
for (int i = 0; i < provinces; i++) {
for (int j = i + 1; j < provinces; j++) {
if (isConnected[i][j] == 1) {
}
}
}
int count = 0;
for (int i = 0; i < provinces; i++) {
count++;
}
}
return count;
}
static int find(int x, int[] arr) {
if(arr[x] == x)
return x;
else
return arr[x];
}
static void merge(int x, int y,int[] arr,int[] level) {
int i = find(x,arr);
int j = find(y,arr);
if(i == j){
return;
}
if(level[i] <= level[j]){
arr[i] = j;
}else{
arr[j] = i;
}
//深度加1
level[j]++;
}



## 2 三角形的最大周长

### 解题思路与代码

#### 贪心算法：

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;
}


## 3 打家劫舍

#### 解题思路与代码

    static int maxMoney(int[] nums,int index){
if (nums == null || index < 0) {
return 0;
}
if (index == 0) {
return nums[0];
}
return Math.max(maxMoney(nums,index - 2) + nums[index], maxMoney(nums,index
- 1));
}
static int maxMoney(int[] nums){
if (nums == null || nums.length == 0) {
return 0;
}
int length = nums.length;
if (length == 1) {
return nums[0];
}

/*
int[] dp = new int[length];
dp[0] = nums[0];
dp[1] = Math.max(nums[0], nums[1]);
for (int i = 2; i < length; i++) {
dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);
}
return dp[length - 1];
*/

int first = nums[0], second = Math.max(nums[0], nums[1]);
for (int i = 2; i < length; i++) {
int temp = second;
second = Math.max(first + nums[i], second);
first = temp;
}
return second;
}

##### 如果房子首尾相连：
    public int rob(int[] nums) {
int length = nums.length;
if (length == 1) {
return nums[0];
} else if (length == 2) {
return Math.max(nums[0], nums[1]);
}
return Math.max(robRange(nums, 0, length - 2), robRange(nums, 1, length -
1));
}
public int robRange(int[] nums, int start, int end) {
int first = nums[start], second = Math.max(nums[start], nums[start + 1]);
for (int i = start + 2; i <= end; i++) {
int temp = second;
second = Math.max(first + nums[i], second);
first = temp;
}
return second;
}

    public int rob(TreeNode root) {
int[] rootStatus = dfs(root);
return Math.max(rootStatus[0], rootStatus[1]);
}
public int[] dfs(TreeNode node) {
if (node == null) {
return new int[]{0, 0};
}
int[] l = dfs(node.left);
int[] r = dfs(node.right);
int selected = node.val + l[1] + r[1];
int notSelected = Math.max(l[0], l[1]) + Math.max(r[0], r[1]);
return new int[]{selected, notSelected};
}



|
19天前
|

38 1
|
25天前
|

LeetCode第12题目整数转罗马数字

23 0
|
1月前
|

LeetCode经典算法题：打家劫舍java详解
LeetCode经典算法题：打家劫舍java详解
38 2
|
1月前
|

LeetCode经典算法题：井字游戏+优势洗牌+Dota2参议院java解法
LeetCode经典算法题：井字游戏+优势洗牌+Dota2参议院java解法
35 1
|
1月前
|

LeetCode经典算法题：预测赢家+香槟塔java解法
LeetCode经典算法题：预测赢家+香槟塔java解法
32 1
|
25天前
|

LeetCode第13题目罗马数字转整数

24 0
|
4天前
|

36 20
|
5天前
|

36 19
|
27天前
|

38 7
|
6天前
|

19 2

DDNS