Leetcode编程练习

LeetCode 编程训练的积累,目前在努力做题中,日后整理!

<!– more –>

1 maxCount

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
func maxCount(m int, n int, ops [][]int) int {
M := make([]([]int), 0,m)
for i := 0; i < m; i+=1 {
r := make([]int,n)
M = append(M, r)
}
var max int
var max_count int
for index, _ := range ops {
a, b := ops[index][0],ops[index][1]
fmt.Println(a,b)
rs := M[0:a]
for index, _ := range rs {
ris := rs[index]
for index, _ := range ris {
ri := ris[index]
if index == b {
break
}
ri +=1
ris[index]=ri
if ri > max {
max = ri
max_count = 0
}
if ri == max {
max_count +=1
}
}
rs[index] = ris
}
}
return max_count
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
func maxCount(m int, n int, ops [][]int) int {
m_r, m_c := m, n
for _, op := range ops {
op_r := op[0]
op_c := op[1]
if op_r < m_r {
m_r = op_r
}
if op_c < m_c {
m_c = op_c
}
}
return m_r * m_c
}
1
2
3
func main() {
fmt.Println(maxCount(3,3, [][]int{[]int{2,2},[]int{3,3}}))
}

2 lengthOfLongestSubstring

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
func lengthOfLongestSubstring(s string) int {
byte_arr := []byte(s)
max_sub_arr := make([]byte, 0)
byte_sub_arr := make([]byte, 0)
byte_m := make(map[byte]int)
var start_index int
for index, byte_i := range byte_arr {
if ori_index, ok := byte_m[byte_i]; !ok {
byte_m[byte_i] = index
byte_sub_arr = append(byte_sub_arr, byte_i)
} else {
if len(max_sub_arr) < len(byte_sub_arr) {
max_sub_arr = byte_sub_arr
}
byte_sub_arr = byte_arr[ori_index+1 : index+1]
for ; start_index <= ori_index; start_index += 1 {
delete(byte_m, byte_arr[start_index])
}
byte_m[byte_i] = index
}
}
if len(max_sub_arr) < len(byte_sub_arr) {
max_sub_arr = byte_sub_arr
}
return len(max_sub_arr)
}
1
2
3
func main() {
fmt.Println(lengthOfLongestSubstring("abcabcbb"))
}

3 findMedianSortedArrays

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
total := len(nums1) + len(nums2)
if total%2 > 0 {
return findKth(nums1, nums2, total/2+1)
} else {
return (findKth(nums1, nums2, total/2) + findKth(nums1, nums2, total/2+1)) / float64(2)
}
}

func min(a, b int) int {
if a > b {
return b
} else {
return a
}
}

func findKth(a []int, b []int, k int ) float64 {
m, n := len(a), len(b)

//always assume that m is equal or smaller than n
if m > n {
return findKth(b, a, k)
}
if m == 0 {
return float64(b[k-1])
}

if k == 1 {
return float64(min(a[0], b[0]))
}

//divide k into two parts
pa := min(k/2, m)
pb := k - pa
if a[pa-1] < b[pb-1] {
return findKth(a[pa:], b, k-pa)
} else if a[pa-1] > b[pb-1] {
return findKth(a, b[pb:], k-pb)
} else {
return float64(a[pa-1])
}
}
1
2
3
4
5
6
func main() {
fmt.Println(findMedianSortedArrays([]int{1,3}, []int{2}))
fmt.Println(findMedianSortedArrays([]int{1,2}, []int{3, 4}))
fmt.Println(findMedianSortedArrays([]int{2,4,8}, []int{3,6,9}))
fmt.Println(findMedianSortedArrays([]int{2,4,7,8}, []int{3,5,6,9}))
}

4 findMin

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
func findMin(nums []int) int {
if len(nums) < 1 {
return 0
}

if len(nums) == 1 {
return nums[0]
}

if len(nums) == 2 {
return min(nums[0], nums[1])
}

size := len(nums)
max_min_num := nums[0]
mid_num := nums[size/2]
if mid_num > max_min_num {
return findMin(nums[size/2+1:])
} else {
if nums[size/2-1] > nums[size/2] {
return nums[size/2]
} else {
return findMin(nums[:size/2])
}
}
}

