8000 feat: [贪心] · chenshiwei-io/leetcode@73988cf · GitHub
[go: up one dir, main page]
Skip to content

Commit 73988cf

Browse files
author
chen-shiwei
committed
feat: [贪心]
1 parent 8405b9a commit 73988cf

File tree

8 files changed

+234
-0
lines changed

8 files changed

+234
-0
lines changed

‎leetcode/1005.K次取反后最大化的数组和/largestSumAfterKNegations.go

Lines changed: 37 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,37 @@
1+
package _005_K次取反后最大化的数组和
2+
3+
import (
4+
"sort"
5+
)
6+
7+
func largestSumAfterKNegations(nums []int, k int) int {
8+
l := len(nums)
9+
sort.Slice(nums, func(i, j int) bool {
10+
a := nums[i]
11+
if nums[i] < 0 {
12+
a = nums[i] * -1
13+
}
14+
b := nums[j]
15+
if nums[j] < 0 {
16+
b = nums[j] * -1
17+
}
18+
return a > b
19+
})
20+
var ans int
21+
for i := 0; i < len(nums); i++ {
22+
if nums[i] < 0 && k > 0 {
23+
k--
24+
nums[i] = -nums[i]
25+
}
26+
}
27+
28+
for k > 0 {
29+
nums[l-1] = -nums[l-1]
30+
k--
31+
}
32+
for i := 0; i < len(nums); i++ {
33+
ans += nums[i]
34+
}
35+
36+
return ans
37+
}

‎leetcode/1005.K次取反后最大化的数组和/largestSumAfterKNegations_test.go

Lines changed: 33 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,33 @@
1+
package _005_K次取反后最大化的数组和
2+
3+
import "testing"
4+
5+
func Test_largestSumAfterKNegations(t *testing.T) {
6+
type args struct {
7+
nums []int
8+
k int
9+
}
10+
tests := []struct {
11+
name string
12+
args args
13+
want int
14+
}{
15+
{name: `[3,-1,0,2]
16+
3`, args: args{
17+
nums: []int{3, -1, 0, 2},
18+
k: 3,
19+
}, want: 6},
20+
{name: `[2,-3,-1,5,-4]
21+
2`, args: args{
22+
nums: []int{2, -3, -1, 5, -4},
23+
k: 2,
24+
}, want: 13},
25+
}
26+
for _, tt := range tests {
27 6D4E +
t.Run(tt.name, func(t *testing.T) {
28+
if got := largestSumAfterKNegations(tt.args.nums, tt.args.k); got != tt.want {
29+
t.Errorf("largestSumAfterKNegations() = %v, want %v", got, tt.want)
30+
}
31+
})
32+
}
33+
}

‎leetcode/122.买卖股票的最佳时机II/maxProfit.go

Lines changed: 39 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,39 @@
1+
package _22_买卖股票的最佳时机II
2+
3+
func maxProfit(prices []int) int {
4+
var ans int
5+
6+
for i := 1; i < len(prices); i++ {
7+
if prices[i]-prices[i-1] > 0 {
8+
ans += prices[i] - prices[i-1]
9+
}
10+
}
11+
12+
return ans
13+
}
14+
15+
func maxProfitWithDP(prices []int) int {
16+
var l = len(prices)
17+
18+
var dp = make([][2]int, len(prices))
19+
// 现金
20+
dp[0][0] = 0
21+
// 股票
22+
dp[0][1] -= prices[0]
23+
24+
for i := 1; i < l; i++ {
25+
// 昨天的股票以今天价格卖了换成现金
26+
dp[i][0] = max(dp[i-1][0], dp[i-1][1]+prices[i])
27+
// 昨天的现金买了今天的股票
28+
dp[i][1] = max(dp[i-1][1], dp[i-1][0]-prices[i])
29+
}
30+
31+
return max(dp[l-1][0], dp[l-1][1])
32+
}
33+
34+
func max(a, b int) int {
35+
if a > b {
36+
return a
37+
}
38+
return b
39+
}

‎leetcode/122.买卖股票的最佳时机II/maxProfit_test.go

