Skip to content

Commit 0468622

Browse files
halfrosthalfrost
committed
Update 997 solution
1 parent 1499e78 commit 0468622

File tree

8 files changed

+104
-8
lines changed

8 files changed

+104
-8
lines changed

‎leetcode/0997.Find-the-Town-Judge/README.md

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -1,4 +1,4 @@
1-
# [997. Find the Town Judge](https://leetcode-cn.com/problems/find-the-town-judge/)
1+
# [997. Find the Town Judge](https://leetcode.com/problems/find-the-town-judge/)
22

33
## 题目
44

@@ -57,7 +57,7 @@ Return the label of the town judge if the town judge exists and can be identifie
5757
入度和出度统计
5858

5959
- 被人信任定义为入度, 信任别人定义为出度
60-
- 如果1-n之间有数字x的入度为n - 1，出度为0，则返回x
60+
- 如果 1-n 之间有数字 x 的入度为 n - 1，出度为 0，则返回 x
6161

6262
## 代码
6363

‎website/content/ChapterFour/0900~0999/0996.Number-of-Squareful-Arrays.md

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -110,5 +110,5 @@ func checkSquare(num int) bool {
110110
----------------------------------------------
111111
<div style="display: flex;justify-content: space-between;align-items: center;">
112112
<p><a href="https://books.halfrost.com/leetcode/ChapterFour/0900~0999/0995.Minimum-Number-of-K-Consecutive-Bit-Flips/">⬅️上一页</a></p>
113-
<p><a href="https://books.halfrost.com/leetcode/ChapterFour/0900~0999/0999.Available-Captures-for-Rook/">下一页➡️</a></p>
113+
<p><a href="https://books.halfrost.com/leetcode/ChapterFour/0900~0999/0997.Find-the-Town-Judge/">下一页➡️</a></p>
114114
</div>

‎website/content/ChapterFour/0900~0999/0997.Find-the-Town-Judge.md

Lines changed: 94 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,94 @@
1+
# [997. Find the Town Judge](https://leetcode.com/problems/find-the-town-judge/)
2+
3+
## 题目
4+
5+
In a town, there are n people labeled from 1 to n. There is a rumor that one of these people is secretly the town judge.
6+
7+
If the town judge exists, then:
8+
9+
- The town judge trusts nobody.
10+
- Everybody (except for the town judge) trusts the town judge.
11+
- There is exactly one person that satisfies properties 1 and 2.
12+
13+
You are given an array trust where trust[i] = [ai, bi] representing that the person labeled ai trusts the person labeled bi.
14+
15+
Return the label of the town judge if the town judge exists and can be identified, or return -1 otherwise.
16+
17+
**Example 1**:
18+
19+
Input: n = 2, trust = [[1,2]]
20+
Output: 2
21+
22+
**Example 2**:
23+
24+
Input: n = 3, trust = [[1,3],[2,3]]
25+
Output: 3
26+
27+
**Example 3**:
28+
29+
Input: n = 3, trust = [[1,3],[2,3],[3,1]]
30+
Output: -1
31+
32+
**Constraints:**
33+
34+
- 1 <= n <= 1000
35+
- 0 <= trust.length <= 10000
36+
- trust[i].length == 2
37+
- All the pairs of trust are unique.
38+
- ai != bi
39+
- 1 <= ai, bi <= n
40+
41+
## 题目大意
42+
43+
小镇里有 n 个人，按从 1 到 n 的顺序编号。传言称，这些人中有一个暗地里是小镇法官。
44+
45+
如果小镇法官真的存在，那么：
46+
47+
- 小镇法官不会信任任何人。
48+
- 每个人（除了小镇法官）都信任这位小镇法官。
49+
- 只有一个人同时满足属性 1 和属性 2 。
50+
51+
给你一个数组 trust ，其中 trust[i] = [ai, bi] 表示编号为 ai 的人信任编号为 bi 的人。
52+
53+
如果小镇法官存在并且可以确定他的身份，请返回该法官的编号；否则，返回 -1 。
54+
55+
## 解题思路
56+
57+
入度和出度统计
58+
59+
- 被人信任定义为入度, 信任别人定义为出度
60+
- 如果 1-n 之间有数字 x 的入度为 n - 1，出度为 0，则返回 x
61+
62+
## 代码
63+
64+
```go
65+
package leetcode
66+
67+
func findJudge(n int, trust [][]int) int {
68+
if n == 1 && len(trust) == 0 {
69+
return 1
70+
}
71+
judges := make(map[int]int)
72+
for _, v := range trust {
73+
judges[v[1]] += 1
74+
}
75+
for _, v := range trust {
76+
if _, ok := judges[v[0]]; ok {
77+
delete(judges, v[0])
78+
}
79+
}
80+
for k, v := range judges {
81+
if v == n-1 {
82+
return k
83+
}
84+
}
85+
return -1
86+
}
87+
```
88+
89+
90+
----------------------------------------------
91+
<div style="display: flex;justify-content: space-between;align-items: center;">
92+
<p><a href="https://books.halfrost.com/leetcode/ChapterFour/0900~0999/0996.Number-of-Squareful-Arrays/">⬅️上一页</a></p>
93+
<p><a href="https://books.halfrost.com/leetcode/ChapterFour/0900~0999/0999.Available-Captures-for-Rook/">下一页➡️</a></p>
94+
</div>

‎website/content/ChapterFour/0900~0999/0999.Available-Captures-for-Rook.md

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -101,6 +101,6 @@ func caputure(board [][]byte, x, y int, bx, by int) int {
101101

102102
----------------------------------------------
103103
<div style="display: flex;justify-content: space-between;align-items: center;">
104-
<p><a href="https://books.halfrost.com/leetcode/ChapterFour/0900~0999/0996.Number-of-Squareful-Arrays/">⬅️上一页</a></p>
104+
<p><a href="https://books.halfrost.com/leetcode/ChapterFour/0900~0999/0997.Find-the-Town-Judge/">⬅️上一页</a></p>
105105
<p><a href="https://books.halfrost.com/leetcode/ChapterFour/1000~1099/1002.Find-Common-Characters/">下一页➡️</a></p>
106106
</div>

‎website/content/ChapterTwo/Array.md

Lines changed: 3 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -23,7 +23,7 @@ weight: 1
2323
|0036|Valid Sudoku|[Go]({{< relref "/ChapterFour/0001~0099/0036.Valid-Sudoku.md" >}})|Medium||||53.8%|
2424
|0037|Sudoku Solver|[Go]({{< relref "/ChapterFour/0001~0099/0037.Sudoku-Solver.md" >}})|Hard||||52.0%|
2525
|0039|Combination Sum|[Go]({{< relref "/ChapterFour/0001~0099/0039.Combination-Sum.md" >}})|Medium| O(n log n)| O(n)||63.1%|
26-
|0040|Combination Sum II|[Go]({{< relref "/ChapterFour/0001~0099/0040.Combination-Sum-II.md" >}})|Medium| O(n log n)| O(n)||51.8%|
26+
|0040|Combination Sum II|[Go]({{< relref "/ChapterFour/0001~0099/0040.Combination-Sum-II.md" >}})|Medium| O(n log n)| O(n)||51.7%|
2727
|0041|First Missing Positive|[Go]({{< relref "/ChapterFour/0001~0099/0041.First-Missing-Positive.md" >}})|Hard| O(n)| O(n)||35.4%|
2828
|0042|Trapping Rain Water|[Go]({{< relref "/ChapterFour/0001~0099/0042.Trapping-Rain-Water.md" >}})|Hard| O(n)| O(1)|❤️|54.9%|
2929
|0045|Jump Game II|[Go]({{< relref "/ChapterFour/0001~0099/0045.Jump-Game-II.md" >}})|Medium||||35.7%|
@@ -276,6 +276,7 @@ weight: 1
276276
|0992|Subarrays with K Different Integers|[Go]({{< relref "/ChapterFour/0900~0999/0992.Subarrays-with-K-Different-Integers.md" >}})|Hard||||52.9%|
277277
|0995|Minimum Number of K Consecutive Bit Flips|[Go]({{< relref "/ChapterFour/0900~0999/0995.Minimum-Number-of-K-Consecutive-Bit-Flips.md" >}})|Hard||||50.5%|
278278
|0996|Number of Squareful Arrays|[Go]({{< relref "/ChapterFour/0900~0999/0996.Number-of-Squareful-Arrays.md" >}})|Hard||||49.1%|
279+
|0997|Find the Town Judge|[Go]({{< relref "/ChapterFour/0900~0999/0997.Find-the-Town-Judge.md" >}})|Easy||||49.9%|
279280
|0999|Available Captures for Rook|[Go]({{< relref "/ChapterFour/0900~0999/0999.Available-Captures-for-Rook.md" >}})|Easy||||67.6%|
280281
|1002|Find Common Characters|[Go]({{< relref "/ChapterFour/1000~1099/1002.Find-Common-Characters.md" >}})|Easy||||68.4%|
281282
|1004|Max Consecutive Ones III|[Go]({{< relref "/ChapterFour/1000~1099/1004.Max-Consecutive-Ones-III.md" >}})|Medium||||62.0%|
@@ -332,7 +333,7 @@ weight: 1
332333
|1383|Maximum Performance of a Team|[Go]({{< relref "/ChapterFour/1300~1399/1383.Maximum-Performance-of-a-Team.md" >}})|Hard||||41.3%|
333334
|1385|Find the Distance Value Between Two Arrays|[Go]({{< relref "/ChapterFour/1300~1399/1385.Find-the-Distance-Value-Between-Two-Arrays.md" >}})|Easy||||66.1%|
334335
|1389|Create Target Array in the Given Order|[Go]({{< relref "/ChapterFour/1300~1399/1389.Create-Target-Array-in-the-Given-Order.md" >}})|Easy||||85.3%|
335-
|1423|Maximum Points You Can Obtain from Cards|[Go]({{< relref "/ChapterFour/1400~1499/1423.Maximum-Points-You-Can-Obtain-from-Cards.md" >}})|Medium||||49.6%|
336+
|1423|Maximum Points You Can Obtain from Cards|[Go]({{< relref "/ChapterFour/1400~1499/1423.Maximum-Points-You-Can-Obtain-from-Cards.md" >}})|Medium||||49.5%|
336337
|1437|Check If All 1's Are at Least Length K Places Away|[Go]({{< relref "/ChapterFour/1400~1499/1437.Check-If-All-1s-Are-at-Least-Length-K-Places-Away.md" >}})|Easy||||60.5%|
337338
|1438|Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit|[Go]({{< relref "/ChapterFour/1400~1499/1438.Longest-Continuous-Subarray-With-Absolute-Diff-Less-Than-or-Equal-to-Limit.md" >}})|Medium||||45.5%|
338339
|1439|Find the Kth Smallest Sum of a Matrix With Sorted Rows|[Go]({{< relref "/ChapterFour/1400~1499/1439.Find-the-Kth-Smallest-Sum-of-a-Matrix-With-Sorted-Rows.md" >}})|Hard||||61.7%|

‎website/content/ChapterTwo/Backtracking.md

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -104,7 +104,7 @@ func updateMatrix_BFS(matrix [][]int) [][]int {
104104
|0022|Generate Parentheses|[Go]({{< relref "/ChapterFour/0001~0099/0022.Generate-Parentheses.md" >}})|Medium| O(log n)| O(1)||68.7%|
105105
|0037|Sudoku Solver|[Go]({{< relref "/ChapterFour/0001~0099/0037.Sudoku-Solver.md" >}})|Hard| O(n^2)| O(n^2)|❤️|52.0%|
106106
|0039|Combination Sum|[Go]({{< relref "/ChapterFour/0001~0099/0039.Combination-Sum.md" >}})|Medium| O(n log n)| O(n)||63.1%|
107-
|0040|Combination Sum II|[Go]({{< relref "/ChapterFour/0001~0099/0040.Combination-Sum-II.md" >}})|Medium| O(n log n)| O(n)||51.8%|
107+
|0040|Combination Sum II|[Go]({{< relref "/ChapterFour/0001~0099/0040.Combination-Sum-II.md" >}})|Medium| O(n log n)| O(n)||51.7%|
108108
|0046|Permutations|[Go]({{< relref "/ChapterFour/0001~0099/0046.Permutations.md" >}})|Medium| O(n)| O(n)|❤️|70.5%|
109109
|0047|Permutations II|[Go]({{< relref "/ChapterFour/0001~0099/0047.Permutations-II.md" >}})|Medium| O(n^2)| O(n)|❤️|52.7%|
110110
|0051|N-Queens|[Go]({{< relref "/ChapterFour/0001~0099/0051.N-Queens.md" >}})|Hard| O(n!)| O(n)|❤️|55.2%|

‎website/content/ChapterTwo/Hash_Table.md

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -124,6 +124,7 @@ weight: 13
124124
|0981|Time Based Key-Value Store|[Go]({{< relref "/ChapterFour/0900~0999/0981.Time-Based-Key-Value-Store.md" >}})|Medium||||53.0%|
125125
|0987|Vertical Order Traversal of a Binary Tree|[Go]({{< relref "/ChapterFour/0900~0999/0987.Vertical-Order-Traversal-of-a-Binary-Tree.md" >}})|Hard||||40.3%|
126126
|0992|Subarrays with K Different Integers|[Go]({{< relref "/ChapterFour/0900~0999/0992.Subarrays-with-K-Different-Integers.md" >}})|Hard| O(n)| O(n) |❤️|52.9%|
127+
|0997|Find the Town Judge|[Go]({{< relref "/ChapterFour/0900~0999/0997.Find-the-Town-Judge.md" >}})|Easy||||49.9%|
127128
|1002|Find Common Characters|[Go]({{< relref "/ChapterFour/1000~1099/1002.Find-Common-Characters.md" >}})|Easy||||68.4%|
128129
|1048|Longest String Chain|[Go]({{< relref "/ChapterFour/1000~1099/1048.Longest-String-Chain.md" >}})|Medium||||57.3%|
129130
|1054|Distant Barcodes|[Go]({{< relref "/ChapterFour/1000~1099/1054.Distant-Barcodes.md" >}})|Medium||||45.0%|

‎website/content/ChapterTwo/Sliding_Window.md

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -56,7 +56,7 @@ weight: 17
5656
|1052|Grumpy Bookstore Owner|[Go]({{< relref "/ChapterFour/1000~1099/1052.Grumpy-Bookstore-Owner.md" >}})|Medium| O(n log n)| O(1) ||56.5%|
5757
|1208|Get Equal Substrings Within Budget|[Go]({{< relref "/ChapterFour/1200~1299/1208.Get-Equal-Substrings-Within-Budget.md" >}})|Medium||||45.8%|
5858
|1234|Replace the Substring for Balanced String|[Go]({{< relref "/ChapterFour/1200~1299/1234.Replace-the-Substring-for-Balanced-String.md" >}})|Medium||||35.6%|
59-
|1423|Maximum Points You Can Obtain from Cards|[Go]({{< relref "/ChapterFour/1400~1499/1423.Maximum-Points-You-Can-Obtain-from-Cards.md" >}})|Medium||||49.6%|
59+
|1423|Maximum Points You Can Obtain from Cards|[Go]({{< relref "/ChapterFour/1400~1499/1423.Maximum-Points-You-Can-Obtain-from-Cards.md" >}})|Medium||||49.5%|
6060
|1438|Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit|[Go]({{< relref "/ChapterFour/1400~1499/1438.Longest-Continuous-Subarray-With-Absolute-Diff-Less-Than-or-Equal-to-Limit.md" >}})|Medium||||45.5%|
6161
|1658|Minimum Operations to Reduce X to Zero|[Go]({{< relref "/ChapterFour/1600~1699/1658.Minimum-Operations-to-Reduce-X-to-Zero.md" >}})|Medium||||33.4%|
6262
|1695|Maximum Erasure Value|[Go]({{< relref "/ChapterFour/1600~1699/1695.Maximum-Erasure-Value.md" >}})|Medium||||52.2%|

0 commit comments

Comments
 (0)