func min(a, b int) int{
if a > b{
return b
} else {
return a
}
}

5 findDiagonalOrder

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
func findDiagonalOrder(matrix [][]int) []int {
rst_arr := make([]int, 0)
if len(martix) < 1 || len(matrix[0]) < 1 {
return rst_arr
}
r_n := len(matrix)
c_n := len(matrix[0])
max_n := max(r_n, c_n)
order := "asc" // desc
var r_index, c_index int
for {
if r_index == r_n-1 && c_index == c_n-1 {
rst_arr = append(rst_arr, matrix[r_index][c_index])
break
}

switch order {
case "asc":
order = "desc"
for {
rst_arr = append(rst_arr, matrix[r_index][c_index])
if c_index == c_n-1 || r_index == 0 {
break
}
c_index += 1
r_index -= 1
}

if r_index == 0 {
if c_index == c_n-1 {
r_index += 1
} else {
c_index += 1
}
} else if c_index == c_n-1 {
r_index += 1
}
case "desc":
order = "asc"
for {
rst_arr = append(rst_arr, matrix[r_index][c_index])
if c_index == 0 || r_index == r_n-1 {
break
}
c_index -= 1
r_index += 1
}

if c_index == 0 {
if r_index == r_n-1 {
c_index += 1
} else {
r_index += 1
}
} else if r_index == r_n-1 {
c_index += 1
}
}
}
return rst_arr
}

6 thirdMax

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
func parent(i int) int {
return i / 2
}

func left(i int) int {
return 2*i + 1
}

func right(i int) int {
return 2 * (i + 1)
}

func min_heapify(A []int, i int) {
l := left(i)
r := right(i)
var least int
if l < len(A) && A[l] < A[i] {
least = l
} else {
least = i
}
if r < len(A) && A[r] < A[least] {
least = r
}

if least != i {
A[i], A[least] = A[least], A[i]
min_heapify(A, least)
}
}

func thirdMax(nums []int) int {
var size int = 3
min_heap := make([]int, 0)
heap_M := make(map[int]bool)
var index int
for {
if !heap_M[nums[index]] {
heap_M[nums[index]] = true
min_heap = append(min_heap, nums[index])
}
index += 1
if len(min_heap) == size {
break
}
if index == len(nums) {
break
}
}

for i := len(min_heap) / 2; i >= 0; i -= 1 {
min_heapify(min_heap, i)
}

if index == len(nums) {
if len(min_heap) == size {
return min_heap[0]
} else {
var max int
for _, num := range min_heap {
if num > max {
max = num
}
}
return max
}
}

for i := index; i < len(nums); i += 1 {
num := nums[i]
if num > min_heap[0] && !heap_M[num] {
delete(heap_M, min_heap[0])
heap_M[num] = true
min_heap[0] = num
min_heapify(min_heap, 0)
}
}

return min_heap[0]
}
1
2
3
4
5
6
func main() {
fmt.Println(thirdMax([]int{3, 2, 1}))
fmt.Println(thirdMax([]int{1, 2}))
fmt.Println(thirdMax([]int{2, 2, 3, 1}))
fmt.Println(thirdMax([]int{5,2,4,1,3,6,0}))
}

7 combinationSum

7.1 combinationSum

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
type PreCombin struct {
Sum int
Arr []int
}

func IsEqualCombin(lc, rc *PreCombin) bool {
if lc.Sum != rc.Sum {
return false
}

if len(lc.Arr) != len(rc.Arr) {
return false
}

for i := 0; i < len(lc.Arr); i += 1 {
l_num := lc.Arr[i]
r_num := rc.Arr[i]
if l_num != r_num {
return false
}
}
return true
}

