Skip to content

Commit 5e49c8d

Browse files
novahenovahe
committed
Merge branch 'master' of https://github.com/halfrost/LeetCode-Go 
2 parents daa7c7f + 2189396 commit 5e49c8d

File tree

225 files changed

+10848
-3101
lines changed

Some content is hidden

Large Commits have some content hidden by default. Use the searchbox below for content that may be hidden.

225 files changed

+10848
-3101
lines changed

‎README.md

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

‎ctl/label.go

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -18,7 +18,7 @@ var (
1818
chapterOneFileOrder = []string{"_index", "Data_Structure", "Algorithm", "Time_Complexity"}
1919
chapterOneMenuOrder = []string{"_index", "#关于作者", "Data_Structure", "Algorithm", "Time_Complexity"}
2020
chapterTwoFileOrder = []string{"_index", "Array", "String", "Two_Pointers", "Linked_List", "Stack", "Tree", "Dynamic_Programming", "Backtracking", "Depth_First_Search", "Breadth_First_Search",
21-
"Binary_Search", "Math", "Hash_Table", "Sort", "Bit_Manipulation", "Union_Find", "Sliding_Window", "Segment_Tree", "Binary_Indexed_Tree"}
21+
"Binary_Search", "Math", "Hash_Table", "Sorting", "Bit_Manipulation", "Union_Find", "Sliding_Window", "Segment_Tree", "Binary_Indexed_Tree"}
2222
chapterThreeFileOrder = []string{"_index", "Segment_Tree", "UnionFind", "LRUCache", "LFUCache"}
2323
preNextHeader = "----------------------------------------------\n<div style=\"display: flex;justify-content: space-between;align-items: center;\">\n"
2424
preNextFotter = "</div>"
@@ -55,7 +55,7 @@ var (
5555
"Binary_Search": "2.11 Binary Search",
5656
"Math": "2.12 Math",
5757
"Hash_Table": "2.13 Hash Table",
58-
"Sort": "2.14 ✅ Sort",
58+
"Sorting": "2.14 ✅ Sorting",
5959
"Bit_Manipulation": "2.15 ✅ Bit Manipulation",
6060
"Union_Find": "2.16 ✅ Union Find",
6161
"Sliding_Window": "2.17 ✅ Sliding Window",

‎ctl/meta/Sort renamed to ‎ctl/meta/Sorting

File renamed without changes.

‎ctl/models/mdrow.go

Lines changed: 28 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -18,15 +18,38 @@ type Mdrow struct {
1818

1919
// GenerateMdRows define
2020
func GenerateMdRows(solutionIds []int, mdrows []Mdrow) {
21+
mdMap := map[int]Mdrow{}
22+
for _, row := range mdrows {
23+
mdMap[int(row.FrontendQuestionID)] = row
24+
}
2125
for i := 0; i < len(solutionIds); i++ {
22-
id := mdrows[solutionIds[i]-1].FrontendQuestionID
23-
if solutionIds[i] == int(id) {
24-
//fmt.Printf("id = %v i = %v solutionIds = %v\n", id, i, solutionIds[i])
25-
mdrows[id-1].SolutionPath = fmt.Sprintf("[Go](https://github.com/halfrost/LeetCode-Go/tree/master/leetcode/%v)", fmt.Sprintf("%04d.%v", id, strings.Replace(strings.TrimSpace(mdrows[id-1].QuestionTitle), " ", "-", -1)))
26+
if row, ok := mdMap[solutionIds[i]]; ok {
27+
s7 := standardizedTitle(row.QuestionTitle, row.FrontendQuestionID)
28+
mdMap[solutionIds[i]] = Mdrow{
29+
FrontendQuestionID: row.FrontendQuestionID,
30+
QuestionTitle: strings.TrimSpace(row.QuestionTitle),
31+
QuestionTitleSlug: row.QuestionTitleSlug,
32+
SolutionPath: fmt.Sprintf("[Go](https://github.com/halfrost/LeetCode-Go/tree/master/leetcode/%v)", fmt.Sprintf("%04d.%v", solutionIds[i], s7)),
33+
Acceptance: row.Acceptance,
34+
Difficulty: row.Difficulty,
35+
Frequency: row.Frequency,
36+
}
2637
} else {
27-
fmt.Printf("序号出错了 solutionIds = %v id = %v\n", solutionIds[i], id)
38+
fmt.Printf("序号不存在 len(solutionIds) = %v len(mdrows) = %v len(solutionIds) = %v solutionIds[i] = %v QuestionTitle = %v\n", len(solutionIds), len(mdrows), len(solutionIds), solutionIds[i], mdrows[solutionIds[i]-1].QuestionTitle)
39+
}
40+
}
41+
for i := range mdrows {
42+
mdrows[i] = Mdrow{
43+
FrontendQuestionID: mdrows[i].FrontendQuestionID,
44+
QuestionTitle: strings.TrimSpace(mdrows[i].QuestionTitle),
45+
QuestionTitleSlug: mdrows[i].QuestionTitleSlug,
46+
SolutionPath: mdMap[int(mdrows[i].FrontendQuestionID)].SolutionPath,
47+
Acceptance: mdrows[i].Acceptance,
48+
Difficulty: mdrows[i].Difficulty,
49+
Frequency: mdrows[i].Frequency,
2850
}
2951
}
52+
// fmt.Printf("mdrows = %v\n\n", mdrows)
3053
}
3154

3255
// | 0001 | Two Sum | [Go](https://github.com/halfrost/LeetCode-Go/tree/master/leetcode/0001.Two-Sum)| 45.6% | Easy | |

‎ctl/models/tagproblem.go

Lines changed: 36 additions & 30 deletions
Original file line numberDiff line numberDiff line change
@@ -115,6 +115,41 @@ func (t TagList) tableLine() string {
115115
return fmt.Sprintf("|%04d|%v|%v|%v|%v|%v|%v|%v|\n", t.FrontendQuestionID, t.QuestionTitle, t.SolutionPath, t.Difficulty, t.TimeComplexity, t.SpaceComplexity, t.Favorite, t.Acceptance)
116116
}
117117

118+
func standardizedTitle(orig string, frontendQuestionID int32) string {
119+
s0 := strings.TrimSpace(orig)
120+
s1 := strings.Replace(s0, " ", "-", -1)
121+
s2 := strings.Replace(s1, "'", "", -1)
122+
s3 := strings.Replace(s2, "%", "", -1)
123+
s4 := strings.Replace(s3, "(", "", -1)
124+
s5 := strings.Replace(s4, ")", "", -1)
125+
s6 := strings.Replace(s5, ",", "", -1)
126+
s7 := strings.Replace(s6, "?", "", -1)
127+
count := 0
128+
// 去掉 --- 这种情况，这种情况是由于题目标题中包含 - ，左右有空格，左右一填充，造成了 ---，3 个 -
129+
for i := 0; i < len(s7)-2; i++ {
130+
if s7[i] == '-' && s7[i+1] == '-' && s7[i+2] == '-' {
131+
fmt.Printf("【需要修正 --- 的标题是 %v】\n", fmt.Sprintf("%04d.%v", int(frontendQuestionID), s7))
132+
s7 = s7[:i+1] + s7[i+3:]
133+
count++
134+
}
135+
}
136+
if count > 0 {
137+
fmt.Printf("总共修正了 %v 个标题\n", count)
138+
}
139+
// 去掉 -- 这种情况，这种情况是由于题目标题中包含负号 -
140+
for i := 0; i < len(s7)-2; i++ {
141+
if s7[i] == '-' && s7[i+1] == '-' {
142+
fmt.Printf("【需要修正 -- 的标题是 %v】\n", fmt.Sprintf("%04d.%v", int(frontendQuestionID), s7))
143+
s7 = s7[:i+1] + s7[i+2:]
144+
count++
145+
}
146+
}
147+
if count > 0 {
148+
fmt.Printf("总共修正了 %v 个标题\n", count)
149+
}
150+
return s7
151+
}
152+
118153
// GenerateTagMdRows define
119154
func GenerateTagMdRows(solutionIds []int, metaMap map[int]TagList, mdrows []Mdrow, internal bool) []TagList {
120155
tl := []TagList{}
@@ -123,36 +158,7 @@ func GenerateTagMdRows(solutionIds []int, metaMap map[int]TagList, mdrows []Mdro
123158
tmp := TagList{}
124159
tmp.FrontendQuestionID = row.FrontendQuestionID
125160
tmp.QuestionTitle = strings.TrimSpace(row.QuestionTitle)
126-
s1 := strings.Replace(tmp.QuestionTitle, " ", "-", -1)
127-
s2 := strings.Replace(s1, "'", "", -1)
128-
s3 := strings.Replace(s2, "%", "", -1)
129-
s4 := strings.Replace(s3, "(", "", -1)
130-
s5 := strings.Replace(s4, ")", "", -1)
131-
s6 := strings.Replace(s5, ",", "", -1)
132-
s7 := strings.Replace(s6, "?", "", -1)
133-
count := 0
134-
// 去掉 --- 这种情况，这种情况是由于题目标题中包含 - ，左右有空格，左右一填充，造成了 ---，3 个 -
135-
for i := 0; i < len(s7)-2; i++ {
136-
if s7[i] == '-' && s7[i+1] == '-' && s7[i+2] == '-' {
137-
fmt.Printf("【需要修正 --- 的标题是 %v】\n", fmt.Sprintf("%04d.%v", int(row.FrontendQuestionID), s7))
138-
s7 = s7[:i+1] + s7[i+3:]
139-
count++
140-
}
141-
}
142-
if count > 0 {
143-
fmt.Printf("总共修正了 %v 个标题\n", count)
144-
}
145-
// 去掉 -- 这种情况，这种情况是由于题目标题中包含负号 -
146-
for i := 0; i < len(s7)-2; i++ {
147-
if s7[i] == '-' && s7[i+1] == '-' {
148-
fmt.Printf("【需要修正 -- 的标题是 %v】\n", fmt.Sprintf("%04d.%v", int(row.FrontendQuestionID), s7))
149-
s7 = s7[:i+1] + s7[i+2:]
150-
count++
151-
}
152-
}
153-
if count > 0 {
154-
fmt.Printf("总共修正了 %v 个标题\n", count)
155-
}
161+
s7 := standardizedTitle(row.QuestionTitle, row.FrontendQuestionID)
156162
if internal {
157163
tmp.SolutionPath = fmt.Sprintf("[Go]({{< relref \"/ChapterFour/%v/%v.md\" >}})", util.GetChpaterFourFileNum(int(row.FrontendQuestionID)), fmt.Sprintf("%04d.%v", int(row.FrontendQuestionID), s7))
158164
} else {

‎ctl/render.go

Lines changed: 3 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -18,11 +18,11 @@ import (
1818

1919
var (
2020
chapterTwoList = []string{"Array", "String", "Two Pointers", "Linked List", "Stack", "Tree", "Dynamic Programming", "Backtracking", "Depth First Search", "Breadth First Search",
21-
"Binary Search", "Math", "Hash Table", "Sort", "Bit Manipulation", "Union Find", "Sliding Window", "Segment Tree", "Binary Indexed Tree"}
21+
"Binary Search", "Math", "Hash Table", "Sorting", "Bit Manipulation", "Union Find", "Sliding Window", "Segment Tree", "Binary Indexed Tree"}
2222
chapterTwoFileName = []string{"Array", "String", "Two_Pointers", "Linked_List", "Stack", "Tree", "Dynamic_Programming", "Backtracking", "Depth_First_Search", "Breadth_First_Search",
23-
"Binary_Search", "Math", "Hash_Table", "Sort", "Bit_Manipulation", "Union_Find", "Sliding_Window", "Segment_Tree", "Binary_Indexed_Tree"}
23+
"Binary_Search", "Math", "Hash_Table", "Sorting", "Bit_Manipulation", "Union_Find", "Sliding_Window", "Segment_Tree", "Binary_Indexed_Tree"}
2424
chapterTwoSlug = []string{"array", "string", "two-pointers", "linked-list", "stack", "tree", "dynamic-programming", "backtracking", "depth-first-search", "breadth-first-search",
25-
"binary-search", "math", "hash-table", "sort", "bit-manipulation", "union-find", "sliding-window", "segment-tree", "binary-indexed-tree"}
25+
"binary-search", "math", "hash-table", "sorting", "bit-manipulation", "union-find", "sliding-window", "segment-tree", "binary-indexed-tree"}
2626
)
2727

2828
func newBuildCommand() *cobra.Command {

‎ctl/template/Sort.md renamed to ‎ctl/template/Sorting.md

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -1,10 +1,10 @@
11
---
2-
title: 2.14 ✅ Sort
2+
title: 2.14 ✅ Sorting
33
type: docs
44
weight: 14
55
---
66

7-
# Sort
7+
# Sorting
88

99
![](https://img.halfrost.com/Leetcode/Sort.png)
1010

‎leetcode/0016.3Sum-Closest/16. 3Sum Closest.go

Lines changed: 3 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -11,6 +11,9 @@ func threeSumClosest(nums []int, target int) int {
1111
if n > 2 {
1212
sort.Ints(nums)
1313
for i := 0; i < n-2; i++ {
14+
if i > 0 && nums[i] == nums[i-1] {
15+
continue
16+
}
1417
for j, k := i+1, n-1; j < k; {
1518
sum := nums[i] + nums[j] + nums[k]
1619
if abs(sum-target) < diff {

‎leetcode/0018.4Sum/18. 4Sum.go

Lines changed: 86 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -2,7 +2,92 @@ package leetcode
22

33
import "sort"
44

5-
func fourSum(nums []int, target int) [][]int {
5+
// 解法一 双指针
6+
func fourSum(nums []int, target int) (quadruplets [][]int) {
7+
sort.Ints(nums)
8+
n := len(nums)
9+
for i := 0; i < n-3 && nums[i]+nums[i+1]+nums[i+2]+nums[i+3] <= target; i++ {
10+
if i > 0 && nums[i] == nums[i-1] || nums[i]+nums[n-3]+nums[n-2]+nums[n-1] < target {
11+
continue
12+
}
13+
for j := i + 1; j < n-2 && nums[i]+nums[j]+nums[j+1]+nums[j+2] <= target; j++ {
14+
if j > i+1 && nums[j] == nums[j-1] || nums[i]+nums[j]+nums[n-2]+nums[n-1] < target {
15+
continue
16+
}
17+
for left, right := j+1, n-1; left < right; {
18+
if sum := nums[i] + nums[j] + nums[left] + nums[right]; sum == target {
19+
quadruplets = append(quadruplets, []int{nums[i], nums[j], nums[left], nums[right]})
20+
for left++; left < right && nums[left] == nums[left-1]; left++ {
21+
}
22+
for right--; left < right && nums[right] == nums[right+1]; right-- {
23+
}
24+
} else if sum < target {
25+
left++
26+
} else {
27+
right--
28+
}
29+
}
30+
}
31+
}
32+
return
33+
}
34+
35+
// 解法二 kSum
36+
func fourSum1(nums []int, target int) [][]int {
37+
res, cur := make([][]int, 0), make([]int, 0)
38+
sort.Ints(nums)
39+
kSum(nums, 0, len(nums)-1, target, 4, cur, &res)
40+
return res
41+
}
42+
43+
func kSum(nums []int, left, right int, target int, k int, cur []int, res *[][]int) {
44+
if right-left+1 < k || k < 2 || target < nums[left]*k || target > nums[right]*k {
45+
return
46+
}
47+
if k == 2 {
48+
// 2 sum
49+
twoSum(nums, left, right, target, cur, res)
50+
} else {
51+
for i := left; i < len(nums); i++ {
52+
if i == left || (i > left && nums[i-1] != nums[i]) {
53+
next := make([]int, len(cur))
54+
copy(next, cur)
55+
next = append(next, nums[i])
56+
kSum(nums, i+1, len(nums)-1, target-nums[i], k-1, next, res)
57+
}
58+
}
59+
}
60+
61+
}
62+
63+
func twoSum(nums []int, left, right int, target int, cur []int, res *[][]int) {
64+
for left < right {
65+
sum := nums[left] + nums[right]
66+
if sum == target {
67+
cur = append(cur, nums[left], nums[right])
68+
temp := make([]int, len(cur))
69+
copy(temp, cur)
70+
*res = append(*res, temp)
71+
// reset cur to previous state
72+
cur = cur[:len(cur)-2]
73+
left++
74+
right--
75+
for left < right && nums[left] == nums[left-1] {
76+
left++
77+
}
78+
for left < right && nums[right] == nums[right+1] {
79+
right--
80+
}
81+
} else if sum < target {
82+
left++
83+
} else {
84+
right--
85+
}
86+
}
87+
}
88+
89+
// 解法三
90+
func fourSum2(nums []int, target int) [][]int {
691
res := [][]int{}
792
counter := map[int]int{}
893
for _, value := range nums {

‎leetcode/0065.Valid-Number/65. Valid Number.go

Lines changed: 22 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,22 @@
1+
package leetcode
2+
3+
func isNumber(s string) bool {
4+
numFlag, dotFlag, eFlag := false, false, false
5+
for i := 0; i < len(s); i++ {
6+
if '0' <= s[i] && s[i] <= '9' {
7+
numFlag = true
8+
} else if s[i] == '.' && !dotFlag && !eFlag {
9+
dotFlag = true
10+
} else if (s[i] == 'e' || s[i] == 'E') && !eFlag && numFlag {
11+
eFlag = true
12+
numFlag = false // reJudge integer after 'e' or 'E'
13+
} else if (s[i] == '+' || s[i] == '-') && (i == 0 || s[i-1] == 'e' || s[i-1] == 'E') {
14+
continue
15+
} else {
16+
return false
17+
}
18+
}
19+
// avoid case: s == '.' or 'e/E' or '+/-' and etc...
20+
// string s must have num
21+
return numFlag
22+
}

‎leetcode/0065.Valid-Number/65. Valid Number_test.go

Lines changed: 41 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,41 @@
1+
package leetcode
2+
3+
import (
4+
"fmt"
5+
"testing"
6+
)
7+
8+
func Test_Problem65(t *testing.T) {
9+
10+
tcs := []struct {
11+
s string
12+
ans bool
13+
}{
14+
15+
{
16+
"0",
17+
true,
18+
},
19+
20+
{
21+
"e",
22+
false,
23+
},
24+
25+
{
26+
".",
27+
false,
28+
},
29+
30+
{
31+
".1",
32+
true,
33+
},
34+
}
35+
fmt.Printf("------------------------Leetcode Problem 65------------------------\n")
36+
37+
for _, tc := range tcs {
38+
fmt.Printf("【input】:%v 【output】:%v\n", tc, isNumber(tc.s))
39+
}
40+
fmt.Printf("\n\n\n")
41+
}

0 commit comments

Comments
 (0)