Skip to content

Commit d469307

Browse files
halfrosthalfrost
committed
Add solution 1319
1 parent 228bde3 commit d469307

27 files changed

+646
-366
lines changed

‎README.md

Lines changed: 270 additions & 269 deletions
Large diffs are not rendered by default.

‎leetcode/0042.Trapping-Rain-Water/README.md

Lines changed: 8 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -10,9 +10,9 @@ Given n non-negative integers representing an elevation map where the width of e
1010
The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped. Thanks Marcos for contributing this image!
1111

1212

13-
Example:
13+
**Example**:
1414

15-
```c
15+
```go
1616
Input: [0,1,0,2,1,0,1,3,2,1,2,1]
1717
Output: 6
1818
```
@@ -23,7 +23,9 @@ Output: 6
2323

2424
## 解题思路
2525

26-
27-
![](https://image.ibb.co/d6A2ZU/IMG-0139.jpg)
28-
29-
每个数组里面的元素值可以想象成一个左右都有壁的圆柱筒。例如上图中左边的第二个元素 1，当前左边最大的元素是 2 ，所以 2 高度的水会装到 1 的上面(因为想象成了左右都有筒壁)。这道题的思路就是左指针从 0 开始往右扫，右指针从最右边开始往左扫。额外还需要 2 个变量分别记住左边最大的高度和右边最大高度。遍历扫数组元素的过程中，如果左指针的高度比右指针的高度小，就不断的移动左指针，否则移动右指针。循环的终止条件就是左右指针碰上以后就结束。只要数组中元素的高度比保存的局部最大高度小，就累加 res 的值，否则更新局部最大高度。最终解就是 res 的值。
26+
- 每个数组里面的元素值可以想象成一个左右都有壁的圆柱筒。例如下图中左边的第二个元素 1，当前左边最大的元素是 2 ，所以 2 高度的水会装到 1 的上面(因为想象成了左右都有筒壁)。这道题的思路就是左指针从 0 开始往右扫，右指针从最右边开始往左扫。额外还需要 2 个变量分别记住左边最大的高度和右边最大高度。遍历扫数组元素的过程中，如果左指针的高度比右指针的高度小，就不断的移动左指针，否则移动右指针。循环的终止条件就是左右指针碰上以后就结束。只要数组中元素的高度比保存的局部最大高度小，就累加 res 的值，否则更新局部最大高度。最终解就是 res 的值。
27+
![](https://image.ibb.co/d6A2ZU/IMG-0139.jpg)
28+
- 抽象一下，本题是想求针对每个 i，找到它左边最大值 leftMax，右边的最大值 rightMax，然后 min(leftMax，rightMax) 为能够接到水的高度。left 和 right 指针是两边往中间移动的游标指针。最傻的解题思路是针对每个下标 i，往左循环找到第一个最大值，往右循环找到第一个最大值，然后把这两个最大值取出最小者，即为当前雨水的高度。这样做时间复杂度高，浪费了很多循环。i 在从左往右的过程中，是可以动态维护最大值的。右边的最大值用右边的游标指针来维护。从左往右扫一遍下标，和，从两边往中间遍历一遍下标，是相同的结果，每个下标都遍历了一次。
29+
![](https://img.halfrost.com/Leetcode/leetcode_42_1.png)
30+
- 每个 i 的宽度固定为 1，所以每个“坑”只需要求出高度，即当前这个“坑”能积攒的雨水。最后依次将每个“坑”中的雨水相加即是能接到的雨水数。
31+
![](https://img.halfrost.com/Leetcode/leetcode_42_0.png)

‎leetcode/1319.Number-of-Operations-to-Make-Network-Connected/1319. Number of Operations to Make Network Connected.go

Lines changed: 24 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,24 @@
1+
package leetcode
2+
3+
import (
4+
"github.com/halfrost/LeetCode-Go/template"
5+
)
6+
7+
func makeConnected(n int, connections [][]int) int {
8+
if n-1 > len(connections) {
9+
return -1
10+
}
11+
uf, redundance := template.UnionFind{}, 0
12+
uf.Init(n)
13+
for _, connection := range connections {
14+
if uf.Find(connection[0]) == uf.Find(connection[1]) {
15+
redundance++
16+
} else {
17+
uf.Union(connection[0], connection[1])
18+
}
19+
}
20+
if uf.TotalCount() == 1 || redundance < uf.TotalCount()-1 {
21+
return 0
22+
}
23+
return uf.TotalCount() - 1
24+
}

‎leetcode/1319.Number-of-Operations-to-Make-Network-Connected/1319. Number of Operations to Make Network Connected_test.go

Lines changed: 63 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,63 @@
1+
package leetcode
2+
3+
import (
4+
"fmt"
5+
"testing"
6+
)
7+
8+
type question1319 struct {
9+
para1319
10+
ans1319
11+
}
12+
13+
// para 是参数
14+
// one 代表第一个参数
15+
type para1319 struct {
16+
n int
17+
connections [][]int
18+
}
19+
20+
// ans 是答案
21+
// one 代表第一个答案
22+
type ans1319 struct {
23+
one int
24+
}
25+
26+
func Test_Problem1319(t *testing.T) {
27+
28+
qs := []question1319{
29+
30+
{
31+
para1319{4, [][]int{{0, 1}, {0, 2}, {1, 2}}},
32+
ans1319{1},
33+
},
34+
35+
{
36+
para1319{6, [][]int{{0, 1}, {0, 2}, {0, 3}, {1, 2}, {1, 3}}},
37+
ans1319{2},
38+
},
39+
40+
{
41+
para1319{6, [][]int{{0, 1}, {0, 2}, {0, 3}, {1, 2}}},
42+
ans1319{-1},
43+
},
44+
45+
{
46+
para1319{5, [][]int{{0, 1}, {0, 2}, {3, 4}, {2, 3}}},
47+
ans1319{0},
48+
},
49+
50+
{
51+
para1319{12, [][]int{{1, 5}, {1, 7}, {1, 2}, {1, 4}, {3, 7}, {4, 7}, {3, 5}, {0, 6}, {0, 1}, {0, 4}, {2, 6}, {0, 3}, {0, 2}}},
52+
ans1319{4},
53+
},
54+
}
55+
56+
fmt.Printf("------------------------Leetcode Problem 1319------------------------\n")
57+
58+
for _, q := range qs {
59+
_, p := q.ans1319, q.para1319
60+
fmt.Printf("【input】:%v 【output】:%v\n", p, makeConnected(p.n, p.connections))
61+
}
62+
fmt.Printf("\n\n\n")
63+
}

‎leetcode/1319.Number-of-Operations-to-Make-Network-Connected/README.md

Lines changed: 90 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,90 @@
1+
# [1319. Number of Operations to Make Network Connected](https://leetcode.com/problems/number-of-operations-to-make-network-connected/)
2+
3+
4+
## 题目
5+
6+
There are `n` computers numbered from `0` to `n-1` connected by ethernet cables `connections` forming a network where `connections[i] = [a, b]` represents a connection between computers `a` and `b`. Any computer can reach any other computer directly or indirectly through the network.
7+
8+
Given an initial computer network `connections`. You can extract certain cables between two directly connected computers, and place them between any pair of disconnected computers to make them directly connected. Return the *minimum number of times* you need to do this in order to make all the computers connected. If it's not possible, return -1.
9+
10+
**Example 1:**
11+
12+
![https://assets.leetcode.com/uploads/2020/01/02/sample_1_1677.png](https://assets.leetcode.com/uploads/2020/01/02/sample_1_1677.png)
13+
14+
```
15+
Input: n = 4, connections = [[0,1],[0,2],[1,2]]
16+
Output: 1
17+
Explanation: Remove cable between computer 1 and 2 and place between computers 1 and 3.
18+
```
19+
20+
**Example 2:**
21+
22+
![https://assets.leetcode.com/uploads/2020/01/02/sample_2_1677.png](https://assets.leetcode.com/uploads/2020/01/02/sample_2_1677.png)
23+
24+
```
25+
Input: n = 6, connections = [[0,1],[0,2],[0,3],[1,2],[1,3]]
26+
Output: 2
27+
```
28+
29+
**Example 3:**
30+
31+
```
32+
Input: n = 6, connections = [[0,1],[0,2],[0,3],[1,2]]
33+
Output: -1
34+
Explanation: There are not enough cables.
35+
```
36+
37+
**Example 4:**
38+
39+
```
40+
Input: n = 5, connections = [[0,1],[0,2],[3,4],[2,3]]
41+
Output: 0
42+
```
43+
44+
**Constraints:**
45+
46+
- `1 <= n <= 10^5`
47+
- `1 <= connections.length <= min(n*(n-1)/2, 10^5)`
48+
- `connections[i].length == 2`
49+
- `0 <= connections[i][0], connections[i][1] < n`
50+
- `connections[i][0] != connections[i][1]`
51+
- There are no repeated connections.
52+
- No two computers are connected by more than one cable.
53+
54+
## 题目大意
55+
56+
用以太网线缆将 n 台计算机连接成一个网络，计算机的编号从 0 到 n-1。线缆用 connections 表示，其中 connections[i] = [a, b] 连接了计算机 a 和 b。网络中的任何一台计算机都可以通过网络直接或者间接访问同一个网络中其他任意一台计算机。给你这个计算机网络的初始布线 connections，你可以拔开任意两台直连计算机之间的线缆，并用它连接一对未直连的计算机。请你计算并返回使所有计算机都连通所需的最少操作次数。如果不可能，则返回 -1 。
57+
58+
## 解题思路
59+
60+
- 很明显这题的解题思路是并查集。先将每个 connections 构建出并查集。构建中需要累加冗余的连接。例如 2 个节点已经连通，再连接这个集合中的任意 2 个节点就算冗余连接。冗余连接的线都可以移动，去连接还没有连通的节点。计算出冗余连接数，再根据并查集的集合总数，即可得出答案。
61+
- 这一题答案有 3 种可能。第一种，所有点都在一个集合内，即全部连通，这时输出 0 。第二种，冗余的连接不够串起所有点，这时输出 -1 。第三种情况是可以连通的情况。 m 个集合需要连通，最少需要 m - 1 条线。如果冗余连接数大于 m - 1，则输出 m - 1 即可。
62+
63+
## 代码
64+
65+
```go
66+
package leetcode
67+
68+
import (
69+
"github.com/halfrost/LeetCode-Go/template"
70+
)
71+
72+
func makeConnected(n int, connections [][]int) int {
73+
if n-1 > len(connections) {
74+
return -1
75+
}
76+
uf, redundance := template.UnionFind{}, 0
77+
uf.Init(n)
78+
for _, connection := range connections {
79+
if uf.Find(connection[0]) == uf.Find(connection[1]) {
80+
redundance++
81+
} else {
82+
uf.Union(connection[0], connection[1])
83+
}
84+
}
85+
if uf.TotalCount() == 1 || redundance < uf.TotalCount()-1 {
86+
return 0
87+
}
88+
return uf.TotalCount() - 1
89+
}
90+
```

‎website/content/ChapterFour/0042.Trapping-Rain-Water.md

Lines changed: 9 additions & 9 deletions
Original file line numberDiff line numberDiff line change
@@ -12,11 +12,9 @@ The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In th
1212

1313
**Example**:
1414

15-
```
16-
15+
```go
1716
Input: [0,1,0,2,1,0,1,3,2,1,2,1]
1817
Output: 6
19-
2018
```
2119