func sortInsert(nums []int, num int) []int {
if len(nums) < 1 {
return []int{num}
}
new_nums := make([]int, len(nums)+1)
copy(new_nums, nums)
new_nums[len(nums)] = num

num_index := len(new_nums) - 1
for i := len(new_nums) - 2; i >= 0; i -= 1 {
if new_nums[i] <= new_nums[num_index] {
break
}
new_nums[i], new_nums[num_index] = new_nums[num_index], new_nums[i]
num_index = i
}
return new_nums
}

func combinationSum(candidates []int, target int) [][]int {
combin_arr := make([]([]int), 0)
pre_combin_arr := make([]*PreCombin, 0)
for index, _ := range candidates {
num := candidates[index]
if num > target {
continue
}

sub_pre_combin_arr := make([]*PreCombin, 0)
for index, _ := range pre_combin_arr {
pre_combin := pre_combin_arr[index]
if pre_combin.Sum == target {
continue
}

for {
if pre_combin.Sum+num <= target {
_pre_combin := &PreCombin{
Sum: pre_combin.Sum + num,
Arr: sortInsert(pre_combin.Arr, num),
}
sub_pre_combin_arr = append(sub_pre_combin_arr, _pre_combin)
pre_combin = _pre_combin
} else {
break
}
}
}

pre_combin := &PreCombin{
Sum: num,
Arr: []int{num},
}
sub_pre_combin_arr = append(sub_pre_combin_arr, pre_combin)
for {
if pre_combin.Sum+num <= target {
_pre_combin := &PreCombin{
Sum: pre_combin.Sum + num,
Arr: sortInsert(pre_combin.Arr, num),
}
sub_pre_combin_arr = append(sub_pre_combin_arr, _pre_combin)
pre_combin = _pre_combin
} else {
break
}
}

for index, _ := range sub_pre_combin_arr {
sub_pre_combin := sub_pre_combin_arr[index]
var hasEqual bool
for index, _ := range pre_combin_arr {
pre_combin := pre_combin_arr[index]
if IsEqualCombin(sub_pre_combin, pre_combin) {
hasEqual = true
break
}
}
if !hasEqual {
pre_combin_arr = append(pre_combin_arr, sub_pre_combin)
}
}
}

for index, _ := range pre_combin_arr {
pre_combin := pre_combin_arr[index]
if pre_combin.Sum == target {
combin_arr = append(combin_arr, pre_combin.Arr)
}
}

return combin_arr
}
1
2
3
func main() {
fmt.Println(combinationSum([]int{2, 3, 6, 7}, 7))
}

7.2 combinationSum2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
type PreCombin struct {
Sum int
Arr []int
}

func IsEqualCombin(lc, rc *PreCombin) bool {
if lc.Sum != rc.Sum {
return false
}

if len(lc.Arr) != len(rc.Arr) {
return false
}

for i := 0; i < len(lc.Arr); i += 1 {
l_num := lc.Arr[i]
r_num := rc.Arr[i]
if l_num != r_num {
return false
}
}
return true
}

func sortInsert(nums []int, num int) []int {
if len(nums) < 1 {
return []int{num}
}
new_nums := make([]int, len(nums)+1)
copy(new_nums, nums)
new_nums[len(nums)] = num

num_index := len(new_nums) - 1
for i := len(new_nums) - 2; i >= 0; i -= 1 {
if new_nums[i] <= new_nums[num_index] {
break
}
new_nums[i], new_nums[num_index] = new_nums[num_index], new_nums[i]
num_index = i
}
return new_nums
}

