8000 README · kimi0230/LeetcodeGolang@ed7ebab · GitHub
[go: up one dir, main page]
Skip to content

Commit ed7ebab

Browse files
kimi0230kimi0230
committed
README
1 parent e9c9089 commit ed7ebab

File tree

5 files changed

+320
-5
lines changed

5 files changed

+320
-5
lines changed

‎Leetcode/0035.Search-Insert-Position/README.md

Lines changed: 55 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -39,4 +39,58 @@ You may assume no duplicates in the array.
3939
## 來源
4040
* https://books.halfrost.com/leetcode/ChapterFour/0001~0099/0035.Search-Insert-Position/
4141
* https://leetcode-cn.com/problems/search-insert-position/
42-
* [數組：每次遇到二分法，都是一看就會，一寫就廢](https://mp.weixin.qq.com/s/fCf5QbPDtE6SSlZ1yh_q8Q)
42+
* [數組：每次遇到二分法，都是一看就會，一寫就廢](https://mp.weixin.qq.com/s/fCf5QbPDtE6SSlZ1yh_q8Q)
43+
44+
## 解答
45+
https://github.com/kimi0230/LeetcodeGolang/blob/master/Leetcode/0035.Search-Insert-Position/Search-Insert-Position.go
46+
47+
```go
48+
package searchinsertposition
49+
50+
// 暴力解 時間複雜 O(n) 空間複雜 O(1)
51+
func SearchInsertBurst(nums []int, target int) int {
52+
for i := 0; i < len(nums); i++ {
53+ 10000
if nums[i] >= target {
54+
return i
55+
}
56+
}
57+
return len(nums)
58+
}
59+
60+
//二分法 時間複雜 O(log n) 空間複雜 O(1)
61+
func SearchInsertBisection(nums []int, target int) int {
62+
left, right := 0, len(nums)-1
63+
for left <= right {
64+
// / 防止溢出 同(left + right)/2
65+
mid := left + (right-left)>>1
66+
if nums[mid] >= target {
67+
right = mid - 1
68+
} else if nums[mid] < target {
69+
left = mid + 1
70+
} else {
71+
return mid
72+
}
73+
}
74+
// 分別處理如下四種情況
75+
// targe在所有元素之前 [0, -1]
76+
// targe等於數組中某一個元素 return middle;
77+
// targe在數組中的位置 [left, right]，return right + 1
78+
// targe在數組所有元素之後的情況 [left, right]， return right + 1
79+
return right + 1
80+
}
81+
82+
//二分法 時間複雜 O(log n) 空間複雜 O(1)
83+
func SearchInsertBisection2(nums []int, target int) int {
84+
left, right := 0, len(nums)-1
85+
for left <= right {
86+
// / 防止溢出 同(left + right)/2
87+
mid := left + (right-left)>>1
88+
if nums[mid] >= target {
89+
right = mid - 1
90+
} else {
91+
left = mid + 1
92+
}
93+
}
94+
return left
95+
}
96+
```

‎Leetcode/0046.Permutations/README.md

Lines changed: 40 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -33,4 +33,43 @@ Given a collection of **distinct** integers, return all possible permutations(
3333

3434
## 來源
3535
* https://books.halfrost.com/leetcode/ChapterFour/0001~0099/0046.Permutations/
36-
* https://leetcode-cn.com/problems/permutations/
36+
* https://leetcode-cn.com/problems/permutations/
37+
38+
## 解答
39+
https://github.com/kimi0230/LeetcodeGolang/blob/master/Leetcode/0046.Permutations/Permutations.go
40+
41+
```go
42+
package permutations
43+
44+
func Permute(nums []int) [][]int {
45+
numsLen := len(nums)
46+
if numsLen == 0 {
47+
return [][]int{}
48+
}
49+
used, path, res := make([]bool, numsLen), []int{}, [][]int{}
50+
dfs(nums, numsLen, 0, path, &used, &res)
51+
return res
52+
}
53+
54+
// dfs: 輸入數組, 數組長度, 遞迴到第幾層depth, path, 使用過的, 結果
55+
func dfs(nums []int, numsLen int, depth int, path []int, used *[]bool, res *[][]int) {
56+
if depth == numsLen {
57+
temp := make([]int, len(path))
58+
copy(temp, path)
59+
*res = append(*res, temp)
60+
return
61+
}
62+
63+
for i := 0; i < numsLen; i++ {
64+
if !(*used)[i] {
65+
// 沒使用過, 將其紀錄走過
66+
(*used)[i] = true
67+
path = append(path, nums[i])
68+
dfs(nums, numsLen, depth+1, path, used, res)
69+
path = path[:len(path)-1]
70+
// 回朔
71+
(*used)[i] = false
72+
}
73+
}
74+
}
75+
```

‎Leetcode/0053.Maximum-Subarray/README.md

Lines changed: 63 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -23,4 +23,66 @@ If you have figured out the O(*n*) solution, try coding another solution using t
2323

2424
## 來源
2525
* https://books.halfrost.com/leetcode/ChapterFour/0001~0099/0053.Maximum-Subarray/
26-
* https://leetcode-cn.com/problems/maximum-subarray/
26+
* https://leetcode-cn.com/problems/maximum-subarray/
27+
28+
## 解答
29+
https://github.com/kimi0230/LeetcodeGolang/blob/master/Leetcode/0053.Maximum-Subarray/Maximum-Subarray.go
30+
31+
```go
32+
package maximumsubarray
33+
34+
// MaxSubArrayDP : DP (dynamic programming)
35+
func MaxSubArrayDP(nums []int) int {
36+
if len(nums) == 0 {
37+
return 0
38+
}
39+
40+
if len(nums) == 1 {
41+
return nums[0]
42+
}
43+
44+
dp, res := make([]int, len(nums)), nums[0]
45+
dp[0] = nums[0]
46+
47+
for i := 1; i < len(nums); i++ {
48+
if dp[i-1] > 0 {
49+
// 前一個和是正的 繼續加下去
50+
dp[i] = nums[i] + dp[i-1]
51+
} else {
52+
// 前一個和是小於等於0 直接拿現在值取代
53+
dp[i] = nums[i]
54+
}
55+
res = max(res, dp[i])
56+
}
57+
return res
58+
}
59+
60+
// MaxSubArray1 : 模擬, 比DP快
61+
func MaxSubArray1(nums []int) int {
62+
if len(nums) == 1 {
63+
return nums[0]
64+
}
65+
66+
maxSum := 0
67+
tmp := 0
68+
for i := 0; i < len(nums); i++ {
69+
tmp += nums[i]
70+
if tmp > maxSum {
71+
maxSum = tmp
72+
}
73+
if tmp < 0 {
74+
tmp = 0
75+
}
76+
}
77+
return maxSum
78+
}
79+
80+
func max(a int, b int) int {
81+
if a > b {
82+
return a
83+
}
84+
return b
85+
}
86+
87+
//TODO: 分治法, 這個分治方法類似於「線段樹求解最長公共上升子序列問題」的pushUp操作
88+
```

‎Leetcode/0059.Spiral-Matrix-II/README.md

Lines changed: 82 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -30,4 +30,85 @@ Given a positive integer *n*, generate a square matrix filled with elements fro
3030
## 來源
3131
* https://books.halfrost.com/leetcode/ChapterFour/0001~0099/0059.Spiral-Matrix-II/
3232
* https://leetcode-cn.com/problems/spiral-matrix-ii/
33-
* [數組：這個循環可以轉懵很多人！](https://mp.weixin.qq.com/s/KTPhaeqxbMK9CxHUUgFDmg)
33+
* [數組：這個循環可以轉懵很多人！](https://mp.weixin.qq.com/s/KTPhaeqxbMK9CxHUUgFDmg)
34+
35+
## 解答
36+
https://github.com/kimi0230/LeetcodeGolang/blob/master/Leetcode/0059.Spiral-Matrix-II/Spiral-Matrix-II.go
37+
38+
```go
39+
package spiralmatrixii
40+
41+
// GenerateMatrix : 按層模擬, 時間複雜 O(n^2) 空間複雜 O(1)
42+
func GenerateMatrix(n int) [][]int {
43+
result := make([][]int, n)
44+
for i := range result {
45+
result[i] = make([]int, n)
46+
}
47+
48+
left, right, top, botton := 0, n-1, 0, n-1
49+
num := 1
50+
target := n * n
51+
52+
for num <= target {
53+
// 上層 left to right, 上層邊界++
54+
for i := left; i <= right; i++ {
55+
result[top][i] = num
56+
num++
57+
}
58+
top++
59+
60+
// 右層 top to botton , 右層邊界--
61+
for i := top; i <= botton; i++ {
62+
result[i][right] = num
63+
num++
64+
}
65+
right--
66+
67+
// 下層 right to left , 下層邊界--
68+
for i := right; i >= left; i-- {
69+
result[botton][i] = num
70+
num++
71+
}
72+
botton--
73+
74+
// 左層 botton to top, 左層邊界++
75+
for i := botton; i >= top; i-- {
76+
result[i][left] = num
77+
num++
78+
}
79+
left++
80+
}
81+
82+
return result
83+
}
84+
85+
// 模擬 : O(n)
86+
// https://books.halfrost.com/leetcode/ChapterFour/0001~0099/0059.Spiral-Matrix-II/
87+
func GenerateMatrix2(n int) [][]int {
88+
if n == 0 {
89+
return [][]int{}
90+
}
91+
if n == 1 {
92+
return [][]int{{1}}
93+
}
94+
result, visit, round, x, y, spDir := make([][]int, n), make([][]int, n), 0, 0, 0, [][]int{
95+
{0, 1}, // 朝右
96+
{1, 0}, // 朝下
97+
{0, -1}, // 朝左
98+
{-1, 0}, // 朝上
99+
}
100+
for i := 0; i < n; i++ {
101+
visit[i] = make([]int, n)
102+
result[i] = make([]int, n)
103+
}
104+
visit[x][y] = 1
105+
result[x][y] = 1
106+
107+
for i := 0; i < n*n; i++ {
108+
x += spDir[round%4][0]
109+
y += spDir[round%4][1]
110+
}
111+
112+
return result
113+
}
114+
```

‎Leetcode/0075.Sort-Colors/README.md

Lines changed: 80 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -78,4 +78,83 @@ First, iterate the array counting number of 0's, 1's, and 2's, then overwrite ar
7878

7979
## 來源
8080
* https://books.halfrost.com/leetcode/ChapterFour/0001~0099/0075.Sort-Colors/
81-
* https://leetcode-cn.com/problems/sort-colors/
81+
* https://leetcode-cn.com/problems/sort-colors/
82+
83+
## 解答
84+
https://github.com/kimi0230/LeetcodeGolang/blob/master/Leetcode/0075.Sort-Colors/0075.Sort-Colors.go
85+
86+
```go
87+
package sortcolors
88+
89+
func sortColors(nums []int) {
90+
if len(nums) == 0 {
91+
return
92+
}
93+
94+
var index0, index1, index2 = 0, 0, 0
95+
for _, num := range nums {
96+
switch num {
97+
case 0:
98+
nums[index2] = 2
99+
index2++
100+
nums[index1] = 1
101+
index1++
102+
nums[index0] = 0
103+
index0++
104+
case 1:
105+
nums[index2] = 2
106+
index2++
107+
nums[index1] = 1
108+
index1++
109+
case 2:
110+
index2++
111+
}
112+
}
113+
}
114+
115+
/*
116+
二路快排與三路快排
117+
先掌握二路快排， https://leetcode-cn.com/problems/sort-an-array/solution/golang-er-lu-kuai-pai-by-rqb-2/
118+
三路快排稍微改下即可
119+
120+
區別：
121+
二路快排，分兩部分：小於等於、大於二部分。
122+
三路快排分為，小於、等於、大於三部分。
123+
124+
三路快排：
125+
相比二路快排增加一個變量記錄相等的起始元素。
126+
假設選擇數組第一個元素作為參考元素。則起始下邊為0，即為equalHead
127+
128+
作者：hibrq
129+
链接：https://leetcode-cn.com/problems/sort-an-array/solution/golang-san-lu-kuai-pai-by-rqb-2/
130+
来源：力扣（LeetCode）
131+
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
132+
*/
133+
func sortColorsQuickSort(nums []int) {
134+
if len(nums) < 2 {
135+
return
136+
}
137+
138+
pivot := nums[0]
139+
140+
head, tail := 0, len(nums)-1
141+
i := 1
142+
equalHead := 0
143+
for head < tail {
144+
if nums[i] < pivot {
145+
nums[i], nums[equalHead] = nums[equalHead], nums[i]
146+
head++
147+
i++
148+
equalHead++
149+
} else if nums[i] == pivot {
150+
i++
151+
head++
152+
} else {
153+
nums[i], nums[tail] = nums[tail], nums[i]
154+
tail--
155+
}
156+
}
157+
sortColorsQuickSort(nums[:equalHead])
158+
sortColorsQuickSort(nums[tail+1:])
159+
}
160+
```

0 commit comments

Comments
 (0)
0