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)