func combinationSum2(candidates []int, target int) [][]int {
combin_arr := make([]([]int), 0)
pre_combin_arr := make([]*PreCombin, 0)
for index, _ := range candidates {
num := candidates[index]
if num > target {
continue
}

sub_pre_combin_arr := make([]*PreCombin, 0)
for index, _ := range pre_combin_arr {
pre_combin := pre_combin_arr[index]
if pre_combin.Sum == target {
continue
}
if pre_combin.Sum+num <= target {
_pre_combin := &PreCombin{
Sum: pre_combin.Sum + num,
Arr: sortInsert(pre_combin.Arr, num),
}
sub_pre_combin_arr = append(sub_pre_combin_arr, _pre_combin)
}
}

pre_combin := &PreCombin{
Sum: num,
Arr: []int{num},
}
sub_pre_combin_arr = append(sub_pre_combin_arr, pre_combin)

for index, _ := range sub_pre_combin_arr {
sub_pre_combin := sub_pre_combin_arr[index]
var hasEqual bool
for index, _ := range pre_combin_arr {
pre_combin := pre_combin_arr[index]
if IsEqualCombin(sub_pre_combin, pre_combin) {
hasEqual = true
break
}
}
if !hasEqual {
pre_combin_arr = append(pre_combin_arr, sub_pre_combin)
}
}
}

for index, _ := range pre_combin_arr {
pre_combin := pre_combin_arr[index]
if pre_combin.Sum == target {
combin_arr = append(combin_arr, pre_combin.Arr)
}
}

return combin_arr
}
1
2
3
4
5
func main() {
fmt.Println(combinationSum2([]int{10, 1, 2, 7, 6, 1, 5}, 8))
fmt.Println(combinationSum2([]int{4,4,2,1,4,2,2,1,3}, 6))
fmt.Println(combinationSum2([]int{3,1,3,5,1,1}, 8))
}

7.3 combinationSum3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
type PreCombin struct {
Sum int
Arr []int
}

func IsEqualCombin(lc, rc *PreCombin) bool {
if lc.Sum != rc.Sum {
return false
}

if len(lc.Arr) != len(rc.Arr) {
return false
}

for i := 0; i < len(lc.Arr); i += 1 {
l_num := lc.Arr[i]
r_num := rc.Arr[i]
if l_num != r_num {
return false
}
}
return true
}

func sortInsert(nums []int, num int) []int {
if len(nums) < 1 {
return []int{num}
}
new_nums := make([]int, len(nums)+1)
copy(new_nums, nums)
new_nums[len(nums)] = num

num_index := len(new_nums) - 1
for i := len(new_nums) - 2; i >= 0; i -= 1 {
if new_nums[i] <= new_nums[num_index] {
break
}
new_nums[i], new_nums[num_index] = new_nums[num_index], new_nums[i]
num_index = i
}
return new_nums
}

func combinationSum3(k int, n int) [][]int {
candidates := make([]int, 9)
for index, _ := range candidates {
candidates[index] = index + 1
}
target := n

combin_arr := make([]([]int), 0)
pre_combin_arr := make([]*PreCombin, 0)
for index, _ := range candidates {
num := candidates[index]
if num > target {
continue
}

sub_pre_combin_arr := make([]*PreCombin, 0)
for index, _ := range pre_combin_arr {
pre_combin := pre_combin_arr[index]
if pre_combin.Sum == target {
continue
}
if pre_combin.Sum+num <= target {
_pre_combin := &PreCombin{
Sum: pre_combin.Sum + num,
Arr: sortInsert(pre_combin.Arr, num),
}
sub_pre_combin_arr = append(sub_pre_combin_arr, _pre_combin)
}
}

pre_combin := &PreCombin{
Sum: num,
Arr: []int{num},
}
sub_pre_combin_arr = append(sub_pre_combin_arr, pre_combin)

for index, _ := range sub_pre_combin_arr {
sub_pre_combin := sub_pre_combin_arr[index]
var hasEqual bool
for index, _ := range pre_combin_arr {
pre_combin := pre_combin_arr[index]
if IsEqualCombin(sub_pre_combin, pre_combin) {
hasEqual = true
break
}
}
if !hasEqual {
pre_combin_arr = append(pre_combin_arr, sub_pre_combin)
}
}
}


for index, _ := range pre_combin_arr {
pre_combin := pre_combin_arr[index]
if pre_combin.Sum == target && len(pre_combin.Arr) == k {
combin_arr = append(combin_arr, pre_combin.Arr)
}
}

return combin_arr
}
1
2
3
4
func main() {
fmt.Println(combinationSum3(3, 7))
fmt.Println(combinationSum3(3, 9))
}

