Skip to content

Commit 3bd8dd1

Browse files
halfrosthalfrost
committed
Add solution 0821
1 parent 8d2a341 commit 3bd8dd1

File tree

15 files changed

+309
-77
lines changed

15 files changed

+309
-77
lines changed

‎README.md

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

‎leetcode/0643.Maximum-Average-Subarray-I/README.md

Lines changed: 1 addition & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -1,10 +1,4 @@
1-
# 643. Maximum Average Subarray I
2-
3-
Added By: halfrost
4-
Created Time: Feb 7, 2021 5:07 PM
5-
Difficulty: Easy
6-
Link: https://leetcode.com/problems/maximum-average-subarray-i/
7-
Tags: Array
1+
# [643. Maximum Average Subarray I](https://leetcode.com/problems/maximum-average-subarray-i/)
82

93
## 题目
104

‎leetcode/0821.Shortest-Distance-to-a-Character/821. Shortest Distance to a Character.go

Lines changed: 37 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,37 @@
1+
package leetcode
2+
3+
import (
4+
"math"
5+
)
6+
7+
func shortestToChar(s string, c byte) []int {
8+
res := make([]int, len(s))
9+
for i := 0; i < len(s); i++ {
10+
if s[i] == c {
11+
res[i] = 0
12+
} else {
13+
left, right := math.MaxInt32, math.MaxInt32
14+
for j := i + 1; j < len(s); j++ {
15+
if s[j] == c {
16+
right = j - i
17+
break
18+
}
19+
}
20+
for k := i - 1; k >= 0; k-- {
21+
if s[k] == c {
22+
left = i - k
23+
break
24+
}
25+
}
26+
res[i] = min(left, right)
27+
}
28+
}
29+
return res
30+
}
31+
32+
func min(a, b int) int {
33+
if a > b {
34+
return b
35+
}
36+
return a
37+
}

‎leetcode/0821.Shortest-Distance-to-a-Character/821. Shortest Distance to a Character_test.go

Lines changed: 48 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,48 @@
1+
package leetcode
2+
3+
import (
4+
"fmt"
5+
"testing"
6+
)
7+
8+
type question821 struct {
9+
para821
10+
ans821
11+
}
12+
13+
// para 是参数
14+
// one 代表第一个参数
15+
type para821 struct {
16+
s string
17+
c byte
18+
}
19+
20+
// ans 是答案
21+
// one 代表第一个答案
22+
type ans821 struct {
23+
one []int
24+
}
25+
26+
func Test_Problem821(t *testing.T) {
27+
28+
qs := []question821{
29+
30+
{
31+
para821{"loveleetcode", 'e'},
32+
ans821{[]int{3, 2, 1, 0, 1, 0, 0, 1, 2, 2, 1, 0}},
33+
},
34+
35+
{
36+
para821{"baaa", 'b'},
37+
ans821{[]int{0, 1, 2, 3}},
38+
},
39+
}
40+
41+
fmt.Printf("------------------------Leetcode Problem 821------------------------\n")
42+
43+
for _, q := range qs {
44+
_, p := q.ans821, q.para821
45+
fmt.Printf("【input】:%v 【output】:%v\n", p, shortestToChar(p.s, p.c))
46+
}
47+
fmt.Printf("\n\n\n")
48+
}

‎leetcode/0821.Shortest-Distance-to-a-Character/README.md

Lines changed: 76 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,76 @@
1+
# [821. Shortest Distance to a Character](https://leetcode.com/problems/shortest-distance-to-a-character/)
2+
3+
4+
## 题目
5+
6+
Given a string `s` and a character `c` that occurs in `s`, return *an array of integers `answer` where* `answer.length == s.length` *and* `answer[i]` *is the shortest distance from* `s[i]` *to the character* `c` *in* `s`.
7+
8+
**Example 1:**
9+
10+
```
11+
Input: s = "loveleetcode", c = "e"
12+
Output: [3,2,1,0,1,0,0,1,2,2,1,0]
13+
```
14+
15+
**Example 2:**
16+
17+
```
18+
Input: s = "aaab", c = "b"
19+
Output: [3,2,1,0]
20+
```
21+
22+
**Constraints:**
23+
24+
- `1 <= s.length <= 104`
25+
- `s[i]` and `c` are lowercase English letters.
26+
- `c` occurs at least once in `s`.
27+
28+
## 题目大意
29+
30+
给定一个字符串 S 和一个字符 C。返回一个代表字符串 S 中每个字符到字符串 S 中的字符 C 的最短距离的数组。
31+
32+
## 解题思路
33+
34+
- 简单题。依次扫描字符串 S，针对每一个非字符 C 的字符，分别往左扫一次，往右扫一次，计算出距离目标字符 C 的距离，然后取左右两个距离的最小值存入最终答案数组中。
35+
36+
## 代码
37+
38+
```go
39+
package leetcode
40+
41+
import (
42+
"math"
43+
)
44+
45+
func shortestToChar(s string, c byte) []int {
46+
res := make([]int, len(s))
47+
for i := 0; i < len(s); i++ {
48+
if s[i] == c {
49+
res[i] = 0
50+
} else {
51+
left, right := math.MaxInt32, math.MaxInt32
52+
for j := i + 1; j < len(s); j++ {
53+
if s[j] == c {
54+
right = j - i
55+
break
56+
}
57+
}
58+
for k := i - 1; k >= 0; k-- {
59+
if s[k] == c {
60+
left = i - k
61+
break
62+
}
63+
}
64+
res[i] = min(left, right)
65+
}
66+
}
67+
return res
68+
}
69+
70+
func min(a, b int) int {
71+
if a > b {
72+
return b
73+
}
74+
return a
75+
}
76+
```

