Skip to content

Commit 5a5325b

Browse files
chefyuanchefyuan
authored
Merge pull request chefyuan#44 from ZouXinyao/main
添加Go语言题解
2 parents 7eb8b4a + 575b761 commit 5a5325b

52 files changed

Lines changed: 1679 additions & 104 deletions

File tree

Some content is hidden

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

‎animation-simulation/二分查找及其变种/leetcode 81不完全有序查找目标元素(包含重复值) .md‎

Lines changed: 32 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -73,3 +73,35 @@ class Solution {
7373
}
7474
}
7575
```
76+
77+
Go Code:
78+
79+
```go
80+
func search(nums []int, target int) bool {
81+
l, r := 0, len(nums) - 1
82+
for l <= r {
83+
m := l + (r - l) / 2
84+
if nums[m] == target {
85+
return true
86+
}
87+
// 先判断哪边是递增的，再查找范围
88+
if nums[m] == nums[l] {
89+
l++
90+
} else if nums[l] < nums[m] {
91+
// 判断target是否在有序的那边就行了。
92+
if nums[l] <= target && target < nums[m] {
93+
r = m - 1
94+
} else {
95+
l = m + 1
96+
}
97+
} else if nums[l] > nums[m] {
98+
if nums[m] < target && target <= nums[r] {
99+
l = m + 1
100+
} else {
101+
r = m - 1
102+
}
103+
}
104+
}
105+
return false
106+
}
107+
```

‎animation-simulation/二分查找及其变种/leetcode153搜索旋转数组的最小值.md‎

Lines changed: 20 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -104,3 +104,23 @@ public:
104104
}
105105
};
106106
```
107+
108+
Go Code:
109+
110+
```go
111+
func findMin(nums []int) int {
112+
l, r := 0, len(nums) - 1
113+
for l < r {
114+
if nums[l] < nums[r] {
115+
return nums[l]
116+
}
117+
m := l + (r - l) / 2
118+
if nums[l] > nums[m] {
119+
r = m
120+
} else {
121+
l = m + 1
122+
}
123+
}
124+
return nums[l]
125+
}
126+
```

‎animation-simulation/二分查找及其变种/leetcode33不完全有序查找目标元素(不包含重复值).md‎

Lines changed: 31 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -127,4 +127,34 @@ class Solution {
127127
}
128128
```
129129

130-
##
130+
Go Code:
131+
132+
```go
133+
func search(nums []int, target int) int {
134+
l, r := 0, len(nums) - 1
135+
for l <= r {
136+
m := (l + r) / 2
137+
if target == nums[m] {
138+
return m
139+
}
140+
// 先判断哪边是有序的
141+
if nums[m] < nums[r] {
142+
// 再判断target在左右哪边
143+
if target > nums[m] && target <= nums[r] {
144+
l = m + 1
145+
} else {
146+
r = m - 1
147+
}
148+
} else {
149+
if target < nums[m] && target >= nums[l] {
150+
r = m - 1
151+
} else {
152+
l = m + 1
153+
}
154+
}
155+
}
156+
return -1
157+
}
158+
```
159+
160+
##

‎animation-simulation/二分查找及其变种/leetcode34查找第一个位置和最后一个位置.md‎

Lines changed: 42 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -166,3 +166,45 @@ class Solution {
166166
}
167167
}
168168
```
169+
170+
Go Code:
171+
172+
```go
173+
func searchRange(nums []int, target int) []int {
174+
upper := upperBound(nums, target)
175+
lower := lowerBound(nums, target)
176+
177+
if (upper < lower) {
178+
return []int{-1, -1}
179+
}
180+
return []int{lower, upper}
181+
}
182+
183+
// upperBound 计算上边界
184+
func upperBound(nums []int, target int) int {
185+
l, r := 0, len(nums) - 1
186+
for l <= r {
187+
m := l + (r - l) / 2
188+
if target >= nums[m] {
189+
l = m + 1
190+
} else if target < nums[m] {
191+
r = m - 1
192+
}
193+
}
194+
return r
195+
}
196+
197+
// lowerBound 计算下边界
198+
func lowerBound(nums []int, target int) int {
199+
l, r := 0, len(nums) - 1
200+
for l <= r {
201+
m := l + (r - l) / 2
202+
if target <= nums[m] {
203+
r = m - 1
204+
} else if target > nums[m] {
205+
l = m + 1
206+
}
207+
}
208+
return l
209+
}
210+
```

‎animation-simulation/二分查找及其变种/leetcode35搜索插入位置.md‎

