Skip to content

Commit 0ae1bb2

Browse files
halfrosthalfrost
committed
Add solution 1696 & ctl add build menu
1 parent ff57047 commit 0ae1bb2

28 files changed

+657
-150
lines changed

‎README.md

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

‎ctl/label.go

Lines changed: 42 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -15,6 +15,7 @@ import (
1515

1616
var (
1717
chapterOneFileOrder = []string{"_index", "Data_Structure", "Algorithm"}
18+
chapterOneMenuOrder = []string{"_index", "#关于作者", "Data_Structure", "Algorithm"}
1819
chapterTwoFileOrder = []string{"_index", "Array", "String", "Two_Pointers", "Linked_List", "Stack", "Tree", "Dynamic_Programming", "Backtracking", "Depth_First_Search", "Breadth_First_Search",
1920
"Binary_Search", "Math", "Hash_Table", "Sort", "Bit_Manipulation", "Union_Find", "Sliding_Window", "Segment_Tree", "Binary_Indexed_Tree"}
2021
chapterThreeFileOrder = []string{"_index", "Segment_Tree", "UnionFind", "LRUCache", "LFUCache"}
@@ -30,6 +31,47 @@ var (
3031

3132
//ErrInvalidLineCount is thrown when the user provided 0 (zero) as the value for number of lines to tail
3233
ErrInvalidLineCount = errors.New("You cannot tail zero lines.")
34+
35+
chapterMap = map[string]map[string]string{
36+
"ChapterOne": {
37+
"_index": "第一章 序章",
38+
"#关于作者": "1.1 关于作者",
39+
"Data_Structure": "1.2 数据结构知识",
40+
"Algorithm": "1.3 算法知识",
41+
},
42+
"ChapterTwo": {
43+
"_index": "第二章 算法专题",
44+
"Array": "2.01 Array",
45+
"String": "2.02 String",
46+
"Two_Pointers": "2.03 ✅ Two Pointers",
47+
"Linked_List": "2.04 ✅ Linked List",
48+
"Stack": "2.05 ✅ Stack",
49+
"Tree": "2.06 Tree",
50+
"Dynamic_Programming": "2.07 Dynamic Programming",
51+
"Backtracking": "2.08 ✅ Backtracking",
52+
"Depth_First_Search": "2.09 Depth First Search",
53+
"Breadth_First_Search": "2.10 Breadth First Search",
54+
"Binary_Search": "2.11 Binary Search",
55+
"Math": "2.12 Math",
56+
"Hash_Table": "2.13 Hash Table",
57+
"Sort": "2.14 ✅ Sort",
58+
"Bit_Manipulation": "2.15 ✅ Bit Manipulation",
59+
"Union_Find": "2.16 ✅ Union Find",
60+
"Sliding_Window": "2.17 ✅ Sliding Window",
61+
"Segment_Tree": "2.18 ✅ Segment Tree",
62+
"Binary_Indexed_Tree": "2.19 ✅ Binary Indexed Tree",
63+
},
64+
"ChapterThree": {
65+
"_index": "第三章 一些模板",
66+
"Segment_Tree": "3.1 Segment Tree",
67+
"UnionFind": "3.2 UnionFind",
68+
"LRUCache": "3.3 LRUCache",
69+
"LFUCache": "3.4 LFUCache",
70+
},
71+
"ChapterFour": {
72+
"_index": "第四章 Leetcode 题解",
73+
},
74+
}
3375
)
3476

3577
func getChapterFourFileOrder() []string {

‎ctl/refresh.go

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -18,6 +18,7 @@ func newRefresh() *cobra.Command {
1818
}
1919

2020
func refresh() {
21+
buildBookMenu()
2122
delPreNext()
2223
buildREADME()
2324
buildChapterTwo(true)

‎ctl/render.go

Lines changed: 102 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -33,6 +33,7 @@ func newBuildCommand() *cobra.Command {
3333
mc.AddCommand(
3434
newBuildREADME(),
3535
newBuildChapterTwo(),
36+
newBuildMenu(),
3637
)
3738
return mc
3839
}
@@ -63,6 +64,19 @@ func newBuildChapterTwo() *cobra.Command {
6364
return cmd
6465
}
6566

67+
func newBuildMenu() *cobra.Command {
68+
cmd := &cobra.Command{
69+
Use: "menu",
70+
Short: "Build Menu commands",
71+
Run: func(cmd *cobra.Command, args []string) {
72+
buildBookMenu()
73+
},
74+
}
75+
// cmd.Flags().StringVar(&alias, "alias", "", "alias")
76+
// cmd.Flags().StringVar(&appId, "appid", "", "appid")
77+
return cmd
78+
}
79+
6680
func buildREADME() {
6781
var (
6882
problems []m.StatStatusPairs
@@ -87,7 +101,7 @@ func buildREADME() {
87101
}
88102
mdrows := m.ConvertMdModelFromSsp(problems)
89103
sort.Sort(m.SortByQuestionID(mdrows))
90-
solutionIds, try := util.LoadSolutionsDir()
104+
solutionIds, _, try := util.LoadSolutionsDir()
91105
m.GenerateMdRows(solutionIds, mdrows)
92106
info.EasyTotal, info.MediumTotal, info.HardTotal, info.OptimizingEasy, info.OptimizingMedium, info.OptimizingHard, optimizingIds = statisticalData(problemsMap, solutionIds)
93107
omdrows := m.ConvertMdModelFromIds(problemsMap, optimizingIds)
@@ -166,7 +180,7 @@ func buildChapterTwo(internal bool) {
166180
questions = gr.Data.TopicTag.Questions
167181
mdrows := m.ConvertMdModelFromQuestions(questions)
168182
sort.Sort(m.SortByQuestionID(mdrows))
169-
solutionIds, _ := util.LoadSolutionsDir()
183+
solutionIds, _, _ := util.LoadSolutionsDir()
170184
tl, err := loadMetaData(fmt.Sprintf("./meta/%v", chapterTwoFileName[index]))
171185
if err != nil {
172186
fmt.Printf("err = %v\n", err)
@@ -247,3 +261,89 @@ func renderChapterTwo(filePath string, tls m.TagLists) ([]byte, error) {
247261
}
248262
}
249263
}
264+
265+
func buildBookMenu() {
266+
solutionIds, soName, _ := util.LoadSolutionsDir()
267+
ch4Ids, _ := util.LoadChapterFourIds()
268+
269+
needCopy := []string{}
270+
for i := 0; i < len(solutionIds); i++ {
271+
if util.BinarySearch(ch4Ids, solutionIds[i]) == -1 {
272+
needCopy = append(needCopy, soName[i])
273+
}
274+
}
275+
if len(needCopy) > 0 {
276+
fmt.Printf("有 %v 道题需要拷贝到第四章中\n", len(needCopy))
277+
for i := 0; i < len(needCopy); i++ {
278+
util.CopyFile(fmt.Sprintf("../website/content/ChapterFour/%v.md", needCopy[i]), fmt.Sprintf("../leetcode/%v/README.md", needCopy[i]))
279+
}
280+
} else {
281+
fmt.Printf("【第四章没有需要添加的题解，已经完整了】\n")
282+
}
283+
284+
// 按照模板重新渲染 Menu
285+
res, err := renderBookMenu("./template/menu.md")
286+
if err != nil {
287+
fmt.Println(err)
288+
return
289+
}
290+
util.WriteFile("../website/content/menu/index.md", res)
291+
fmt.Println("generate Menu successful")
292+
}
293+
294+
func generateMenu() string {
295+
res := ""
296+
res += menuLine(chapterOneMenuOrder, "ChapterOne")
297+
res += menuLine(chapterTwoFileOrder, "ChapterTwo")
298+
res += menuLine(chapterThreeFileOrder, "ChapterThree")
299+
res += menuLine(getChapterFourFileOrder(), "ChapterFour")
300+
return res
301+
}
302+
303+
func menuLine(order []string, chapter string) string {
304+
res := ""
305+
for i := 0; i < len(order); i++ {
306+
if i == 1 && chapter == "ChapterOne" {
307+
res += fmt.Sprintf(" - [%v]({{< relref \"/%v/%v\" >}})\n", chapterMap[chapter][order[i]], chapter, order[i])
308+
continue
309+
}
310+
if i == 0 {
311+
res += fmt.Sprintf("- [%v]({{< relref \"/%v/%v.md\" >}})\n", chapterMap[chapter][order[i]], chapter, order[i])
312+
} else {
313+
if chapter == "ChapterFour" {
314+
res += fmt.Sprintf(" - [%v]({{< relref \"/%v/%v.md\" >}})\n", order[i], chapter, order[i])
315+
} else {
316+
res += fmt.Sprintf(" - [%v]({{< relref \"/%v/%v.md\" >}})\n", chapterMap[chapter][order[i]], chapter, order[i])
317+
}
318+
}
319+
}
320+
return res
321+
}
322+
323+
func renderBookMenu(filePath string) ([]byte, error) {
324+
f, err := os.OpenFile(filePath, os.O_RDONLY, 0644)
325+
if err != nil {
326+
return nil, err
327+
}
328+
defer f.Close()
329+
reader, output := bufio.NewReader(f), []byte{}
330+
331+
for {
332+
line, _, err := reader.ReadLine()
333+
if err != nil {
334+
if err == io.EOF {
335+
return output, nil
336+
}
337+
return nil, err
338+
}
339+
if ok, _ := regexp.Match("{{.BookMenu}}", line); ok {
340+
reg := regexp.MustCompile("{{.BookMenu}}")
341+
newByte := reg.ReplaceAll(line, []byte(generateMenu()))
342+
output = append(output, newByte...)
343+
output = append(output, []byte("\n")...)
344+
} else {
345+
output = append(output, line...)
346+
output = append(output, []byte("\n")...)
347+
}
348+
}
349+
}

‎ctl/template/menu.md

Lines changed: 9 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,9 @@
1+
---
2+
headless: true
3+
---
4+
5+
<hr>
6+
7+
{{.BookMenu}}
8+
9+
<br />

‎ctl/util/util.go

Lines changed: 23 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -13,24 +13,42 @@ import (
1313
)
1414

1515
// LoadSolutionsDir define
16-
func LoadSolutionsDir() ([]int, int) {
17-
files, err := ioutil.ReadDir("../leetcode/")
16+
func LoadSolutionsDir() ([]int, []string, int) {
17+
solutionIds, soNames, total := loadFile("../leetcode/")
18+
fmt.Printf("读取了 %v 道题的题解，当前目录下有 %v 个文件(可能包含 .DS_Store)，目录中有 %v 道题在尝试中\n", len(solutionIds), total, total-len(solutionIds))
19+
return solutionIds, soNames, total - len(solutionIds)
20+
}
21+
22+
// LoadChapterFourIds define
23+
func LoadChapterFourIds() ([]int, []string) {
24+
solutionIds, soNames, _ := loadFile("../website/content/ChapterFour/")
25+
fmt.Printf("读取了第四章 %v 道题的题解\n", len(solutionIds))
26+
return solutionIds, soNames
27+
}
28+
29+
func loadFile(path string) ([]int, []string, int) {
30+
files, err := ioutil.ReadDir(path)
1831
if err != nil {
1932
fmt.Println(err)
2033
}
21-
solutionIds := []int{}
34+
solutionIds, soNames, solutionsMap := []int{}, []string{}, map[int]string{}
2235
for _, f := range files {
2336
if f.Name()[4] == '.' {
2437
tmp, err := strconv.Atoi(f.Name()[:4])
2538
if err != nil {
2639
fmt.Println(err)
2740
}
2841
solutionIds = append(solutionIds, tmp)
42+
solutionsMap[tmp] = f.Name()
2943
}
3044
}
3145
sort.Ints(solutionIds)
32-
fmt.Printf("读取了 %v 道题的题解，当前目录下有 %v 个文件(可能包含 .DS_Store)，目录中有 %v 道题在尝试中\n", len(solutionIds), len(files), len(files)-len(solutionIds))
33-
return solutionIds, len(files) - len(solutionIds)
46+
for _, v := range solutionIds {
47+
if name, ok := solutionsMap[v]; ok {
48+
soNames = append(soNames, name)
49+
}
50+
}
51+
return solutionIds, soNames, len(files)
3452
}
3553

3654
// LoadChapterFourDir define

‎leetcode/1696.Jump-Game-VI/1696. Jump Game VI.go

Lines changed: 53 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,53 @@
1+
package leetcode
2+
3+
import (
4+
"math"
5+
)
6+
7+
// 单调队列
8+
func maxResult(nums []int, k int) int {
9+
dp := make([]int, len(nums))
10+
dp[0] = nums[0]
11+
for i := 1; i < len(dp); i++ {
12+
dp[i] = math.MinInt32
13+
}
14+
window := make([]int, k)
15+
for i := 1; i < len(nums); i++ {
16+
dp[i] = nums[i] + dp[window[0]]
17+
for len(window) > 0 && dp[window[len(window)-1]] <= dp[i] {
18+
window = window[:len(window)-1]
19+
}
20+
for len(window) > 0 && i-k >= window[0] {
21+
window = window[1:]
22+
}
23+
window = append(window, i)
24+
}
25+
return dp[len(nums)-1]
26+
}
27+
28+
// 超时
29+
func maxResult1(nums []int, k int) int {
30+
dp := make([]int, len(nums))
31+
if k > len(nums) {
32+
k = len(nums)
33+
}
34+
dp[0] = nums[0]
35+
for i := 1; i < len(dp); i++ {
36+
dp[i] = math.MinInt32
37+
}
38+
for i := 1; i < len(nums); i++ {
39+
left, tmp := max(0, i-k), math.MinInt32
40+
for j := left; j < i; j++ {
41+
tmp = max(tmp, dp[j])
42+
}
43+
dp[i] = nums[i] + tmp
44+
}
45+
return dp[len(nums)-1]
46+
}
47+
48+
func max(a, b int) int {
49+
if a > b {
50+
return a
51+
}
52+
return b
53+
}

‎leetcode/1696.Jump-Game-VI/1696. Jump Game VI_test.go

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

0 commit comments

Comments
 (0)