7.4 combinationSum4

7.4.1 V1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
type PreCombin struct {
Sum int
Arr []int
}

func IsEqualCombin(lc, rc *PreCombin) bool {
if lc.Sum != rc.Sum {
return false
}

if len(lc.Arr) != len(rc.Arr) {
return false
}

for i := 0; i < len(lc.Arr); i += 1 {
l_num := lc.Arr[i]
r_num := rc.Arr[i]
if l_num != r_num {
return false
}
}
return true
}

func sortInsert(nums []int, num int) []int {
if len(nums) < 1 {
return []int{num}
}
new_nums := make([]int, len(nums)+1)
copy(new_nums, nums)
new_nums[len(nums)] = num

num_index := len(new_nums) - 1
for i := len(new_nums) - 2; i >= 0; i -= 1 {
if new_nums[i] <= new_nums[num_index] {
break
}
new_nums[i], new_nums[num_index] = new_nums[num_index], new_nums[i]
num_index = i
}
return new_nums
}

func permut_num(nums []int) int {
size := len(nums)
num_M := make(map[int]int)
for _, num := range nums {
num_M[num] += 1
}

if len(num_M) == 1 {
return 1
}

var max_count int
var max_count_num int
for num, count := range num_M {
if count > max_count {
max_count = count
max_count_num = num
}
}
delete(num_M, max_count_num)

var factor int = 1
for i := size; i > max_count; i -= 1 {
factor *= i
}

var un_factor int = 1
for _, count := range num_M {
for i := count; i > 0; i -= 1 {
un_factor *= i
}
}

return factor / un_factor
}

func combinationSum4(nums []int, target int) int {
pre_combin_arr := make([]*PreCombin, 0)
for index, _ := range nums {
num := nums[index]
if num > target {
continue
}

sub_pre_combin_arr := make([]*PreCombin, 0)
for index, _ := range pre_combin_arr {
pre_combin := pre_combin_arr[index]
if pre_combin.Sum == target {
continue
}

for {
if pre_combin.Sum+num <= target {
_pre_combin := &PreCombin{
Sum: pre_combin.Sum + num,
Arr: sortInsert(pre_combin.Arr, num),
}
sub_pre_combin_arr = append(sub_pre_combin_arr, _pre_combin)
pre_combin = _pre_combin
} else {
break
}
}
}

pre_combin := &PreCombin{
Sum: num,
Arr: []int{num},
}
sub_pre_combin_arr = append(sub_pre_combin_arr, pre_combin)
for {
if pre_combin.Sum+num <= target {
_pre_combin := &PreCombin{
Sum: pre_combin.Sum + num,
Arr: sortInsert(pre_combin.Arr, num),
}
sub_pre_combin_arr = append(sub_pre_combin_arr, _pre_combin)
pre_combin = _pre_combin
} else {
break
}
}

for index, _ := range sub_pre_combin_arr {
sub_pre_combin := sub_pre_combin_arr[index]
var hasEqual bool
for index, _ := range pre_combin_arr {
pre_combin := pre_combin_arr[index]
if IsEqualCombin(sub_pre_combin, pre_combin) {
hasEqual = true
break
}
}
if !hasEqual {
pre_combin_arr = append(pre_combin_arr, sub_pre_combin)
}
}
}

var permuts int
for index, _ := range pre_combin_arr {
pre_combin := pre_combin_arr[index]
if pre_combin.Sum == target {
permuts += permut_num(pre_combin.Arr)
}
}

return permuts
}

7.4.2 V2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
func permut_num(num_M map[int]int) int {
if len(num_M) == 1 {
return 1
}

var sum_count int
var max_count int
var max_count_num int
for num, count := range num_M {
sum_count += count
if count > max_count {
max_count = count
max_count_num = num
}
}
delete(num_M, max_count_num)

var factor int = 1
for i := sum_count; i > max_count; i -= 1 {
factor *= i
}

var un_factor int = 1
for _, count := range num_M {
for i := count; i > 0; i -= 1 {
un_factor *= i
}
}

return factor / un_factor
}

