8000 Merge pull request #52 from kylesliu/develop · folai/awesome-golang-leetcode@73119a0 · GitHub
[go: up one dir, main page]
Skip to content

Commit 73119a0

Browse files
6boris6boris
authored
Merge pull request 6boris#52 from kylesliu/develop
Add 122 , 455 solution
2 parents e6e59c6 + 028bd3e commit 73119a0

File tree

6 files changed

+195
-0
lines changed

6 files changed

+195
-0
lines changed

‎src/0122.Best-Time-To-Buy-And-Sell-Stock-II/README.md

Lines changed: 38 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,38 @@
1+
# [122. Best Time to Buy and Sell Stock II][title]
2+
3+
## Description
4+
5+
Say you have an array for which the ith element is the price of a given stock on day i.
6+
7+
Design an algorithm to find the maximum profit. You may complete as many transactions as you like (i.e., buy one and sell one share of the stock multiple times).
8+
9+
10+
**Example 1:**
11+
12+
```
13+
Input: [7,1,5,3,6,4]
14+
Output: 7
15+
Explanation: Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit = 5-1 = 4.
16+
Then buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 6-3 = 3.
17+
```
18+
19+
**Example 2:**
20+
21+
```
22+
Input: [1,2,3,4,5]
23+
Output: 4
24+
Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4.
25+
Note that you cannot buy on day 1, buy on day 2 and sell 10000 them later, as you are
26+
engaging multiple transactions at the same time. You must sell before buying again.
27+
```
28+
29+
**Example 3:**
30+
31+
```
32+
Input: [7,6,4,3,1]
33+
Output: 0
34+
Explanation: In this case, no transaction is done, i.e. max profit = 0.
35+
```
36+
37+
38+
[title]: https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii/

‎src/0122.Best-Time-To-Buy-And-Sell-Stock-II/Solution.go

Lines changed: 11 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,11 @@
1+
package Solution
2+
3+
func maxProfit(prices []int) int {
4+
maxProfit := 0
5+
for i := 0; i < len(prices)-1; i++ {
6+
if prices[i] < prices[i+1] {
7+
maxProfit += (prices[i+1] - prices[i])
8+
}
9+
}
10+
return maxProfit
11+
}

‎src/0122.Best-Time-To-Buy-And-Sell-Stock-II/Solution_test.go

Lines changed: 28 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,28 @@
1+
package Solution
2+
3+
import (
4+
"reflect"
5+
"testing"
6+
)
7+
8+
func TestMaxProfit(t *testing.T) {
9+
cases := []struct {
10+
name string
11+
inputs []int
12+
expect int
13+
}{
14+
{"TestCase 1", []int{7, 1, 5, 3, 6, 4}, 7},
15+
{"TestCase 2", []int{1, 2, 3, 4, 5}, 4},
16+
{"TestCase 3", []int{7, 6, 4, 3, 1}, 0},
17+
}
18+
19+
for _, testcase := range cases {
20+
t.Run(testcase.name, func(t *testing.T) {
21+
got := maxProfit(testcase.inputs)
22+
if !reflect.DeepEqual(got, testcase.expect) {
23+
t.Fatalf("expected: %v, but got %v, with inputs : %v", testcase.expect, got, testcase.inputs)
24+
}
25+
})
26+
}
27+
28+
}

‎src/0455.Assign-Cookies/README.md

Lines changed: 48 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,48 @@
1+
# [455. Assign Cookies][title]
2+
3+
## Description
4+
5+
Given two binary strings, return their sum (also a binary string).
6+
7+
The input strings are both **non-empty** and contains only characters `1` or `0`.
8+
9+
**Example 1:**
10+
11+
```
12+
Input: a = "11", b = "1"
13+
Output: "100"
14+
```
15+
16+
**Example 2:**
17+
18+
```
19+
Input: a = "1010", b = "1011"
20+
Output: "10101"
21+
```
22+
23+
**Tags:** Math, String
24+
25+
## 题意
26+
>给你两个二进制串，求其和的二进制串。
27+
28+
## 题解
29+
30+
### 思路1
31+
> 按照小学算数那么来做，用 `carry` 表示进位，从后往前算，依次往前，每算出一位就插入到最前面即可，直到把两个二进制串都遍历完即可。
32+
33+
```go
34+
35+
```
36+
37+
### 思路2
38+
> 思路2
39+
```go
40+
41+
```
42+
43+
## 结语
44+
45+
如果你同我一样热爱数据结构、算法、LeetCode，可以关注我 GitHub 上的 LeetCode 题解：[awesome-golang-leetcode][me]
46+
47+
[title]: https://leetcode.com/problems/assign-cookies/
48+
[me]: https://github.com/kylesliu/awesome-golang-leetcode

‎src/0455.Assign-Cookies/Solution.go

Lines changed: 24 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,24 @@
1+
package Solution
2+
3+
import "sort"
4+
5+
// 先排序，然后直接贪心每一步即可
6+
// 需求 g[i] 满足s[j]
7+
func findContentChildren(g []int, s []int) int {
8+
// 排序准备使用贪心
9+
sort.Ints(g)
10+
sort.Ints(s)
11+
i := 0
12+
for j := 0; i < len(g) && j < len(s); j++ {
13+
// 第j个糖果可以满足第i个孩子
14+
if g[i] <= s[j] {
15+
i++
16+
}
17+
// 糖果已经检查完毕直接结束
18+
if j == len(s) {
19+
break
20+
}
21+
22+
}
23+
return i
24+
}

‎src/0455.Assign-Cookies/Solution_test.go

Lines changed: 46 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,46 @@
1+
package Solution
2+
3+
import (
4+
"reflect"
5+
"strconv"
6+
"testing"
7+
)
8+
9+
func TestSolution(t *testing.T) {
10+
// 测试用例
11+
cases := []struct {
12+
name string
13+
inputs [][]int
14+
expect int
15+
}{
16+
{"TestCase", [][]int{
17+
{1, 2, 3},
18+
{1, 1},
19+
}, 1},
20+
{"TestCase", [][]int{
21+
{1, 2},
22+
{1, 2, 3},
23+
}, 2},
24+
}
25+
26+
// 开始测试
27+
for i, c := range cases {
28+
t.Run(c.name+strconv.Itoa(i), func(t *testing.T) {
29+
got := findContentChildren(c.inputs[0], c.inputs[1])
30+
if !reflect.DeepEqual(got, c.expect) {
31+
t.Fatalf("expected: %v, but got: %v, with inputs: %v",
32+
c.expect, got, c.inputs)
33+
}
34+
})
35+
}
36+
}
37+
38+
// 压力测试
39+
func BenchmarkSolution(b *testing.B) {
40+
41+
}
42+
43+
// 使用案列
44+
func ExampleSolution() {
45+
46+
}

0 commit comments

Comments
 (0)
0