代码随想录算法训练营第二十六天 | 455、376、53

算法
, , ,

455. 分发饼干

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
package main

import "sort"

func findContentChildren(g []int, s []int) int {
    sort.Ints(g)
    sort.Ints(s)
    i, j := 0, 0
    count := 0
    for i < len(g) && j < len(s) {
        if s[j] >= g[i] {
            count++
            i++
        }
        j++
    }
    return count
}

376. 摆动序列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
package main

func wiggleMaxLength(nums []int) int {
    n := len(nums)
    if n < 2 {
        return n
    }
    up, down := 1, 1
    for i := 1; i < n; i++ {
        currentDiff := nums[i] - nums[i-1]
        if currentDiff > 0 {
            up = down + 1
        } else if currentDiff < 0 {
            down = up + 1
        }
    }
    if up > down {
        return up
    }
    return down
}

53. 最大子序和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
package main

func maxSubArray(nums []int) int {
    if len(nums) == 0 {
        return 0
    }
    currentMax := nums[0]
    globalMax := nums[0]
    for i := 1; i < len(nums); i++ {
        sum := currentMax + nums[i]
        if nums[i] > sum {
            currentMax = nums[i]
        } else {
            currentMax = sum
        }
        if currentMax > globalMax {
            globalMax = currentMax
        }
    }
    return globalMax
}