func combinationSum4(nums []int, target int) int {
var result_num int
if len(nums) == 0 {
return 0
}

if len(nums) == 1 {
if target%nums[0] == 0 {
return 1
} else {
return 0
}
}

fir_num := nums[0]
var factor int = 0
for sub_sum := 0; sub_sum <= target; sub_sum += fir_num {
combin_M_arr := sub_combin(nums[1:], target-fir_num*factor)
if len(combin_M_arr) > 0 {
for index, _ := range combin_M_arr {
combin_M := combin_M_arr[index]
combin_M[fir_num] = factor
result_num += permut_num(combin_M)
}
}
if fir_num*factor == target {
result_num += 1
}
factor += 1
}

return result_num
}

func sub_combin(nums []int, target int) [](map[int]int) {
if target < 1 {
return []map[int]int{}
}

if len(nums) == 1 {
if target%nums[0] == 0 {
return []map[int]int{
map[int]int{
nums[0]: target / nums[0],
},
}
} else {
return []map[int]int{}
}
}

fir_num := nums[0]
var factor int = 0
combin_M_arr := make([]map[int]int, 0)
for sub_sum := 0; sub_sum <= target; sub_sum += fir_num {
sub_combin_M_arr := sub_combin(nums[1:], target-fir_num*factor)
if len(sub_combin_M_arr) > 0 {
for index, _ := range sub_combin_M_arr {
combin_M := sub_combin_M_arr[index]
combin_M[fir_num] = factor
combin_M_arr = append(combin_M_arr, combin_M)
}
}

if fir_num*factor == target {
combin_M := map[int]int{
fir_num: factor,
}
combin_M_arr = append(combin_M_arr, combin_M)
}

factor += 1
}

return combin_M_arr
}
1
2
3
4
5
func main() {
fmt.Println(combinationSum4([]int{1,2,3}, 4))
fmt.Println(combinationSum4([]int{1,50}, 200))
fmt.Println(combinationSum4([]int{3,33,333}, 10000))
}

7.4.3 V3

动态规划解法

  • dp[i] += dp[i-num]
  • dp[i+num] += dp[i]
1
2
3
4
5
6
7
8
9
10
11
12
func combinationSum4(nums []int, target int) int {
dp := make([]int, target+1)
dp[0] = 1
for i := 1; i <= target; i += 1 {
for _, num := range nums {
if i >= num {
dp[i] += dp[i-num]
}
}
}
return dp[target]
}
1
2
3
4
5
func main() {
fmt.Println(combinationSum4([]int{1,2,3}, 4))
fmt.Println(combinationSum4([]int{1,50}, 200))
fmt.Println(combinationSum4([]int{3,33,333}, 10000))
}

8 combine

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
func combine(n int, k int) [][]int {
return subCombine(1, n, k)
}

func subCombine(start, end, k int) [][]int {
if k < 1 || end-start+1 < k {
return [][]int{}
}

combine_arr := make([][]int, 0)
if k == 1 {
for i := start; i <= end; i += 1 {
combine_arr = append(combine_arr, []int{i})
}
}

for i := start; i <= end-(k-1); i += 1 {
sub_combine_arr := subCombine(i+1, end, k-1)
if len(sub_combine_arr) > 0 {
for index, _ := range sub_combine_arr {
combines := append([]int{i}, sub_combine_arr[index]...)
combine_arr = append(combine_arr, combines)
}
}
}

return combine_arr
}
1
2
3
func main() {
fmt.Println(combine(4,2))
}

9 pathSum

9.1 hasPathSum

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}

