Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly
Sign up
Appearance settings

Commit 4124938

Browse files
Merge pull request #1 from greyireland/master
merge algorithm-pattern master
2 parents d3525f5 + 5e524d2 commit 4124938

File tree

5 files changed

+69
-32
lines changed

5 files changed

+69
-32
lines changed

‎README.md

Lines changed: 25 additions & 14 deletions
Original file line numberDiff line numberDiff line change
@@ -18,28 +18,28 @@
1818

1919
### 入门篇 🐶
2020

21-
- [go 语言入门](https://github.com/greyireland/algorithm-pattern/blob/master/introduction/golang.md)
22-
- [算法快速入门](https://github.com/greyireland/algorithm-pattern/blob/master/introduction/quickstart.md)
21+
- [go 语言入门](./introduction/golang.md)
22+
- [算法快速入门](./introduction/quickstart.md)
2323

2424
### 数据结构篇 🐰
2525

26-
- [二叉树](https://github.com/greyireland/algorithm-pattern/blob/master/data_structure/binary_tree.md)
27-
- [链表](https://github.com/greyireland/algorithm-pattern/blob/master/data_structure/linked_list.md)
28-
- [栈和队列](https://github.com/greyireland/algorithm-pattern/blob/master/data_structure/stack_queue.md)
29-
- [二进制](https://github.com/greyireland/algorithm-pattern/blob/master/data_structure/binary_op.md)
26+
- [二叉树](./data_structure/binary_tree.md)
27+
- [链表](./data_structure/linked_list.md)
28+
- [栈和队列](./data_structure/stack_queue.md)
29+
- [二进制](./data_structure/binary_op.md)
3030

3131
### 基础算法篇 🐮
3232

33-
- [二分搜索](https://github.com/greyireland/algorithm-pattern/blob/master/basic_algorithm/binary_search.md)
34-
- [排序算法](https://github.com/greyireland/algorithm-pattern/blob/master/basic_algorithm/sort.md)
35-
- [动态规划](https://github.com/greyireland/algorithm-pattern/blob/master/basic_algorithm/dp.md)
33+
- [二分搜索](./basic_algorithm/binary_search.md)
34+
- [排序算法](./basic_algorithm/sort.md)
35+
- [动态规划](./basic_algorithm/dp.md)
3636

3737
### 算法思维 🦁
3838

39-
- [递归思维](https://github.com/greyireland/algorithm-pattern/blob/master/advanced_algorithm/recursion.md)
40-
- [滑动窗口思想](https://github.com/greyireland/algorithm-pattern/blob/master/advanced_algorithm/slide_window.md)
41-
- [二叉搜索树](https://github.com/greyireland/algorithm-pattern/blob/master/advanced_algorithm/binary_search_tree.md)
42-
- [回溯法](https://github.com/greyireland/algorithm-pattern/blob/master/advanced_algorithm/backtrack.md)
39+
- [递归思维](./advanced_algorithm/recursion.md)
40+
- [滑动窗口思想](./advanced_algorithm/slide_window.md)
41+
- [二叉搜索树](./advanced_algorithm/binary_search_tree.md)
42+
- [回溯法](./advanced_algorithm/backtrack.md)
4343

4444
## 心得体会
4545

@@ -85,8 +85,19 @@
8585

8686
[我看过的 100 本书](https://github.com/greyireland/awesome-programming-books-1)
8787

88-
## 后续
88+
## 更新计划
8989

9090
持续更新中,觉得还可以的话点个 **star** 收藏呀 ⭐️~
9191

9292
【 Github 】[https://github.com/greyireland/algorithm-pattern](https://github.com/greyireland/algorithm-pattern) ⭐️
93+
94+
## 完成打卡
95+
96+
完成计划之后,可以提交 Pull requests,在下面添加自己的项目仓库,完成自己的算法模板打卡呀~
97+
98+
| 完成 | 用户 | 项目地址 |
99+
| ---- | ------------------------------------------------- | ------------------------------------------------------------------- |
100+
| ✅ | [easyui](https://github.com/easyui/) | [algorithm-pattern-swift(Swift 实现)](https://github.com/easyui/algorithm-pattern-swift),[在线文档 Gitbook](https://zyj.gitbook.io/algorithm-pattern-swift/) |
101+
| ✅ | [wardseptember](https://github.com/wardseptember) | [notes(Java 实现)](https://github.com/wardseptember/notes) |
102+
| ✅ | [dashidhy](https://github.com/dashidhy) | [algorithm-pattern-python(Python 实现)](https://github.com/dashidhy/algorithm-pattern-python) |
103+
| ✅ | [binzi56](https://github.com/binzi56) | [algorithm-pattern-c(c++ 实现)](https://github.com/binzi56/algorithm-pattern-c) |

‎basic_algorithm/dp.md

Lines changed: 34 additions & 8 deletions
Original file line numberDiff line numberDiff line change
@@ -356,6 +356,7 @@ func canJump(nums []int) bool {
356356
> 你的目标是使用最少的跳跃次数到达数组的最后一个位置。
357357
358358
```go
359+
// v1动态规划(其他语言超时参考v2)
359360
func jump(nums []int) int {
360361
// 状态:f[i] 表示从起点到当前位置最小次数
361362
// 推导:f[i] = f[j],a[j]+j >=i,min(f[j]+1)
@@ -383,6 +384,26 @@ func min(a, b int) int {
383384
}
384385
```
385386

387+
```go
388+
// v2 动态规划+贪心优化
389+
func jump(nums []int) int {
390+
n:=len(nums)
391+
f := make([]int, n)
392+
f[0] = 0
393+
for i := 1; i < n; i++ {
394+
// 取第一个能跳到当前位置的点即可
395+
// 因为跳跃次数的结果集是单调递增的,所以贪心思路是正确的
396+
idx:=0
397+
for idx<n&&idx+nums[idx]<i{
398+
idx++
399+
}
400+
f[i]=f[idx]+1
401+
}
402+
return f[n-1]
403+
}
404+
405+
```
406+
386407
### [palindrome-partitioning-ii](https://leetcode-cn.com/problems/palindrome-partitioning-ii/)
387408

388409
> 给定一个字符串 _s_,将 _s_ 分割成一些子串,使每个子串都是回文串。
@@ -486,32 +507,37 @@ func wordBreak(s string, wordDict []string) bool {
486507
}
487508
f := make([]bool, len(s)+1)
488509
f[0] = true
489-
max := maxLen(wordDict)
510+
max,dict := maxLen(wordDict)
490511
for i := 1; i <= len(s); i++ {
491-
for j := i - max; j < i && j >= 0; j++ {
492-
if f[j] && inDict(s[j:i]) {
512+
l := 0
513+
if i - max > 0 {
514+
l = i - max
515+
}
516+
for j := l; j < i; j++ {
517+
if f[j] && inDict(s[j:i],dict) {
493518
f[i] = true
494-
break
519+
break
495520
}
496521
}
497522
}
498523
return f[len(s)]
499524
}
500525

501-
var dict = make(map[string]bool)
502526

503-
func maxLen(wordDict []string) int {
527+
528+
func maxLen(wordDict []string) (int,map[string]bool) {
529+
dict := make(map[string]bool)
504530
max := 0
505531
for _, v := range wordDict {
506532
dict[v] = true
507533
if len(v) > max {
508534
max = len(v)
509535
}
510536
}
511-
return max
537+
return max,dict
512538
}
513539

514-
func inDict(s string) bool {
540+
func inDict(s string,dictmap[string]bool) bool {
515541
_, ok := dict[s]
516542
return ok
517543
}

‎data_structure/binary_tree.md

Lines changed: 1 addition & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -640,9 +640,7 @@ func zigzagLevelOrder(root *TreeNode) [][]int {
640640
}
641641
func reverse(nums []int) {
642642
for i := 0; i < len(nums)/2; i++ {
643-
t := nums[i]
644-
nums[i] = nums[len(nums)-1-i]
645-
nums[len(nums)-1-i] = t
643+
nums[i], nums[len(nums)-1-i] = nums[len(nums)-1-i], nums[i]
646644
}
647645
}
648646
```

‎data_structure/linked_list.md

Lines changed: 4 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -379,7 +379,8 @@ func hasCycle(head *ListNode) bool {
379379
fast := head.Next
380380
slow := head
381381
for fast != nil && fast.Next != nil {
382-
if fast.Val == slow.Val {
382+
// 比较指针是否相等(不要使用val比较!)
383+
if fast == slow {
383384
return true
384385
}
385386
fast = fast.Next.Next
@@ -389,7 +390,7 @@ func hasCycle(head *ListNode) bool {
389390
}
390391
```
391392

392-
### [linked-list-cycle-ii](https://leetcode-cn.com/problems/https://leetcode-cn.com/problems/linked-list-cycle-ii/)
393+
### [linked-list-cycle-ii](https://leetcode-cn.com/problems/linked-list-cycle-ii/)
393394

394395
> 给定一个链表,返回链表开始入环的第一个节点。 如果链表无环,则返回 `null`。
395396
@@ -581,6 +582,6 @@ func copyRandomList(head *Node) *Node {
581582
- [ ] [sort-list](https://leetcode-cn.com/problems/sort-list/)
582583
- [ ] [reorder-list](https://leetcode-cn.com/problems/reorder-list/)
583584
- [ ] [linked-list-cycle](https://leetcode-cn.com/problems/linked-list-cycle/)
584-
- [ ] [linked-list-cycle-ii](https://leetcode-cn.com/problems/https://leetcode-cn.com/problems/linked-list-cycle-ii/)
585+
- [ ] [linked-list-cycle-ii](https://leetcode-cn.com/problems/linked-list-cycle-ii/)
585586
- [ ] [palindrome-linked-list](https://leetcode-cn.com/problems/palindrome-linked-list/)
586587
- [ ] [copy-list-with-random-pointer](https://leetcode-cn.com/problems/copy-list-with-random-pointer/)

‎data_structure/stack_queue.md

Lines changed: 5 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -83,8 +83,9 @@ func (this *MinStack) GetMin() int {
8383

8484
[evaluate-reverse-polish-notation](https://leetcode-cn.com/problems/evaluate-reverse-polish-notation/)
8585

86-
> **波兰表达式计算** > **输入:** ["2", "1", "+", "3", "*"] > **输出:** 9
87-
> **解释:** ((2 + 1) \* 3) = 9
86+
> **波兰表达式计算** > **输入:** `["2", "1", "+", "3", "*"]` > **输出:** 9
87+
>
88+
> **解释:** `((2 + 1) * 3) = 9`
8889
8990
思路:通过栈保存原来的元素,遇到表达式弹出运算,再推入结果,重复这个过程
9091

@@ -100,7 +101,7 @@ func evalRPN(tokens []string) int {
100101
if len(stack)<2{
101102
return -1
102103
}
103-
// 注意:a为除数,b为被除数
104+
// 注意:a为被除数,b为除数
104105
b:=stack[len(stack)-1]
105106
a:=stack[len(stack)-2]
106107
stack=stack[:len(stack)-2]
@@ -513,7 +514,7 @@ func updateMatrix(matrix [][]int) [][]int {
513514
## 总结
514515

515516
- 熟悉栈的使用场景
516-
- 后出先出,保存临时值
517+
- 后入先出,保存临时值
517518
- 利用栈 DFS 深度搜索
518519
- 熟悉队列的使用场景
519520
- 利用队列 BFS 广度搜索

0 commit comments

Comments
(0)

AltStyle によって変換されたページ (->オリジナル) /