Leetcode-greedy

1 DONE 分发饼干

  • State "DONE" from "TODO" [2018-03-29 四 15:45]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
import "sort"

func findContentChildren(g []int, s []int) int {
sort.Ints(g)
sort.Ints(s)
var ans, gi int
for i, _ := range s {
for j := gi; j < len(g); j += 1 {
if g[j] <= s[i] {
gi = j + 1
ans += 1
break
}
}
}

return ans
}

2 DONE 分配糖果

  • State "DONE" from "TODO" [2018-03-30 五 17:52]
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
func max(a, b int) int {
if a > b {
return a
} else {
return b
}
}

func candy(ratings []int) int {
if len(ratings) == 0 {
return 0
}
if len(ratings) == 1 {
return 1
}

candys := make([]int, len(ratings))
candyHelper(ratings, candys, 0, len(candys))
ans := 0
for i, _ := range candys {
ans += candys[i]
}

return ans
}

func candyHelper(ratings, candys []int, start, end int) {
if start >= end {
return
}

ti := start
tn := 0
for i := start + 1; i < end; i += 1 {
if ratings[i] == ratings[ti] && ti+tn+1 == i {
tn += 1
continue
}

if ratings[i] < ratings[ti] {
ti = i
tn = 0
}
}

var cs, ce int
if ti > start && ti+tn < end-1 {
cs, ce = 1, 1
} else if ti == start && ti+tn == end-1 {
if start > 0 && end < len(ratings) {
cs, ce = candys[start-1]+1, candys[end]+1
} else if start == 0 && end == len(ratings) {
cs, ce = 1, 1
} else if start == 0 {
cs, ce = 1, candys[end]+1
} else if end == len(ratings) {
cs, ce = candys[start-1]+1, 1
}
} else if ti == start {
if start > 0 {
cs = candys[start-1] + 1
} else {
cs = 1
}
ce = 1
} else if ti+tn == end-1 {
if end < len(ratings) {
ce = candys[end] + 1
} else {
ce = 1
}
cs = 1
}

if tn == 0 {
candys[ti] = max(cs, ce)
} else {
candys[ti], candys[ti+tn] = cs, ce
for i := 1; i < tn; i += 1 {
candys[ti+i] = 1
}
}

candyHelper(ratings, candys, start, ti)
candyHelper(ratings, candys, ti+tn+1, end)
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
package main

import "fmt"



func main() {
fmt.Println(candy([]int{2, 1, 3, 1}))
fmt.Println(candy([]int{2, 1, 3, 1, 4, 5}))
fmt.Println(candy([]int{2}))
fmt.Println(candy([]int{2, 1 }))
fmt.Println(candy([]int{1, 2 }))
fmt.Println(candy([]int{3,2,1}))
fmt.Println(candy([]int{1,2,3}))
fmt.Println(candy([]int{2,2,1}))
fmt.Println(candy([]int{2,1,1}))
fmt.Println(candy([]int{2,2}))
fmt.Println(candy([]int{2,1,1,2}))
fmt.Println(candy([]int{2,1,1,1,3}))
fmt.Println(candy([]int{1,2,2}))
}

3 DONE 通配符匹配

  • State "DONE" from "TODO" [2018-04-02 一 15:50]
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
import "strings"

func isMatch(s string, p string) bool {
for strings.Contains(p, "**") {
p = strings.Replace(p, "**", "*", -1)
}

return match(s, p)
}

func match(s string, p string) bool {
if len(s) == 0 && len(p) == 0 {
return true
}

if len(p) == 0 && len(s) > 0 {
return false
}

if len(s) == 0 {
for i, _ := range p {
if p[i:i+1] != "*" {
return false
}
}
return true
}

if p[0:1] == "?" || p[0] == s[0] {
return match(s[1:], p[1:])
}

if p[0:1] == "*" {
return match(s, p[1:]) || isMatch(s[1:], p)
}

return false
}
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
func isMatch(s string, p string) bool {
slen, plen := len(s), len(p)
i, j := 0, 0
is, ip := -1, -1
for i < slen {
if j == plen {
if ip == -1 {
return false
} else {
is += 1
i = is
j = ip + 1
}
continue
}

if p[j:j+1] == "*" {
is = i
ip = j
j += 1
} else {
if s[i] == p[j] || p[j:j+1] == "?" {
i += 1
j += 1
} else if ip == -1 {
return false
} else {
is += 1
i = is
j = ip + 1
}
}
}

for j < plen && p[j:j+1] == "*" {
j += 1
}

return j == plen
}

4 DONE 拼接最大数

  • State "DONE" from "TODO" [2018-04-03 二 14:31]
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
func maxNumber(nums1 []int, nums2 []int, k int) []int {
if k < 1 {
return []int{}
}
if len(nums2) > len(nums1) {
nums1, nums2 = nums2, nums1
}

num := nums1[0]
ai := 0
ni := 0
prev_ai := 1
for i := 0; i < len(nums1); i += 1 {
if len(nums1)+len(nums2)-i < k {
break
}

if nums1[i] > num {
prev_ai = ai
num = nums1[i]
ai, ni = 0, i
}

if nums1[i] == num {
if 0 != prev_ai && ai != 0 {
num = nums1[i]
ai, ni = 0, i
}
}

for j := 0; j < len(nums2); j += 1 {
if len(nums1)+len(nums2)-(i+j) < k {
break
}

if nums2[j] > num {
prev_ai = ai
num = nums2[j]
ai, ni = 1, j
}

if nums2[j] == num {
if 1 != prev_ai && ai != 1 {
num = nums2[j]
ai, ni = 1, j
}
}
}
}

ans := []int{num}
if ai == 0 {
return append(ans, maxNumber(nums1[ni+1:], nums2, k-1)...)
} else {
return append(ans, maxNumber(nums1, nums2[ni+1:], k-1)...)
}
}
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
func maxNumber(nums1 []int, nums2 []int, k int) []int {
ans := make([]int, k)
len1, len2 := len(nums1), len(nums2)
for i := max(k-len2, 0); i <= min(k, len1); i += 1 {
ans = maxInts(ans, merge(getMax(nums1, i), getMax(nums2, k-i)))
}

return ans
}

func getMax(nums []int, k int) []int {
ans := make([]int, 0)
drop := len(nums) - k
for i := 0; i < len(nums); i += 1 {
for drop > 0 && len(ans) > 0 && nums[i] > ans[len(ans)-1] {
drop -= 1
ans = ans[:len(ans)-1]
}
ans = append(ans, nums[i])
}

return ans[:k]
}

func merge(lnums []int, rnums []int) []int {
ans := make([]int, 0, len(lnums)+len(rnums))
li, ri := 0, 0
ll, lr := len(lnums), len(rnums)
for li < ll && ri < lr {
if lnums[li] > rnums[ri] {
ans = append(ans, lnums[li])
li += 1
} else if lnums[li] < rnums[ri] {
ans = append(ans, rnums[ri])
ri += 1
} else {
if isMaxInts(lnums[li:], rnums[ri:]) {
ans = append(ans, lnums[li])
li += 1
} else {
ans = append(ans, rnums[ri])
ri += 1
}
}
}

if li < ll {
ans = append(ans, lnums[li:]...)
}
if ri < lr {
ans = append(ans, rnums[ri:]...)
}

return ans
}

func maxInts(lnums []int, rnums []int) []int {
i := 0
ll, lr := len(lnums), len(rnums)
for i < ll && i < lr {
if lnums[i] > rnums[i] {
return lnums
}

if lnums[i] < rnums[i] {
return rnums
}

i += 1
}

if i == ll && i == lr {
return lnums
} else if i < ll {
return lnums
} else {
return rnums
}
}

func isMaxInts(lnums, rnums []int) bool {
i := 0
ll, lr := len(lnums), len(rnums)
for i < ll && i < lr {
if lnums[i] > rnums[i] {
return true
}

if lnums[i] < rnums[i] {
return false
}

i += 1
}

if i == ll && i == lr {
return true
} else if i < ll {
return true
} else {
return false
}
}

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

func min(a, b int) int {
if a < b {
return a
} else {
return b
}
}
1
2
3
4
5
6
7
8
9
10
11
package main

import "fmt"



func main() {
fmt.Println(maxNumber([]int{3, 4, 6, 5}, []int{9, 1, 2, 5, 8, 3}, 5))
fmt.Println(maxNumber([]int{6, 7}, []int{6, 0, 4}, 5))
fmt.Println(maxNumber([]int{3, 9}, []int{8, 9}, 3))
}

5 DONE 去除重复字母

  • State "DONE" from "TODO" [2018-04-03 二 16:36]
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
func removeDuplicateLetters(s string) string {
sM := make(map[string]int)
for i := 0; i < len(s); i += 1 {
sM[s[i:i+1]] += 1
}

var ans string
drop := len(s) - len(sM)
eM := make(map[string]bool)
for i := 0; i < len(s); i += 1 {
if eM[s[i:i+1]] {
drop -= 1
sM[s[i:i+1]] -= 1
continue
}

for drop > 0 && len(ans) > 0 && s[i:i+1] <= ans[len(ans)-1:] && sM[ans[len(ans)-1:]] > 1 {

drop -= 1
sM[ans[len(ans)-1:]] -= 1
eM[ans[len(ans)-1:]] = false
ans = ans[:len(ans)-1]
}
ans += s[i : i+1]
eM[s[i:i+1]] = true
}

return ans[:len(sM)]
}
1
2
3
4
5
6
7
8
9
10
11
12
package main

import "fmt"



func main() {
fmt.Println(removeDuplicateLetters("bcabc"))
fmt.Println(removeDuplicateLetters("cbacdcbc"))
fmt.Println(removeDuplicateLetters("ccacbaba"))
fmt.Println(removeDuplicateLetters("rusrbofeggbbkyuyjsrzornpdguwzizqszpbicdquakqws"))
}

6 DONE 跳跃游戏 II

  • State "DONE" from "TODO" [2018-04-03 二 17:17]
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 jump(nums []int) int {
if len(nums) < 2 {
return 0
}

dp := make([]int, len(nums))
dp[0] = 0
for i := 1; i < len(nums); i += 1 {
dp[i] = len(nums)
for j := i-1; j >= 0; j -= 1 {
if nums[j] >= i-j {
dp[i] = min(dp[i], dp[j]+1)
}
}
}

return dp[len(dp)-1]
}

func min(a, b int) int {
if a < b {
return a
} else {
return b
}
}
1
2
3
4
5
6
7
8
9
package main

import "fmt"



func main() {
fmt.Println(jump([]int{2, 3, 1, 1, 4}))
}

7 DONE 设置交集大小至少为2

  • State "DONE" from "TODO" [2018-04-04 三 13:39]
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
func intersectionSizeTwo(intervals [][]int) int {
sort.Slice(intervals,
func(i, j int) bool {
return intervals[i][1] < intervals[j][1] ||
intervals[i][1] == intervals[j][1] && intervals[i][0] < intervals[j][0]
})

new_intervals := make([][]int, 0)
left := intervals[0][0]
right := intervals[0][1]
for i := 1; i < len(intervals); i += 1 {
interval := intervals[i]
if interval[1] == right {
left = interval[0]
} else if interval[0] > left {
new_intervals = append(new_intervals, []int{left, right})
left = interval[0]
right = interval[1]
}
}
new_intervals = append(new_intervals, []int{left, right})
fmt.Println(new_intervals)

first := new_intervals[0][1] - 1
second := first + 1
ans := 2
for i := 1; i < len(new_intervals); i += 1 {
interval := new_intervals[i]
if interval[0] > second {
ans += 2
first = interval[1] - 1
second = first + 1
} else if interval[0] > first {
ans += 1
first = second
second = interval[1]
}
}

return ans
}

8 DONE Course Schedule III

  • State "DONE" from "TODO" [2018-04-04 三 17:02]
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
type IntHeap []int

func (h IntHeap) Len() int { return len(h) }
func (h IntHeap) Less(i, j int) bool { return h[i] > h[j] }
func (h IntHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }

func (h *IntHeap) Push(x interface{}) {
*h = append(*h, x.(int))
}

func (h *IntHeap) Pop() interface{} {
old := *h
n := len(old)
x := old[n-1]
*h = old[0 : n-1]
return x
}

func scheduleCourse(courses [][]int) int {
sort.Slice(courses,
func(i, j int) bool {
return courses[i][1] < courses[j][1] ||
courses[i][1] == courses[j][1] && courses[i][0] < courses[j][0]
})

h := &IntHeap{}
heap.Init(h)
curTime := 0
for i := 0; i < len(courses); i += 1 {
course := courses[i]
curTime += course[0]
heap.Push(h, course[0])
if curTime > course[1] {
curTime -= heap.Pop(h).(int)
}
}

return h.Len()
}
1
2
3
4
5
6
7
8
9
10
11
12
package main



func main() {
fmt.Println(scheduleCourse([][]int{
[]int{100, 200}, []int{200, 1300},
[]int{1000, 1250}, []int{2000, 3200}}))

fmt.Println(scheduleCourse([][]int{
[]int{5, 5}, []int{1, 2}, []int{2, 6}, []int{2,7}}))
}

9 DONE Patching Array

  • State "DONE" from "TODO" [2018-04-06 五 17:44]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
func minPatches(nums []int, n int) int {
miss, ans, i := 1, 0, 0
for miss <= n {
if i < len(nums) && nums[i] <= miss {
miss += nums[i]
i += 1
} else {
miss += miss
ans += 1
}
}

return ans
}

10 DONE Couples Holding Hands

  • State "DONE" from "TODO" [2018-04-07 六 22:05]
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
func minSwapsCouples(row []int) int {
n, ans := len(row), 0
for i := 0; i < n; i += 2 {
var dest int
if row[i]%2 == 0 {
dest = row[i] + 1
} else {
dest = row[i] - 1
}

if row[i+1] == dest {
continue
}

ans += 1
for j := i + 2; j < n; j += 1 {
if row[j] == dest {
row[i+1], row[j] = row[j], rows[i+1]
break
}
}
}

return ans
}

11 DONE IPO

  • State "DONE" from "TODO" [2018-04-06 五 18:40]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
func findMaximizedCapital(k int, W int, Profits []int, Capital []int) int {
if k < 1 || len(Profits) < 1 {
return W
}

max_profit, index := -1, -1
for i := 0; i < len(Profits); i += 1 {
if Capital[i] <= W && Profits[i] > max_profit {
max_profit = Profits[i]
index = i
}
}

if index < 0 {
return W
}

return findMaximizedCapital(k-1, W+max_profit,
append(Profits[0:index], Profits[index+1:]...),
append(Capital[0:index], Capital[index+1:]...))
}
1
2
3
4
5
6
7
8
9
package main

import "fmt"



func main() {
fmt.Println(findMaximizedCapital(2, 0, []int{1, 2, 3}, []int{0, 1, 1}))
}
Last Updated 2018-04-25 Wed 22:17.
Render by hexo-renderer-org with Emacs 25.3.2 (Org mode 8.2.10)