Lines changed: 25 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -1,8 +1,8 @@
1-
> 如果阅读时，发现错误，或者动画不可以显示的问题可以添加我微信好友 **[tan45du_one](https://raw.githubusercontent.com/tan45du/tan45du.github.io/master/个人微信.15egrcgqd94w.jpg)** ，备注 github + 题目 + 问题 向我反馈
1+
> 如果阅读时，发现错误，或者动画不可以显示的问题可以添加我微信好友 **[tan45du_one](https://raw.githubusercontent.com/tan45du/tan45du.github.io/master/个人微信.15egrcgqd94w.jpg)** ，备注 github + 题目 + 问题 向我反馈
22
>
33
> 感谢支持，该仓库会一直维护，希望对各位有一丢丢帮助。
44
>
5-
> 另外希望手机阅读的同学可以来我的 <u>[**公众号：袁厨的算法小屋**](https://raw.githubusercontent.com/tan45du/test/master/微信图片_20210320152235.2pthdebvh1c0.png)</u> 两个平台同步，想要和题友一起刷题，互相监督的同学，可以在我的小屋点击<u>[**刷题小队**](https://raw.githubusercontent.com/tan45du/test/master/微信图片_20210320152235.2pthdebvh1c0.png)</u>进入。
5+
> 另外希望手机阅读的同学可以来我的 <u>[**公众号：袁厨的算法小屋**](https://raw.githubusercontent.com/tan45du/test/master/微信图片_20210320152235.2pthdebvh1c0.png)</u> 两个平台同步，想要和题友一起刷题，互相监督的同学，可以在我的小屋点击<u>[**刷题小队**](https://raw.githubusercontent.com/tan45du/test/master/微信图片_20210320152235.2pthdebvh1c0.png)</u>进入。
66
77
#### [35. 搜索插入位置](https://leetcode-cn.com/problems/search-insert-position/)
88

@@ -52,10 +52,10 @@ class Solution {
5252
//查询成功
5353
if (target == nums[mid]) {
5454
return mid;
55-
//右区间
55+
//右区间
5656
} else if (nums[mid] < target) {
57-
left = mid + 1;
58-
//左区间
57+
left = mid + 1;
58+
//左区间
5959
} else if (nums[mid] > target) {
6060
right = mid - 1;
6161
}
@@ -65,3 +65,23 @@ class Solution {
6565
}
6666
}
6767
```
68+
69+
Go Code:
70+
71+
```go
72+
func searchInsert(nums []int, target int) int {
73+
l, r := 0, len(nums) - 1
74+
for l <= r {
75+
m := l + (r - l) / 2
76+
if target == nums[m] {
77+
return m
78+
}
79+
if target < nums[m] {
80+
r = m - 1
81+
} else if target > nums[m] {
82+
l = m + 1
83+
}
84+
}
85+
return l
86+
}
87+
```

‎animation-simulation/二分查找及其变种/二维数组的二分查找.md‎

Lines changed: 27 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -83,3 +83,30 @@ class Solution {
8383
}
8484
}
8585
```
86+
87+
Go Code:
88+
89+
```go
90+
func searchMatrix(matrix [][]int, target int) bool {
91+
if len(matrix) == 0 {
92+
return false
93+
}
94+
row, col := len(matrix), len(matrix[0])
95+
// 将二维数组拉平为一维。
96+
l, r := 0, row * col - 1
97+
for l <= r {
98+
m := l + (r - l) / 2
99+
// 将一维的坐标转换为二维
100+
x, y := m / col, m % col
101+
if matrix[x][y] == target {
102+
return true
103+
} else if matrix[x][y] < target {
104+
l = m + 1
105+
} else if matrix[x][y] > target {
106+
// 二分查找时，把所有的情况都要写出来，避免直接else
107+
r = m - 1
108+
}
109+
}
110+
return false
111+
}
112+
```

‎animation-simulation/二叉树/二叉树中序遍历（迭代）.md‎

Lines changed: 29 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -34,7 +34,7 @@ class Solution {
3434
TreeNode cur = new TreeNode(-1);
3535
cur = root;
3636
Stack<TreeNode> stack = new Stack<>();
37-
while (!stack.isEmpty() || cur != null) {
37+
while (!stack.isEmpty() || cur != null) {
3838
//找到当前应该遍历的那个节点
3939
while (cur != null) {
4040
stack.push(cur);
@@ -47,7 +47,7 @@ class Solution {
4747
cur = temp.right;
4848
}
4949
return arr;
50-
}
50+
}
5151
}
5252
```
5353

@@ -78,4 +78,30 @@ class Solution {
7878
}
7979
```
8080

81-
###
81+
Go Code:
82+
83+
```go
84+
func inorderTraversal(root *TreeNode) []int {
85+
res := []int{}
86+
if root == nil {
87+
return res
88+
}
89+
stk := []*TreeNode{}
90+
cur := root
91+
for len(stk) != 0 || cur != nil {
92+
// 找到当前应该遍历的那个节点，并且把左子节点都入栈
93+
for cur != nil {
94+
stk = append(stk, cur)
95+
cur = cur.Left
96+
}
97+
// 没有左子节点，则开始执行出栈操作
98+
temp := stk[len(stk) - 1]
99+
stk = stk[: len(stk) - 1]
100+
res = append(res, temp.Val)
101+
cur = temp.Right
102+
}
103+
return res
104+
}
105+
```
106+
107+
###

‎animation-simulation/二叉树/二叉树基础.md‎

Lines changed: 28 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -426,6 +426,34 @@ class Solution {
426426
}
427427
```
428428

429+
Go Code:
430+
431+
```go
432+
func levelOrder(root *TreeNode) [][]int {
433+
res := [][]int{}
434+
if root == nil {
435+
return res
436+
}
437+
// 初始化队列时，记得把root节点加进去。
438+
que := []*TreeNode{root}
439+
for len(que) != 0 {
440+
t := []int{}
441+
// 这里一定要先求出来que的长度，因为在迭代的过程中，que的长度是变化的。
442+
l := len(que)
443+
for i := 0; i < l; i++ {
444+
temp := que[0]
445+
que = que[1:]
446+
// 子节点不为空，就入队
447+
if temp.Left != nil { que = append(que, temp.Left) }
448+
if temp.Right != nil { que = append(que, temp.Right) }
449+
t = append(t, temp.Val)
450+
}
451+
res = append(res, t)
452+
}
453+
return res
454+
}
455+
```
456+
429457
时间复杂度：O（n） 空间复杂度：O（n）
430458

431459
大家如果吃透了二叉树的层序遍历的话，可以顺手把下面几道题目解决掉，思路一致，甚至都不用拐弯

‎animation-simulation/二叉树/二叉树的前序遍历(栈).md‎

Lines changed: 26 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -49,10 +49,10 @@ class Solution {
4949
public List<Integer> preorderTraversal(TreeNode root) {
5050
List<Integer> list = new ArrayList<>();
5151
Stack<TreeNode> stack = new Stack<>();
52-
if (root == null) return list;
52+
if (root == null) return list;
5353
stack.push(root);
5454
while (!stack.isEmpty()) {
55-
TreeNode temp = stack.pop();
55+
TreeNode temp = stack.pop();
5656
if (temp.right != null) {
5757
stack.push(temp.right);
5858
}
@@ -95,3 +95,27 @@ class Solution {
9595
}
9696
}
9797
```
98+
99+
Go Code:
100+
101+
```go
102+
func preorderTraversal(root *TreeNode) []int {
103+
res := []int{}
104+
if root == nil {
105+
return res
106+
}
107+
stk := []*TreeNode{root}
108+
for len(stk) != 0 {
109+
temp := stk[len(stk) - 1]
110+
stk = stk[: len(stk) - 1]
111+
if temp.Right != nil {
112+
stk = append(stk, temp.Right)
113+
}
114+
if temp.Left != nil {
115+
stk = append(stk, temp.Left)
116+
}
117+
res = append(res, temp.Val)
118+
}
119+
return res
120+
}
121+
```

‎animation-simulation/二叉树/二叉树的后续遍历 (迭代).md‎

Lines changed: 31 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -12,7 +12,7 @@
1212

1313
我们知道后序遍历的顺序是,` 对于树中的某节点, 先遍历该节点的左子树, 再遍历其右子树, 最后遍历该节点`。
1414

15-
那么我们如何利用栈来解决呢？
15+
那么我们如何利用栈来解决呢？
1616

1717
我们直接来看动画，看动画之前，但是我们`需要带着问题看动画`，问题搞懂之后也就搞定了后序遍历。
1818

@@ -104,6 +104,36 @@ class Solution {
104104
}
105105
```
106106

107+
Go Code:
108+
109+
```go
110+
func postorderTraversal(root *TreeNode) []int {
111+
res := []int{}
112+
if root == nil {
113+
return res
114+
}
115+
stk := []*TreeNode{}
116+
cur := root
117+
var pre *TreeNode
118+
for len(stk) != 0 || cur != nil {
119+
for cur != nil {
120+
stk = append(stk, cur)
121+
cur = cur.Left
122+
}
123+
// 这里符合本文最后的说法，使用先获取栈顶元素但是不弹出，根据栈顶元素的情况进行响应的处理。
124+
temp := stk[len(stk) - 1]
125+
if temp.Right == nil || temp.Right == pre {
126+
stk = stk[: len(stk) - 1]
127+
res = append(res, temp.Val)
128+
pre = temp
129+
} else {
130+
cur = temp.Right
131+
}
132+
}
133+
return res
134+
}
135+
```
136+
107137
当然也可以修改下代码逻辑将 `cur = stack.pop()` 改成 `cur = stack.peek()`，下面再修改一两行代码也可以实现，这里这样写是方便动画模拟，大家可以随意发挥。
108138

109139
时间复杂度 O（n）, 空间复杂度 O（n）

0 commit comments

Comments
 (0)