Skip to content

Commit 4b1db8e

Browse files
committed
Add solution 0028、2021
1 parent ea509d2 commit 4b1db8e

20 files changed

+366
-49
lines changed

README.md

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

leetcode/0028.Implement-strStr/README.md renamed to leetcode/0028.Find-the-Index-of-the-First-Occurrence-in-a-String/README.md

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,4 +1,4 @@
1-
# [28. Implement strStr()](https://leetcode.com/problems/implement-strstr/)
1+
# [28. Find the Index of the First Occurrence in a String](https://leetcode.com/problems/find-the-index-of-the-first-occurrence-in-a-string/)
22

33
## 题目
44

Lines changed: 33 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,33 @@
1+
package leetcode
2+
3+
import (
4+
"sort"
5+
)
6+
7+
type lightItem struct {
8+
index int
9+
sign int
10+
}
11+
12+
func brightestPosition(lights [][]int) int {
13+
lightMap, lightItems := map[int]int{}, []lightItem{}
14+
for _, light := range lights {
15+
lightMap[light[0]-light[1]] += 1
16+
lightMap[light[0]+light[1]+1] -= 1
17+
}
18+
for k, v := range lightMap {
19+
lightItems = append(lightItems, lightItem{index: k, sign: v})
20+
}
21+
sort.SliceStable(lightItems, func(i, j int) bool {
22+
return lightItems[i].index < lightItems[j].index
23+
})
24+
res, border, tmp := 0, 0, 0
25+
for _, v := range lightItems {
26+
tmp += v.sign
27+
if border < tmp {
28+
res = v.index
29+
border = tmp
30+
}
31+
}
32+
return res
33+
}
Lines changed: 56 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,56 @@
1+
package leetcode
2+
3+
import (
4+
"fmt"
5+
"testing"
6+
)
7+
8+
type question2021 struct {
9+
para2021
10+
ans2021
11+
}
12+
13+
// para 是参数
14+
type para2021 struct {
15+
lights [][]int
16+
}
17+
18+
// ans 是答案
19+
type ans2021 struct {
20+
ans int
21+
}
22+
23+
func Test_Problem2021(t *testing.T) {
24+
25+
qs := []question2021{
26+
27+
{
28+
para2021{[][]int{{-3, 2}, {1, 2}, {3, 3}}},
29+
ans2021{-1},
30+
},
31+
32+
{
33+
para2021{[][]int{{1, 0}, {0, 1}}},
34+
ans2021{1},
35+
},
36+
37+
{
38+
para2021{[][]int{{1, 2}}},
39+
ans2021{-1},
40+
},
41+
42+
{
43+
para2021{[][]int{{1, 1}, {2, 4}, {-1, 0}, {-3, 5}, {1, 2}}},
44+
ans2021{-1},
45+
},
46+
}
47+
48+
fmt.Printf("------------------------Leetcode Problem 2021------------------------\n")
49+
50+
for _, q := range qs {
51+
_, p := q.ans2021, q.para2021
52+
fmt.Printf("【input】:%v ", p)
53+
fmt.Printf("【output】:%v \n", brightestPosition(p.lights))
54+
}
55+
fmt.Printf("\n\n\n")
56+
}
Lines changed: 109 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,109 @@
1+
# [2021. Brightest Position on Street](https://leetcode.com/problems/brightest-position-on-street/)
2+
3+
4+
## 题目
5+
6+
A perfectly straight street is represented by a number line. The street has street lamp(s) on it and is represented by a 2D integer array `lights`. Each `lights[i] = [positioni, rangei]` indicates that there is a street lamp at position `positioni` that lights up the area from `[positioni - rangei, positioni + rangei]` (**inclusive**).
7+
8+
The **brightness** of a position `p` is defined as the number of street lamp that light up the position `p`.
9+
10+
Given `lights`, return *the **brightest** position on the street. If there are multiple brightest positions, return the **smallest** one.*
11+
12+
**Example 1:**
13+
14+
![https://assets.leetcode.com/uploads/2021/09/28/image-20210928155140-1.png](https://assets.leetcode.com/uploads/2021/09/28/image-20210928155140-1.png)
15+
16+
```
17+
Input: lights = [[-3,2],[1,2],[3,3]]
18+
Output: -1
19+
Explanation:
20+
The first street lamp lights up the area from [(-3) - 2, (-3) + 2] = [-5, -1].
21+
The second street lamp lights up the area from [1 - 2, 1 + 2] = [-1, 3].
22+
The third street lamp lights up the area from [3 - 3, 3 + 3] = [0, 6].
23+
24+
Position -1 has a brightness of 2, illuminated by the first and second street light.
25+
Positions 0, 1, 2, and 3 have a brightness of 2, illuminated by the second and third street light.
26+
Out of all these positions, -1 is the smallest, so return it.
27+
28+
```
29+
30+
**Example 2:**
31+
32+
```
33+
Input: lights = [[1,0],[0,1]]
34+
Output: 1
35+
Explanation:
36+
The first street lamp lights up the area from [1 - 0, 1 + 0] = [1, 1].
37+
The second street lamp lights up the area from [0 - 1, 0 + 1] = [-1, 1].
38+
39+
Position 1 has a brightness of 2, illuminated by the first and second street light.
40+
Return 1 because it is the brightest position on the street.
41+
42+
```
43+
44+
**Example 3:**
45+
46+
```
47+
Input: lights = [[1,2]]
48+
Output: -1
49+
Explanation:
50+
The first street lamp lights up the area from [1 - 2, 1 + 2] = [-1, 3].
51+
52+
Positions -1, 0, 1, 2, and 3 have a brightness of 1, illuminated by the first street light.
53+
Out of all these positions, -1 is the smallest, so return it.
54+
55+
```
56+
57+
**Constraints:**
58+
59+
- `1 <= lights.length <= 105`
60+
- `lights[i].length == 2`
61+
- `108 <= positioni <= 108`
62+
- `0 <= rangei <= 108`
63+
64+
## 题目大意
65+
66+
一条完全笔直的街道由一条数字线表示。街道上有路灯,由二维数据表示。每个 `lights[i] = [positioni, rangei]` 表示位置 `i` 处有一盏路灯,灯可以照亮从 `[positioni - rangei, positioni + rangei]` (含)的区域。 位置 `p` 的亮度定义为点亮位置 `p` 的路灯数量。 给定路灯,返回街道上最亮的位置。如果有多个最亮的位置,则返回最小的一个。
67+
68+
## 解题思路
69+
70+
- 先将每个路灯的起始和终点位置计算出来。这样我们得到了一堆坐标点。假设灯照亮的范围是 [A, B],那么在坐标轴上 A 坐标点处 + 1, B + 1 坐标点处 -1 。这样处理的含义是:坐标点 A 可以被一盏灯照亮,所以它照亮次数加一,坐标点 B + 1 出了灯照亮的范围了,所以照亮次数减一。那么从坐标轴坐标开始扫一遍,每次遇到 + 1 的时候就 + 1,遇到 - 1 的地方就 - 1。如此可以算出某个坐标点处,可以被灯照亮的总次数。
71+
- 需要注意的点是,题目给的测试数据可能会有单点照亮的情况,即某一盏灯只照亮一个坐标点,灯照范围为 0。同一个坐标点也可能是多个灯的起点。用一个 map 去重坐标点即可。
72+
73+
## 代码
74+
75+
```go
76+
package leetcode
77+
78+
import (
79+
"sort"
80+
)
81+
82+
type lightItem struct {
83+
index int
84+
sign int
85+
}
86+
87+
func brightestPosition(lights [][]int) int {
88+
lightMap, lightItems := map[int]int{}, []lightItem{}
89+
for _, light := range lights {
90+
lightMap[light[0]-light[1]] += 1
91+
lightMap[light[0]+light[1]+1] -= 1
92+
}
93+
for k, v := range lightMap {
94+
lightItems = append(lightItems, lightItem{index: k, sign: v})
95+
}
96+
sort.SliceStable(lightItems, func(i, j int) bool {
97+
return lightItems[i].index < lightItems[j].index
98+
})
99+
res, border, tmp := 0, 0, 0
100+
for _, v := range lightItems {
101+
tmp += v.sign
102+
if border < tmp {
103+
res = v.index
104+
border = tmp
105+
}
106+
}
107+
return res
108+
}
109+
```

website/content/ChapterFour/0001~0099/0027.Remove-Element.md

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -94,5 +94,5 @@ func removeElement(nums []int, val int) int {
9494
----------------------------------------------
9595
<div style="display: flex;justify-content: space-between;align-items: center;">
9696
<p><a href="https://books.halfrost.com/leetcode/ChapterFour/0001~0099/0026.Remove-Duplicates-from-Sorted-Array/">⬅️上一页</a></p>
97-
<p><a href="https://books.halfrost.com/leetcode/ChapterFour/0001~0099/0028.Implement-strStr/">下一页➡️</a></p>
97+
<p><a href="https://books.halfrost.com/leetcode/ChapterFour/0001~0099/0028.Find-the-Index-of-the-First-Occurrence-in-a-String/">下一页➡️</a></p>
9898
</div>

website/content/ChapterFour/0001~0099/0028.Implement-strStr.md renamed to website/content/ChapterFour/0001~0099/0028.Find-the-Index-of-the-First-Occurrence-in-a-String.md

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,4 +1,4 @@
1-
# [28. Implement strStr()](https://leetcode.com/problems/implement-strstr/)
1+
# [28. Find the Index of the First Occurrence in a String](https://leetcode.com/problems/find-the-index-of-the-first-occurrence-in-a-string/)
22

33
## 题目
44

website/content/ChapterFour/0001~0099/0029.Divide-Two-Integers.md

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -150,6 +150,6 @@ func divide1(divided int, divisor int) int {
150150

151151
----------------------------------------------
152152
<div style="display: flex;justify-content: space-between;align-items: center;">
153-
<p><a href="https://books.halfrost.com/leetcode/ChapterFour/0001~0099/0028.Implement-strStr/">⬅️上一页</a></p>
153+
<p><a href="https://books.halfrost.com/leetcode/ChapterFour/0001~0099/0028.Find-the-Index-of-the-First-Occurrence-in-a-String/">⬅️上一页</a></p>
154154
<p><a href="https://books.halfrost.com/leetcode/ChapterFour/0001~0099/0030.Substring-with-Concatenation-of-All-Words/">下一页➡️</a></p>
155155
</div>

website/content/ChapterFour/1900~1999/1984.Minimum-Difference-Between-Highest-and-Lowest-of-K-Scores.md

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -74,5 +74,5 @@ func minimumDifference(nums []int, k int) int {
7474
----------------------------------------------
7575
<div style="display: flex;justify-content: space-between;align-items: center;">
7676
<p><a href="https://books.halfrost.com/leetcode/ChapterFour/1800~1899/1877.Minimize-Maximum-Pair-Sum-in-Array/">⬅️上一页</a></p>
77-
<p><a href="https://books.halfrost.com/leetcode/ChapterFour/2000~2099/2022.Convert-1D-Array-Into-2D-Array/">下一页➡️</a></p>
77+
<p><a href="https://books.halfrost.com/leetcode/ChapterFour/2000~2099/2021.Brightest-Position-on-Street/">下一页➡️</a></p>
7878
</div>
Lines changed: 116 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,116 @@
1+
# [2021. Brightest Position on Street](https://leetcode.com/problems/brightest-position-on-street/)
2+
3+
4+
## 题目
5+
6+
A perfectly straight street is represented by a number line. The street has street lamp(s) on it and is represented by a 2D integer array `lights`. Each `lights[i] = [positioni, rangei]` indicates that there is a street lamp at position `positioni` that lights up the area from `[positioni - rangei, positioni + rangei]` (**inclusive**).
7+
8+
The **brightness** of a position `p` is defined as the number of street lamp that light up the position `p`.
9+
10+
Given `lights`, return *the **brightest** position on the street. If there are multiple brightest positions, return the **smallest** one.*
11+
12+
**Example 1:**
13+
14+
![https://assets.leetcode.com/uploads/2021/09/28/image-20210928155140-1.png](https://assets.leetcode.com/uploads/2021/09/28/image-20210928155140-1.png)
15+
16+
```
17+
Input: lights = [[-3,2],[1,2],[3,3]]
18+
Output: -1
19+
Explanation:
20+
The first street lamp lights up the area from [(-3) - 2, (-3) + 2] = [-5, -1].
21+
The second street lamp lights up the area from [1 - 2, 1 + 2] = [-1, 3].
22+
The third street lamp lights up the area from [3 - 3, 3 + 3] = [0, 6].
23+
24+
Position -1 has a brightness of 2, illuminated by the first and second street light.
25+
Positions 0, 1, 2, and 3 have a brightness of 2, illuminated by the second and third street light.
26+
Out of all these positions, -1 is the smallest, so return it.
27+
28+
```
29+
30+
**Example 2:**
31+
32+
```
33+
Input: lights = [[1,0],[0,1]]
34+
Output: 1
35+
Explanation:
36+
The first street lamp lights up the area from [1 - 0, 1 + 0] = [1, 1].
37+
The second street lamp lights up the area from [0 - 1, 0 + 1] = [-1, 1].
38+
39+
Position 1 has a brightness of 2, illuminated by the first and second street light.
40+
Return 1 because it is the brightest position on the street.
41+
42+
```
43+
44+
**Example 3:**
45+
46+
```
47+
Input: lights = [[1,2]]
48+
Output: -1
49+
Explanation:
50+
The first street lamp lights up the area from [1 - 2, 1 + 2] = [-1, 3].
51+
52+
Positions -1, 0, 1, 2, and 3 have a brightness of 1, illuminated by the first street light.
53+
Out of all these positions, -1 is the smallest, so return it.
54+
55+
```
56+
57+
**Constraints:**
58+
59+
- `1 <= lights.length <= 105`
60+
- `lights[i].length == 2`
61+
- `108 <= positioni <= 108`
62+
- `0 <= rangei <= 108`
63+
64+
## 题目大意
65+
66+
一条完全笔直的街道由一条数字线表示。街道上有路灯,由二维数据表示。每个 `lights[i] = [positioni, rangei]` 表示位置 `i` 处有一盏路灯,灯可以照亮从 `[positioni - rangei, positioni + rangei]` (含)的区域。 位置 `p` 的亮度定义为点亮位置 `p` 的路灯数量。 给定路灯,返回街道上最亮的位置。如果有多个最亮的位置,则返回最小的一个。
67+
68+
## 解题思路
69+
70+
- 先将每个路灯的起始和终点位置计算出来。这样我们得到了一堆坐标点。假设灯照亮的范围是 [A, B],那么在坐标轴上 A 坐标点处 + 1, B + 1 坐标点处 -1 。这样处理的含义是:坐标点 A 可以被一盏灯照亮,所以它照亮次数加一,坐标点 B + 1 出了灯照亮的范围了,所以照亮次数减一。那么从坐标轴坐标开始扫一遍,每次遇到 + 1 的时候就 + 1,遇到 - 1 的地方就 - 1。如此可以算出某个坐标点处,可以被灯照亮的总次数。
71+
- 需要注意的点是,题目给的测试数据可能会有单点照亮的情况,即某一盏灯只照亮一个坐标点,灯照范围为 0。同一个坐标点也可能是多个灯的起点。用一个 map 去重坐标点即可。
72+
73+
## 代码
74+
75+
```go
76+
package leetcode
77+
78+
import (
79+
"sort"
80+
)
81+
82+
type lightItem struct {
83+
index int
84+
sign int
85+
}
86+
87+
func brightestPosition(lights [][]int) int {
88+
lightMap, lightItems := map[int]int{}, []lightItem{}
89+
for _, light := range lights {
90+
lightMap[light[0]-light[1]] += 1
91+
lightMap[light[0]+light[1]+1] -= 1
92+
}
93+
for k, v := range lightMap {
94+
lightItems = append(lightItems, lightItem{index: k, sign: v})
95+
}
96+
sort.SliceStable(lightItems, func(i, j int) bool {
97+
return lightItems[i].index < lightItems[j].index
98+
})
99+
res, border, tmp := 0, 0, 0
100+
for _, v := range lightItems {
101+
tmp += v.sign
102+
if border < tmp {
103+
res = v.index
104+
border = tmp
105+
}
106+
}
107+
return res
108+
}
109+
```
110+
111+
112+
----------------------------------------------
113+
<div style="display: flex;justify-content: space-between;align-items: center;">
114+
<p><a href="https://books.halfrost.com/leetcode/ChapterFour/1900~1999/1984.Minimum-Difference-Between-Highest-and-Lowest-of-K-Scores/">⬅️上一页</a></p>
115+
<p><a href="https://books.halfrost.com/leetcode/ChapterFour/2000~2099/2022.Convert-1D-Array-Into-2D-Array/">下一页➡️</a></p>
116+
</div>

website/content/ChapterFour/2000~2099/2022.Convert-1D-Array-Into-2D-Array.md

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -79,6 +79,6 @@ func construct2DArray(original []int, m int, n int) [][]int {
7979

8080
----------------------------------------------
8181
<div style="display: flex;justify-content: space-between;align-items: center;">
82-
<p><a href="https://books.halfrost.com/leetcode/ChapterFour/1900~1999/1984.Minimum-Difference-Between-Highest-and-Lowest-of-K-Scores/">⬅️上一页</a></p>
82+
<p><a href="https://books.halfrost.com/leetcode/ChapterFour/2000~2099/2021.Brightest-Position-on-Street/">⬅️上一页</a></p>
8383
<p><a href="https://books.halfrost.com/leetcode/ChapterFour/2000~2099/2037.Minimum-Number-of-Moves-to-Seat-Everyone/">下一页➡️</a></p>
8484
</div>
Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,4 @@
1+
---
2+
bookCollapseSection: true
3+
weight: 20
4+
---

website/content/ChapterTwo/Breadth_First_Search.md

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -72,7 +72,7 @@ weight: 10
7272
|0924|Minimize Malware Spread|[Go]({{< relref "/ChapterFour/0900~0999/0924.Minimize-Malware-Spread.md" >}})|Hard||||42.1%|
7373
|0928|Minimize Malware Spread II|[Go]({{< relref "/ChapterFour/0900~0999/0928.Minimize-Malware-Spread-II.md" >}})|Hard||||42.6%|
7474
|0958|Check Completeness of a Binary Tree|[Go]({{< relref "/ChapterFour/0900~0999/0958.Check-Completeness-of-a-Binary-Tree.md" >}})|Medium||||53.8%|
75-
|0959|Regions Cut By Slashes|[Go]({{< relref "/ChapterFour/0900~0999/0959.Regions-Cut-By-Slashes.md" >}})|Medium||||69.0%|
75+
|0959|Regions Cut By Slashes|[Go]({{< relref "/ChapterFour/0900~0999/0959.Regions-Cut-By-Slashes.md" >}})|Medium||||69.1%|
7676
|0987|Vertical Order Traversal of a Binary Tree|[Go]({{< relref "/ChapterFour/0900~0999/0987.Vertical-Order-Traversal-of-a-Binary-Tree.md" >}})|Hard||||44.6%|
7777
|0993|Cousins in Binary Tree|[Go]({{< relref "/ChapterFour/0900~0999/0993.Cousins-in-Binary-Tree.md" >}})|Easy| O(n)| O(1)||54.1%|
7878
|1020|Number of Enclaves|[Go]({{< relref "/ChapterFour/1000~1099/1020.Number-of-Enclaves.md" >}})|Medium||||64.8%|

website/content/ChapterTwo/Depth_First_Search.md

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -91,7 +91,7 @@ weight: 9
9191
|0928|Minimize Malware Spread II|[Go]({{< relref "/ChapterFour/0900~0999/0928.Minimize-Malware-Spread-II.md" >}})|Hard||||42.6%|
9292
|0938|Range Sum of BST|[Go]({{< relref "/ChapterFour/0900~0999/0938.Range-Sum-of-BST.md" >}})|Easy||||85.3%|
9393
|0947|Most Stones Removed with Same Row or Column|[Go]({{< relref "/ChapterFour/0900~0999/0947.Most-Stones-Removed-with-Same-Row-or-Column.md" >}})|Medium||||57.0%|
94-
|0959|Regions Cut By Slashes|[Go]({{< relref "/ChapterFour/0900~0999/0959.Regions-Cut-By-Slashes.md" >}})|Medium||||69.0%|
94+
|0959|Regions Cut By Slashes|[Go]({{< relref "/ChapterFour/0900~0999/0959.Regions-Cut-By-Slashes.md" >}})|Medium||||69.1%|
9595
|0968|Binary Tree Cameras|[Go]({{< relref "/ChapterFour/0900~0999/0968.Binary-Tree-Cameras.md" >}})|Hard||||46.8%|
9696
|0971|Flip Binary Tree To Match Preorder Traversal|[Go]({{< relref "/ChapterFour/0900~0999/0971.Flip-Binary-Tree-To-Match-Preorder-Traversal.md" >}})|Medium||||49.9%|
9797
|0979|Distribute Coins in Binary Tree|[Go]({{< relref "/ChapterFour/0900~0999/0979.Distribute-Coins-in-Binary-Tree.md" >}})|Medium||||72.0%|

website/content/ChapterTwo/Hash_Table.md

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -152,7 +152,7 @@ weight: 13
152152
|1512|Number of Good Pairs|[Go]({{< relref "/ChapterFour/1500~1599/1512.Number-of-Good-Pairs.md" >}})|Easy||||88.2%|
153153
|1600|Throne Inheritance|[Go]({{< relref "/ChapterFour/1600~1699/1600.Throne-Inheritance.md" >}})|Medium||||63.6%|
154154
|1624|Largest Substring Between Two Equal Characters|[Go]({{< relref "/ChapterFour/1600~1699/1624.Largest-Substring-Between-Two-Equal-Characters.md" >}})|Easy||||59.0%|
155-
|1636|Sort Array by Increasing Frequency|[Go]({{< relref "/ChapterFour/1600~1699/1636.Sort-Array-by-Increasing-Frequency.md" >}})|Easy||||68.5%|
155+
|1636|Sort Array by Increasing Frequency|[Go]({{< relref "/ChapterFour/1600~1699/1636.Sort-Array-by-Increasing-Frequency.md" >}})|Easy||||68.6%|
156156
|1640|Check Array Formation Through Concatenation|[Go]({{< relref "/ChapterFour/1600~1699/1640.Check-Array-Formation-Through-Concatenation.md" >}})|Easy||||56.1%|
157157
|1656|Design an Ordered Stream|[Go]({{< relref "/ChapterFour/1600~1699/1656.Design-an-Ordered-Stream.md" >}})|Easy||||85.3%|
158158
|1657|Determine if Two Strings Are Close|[Go]({{< relref "/ChapterFour/1600~1699/1657.Determine-if-Two-Strings-Are-Close.md" >}})|Medium||||54.2%|

0 commit comments

Comments
 (0)