func hasPathSum(root *TreeNode, sum int) bool {
if root == nil {
return false
}

if root.Left == nil && root.Right == nil {
if root.Val == sum {
return true
} else {
return false
}
}

return hasPathSum(root.Left, sum-root.Val) || hasPathSum(root.Right, sum-root.Val)
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
func main() {
lc := &TreeNode{
Val: 4,
Left: &TreeNode{
Val: 11,
Left: &TreeNode{
Val: 7,
},
Right: &TreeNode{
Val: 2,
},
},
}
rc := &TreeNode{
Val: 8,
Left: &TreeNode{
Val: 13,
},
Right: &TreeNode{
Val: 4,
Left: &TreeNode{
Val: 5,
},
Right: &TreeNode{
Val: 1,
},
},
}
root := &TreeNode{
Val: 5,
Left: lc,
Right: rc,
}

fmt.Println(hasPathSum(root, 22))
}

9.2 pathSum

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}

func pathSum(root *TreeNode, sum int) [][]int {
if root == nil {
return [][]int{}
}

if root.Left == nil && root.Right == nil {
if root.Val == sum {
return [][]int{[]int{root.Val}}
} else {
return [][]int{}
}
}

var lc_path_arr, rc_path_arr [][]int
if root.Left != nil {
lc_path_arr = pathSum(root.Left, sum-root.Val)
}

if root.Right != nil {
rc_path_arr = pathSum(root.Right, sum-root.Val)
}

path_arr := make([][]int, 0)
if len(lc_path_arr) > 0 {
for index, _ := range lc_path_arr {
path := lc_path_arr[index]
path = append([]int{root.Val}, path...)
path_arr = append(path_arr, path)
}
}

if len(rc_path_arr) > 0 {
for index, _ := range rc_path_arr {
path := rc_path_arr[index]
path = append([]int{root.Val}, path...)
path_arr = append(path_arr, path)
}
}

return path_arr
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
func main() {
lc := &TreeNode{
Val: 4,
Left: &TreeNode{
Val: 11,
Left: &TreeNode{
Val: 7,
},
Right: &TreeNode{
Val: 2,
},
},
}
rc := &TreeNode{
Val: 8,
Left: &TreeNode{
Val: 13,
},
Right: &TreeNode{
Val: 4,
Left: &TreeNode{
Val: 5,
},
Right: &TreeNode{
Val: 1,
},
},
}
root := &TreeNode{
Val: 5,
Left: lc,
Right: rc,
}

fmt.Println(pathSum(root, 22))
}

9.3 number of path

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}

func pathSum(root *TreeNode, sum int) int {
if root == nil {
return 0
}

return sumUp(root, 0, sum) + pathSum(root.Left, sum) + pathSum(root.Right, sum)
}

func sumUp(node *TreeNode, pre, sum int) int {
if node == nil {
return 0
}

var cur int = pre + node.Val
var res_num int
if cur == sum {
res_num += 1
}
return res_num + sumUp(node.Left, cur, sum) + sumUp(node.Right, cur, sum)
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
func main() {
lc := &TreeNode{
Val: 5,
Left: &TreeNode{
Val: 3,
Left: &TreeNode{
Val: 3,
},
Right: &TreeNode{
Val: -2,
},
},
Right: &TreeNode{
Val: 2,
Right: &TreeNode{
Val: 1,
},
},
}
rc := &TreeNode{
Val: -3,
Right: &TreeNode{
Val: 11,
},
}
root := &TreeNode{
Val: 10,
Left: lc,
Right: rc,
}

fmt.Println(pathSum(root, 8))
}

9.4 min path sum

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
func minPathSum(grid [][]int) int {
dp := make([][]int, len(grid))
for index, _ := range dp {
dp[index] = make([]int, len(grid[0]))
}

for r_i, _ := range grid {
for c_i, _ := range grid[r_i] {
if r_i == 0 {
if c_i > 0 {
dp[r_i][c_i] = grid[r_i][c_i] + dp[r_i][c_i-1]
} else {
dp[r_i][c_i] = grid[r_i][c_i]
}
continue
}
if c_i == 0 {
dp[r_i][0] = grid[r_i][0] + dp[r_i-1][0]
continue
}

dp[r_i][c_i] = grid[r_i][c_i] + min(dp[r_i-1][c_i], dp[r_i][c_i-1])
}
}

return dp[len(dp)-1][len(dp[0])-1]
}

func min(a, b int) int {
if a > b {
return b
} else {
return a
}
}
1
2
3
4
5
6
7
func main() {
fmt.Println(minPathSum([][]int{
[]int{1, 3, 1},
[]int{1, 5, 1},
[]int{4, 2, 1},
}))
}

9.5 binary-tree maximum path sum

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}

