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)