Lines changed: 24 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,24 @@
1+
package _22_买卖股票的最佳时机II
2+
3+
import "testing"
4+
5+
func Test_maxProfit(t *testing.T) {
6+
type args struct {
7+
prices []int
8+
}
9+
tests := []struct {
10+
name string
11+
args args
12+
want int
13+
}{
14+
{name: `输入: prices = [7,1,5,3,6,4]
15+
输出: 7`, args: args{prices: []int{7, 1, 5, 3, 6, 4}}, want: 7},
16+
}
17+
for _, tt := range tests {
18+
t.Run(tt.name, func(t *testing.T) {
19+
if got := maxProfitWithDP(tt.args.prices); got != tt.want {
20+
t.Errorf("maxProfit() = %v, want %v", got, tt.want)
21+
}
22+
})
23+
}
24+
}

‎leetcode/45.跳跃游戏II/jump.go

Lines changed: 28 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,28 @@
1+
package _5_跳跃游戏II
2+
3+
func jump(nums []int) int {
4+
l := len(nums)
5+
6+
var next, cur, c int
7+
for i := 0; i < l; i++ {
8+
next = max(nums[i]+i, next)
9+
if i == cur {
10+
if i == l-1 {
11+
break
12+
}
13+
cur = next
14+
c++
15+
if next >= l-1 {
16+
break
17+
}
18+
}
19+
}
20+
return c
21+
}
22+
23+
func max(a, b int) int {
24+
if a > b {
25+
return a
26+
}
27+
return b
28+
}

‎leetcode/45.跳跃游戏II/jump_test.go

Lines changed: 23 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,23 @@
1+
package _5_跳跃游戏II
2+
3+
import "testing"
4+
5+
func Test_jump(t *testing.T) {
6+
type args struct {
7+
nums []int
8+
}
9+
tests := []struct {
10+
name string
11+
args args
12+
want int
13+
}{
14+
{name: `输入: [2,3,1,1,4],输出: 2`, args: args{nums: []int{2, 3, 1, 1, 4}}, want: 2},
15+
}
16+
for _, tt := range tests {
17+
t.Run(tt.name, func(t *testing.T) {
18+
if got := jump(tt.args.nums); got != tt.want {
19+
t.Errorf("jump() = %v, want %v", got, tt.want)
20+
}
21+
})
22+
}
23+
}

‎leetcode/55.跳跃游戏/canJump.go

Lines changed: 25 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,25 @@
1+
package _5_跳跃游戏
2+
3+
func canJump(nums []int) bool {
4+
5+
l := len(nums)
6+
var ans int
7+
if l <= 1 {
8+
return true
9+
}
10+
for i := 0; i <= ans; i++ {
11+
ans = max(ans, nums[i]+i)
12+
if ans >= l-1 {
13+
return true
14+
}
15+
}
16+
17+
return false
18+
}
19+
20+
func max(a, b int) int {
21+
if a > b {
22+
return a
23+
}
24+
return b
25+
}

‎leetcode/55.跳跃游戏/canJump_test.go

Lines changed: 25 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,25 @@
1+
package _5_跳跃游戏
2+
3+
import "testing"
4+
5+
func Test_canJump(t *testing.T) {
6+
type args struct {
7+
nums []int
8+
}
9+
tests := []struct {
10+
name string
11+
args args
12+
want bool
13+
}{
14+
{name: `输入：nums = [2,3,1,1,4],输出：true`, args: args{nums: []int{2, 3, 1, 1, 4}}, want: true},
15+
{name: `输入：nums = [3,2,1,0,4],输出：false`, args: args{nums: []int{3, 2, 1, 0, 4}}, want: false},
16+
{name: `输入：nums = [2,0,0],输出：trur`, args: args{nums: []int{2, 0, 0}}, want: true},
17+
}
18+
for _, tt := range tests {
19+
t.Run(tt.name, func(t *testing.T) {
20+
if got := canJump(tt.args.nums); got != tt.want {
21+
t.Errorf("canJump() = %v, want %v", got, tt.want)
22+
}
23+
})
24+
}
25+
}

0 commit comments

Comments
 (0)
0