‎website/content/ChapterFour/0600~0699/0643.Maximum-Average-Subarray-I.md

Lines changed: 1 addition & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -1,10 +1,4 @@
1-
# 643. Maximum Average Subarray I
2-
3-
Added By: halfrost
4-
Created Time: Feb 7, 2021 5:07 PM
5-
Difficulty: Easy
6-
Link: https://leetcode.com/problems/maximum-average-subarray-i/
7-
Tags: Array
1+
# [643. Maximum Average Subarray I](https://leetcode.com/problems/maximum-average-subarray-i/)
82

93
## 题目
104

‎website/content/ChapterFour/0800~0899/0819.Most-Common-Word.md

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -92,5 +92,5 @@ func mostCommonWord(paragraph string, banned []string) string {
9292
----------------------------------------------
9393
<div style="display: flex;justify-content: space-between;align-items: center;">
9494
<p><a href="https://books.halfrost.com/leetcode/ChapterFour/0800~0899/0817.Linked-List-Components/">⬅️上一页</a></p>
95-
<p><a href="https://books.halfrost.com/leetcode/ChapterFour/0800~0899/0826.Most-Profit-Assigning-Work/">下一页➡️</a></p>
95+
<p><a href="https://books.halfrost.com/leetcode/ChapterFour/0800~0899/0821.Shortest-Distance-to-a-Character/">下一页➡️</a></p>
9696
</div>

‎website/content/ChapterFour/0800~0899/0821.Shortest-Distance-to-a-Character.md

Lines changed: 83 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,83 @@
1+
# [821. Shortest Distance to a Character](https://leetcode.com/problems/shortest-distance-to-a-character/)
2+
3+
4+
## 题目
5+
6+
Given a string `s` and a character `c` that occurs in `s`, return *an array of integers `answer` where* `answer.length == s.length` *and* `answer[i]` *is the shortest distance from* `s[i]` *to the character* `c` *in* `s`.
7+
8+
**Example 1:**
9+
10+
```
11+
Input: s = "loveleetcode", c = "e"
12+
Output: [3,2,1,0,1,0,0,1,2,2,1,0]
13+
```
14+
15+
**Example 2:**
16+
17+
```
18+
Input: s = "aaab", c = "b"
19+
Output: [3,2,1,0]
20+
```
21+
22+
**Constraints:**
23+
24+
- `1 <= s.length <= 104`
25+
- `s[i]` and `c` are lowercase English letters.
26+
- `c` occurs at least once in `s`.
27+
28+
## 题目大意
29+
30+
给定一个字符串 S 和一个字符 C。返回一个代表字符串 S 中每个字符到字符串 S 中的字符 C 的最短距离的数组。
31+
32+
## 解题思路
33+
34+
- 简单题。依次扫描字符串 S，针对每一个非字符 C 的字符，分别往左扫一次，往右扫一次，计算出距离目标字符 C 的距离，然后取左右两个距离的最小值存入最终答案数组中。
35+
36+
## 代码
37+
38+
```go
39+
package leetcode
40+
41+
import (
42+
"math"
43+
)
44+
45+
func shortestToChar(s string, c byte) []int {
46+
res := make([]int, len(s))
47+
for i := 0; i < len(s); i++ {
48+
if s[i] == c {
49+
res[i] = 0
50+
} else {
51+
left, right := math.MaxInt32, math.MaxInt32
52+
for j := i + 1; j < len(s); j++ {
53+
if s[j] == c {
54+
right = j - i
55+
break
56+
}
57+
}
58+
for k := i - 1; k >= 0; k-- {
59+
if s[k] == c {
60+
left = i - k
61+
break
62+
}
63+
}
64+
res[i] = min(left, right)
65+
}
66+
}
67+
return res
68+
}
69+
70+
func min(a, b int) int {
71+
if a > b {
72+
return b
73+
}
74+
return a
75+
}
76+
```
77+
78+
79+
----------------------------------------------
80+
<div style="display: flex;justify-content: space-between;align-items: center;">
81+
<p><a href="https://books.halfrost.com/leetcode/ChapterFour/0800~0899/0819.Most-Common-Word/">⬅️上一页</a></p>
82+
<p><a href="https://books.halfrost.com/leetcode/ChapterFour/0800~0899/0826.Most-Profit-Assigning-Work/">下一页➡️</a></p>
83+
</div>

‎website/content/ChapterFour/0800~0899/0826.Most-Profit-Assigning-Work.md

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -109,6 +109,6 @@ func maxProfitAssignment(difficulty []int, profit []int, worker []int) int {
109109

110110
----------------------------------------------
111111
<div style="display: flex;justify-content: space-between;align-items: center;">
112-
<p><a href="https://books.halfrost.com/leetcode/ChapterFour/0800~0899/0819.Most-Common-Word/">⬅️上一页</a></p>
112+
<p><a href="https://books.halfrost.com/leetcode/ChapterFour/0800~0899/0821.Shortest-Distance-to-a-Character/">⬅️上一页</a></p>
113113
<p><a href="https://books.halfrost.com/leetcode/ChapterFour/0800~0899/0828.Count-Unique-Characters-of-All-Substrings-of-a-Given-String/">下一页➡️</a></p>
114114
</div>

‎website/content/ChapterTwo/Array.md

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -91,7 +91,7 @@ weight: 1
9191
|0729|My Calendar I|[Go]({{< relref "/ChapterFour/0700~0799/0729.My-Calendar-I.md" >}})|Medium||||53.2%|
9292
|0746|Min Cost Climbing Stairs|[Go]({{< relref "/ChapterFour/0700~0799/0746.Min-Cost-Climbing-Stairs.md" >}})|Easy| O(n)| O(1)||50.9%|
9393
|0766|Toeplitz Matrix|[Go]({{< relref "/ChapterFour/0700~0799/0766.Toeplitz-Matrix.md" >}})|Easy| O(n)| O(1)||65.8%|
94-
|0830|Positions of Large Groups|[Go]({{< relref "/ChapterFour/0800~0899/0830.Positions-of-Large-Groups.md" >}})|Easy||||50.3%|
94+
|0830|Positions of Large Groups|[Go]({{< relref "/ChapterFour/0800~0899/0830.Positions-of-Large-Groups.md" >}})|Easy||||50.4%|
9595
|0832|Flipping an Image|[Go]({{< relref "/ChapterFour/0800~0899/0832.Flipping-an-Image.md" >}})|Easy||||78.1%|
9696
|0867|Transpose Matrix|[Go]({{< relref "/ChapterFour/0800~0899/0867.Transpose-Matrix.md" >}})|Easy| O(n)| O(1)||62.1%|
9797
|0888|Fair Candy Swap|[Go]({{< relref "/ChapterFour/0800~0899/0888.Fair-Candy-Swap.md" >}})|Easy||||58.9%|

‎website/content/ChapterTwo/Backtracking.md

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -133,7 +133,7 @@ func updateMatrix_BFS(matrix [][]int) [][]int {
133133
|1641|Count Sorted Vowel Strings|[Go]({{< relref "/ChapterFour/1600~1699/1641.Count-Sorted-Vowel-Strings.md" >}})|Medium||||77.0%|
134134
|1655|Distribute Repeating Integers|[Go]({{< relref "/ChapterFour/1600~1699/1655.Distribute-Repeating-Integers.md" >}})|Hard||||40.5%|
135135
|1659|Maximize Grid Happiness|[Go]({{< relref "/ChapterFour/1600~1699/1659.Maximize-Grid-Happiness.md" >}})|Hard||||35.5%|
136-
|1681|Minimum Incompatibility|[Go]({{< relref "/ChapterFour/1600~1699/1681.Minimum-Incompatibility.md" >}})|Hard||||35.3%|
136+
|1681|Minimum Incompatibility|[Go]({{< relref "/ChapterFour/1600~1699/1681.Minimum-Incompatibility.md" >}})|Hard||||35.4%|
137137
|1688|Count of Matches in Tournament|[Go]({{< relref "/ChapterFour/1600~1699/1688.Count-of-Matches-in-Tournament.md" >}})|Easy||||82.7%|
138138
|------------|-------------------------------------------------------|-------| ----------------| ---------------|-------------|-------------|-------------|
139139

‎website/content/ChapterTwo/Breadth_First_Search.md

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -10,7 +10,7 @@ weight: 10
1010
| No. | Title | Solution | Difficulty | TimeComplexity | SpaceComplexity |Favorite| Acceptance |
1111
|:--------:|:------- | :--------: | :----------: | :----: | :-----: | :-----: |:-----: |
1212
|0101|Symmetric Tree|[Go]({{< relref "/ChapterFour/0100~0199/0101.Symmetric-Tree.md" >}})|Easy| O(n)| O(1)||48.0%|
13-
|0102|Binary Tree Level Order Traversal|[Go]({{< relref "/ChapterFour/0100~0199/0102.Binary-Tree-Level-Order-Traversal.md" >}})|Medium| O(n)| O(1)||56.4%|
13+
|0102|Binary Tree Level Order Traversal|[Go]({{< relref "/ChapterFour/0100~0199/0102.Binary-Tree-Level-Order-Traversal.md" >}})|Medium| O(n)| O(1)||56.5%|
1414
|0103|Binary Tree Zigzag Level Order Traversal|[Go]({{< relref "/ChapterFour/0100~0199/0103.Binary-Tree-Zigzag-Level-Order-Traversal.md" >}})|Medium| O(n)| O(n)||50.0%|
1515
|0107|Binary Tree Level Order Traversal II|[Go]({{< relref "/ChapterFour/0100~0199/0107.Binary-Tree-Level-Order-Traversal-II.md" >}})|Easy| O(n)| O(1)||55.1%|
1616
|0111|Minimum Depth of Binary Tree|[Go]({{< relref "/ChapterFour/0100~0199/0111.Minimum-Depth-of-Binary-Tree.md" >}})|Easy| O(n)| O(1)||39.4%|

‎website/content/ChapterTwo/Segment_Tree.md

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -43,7 +43,7 @@ weight: 18
4343
|0327|Count of Range Sum|[Go]({{< relref "/ChapterFour/0300~0399/0327.Count-of-Range-Sum.md" >}})|Hard| O(n log n)| O(n)|❤️|36.0%|
4444
|0493|Reverse Pairs|[Go]({{< relref "/ChapterFour/0400~0499/0493.Reverse-Pairs.md" >}})|Hard| O(n log n)| O(n)||26.7%|
4545
|0699|Falling Squares|[Go]({{< relref "/ChapterFour/0600~0699/0699.Falling-Squares.md" >}})|Hard| O(n log n)| O(n)|❤️|42.5%|
46-
|0715|Range Module|[Go]({{< relref "/ChapterFour/0700~0799/0715.Range-Module.md" >}})|Hard| O(log n)| O(n)|❤️|40.2%|
46+
|0715|Range Module|[Go]({{< relref "/ChapterFour/0700~0799/0715.Range-Module.md" >}})|Hard| O(log n)| O(n)|❤️|40.1%|
4747
|0732|My Calendar III|[Go]({{< relref "/ChapterFour/0700~0799/0732.My-Calendar-III.md" >}})|Hard| O(log n)| O(n)|❤️|61.6%|
4848
|0850|Rectangle Area II|[Go]({{< relref "/ChapterFour/0800~0899/0850.Rectangle-Area-II.md" >}})|Hard| O(n log n)| O(n)|❤️|48.3%|
4949
|1157|Online Majority Element In Subarray|[Go]({{< relref "/ChapterFour/1100~1199/1157.Online-Majority-Element-In-Subarray.md" >}})|Hard| O(log n)| O(n)|❤️|39.6%|

‎website/content/ChapterTwo/Stack.md

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -29,7 +29,7 @@ weight: 5
2929
|0155|Min Stack|[Go]({{< relref "/ChapterFour/0100~0199/0155.Min-Stack.md" >}})|Easy| O(n)| O(n)||46.2%|
3030
|0173|Binary Search Tree Iterator|[Go]({{< relref "/ChapterFour/0100~0199/0173.Binary-Search-Tree-Iterator.md" >}})|Medium| O(n)| O(1)||59.9%|
3131
|0224|Basic Calculator|[Go]({{< relref "/ChapterFour/0200~0299/0224.Basic-Calculator.md" >}})|Hard| O(n)| O(n)||38.1%|
32-
|0225|Implement Stack using Queues|[Go]({{< relref "/ChapterFour/0200~0299/0225.Implement-Stack-using-Queues.md" >}})|Easy| O(n)| O(n)||47.1%|
32+
|0225|Implement Stack using Queues|[Go]({{< relref "/ChapterFour/0200~0299/0225.Implement-Stack-using-Queues.md" >}})|Easy| O(n)| O(n)||47.2%|
3333
|0232|Implement Queue using Stacks|[Go]({{< relref "/ChapterFour/0200~0299/0232.Implement-Queue-using-Stacks.md" >}})|Easy| O(n)| O(n)||51.9%|
3434
|0331|Verify Preorder Serialization of a Binary Tree|[Go]({{< relref "/ChapterFour/0300~0399/0331.Verify-Preorder-Serialization-of-a-Binary-Tree.md" >}})|Medium| O(n)| O(1)||40.9%|
3535
|0385|Mini Parser|[Go]({{< relref "/ChapterFour/0300~0399/0385.Mini-Parser.md" >}})|Medium||||34.5%|
@@ -53,7 +53,7 @@ weight: 5
5353
|0946|Validate Stack Sequences|[Go]({{< relref "/ChapterFour/0900~0999/0946.Validate-Stack-Sequences.md" >}})|Medium| O(n)| O(n)||63.6%|
5454
|1003|Check If Word Is Valid After Substitutions|[Go]({{< relref "/ChapterFour/1000~1099/1003.Check-If-Word-Is-Valid-After-Substitutions.md" >}})|Medium| O(n)| O(1)||56.3%|
5555
|1019|Next Greater Node In Linked List|[Go]({{< relref "/ChapterFour/1000~1099/1019.Next-Greater-Node-In-Linked-List.md" >}})|Medium| O(n)| O(1)||58.2%|
56-
|1021|Remove Outermost Parentheses|[Go]({{< relref "/ChapterFour/1000~1099/1021.Remove-Outermost-Parentheses.md" >}})|Easy| O(n)| O(1)||78.8%|
56+
|1021|Remove Outermost Parentheses|[Go]({{< relref "/ChapterFour/1000~1099/1021.Remove-Outermost-Parentheses.md" >}})|Easy| O(n)| O(1)||78.9%|
5757
|1047|Remove All Adjacent Duplicates In String|[Go]({{< relref "/ChapterFour/1000~1099/1047.Remove-All-Adjacent-Duplicates-In-String.md" >}})|Easy| O(n)| O(1)||70.5%|
5858
|1673|Find the Most Competitive Subsequence|[Go]({{< relref "/ChapterFour/1600~1699/1673.Find-the-Most-Competitive-Subsequence.md" >}})|Medium||||45.2%|
5959
|------------|-------------------------------------------------------|-------| ----------------| ---------------|-------------|-------------|-------------|

‎website/content/ChapterTwo/Tree.md

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -16,7 +16,7 @@ weight: 6
1616
|0099|Recover Binary Search Tree|[Go]({{< relref "/ChapterFour/0001~0099/0099.Recover-Binary-Search-Tree.md" >}})|Hard| O(n)| O(1)||42.3%|
1717
|0100|Same Tree|[Go]({{< relref "/ChapterFour/0100~0199/0100.Same-Tree.md" >}})|Easy| O(n)| O(1)||54.1%|
1818
|0101|Symmetric Tree|[Go]({{< relref "/ChapterFour/0100~0199/0101.Symmetric-Tree.md" >}})|Easy| O(n)| O(1)||48.0%|
19-
|0102|Binary Tree Level Order Traversal|[Go]({{< relref "/ChapterFour/0100~0199/0102.Binary-Tree-Level-Order-Traversal.md" >}})|Medium| O(n)| O(1)||56.4%|
19+
|0102|Binary Tree Level Order Traversal|[Go]({{< relref "/ChapterFour/0100~0199/0102.Binary-Tree-Level-Order-Traversal.md" >}})|Medium| O(n)| O(1)||56.5%|
2020
|0103|Binary Tree Zigzag Level Order Traversal|[Go]({{< relref "/ChapterFour/0100~0199/0103.Binary-Tree-Zigzag-Level-Order-Traversal.md" >}})|Medium| O(n)| O(n)||50.0%|
2121
|0104|Maximum Depth of Binary Tree|[Go]({{< relref "/ChapterFour/0100~0199/0104.Maximum-Depth-of-Binary-Tree.md" >}})|Easy| O(n)| O(1)||67.9%|
2222
|0105|Construct Binary Tree from Preorder and Inorder Traversal|[Go]({{< relref "/ChapterFour/0100~0199/0105.Construct-Binary-Tree-from-Preorder-and-Inorder-Traversal.md" >}})|Medium||||51.5%|

0 commit comments

Comments
 (0)