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

Commit 237bd62

Browse files
author
陈世伟
committed
feat: 贪心 merge
2 parents c379eb4 + 0efa0b3 commit 237bd62

File tree

34 files changed

+918
-36
lines changed

34 files changed

+918
-36
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+
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: 22 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -1,24 +1,39 @@
11
package _22_买卖股票的最佳时机II
22

33
func maxProfit(prices []int) int {
4-
l := len(prices)
5-
var dp = make([][2]int, len(prices))
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)
617

18+
var dp = make([][2]int, len(prices))
19+
// 现金
720
dp[0][0] = 0
8-
dp[0][1] = -prices[0]
21+
// 股票
22+
dp[0][1] -= prices[0]
923

1024
for i := 1; i < l; i++ {
11-
dp[i][0] = max(dp[i-1][1]+prices[i], dp[i-1][0])
12-
dp[i][1] = max(dp[i-1][0]-prices[i], dp[i-1][1])
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])
1329
}
1430

15-
return max(dp[l-1][1], dp[l-1][0])
31+
return max(dp[l-1][0], dp[l-1][1])
1632
}
1733

1834
func max(a, b int) int {
1935
if a > b {
2036
return a
2137
}
22-
2338
return b
2439
}

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

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -13,6 +13,7 @@ func Test_maxProfit(t *testing.T) {
1313
}{
1414
{name: `输入: prices = [7,1,5,3,6,4] 输出: 7`, args: args{prices: []int{7, 1, 5, 3, 6, 4}}, want: 7},
1515
}
16+
1617
for _, tt := range tests {
1718
t.Run(tt.name, func(t *testing.T) {
1819
if got := maxProfit(tt.args.prices); got != tt.want {

‎leetcode/134.加油站/canCompleteCircuit.go

Lines changed: 36 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,36 @@
1+
package _134_加油站
2+
3+
func canCompleteCircuit(gas []int, cost []int) int {
4+
l1 := len(gas)
5+
6+
for i := 0; i < l1; i++ {
7+
var ans = gas[i] - cost[i]
8+
idx := (i + 1) % l1
9+
for idx != i && ans > 0 {
10+
ans += gas[idx] - cost[idx]
11+
idx = (idx + 1) % l1
12+
}
13+
if ans >= 0 && idx == i {
14+
return i
15+
}
16+
}
17+
return -1
18+
}
19+
20+
func canCompleteCircuitWithGreedy(gas []int, cost []int) int {
21+
l := len(gas)
22+
var curSum, sum, idx int
23+
for i := 0; i < l; i++ {
24+
sum += gas[i] - cost[i]
25+
curSum += gas[i] - cost[i]
26+
if curSum < 0 {
27+
idx = i + 1
28+
curSum = 0
29+
}
30+
}
31+
if sum < 0 {
32+
return -1
33+
}
34+
35+
return idx
36+
}

‎leetcode/134.加油站/canCompleteCircuit_test.go

Lines changed: 28 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,28 @@
1+
package _134_加油站
2+
3+
import "testing"
4+
5+
func Test_canCompleteCircuit(t *testing.T) {
6+
type args struct {
7+
gas []int
8+
cost []int
9+
}
10+
tests := []struct {
11+
name string
12+
args args
13+
want int
14+
}{
15+
{name: `gas = [1,2,3,4,5]
16+
cost = [3,4,5,1,2]`, args: args{
17+
gas: []int{1, 2, 3, 4, 5},
18+
cost: []int{3, 4, 5, 1, 2},
19+
}, want: 3},
20+
}
21+
for _, tt := range tests {
22+
t.Run(tt.name, func(t *testing.T) {
23+
if got := canCompleteCircuitWithGreedy(tt.args.gas, tt.args.cost); got != tt.want {
24+
t.Errorf("canCompleteCircuit() = %v, want %v", got, tt.want)
25+
}
26+
})
27+
}
28+
}

‎leetcode/135.分发糖果/candy.go

Lines changed: 31 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,31 @@
1+
package _35_分发糖果
2+
3+
func candy(ratings []int) int {
4+
l := len(ratings)
5+
s := make([]int, l)
6+
for i := 1; i < l; i++ {
7+
if ratings[i] > ratings[i-1] {
8+
s[i] = s[i-1] + 1
9+
}
10+
}
11+
12+
for i := l - 2; i >= 0; i-- {
13+
if ratings[i] > ratings[i+1] {
14+
s[i] = max(s[i], s[i+1]+1)
15+
}
16+
}
17+
18+
ans := 0
19+
for i := 0; i < l; i++ {
20+
ans += s[i]
21+
}
22+
23+
return ans + l
24+
}
25+
26+
func max(a, b int) int {
27+
if a > b {
28+
return a
29+
}
30+
return b
31+
}

‎leetcode/135.分发糖果/candy_test.go

Lines changed: 25 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,25 @@
1+
package _35_分发糖果
2+
3+
import "testing"
4+
5+
func Test_candy(t *testing.T) {
6+
type args struct {
7+
ratings []int
8+
}
9+
tests := []struct {
10+
name string
11+
args args
12+
want int
13+
}{
14+
{name: `输入：[1,0,2]
15+
输出：5
16+
解释：你可以分别给这三个孩子分发 2、1、2 颗糖果。`, args: args{ratings: []int{1, 0, 2}}, want: 5},
17+
}
18+
for _, tt := range tests {
19+
t.Run(tt.name, func(t *testing.T) {
20+
if got := candy(tt.args.ratings); got != tt.want {
21+
t.Errorf("candy() = %v, want %v", got, tt.want)
22+
}
23+
})
24+
}
25+
}

‎leetcode/28.实现strStr/strStr.go

Lines changed: 3 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -1,7 +1,5 @@
11
package _8_实现strStr
22

3-
import "fmt"
4-
53
func strStr(haystack string, needle string) int {
64
l1 := len(haystack)
75
l2 := len(needle)
@@ -25,8 +23,7 @@ func strStr(haystack string, needle string) int {
2523
func strStrWithKMP(haystack string, needle string) int {
2624
l1 := len(haystack)
2725
l2 := len(needle)
28-
29-
next := make([]int, l2)
26+
var next = make([]int, l2)
3027
for i, j := 1, 0; i < l2; i++ {
3128
for j > 0 && needle[i] != needle[j] {
3229
j = next[j-1]
@@ -36,7 +33,7 @@ func strStrWithKMP(haystack string, needle string) int {
3633
}
3734
next[i] = j
3835
}
39-
fmt.Println(next)
36+
4037
for i, j := 0, 0; i < l1; i++ {
4138
for j > 0 && haystack[i] != needle[j] {
4239
j = next[j-1]
@@ -49,4 +46,5 @@ func strStrWithKMP(haystack string, needle string) int {
4946
}
5047
}
5148
return -1
49+
5250
}

‎leetcode/28.实现strStr/strStr_test.go

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -30,7 +30,7 @@ func Test_strStr(t *testing.T) {
3030
// }
3131
//})
3232
t.Run(tt.name, func(t *testing.T) {
33-
if got := strStrWithKMP(tt.args.haystack, tt.args.needle); got != tt.want {
33+
if got := strStrWithKMP1(tt.args.haystack, tt.args.needle); got != tt.want {
3434
t.Errorf("strStrWithKMP() = %v, want %v", got, tt.want)
3535
}
3636
})

‎leetcode/376.摆动序列/wiggleMaxLength.go

Lines changed: 23 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,23 @@
1+
package _376_摆动序列
2+
3+
func wiggleMaxLength(nums []int) int {
4+
var (
5+
cur int
6+
pre int
7+
result = 1
8+
)
9+
10+
if len(nums) <= 1 {
11+
return len(nums)
12+
}
13+
14+
for i := 1; i < len(nums); i++ {
15+
cur = nums[i] - nums[i-1]
16+
if (cur > 0 && pre <= 0) || (cur < 0 && pre >= 0) {
17+
result++
18+
pre = cur
19+
}
20+
}
21+
22+
return result
23+
}

‎leetcode/406.根据身高重建队列/reconstructQueue.go

Lines changed: 43 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,43 @@
1+
package _406_根据身高重建队列
2+
3+
import (
4+
"container/list"
5+
"sort"
6+
)
7+
8+
func reconstructQueue(people [][]int) [][]int {
9+
length := len(people)
10+
sort.Slice(people, func(i, j int) bool {
11+
if people[i][0] == people[j][0] {
12+
return people[i][1] < people[j][1]
13+
}
14+
return people[i][0] > people[j][0]
15+
16+
})
17+
18+
l := list.New().Init()
19+
20+
for i := 0; i < length; i++ {
21+
if people[i][1] == i {
22+
l.PushBack(people[i])
23+
continue
24+
}
25+
c := l.Front()
26+
for j := 0; j < people[i][1]; j++ {
27+
if c != nil {
28+
c = c.Next()
29+
} else {
30+
break
31+
}
32+
}
33+
l.InsertBefore(people[i], c)
34+
}
35+
36+
cur := l.Front()
37+
var s [][]int
38+
for i := 0; i < length; i++ {
39+
s = append(s, cur.Value.([]int))
40+
cur = cur.Next()
41+
}
42+
return s
43+
}

‎leetcode/406.根据身高重建队列/reconstructQueue_test.go

Lines changed: 30 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,30 @@
1+
package _406_根据身高重建队列
2+
3+
import (
4+
"reflect"
5+
"testing"
6+
)
7+
8+
func Test_reconstructQueue(t *testing.T) {
9+
type args struct {
10+
people [][]int
11+
}
12+
tests := []struct {
13+
name string
14+
args args
15+
want [][]int
16+
}{
17+
{name: `输入：people = [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]
18+
输出：[[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]`, args: args{people: [][]int{
19+
{7, 0}, {4, 4}, {7, 1}, {5, 0}, {6, 1}, {5, 2},
20+
}}, want: [][]int{{5, 0}, {7, 0}, {5, 2}, {6, 1}, {4, 4}, {7, 1}}},
21+
{name: ``, args: args{people: [][]int{{9, 0}, {7, 0}, {1, 9}, {3, 0}, {2, 7}, {5, 3}, {6, 0}, {3, 4}, {6, 2}, {5, 2}}}, want: [][]int{{3, 0}, {6, 0}, {7, 0}, {5, 2}, {3, 4}, {5, 3}, {6, 2}, {2, 7}, {9, 0}, {1, 9}}},
22+
}
23+
for _, tt := range tests {
24+
t.Run(tt.name, func(t *testing.T) {
25+
if got := reconstructQueue(tt.args.people); !reflect.DeepEqual(got, tt.want) {
26+
t.Errorf("reconstructQueue() = %v, want %v", got, tt.want)
27+
}
28+
})
29+
}
30+
}

0 commit comments

Comments
 (0)
0