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

Commit c379eb4

Browse files
author
陈世伟
committed
feat: 贪心
1 parent 1a9f667 commit c379eb4

File tree

8 files changed

+234
-0
lines changed

8 files changed

+234
-0
lines changed

‎leetcode/122.买卖股票的最佳时机II/maxProfit.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+
func maxProfit(prices []int) int {
4+
l := len(prices)
5+
var dp = make([][2]int, len(prices))
6+
7+
dp[0][0] = 0
8+
dp[0][1] = -prices[0]
9+
10+
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])
13+
}
14+
15+
return max(dp[l-1][1], dp[l-1][0])
16+
}
17+
18+
func max(a, b int) int {
19+
if a > b {
20+
return a
21+
}
22+
23+
return b
24+
}

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

Lines changed: 23 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,23 @@
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] 输出: 7`, args: args{prices: []int{7, 1, 5, 3, 6, 4}}, want: 7},
15+
}
16+
for _, tt := range tests {
17+
t.Run(tt.name, func(t *testing.T) {
18+
if got := maxProfit(tt.args.prices); got != tt.want {
19+
t.Errorf("maxProfit() = %v, want %v", got, tt.want)
20+
}
21+
})
22+
}
23+
}

‎leetcode/37.解数独/solveSudoku.go

Lines changed: 59 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,59 @@
1+
package _7_解数独
2+
3+
func solveSudoku(board [][]byte) {
4+
var (
5+
fn func() bool
6+
)
7+
8+
fn = func() bool {
9+
for i := 0; i < len(board); i++ {
10+
for j := 0; j < len(board[0]); j++ {
11+
if board[i][j] != '.' {
12+
continue
13+
}
14+
for k := '1'; k <= '9'; k++ {
15+
if isValid(i, j, byte(k), board) {
16+
board[i][j] = byte(k)
17+
if fn() {
18+
return true
19+
}
20+
board[i][j] = byte('.')
21+
}
22+
}
23+
return false
24+
}
25+
}
26+
return true
27+
}
28+
fn()
29+
return
30+
}
31+
32+
func isValid(row, col int, v byte, board [][]byte) bool {
33+
for i := 0; i < len(board); i++ {
34+
if board[row][i] == v {
35+
return false
36+
}
37+
}
38+
39+
for i := 0; i < len(board[0]); i++ {
40+
if board[i][col] == v {
41+
return false
42+
}
43+
}
44+
45+
var (
46+
// 倍数区间
47+
startRow = (row / 3) * 3
48+
startCol = (col / 3) * 3
49+
)
50+
for i := startRow; i < startRow+3; i++ {
51+
for j := startCol; j < startCol+3; j++ {
52+
if board[i][j] == v {
53+
return false
54+
}
55+
}
56+
}
57+
return true
58+
59+
}

‎leetcode/37.解数独/solveSudoku_test.go

Lines changed: 31 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,31 @@
1+
package _7_解数独
2+
3+
import (
4+
"reflect"
5+
"testing"
6+
)
7+
8+
func Test_solveSudoku(t *testing.T) {
9+
type args struct {
10+
board [][]byte
11+
}
12+
tests := []struct {
13+
name string
14+
args args
15+
want [][]byte
16+
}{
17+
{name: ``, args: args{board: [][]byte{
18+
{'5', '3', '.', '.', '7', '.', '.', '.', '.'}, {'6', '.', '.', '1', '9', '5', '.', '.', '.'}, {'.', '9', '8', '.', '.', '.', '.', '6', '.'}, {'8', '.', '.', '.', '6', '.', '.', '.', '3'}, {'4', '.', '.', '8', '.', '3', '.', '.', '1'}, {'7', '.', '.', '.', '2', '.', '.', '.', '6'}, {'.', '6', '.', '.', '.', '.', '2', '8', '.'}, {'.', '.', '.', '4', '1', '9', '.', '.', '5'}, {'.', '.', '.', '.', '8', '.', '.', '7', '9'},
19+
}}, want: [][]byte{
20+
{'5', '3', '4', '6', '7', '8', '9', '1', '2'}, {'6', '7', '2', '1', '9', '5', '3', '4', '8'}, {'1', '9', '8', '3', '4', '2', '5', '6', '7'}, {'8', '5', '9', '7', '6', '1', '4', '2', '3'}, {'4', '2', '6', '8', '5', '3', '7', '9', '1'}, {'7', '1', '3', '9', '2', '4', '8', '5', '6'}, {'9', '6', '1', '5', '3', '7', '2', '8', '4'}, {'2', '8', '7', '4', '1', '9', '6', '3', '5'}, {'3', '4', '5', '2', '8', '6', '1', '7', '9'},
21+
}},
22+
}
23+
for _, tt := range tests {
24+
t.Run(tt.name, func(t *testing.T) {
25+
solveSudoku(tt.args.board)
26+
if !reflect.DeepEqual(tt.args.board, tt.want) {
27+
t.Error()
28+
}
29+
})
30+
}
31+
}

‎leetcode/714.买卖股票的最佳时机含手续费/maxProfit.go

Lines changed: 22 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,22 @@
1+
package _714_买卖股票的最佳时机含手续费
2+
3+
func maxProfit(prices []int, fee int) int {
4+
l := len(prices)
5+
var dp = make([][2]int, l)
6+
7+
dp[0][0] = 0
8+
dp[0][1] = -prices[0]
9+
for i := 1; i < l; i++ {
10+
dp[i][0] = max(dp[i-1][1]+prices[i]-fee, dp[i-1][0])
11+
dp[i][1] = max(dp[i-1][0]-prices[i], dp[i-1][1])
12+
}
13+
14+
return max(dp[l-1][1], dp[l-1][0])
15+
}
16+
17+
func max(a, b int) int {
18+
if a > b {
19+
return a
20+
}
21+
return b
22+
}

‎leetcode/714.买卖股票的最佳时机含手续费/maxProfit_test.go

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

‎leetcode/738.单调递增的数字/monotoneIncreasingDigits.go

Lines changed: 24 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,24 @@
1+
package _738_单 7802 调递增的数字
2+
3+
import (
4+
"strconv"
5+
)
6+
7+
func monotoneIncreasingDigits(n int) int {
8+
s := []byte(strconv.Itoa(n))
9+
l := len(s)
10+
11+
flag := l
12+
for i := l - 1; i > 0; i-- {
13+
if s[i-1] > s[i] {
14+
s[i-1] -= 1
15+
flag = i
16+
}
17+
}
18+
for i := flag; i < l; i++ {
19+
s[i] = '9'
20+
}
21+
22+
n, _ = strconv.Atoi(string(s))
23+
return n
24+
}

‎leetcode/738.单调递增的数字/monotoneIncreasingDigits_test.go

Lines changed: 24 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,24 @@
1+
package _738_单调递增的数字
2+
3+
import "testing"
4+
5+
func Test_monotoneIncreasingDigits(t *testing.T) {
6+
type args struct {
7+
n int
8+
}
9+
tests := []struct {
10+
name string
11+
args args
12+
want int
13+
}{
14+
{name: `输入: N = 10
15+
输出: 9`, args: args{n: 10}, want: 9},
16+
}
17+
for _, tt := range tests {
18+
t.Run(tt.name, func(t *testing.T) {
19+
if got := monotoneIncreasingDigits(tt.args.n); got != tt.want {
20+
t.Errorf("monotoneIncreasingDigits() = %v, want %v", got, tt.want)
21+
}
22+
})
23+
}
24+
}

0 commit comments

Comments
 (0)
0