type BpNode struct {
MaxSum_c int
MaxSum_b int
Val int
Left *BpNode
Right *BpNode
}

func copyTree2Bp(root *TreeNode) *BpNode {
if root == nil {
return nil
}

return &BpNode{
Val: root.Val,
Left: copyTree2Bp(root.Left),
Right: copyTree2Bp(root.Right),
}
}

func max(a, b int) int {
if a < b {
return b
} else {
return a
}
}

func bpMaxSum(bpr *BpNode) int {
if bpr == nil {
return 0
}

max_n := max(bpr.MaxSum_c, bpr.MaxSum_b)
if bpr.Left != nil {
max_n = max(max_n, bpMaxSum(bpr.Left))
}
if bpr.Right != nil {
max_n = max(max_n, bpMaxSum(bpr.Right))
}

return max_n
}

func maxPathSum(root *TreeNode) int {
bpr := copyTree2Bp(root)
maxPathSumHelper(bpr)
return bpMaxSum(bpr)
}

func maxPathSumHelper(bpr *BpNode) (
max_sum_b int,
) {
if bpr == nil {
return 0
}

lmax_sum_b := maxPathSumHelper(bpr.Left)
rmax_sum_b := maxPathSumHelper(bpr.Right)

bpr.MaxSum_c = bpr.Val + max(0, lmax_sum_b) + max(0, rmax_sum_b)
bpr.MaxSum_b = bpr.Val + max(0, max(lmax_sum_b, rmax_sum_b))

return bpr.MaxSum_b
}
1
2
3
4
5
6
7
8
9
10
11
12
13
func main() {
root := &TreeNode{
Val: 1,
Left: &TreeNode{
Val: 2,
},
Right: &TreeNode{
Val: 3,
},
}

fmt.Println(maxPathSum(root))
}

9.6 sum root to leaf numbers

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}

func sumNumbers(root *TreeNode) int {
path_arr := collectPath(root)

var sum int
for index, _ := range path_arr {
path := path_arr[index]
var sub_sum int
for _, num := range path {
sub_sum = num + sub_sum*10
}
sum += sub_sum
}

return sum
}

func collectPath(root *TreeNode) [][]int {
if root == nil {
return [][]int{}
}

if root.Left == nil && root.Right == nil {
return [][]int{
[]int{root.Val},
}
}

lpath_arr := collectPath(root.Left)
rpath_arr := collectPath(root.Right)
lpath_arr = append(lpath_arr, rpath_arr...)
for index, _ := range lpath_arr {
path := lpath_arr[index]
path = append([]int{root.Val}, path...)
lpath_arr[index] = path
}
return lpath_arr
}
1
2
3
4
5
6
7
8
9
10
11
12
13
func main() {
root := &TreeNode{
Val: 1,
Left: &TreeNode{
Val: 2,
},
Right: &TreeNode{
Val: 3,
},
}

fmt.Println(sumNumbers(root))
}

10 poor pigs

1
2
3
4
5
6
7
8
9
10
11
12
13
func poorPigs(buckets int, minutesToDie int, minutesToTest int) int {
time := minutesToTest/minutesToDie + 1
res := 0
for {
if int(math.Pow(float64(time), float64(res))) < buckets {
res = res + 1
} else {
break
}
}

return res
}
Last Updated 2018-04-25 Wed 22:16.
Render by hexo-renderer-org with Emacs 25.3.2 (Org mode 8.2.10)