代码随想录算法训练营第二十八天 | 134、135、860、406

算法
, , ,

134. 加油站

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

func canCompleteCircuit(gas []int, cost []int) int {
    totalTank, currentTank, start := 0, 0, 0
    for i := 0; i < len(gas); i++ {
        totalTank += gas[i] - cost[i]
        currentTank += gas[i] - cost[i]
        if currentTank < 0 {
            start = i + 1
            currentTank = 0
        }
    }
    if totalTank >= 0 {
        return start
    }
    return -1
}

135. 分发糖果

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
package main

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

    candies := make([]int, n)
    for i := range candies {
        candies[i] = 1
    }

    // 从左到右遍历，确保右边高分孩子糖果更多
    for i := 1; i < n; i++ {
        if ratings[i] > ratings[i-1] {
            candies[i] = candies[i-1] + 1
        }
    }

    // 从右到左遍历，确保左边高分孩子糖果更多，同时不破坏之前的条件
    for i := n - 2; i >= 0; i-- {
        if ratings[i] > ratings[i+1] {
            candies[i] = max(candies[i], candies[i+1]+1)
        }
    }

    // 计算总糖果数
    sum := 0
    for _, c := range candies {
        sum += c
    }
    return sum
}

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

860. 柠檬水找零

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
package main

func lemonadeChange(bills []int) bool {
    five, ten := 0, 0
    for _, bill := range bills {
        switch bill {
        case 5:
            five++
        case 10:
            if five == 0 {
                return false
            }
            five--
            ten++
        case 20:
            if ten > 0 && five > 0 {
                ten--
                five--
            } else if five >= 3 {
                five -= 3
            } else {
                return false
            }
        }
    }
    return true
}

406. 根据身高重建队列

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

import "sort"

func reconstructQueue(people [][]int) [][]int {
    // 按身高降序排序，身高相同按 k 升序排列
    sort.Slice(people, func(i, j int) bool {
        if people[i][0] == people[j][0] {
            return people[i][1] < people[j][1]
        }
        return people[i][0] > people[j][0]
    })

    res := make([][]int, 0)
    for _, p := range people {
        idx := p[1]
        // 将当前元素插入到 k 的位置
        res = append(res[:idx], append([][]int{p}, res[idx:]...)...)
    }
    return res
}