2220
## 题目大意
@@ -25,15 +23,16 @@ Output: 6
2523

2624
## 解题思路
2725

28-
29-
![](https://image.ibb.co/d6A2ZU/IMG-0139.jpg)
30-
31-
每个数组里面的元素值可以想象成一个左右都有壁的圆柱筒。例如上图中左边的第二个元素 1，当前左边最大的元素是 2 ，所以 2 高度的水会装到 1 的上面(因为想象成了左右都有筒壁)。这道题的思路就是左指针从 0 开始往右扫，右指针从最右边开始往左扫。额外还需要 2 个变量分别记住左边最大的高度和右边最大高度。遍历扫数组元素的过程中，如果左指针的高度比右指针的高度小，就不断的移动左指针，否则移动右指针。循环的终止条件就是左右指针碰上以后就结束。只要数组中元素的高度比保存的局部最大高度小，就累加 res 的值，否则更新局部最大高度。最终解就是 res 的值。
26+
- 每个数组里面的元素值可以想象成一个左右都有壁的圆柱筒。例如下图中左边的第二个元素 1，当前左边最大的元素是 2 ，所以 2 高度的水会装到 1 的上面(因为想象成了左右都有筒壁)。这道题的思路就是左指针从 0 开始往右扫，右指针从最右边开始往左扫。额外还需要 2 个变量分别记住左边最大的高度和右边最大高度。遍历扫数组元素的过程中，如果左指针的高度比右指针的高度小，就不断的移动左指针，否则移动右指针。循环的终止条件就是左右指针碰上以后就结束。只要数组中元素的高度比保存的局部最大高度小，就累加 res 的值，否则更新局部最大高度。最终解就是 res 的值。
27+
![](https://image.ibb.co/d6A2ZU/IMG-0139.jpg)
28+
- 抽象一下，本题是想求针对每个 i，找到它左边最大值 leftMax，右边的最大值 rightMax，然后 min(leftMax，rightMax) 为能够接到水的高度。left 和 right 指针是两边往中间移动的游标指针。最傻的解题思路是针对每个下标 i，往左循环找到第一个最大值，往右循环找到第一个最大值，然后把这两个最大值取出最小者，即为当前雨水的高度。这样做时间复杂度高，浪费了很多循环。i 在从左往右的过程中，是可以动态维护最大值的。右边的最大值用右边的游标指针来维护。从左往右扫一遍下标，和，从两边往中间遍历一遍下标，是相同的结果，每个下标都遍历了一次。
29+
![](https://img.halfrost.com/Leetcode/leetcode_42_1.png)
30+
- 每个 i 的宽度固定为 1，所以每个“坑”只需要求出高度，即当前这个“坑”能积攒的雨水。最后依次将每个“坑”中的雨水相加即是能接到的雨水数。
31+
![](https://img.halfrost.com/Leetcode/leetcode_42_0.png)
3232

3333
## 代码
3434

3535
```go
36-
3736
package leetcode
3837

3938
func trap(height []int) int {
@@ -57,10 +56,11 @@ func trap(height []int) int {
5756
}
5857
return res
5958
}
60-
6159
```
6260

6361

62+
63+
6464
----------------------------------------------
6565
<div style="display: flex;justify-content: space-between;align-items: center;">
6666
<p><a href="https://books.halfrost.com/leetcode/ChapterFour/0041.First-Missing-Positive/">⬅️上一页</a></p>

‎website/content/ChapterFour/1317.Convert-Integer-to-the-Sum-of-Two-No-Zero-Integers.md

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -99,5 +99,5 @@ func isNoZero(n int) bool {
9999
----------------------------------------------
100100
<div style="display: flex;justify-content: space-between;align-items: center;">
101101
<p><a href="https://books.halfrost.com/leetcode/ChapterFour/1313.Decompress-Run-Length-Encoded-List/">⬅️上一页</a></p>
102-
<p><a href="https://books.halfrost.com/leetcode/ChapterFour/1380.Lucky-Numbers-in-a-Matrix/">下一页➡️</a></p>
102+
<p><a href="https://books.halfrost.com/leetcode/ChapterFour/1319.Number-of-Operations-to-Make-Network-Connected/">下一页➡️</a></p>
103103
</div>

‎website/content/ChapterFour/1319.Number-of-Operations-to-Make-Network-Connected.md

Lines changed: 97 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,97 @@
1+
# [1319. Number of Operations to Make Network Connected](https://leetcode.com/problems/number-of-operations-to-make-network-connected/)
2+
3+
4+
## 题目
5+
6+
There are `n` computers numbered from `0` to `n-1` connected by ethernet cables `connections` forming a network where `connections[i] = [a, b]` represents a connection between computers `a` and `b`. Any computer can reach any other computer directly or indirectly through the network.
7+
8+
Given an initial computer network `connections`. You can extract certain cables between two directly connected computers, and place them between any pair of disconnected computers to make them directly connected. Return the *minimum number of times* you need to do this in order to make all the computers connected. If it's not possible, return -1.
9+
10+
**Example 1:**
11+
12+
![https://assets.leetcode.com/uploads/2020/01/02/sample_1_1677.png](https://assets.leetcode.com/uploads/2020/01/02/sample_1_1677.png)
13+
14+
```
15+
Input: n = 4, connections = [[0,1],[0,2],[1,2]]
16+
Output: 1
17+
Explanation: Remove cable between computer 1 and 2 and place between computers 1 and 3.
18+
```
19+
20+
**Example 2:**
21+
22+
![https://assets.leetcode.com/uploads/2020/01/02/sample_2_1677.png](https://assets.leetcode.com/uploads/2020/01/02/sample_2_1677.png)
23+
24+
```
25+
Input: n = 6, connections = [[0,1],[0,2],[0,3],[1,2],[1,3]]
26+
Output: 2
27+
```
28+
29+
**Example 3:**
30+
31+
```
32+
Input: n = 6, connections = [[0,1],[0,2],[0,3],[1,2]]
33+
Output: -1
34+
Explanation: There are not enough cables.
35+
```
36+
37+
**Example 4:**
38+
39+
```
40+
Input: n = 5, connections = [[0,1],[0,2],[3,4],[2,3]]
41+
Output: 0
42+
```
43+
44+
**Constraints:**
45+
46+
- `1 <= n <= 10^5`
47+
- `1 <= connections.length <= min(n*(n-1)/2, 10^5)`
48+
- `connections[i].length == 2`
49+
- `0 <= connections[i][0], connections[i][1] < n`
50+
- `connections[i][0] != connections[i][1]`
51+
- There are no repeated connections.
52+
- No two computers are connected by more than one cable.
53+
54+
## 题目大意
55+
56+
用以太网线缆将 n 台计算机连接成一个网络，计算机的编号从 0 到 n-1。线缆用 connections 表示，其中 connections[i] = [a, b] 连接了计算机 a 和 b。网络中的任何一台计算机都可以通过网络直接或者间接访问同一个网络中其他任意一台计算机。给你这个计算机网络的初始布线 connections，你可以拔开任意两台直连计算机之间的线缆，并用它连接一对未直连的计算机。请你计算并返回使所有计算机都连通所需的最少操作次数。如果不可能，则返回 -1 。
57+
58+
## 解题思路
59+
60+
- 很明显这题的解题思路是并查集。先将每个 connections 构建出并查集。构建中需要累加冗余的连接。例如 2 个节点已经连通，再连接这个集合中的任意 2 个节点就算冗余连接。冗余连接的线都可以移动，去连接还没有连通的节点。计算出冗余连接数，再根据并查集的集合总数，即可得出答案。
61+
- 这一题答案有 3 种可能。第一种，所有点都在一个集合内，即全部连通，这时输出 0 。第二种，冗余的连接不够串起所有点，这时输出 -1 。第三种情况是可以连通的情况。 m 个集合需要连通，最少需要 m - 1 条线。如果冗余连接数大于 m - 1，则输出 m - 1 即可。
62+
63+
## 代码
64+
65+
```go
66+
package leetcode
67+
68+
import (
69+
"github.com/halfrost/LeetCode-Go/template"
70+
)
71+
72+
func makeConnected(n int, connections [][]int) int {
73+
if n-1 > len(connections) {
74+
return -1
75+
}
76+
uf, redundance := template.UnionFind{}, 0
77+
uf.Init(n)
78+
for _, connection := range connections {
79+
if uf.Find(connection[0]) == uf.Find(connection[1]) {
80+
redundance++
81+
} else {
82+
uf.Union(connection[0], connection[1])
83+
}
84+
}
85+
if uf.TotalCount() == 1 || redundance < uf.TotalCount()-1 {
86+
return 0
87+
}
88+
return uf.TotalCount() - 1
89+
}
90+
```
91+
92+
93+
----------------------------------------------
94+
<div style="display: flex;justify-content: space-between;align-items: center;">
95+
<p><a href="https://books.halfrost.com/leetcode/ChapterFour/1317.Convert-Integer-to-the-Sum-of-Two-No-Zero-Integers/">⬅️上一页</a></p>
96+
<p><a href="https://books.halfrost.com/leetcode/ChapterFour/1380.Lucky-Numbers-in-a-Matrix/">下一页➡️</a></p>
97+
</div>

‎website/content/ChapterFour/1380.Lucky-Numbers-in-a-Matrix.md

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -89,6 +89,6 @@ func luckyNumbers(matrix [][]int) []int {
8989

9090
----------------------------------------------
9191
<div style="display: flex;justify-content: space-between;align-items: center;">
92-
<p><a href="https://books.halfrost.com/leetcode/ChapterFour/1317.Convert-Integer-to-the-Sum-of-Two-No-Zero-Integers/">⬅️上一页</a></p>
92+
<p><a href="https://books.halfrost.com/leetcode/ChapterFour/1319.Number-of-Operations-to-Make-Network-Connected/">⬅️上一页</a></p>
9393
<p><a href="https://books.halfrost.com/leetcode/ChapterFour/1385.Find-the-Distance-Value-Between-Two-Arrays/">下一页➡️</a></p>
9494
</div>

0 commit comments

Comments
 (0)