【代码随想录】【算法训练营】【第35天】[134]加油站 [135]分发糖果 [860]柠檬水找零 [406]根据身高重建队列

前言

思路及算法思维，指路 代码随想录。
题目来自 LeetCode。

day 35，连休两天~

题目详情

[134] 加油站

题目描述

134 加油站

解题思路

前提：数组
思路：全局贪心算法：最小累加剩余汽油为负数，说明从非0开始，起始点至n-1点汽油剩余累加需要填平最小累加剩余汽油数；局部贪心算法：累加剩余和小于0，从i+1点开始。
重点：整体贪心算法 or 局部贪心算法。

代码实现

C语言

整体贪心算法

整体贪心算法有以下几种情况：
情况一：如果gas的总和小于cost总和，那么无论从哪里出发，一定是跑不了一圈的
情况二：rest[i] = gas[i]-cost[i]为一天剩下的油，i从0开始计算累加到最后一站，如果累加没有出现负数，说明从0出发，油就没有断过，那么0就是起点。
情况三：如果累加的最小值是负数，汽车就要从非0节点出发，从后向前，看哪个节点能把这个负数填平，能把这个负数填平的节点就是出发节点。

int canCompleteCircuit(int* gas, int gasSize, int* cost, int costSize) {
    int rest[gasSize];
    int minRest = 10001;
    int curSum = 0;
    for (int i = 0; i < gasSize; i++) {
        rest[i] = gas[i] - cost[i];
        curSum += rest[i];
        if (curSum < minRest) {
            minRest = curSum;
        }
    }
    // 如果累加剩余汽油为负数，说明总加油量 < 总消耗量，不足以跑一圈
    if (curSum < 0) {
        return -1;
    }
    // 如果最小累加剩余汽油为非负数，说明可以从0开始绕一圈
    if (minRest >= 0) {
        return 0;
    }
    // 最小累加剩余汽油为负数，说明从非0开始，起始点至n-1点汽油剩余累加需要填平最小累加剩余汽油数
    // 从后向前遍历
    for (int j = gasSize - 1; j >= 0; j--) {
        minRest += rest[j];
        if (minRest >= 0) {
            return j;
        }
    }
    return -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

局部贪心算法

局部贪心算法：
局部最优：i从0开始累加rest[i]，和记为curSum，一旦curSum小于零，说明[0, i]区间都不能作为起始位置，因为这个区间选择任何一个位置作为起点，到i这里都会断油，那么起始位置从i+1算起，再从0计算curSum。
全局最优：找到可以跑一圈的起始位置。

int canCompleteCircuit(int* gas, int gasSize, int* cost, int costSize) {
    int start = 0;
    int curSum = 0;
    int totalSum = 0;
    for (int i = 0; i < gasSize; i++) {
        curSum += gas[i] - cost[i];
        totalSum += gas[i] - cost[i];
        // 如果累加和小于0，说明不能从[0, i]中任一点出发
        if (curSum < 0) {
            curSum = 0;
            start = i + 1;
        }
    }
    // 总剩余和小于0，说明无法跑一圈
    if (totalSum < 0) {
        return -1;
    }
    return start;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

[135] 分发糖果

题目描述

135 分发糖果

解题思路

前提：相邻两个孩子评分更高的孩子，需要连续比较左中右3个孩子
思路：先比较右边评分大于左边情况：从前向后遍历数组；局部最优：只要右边评分比左边大，右边的孩子就多一个糖果；全局最优：相邻的孩子中，评分高的右孩子获得比左边孩子更多的糖果。再比较左边大于右边情况：从后向前遍历数组。
重点：确定一边之后，再确定另一边。

代码实现

C语言

贪心算法

先遍历比较右>左【从前向后】情况，后遍历左>右【从后向前】情况

int candy(int* ratings, int ratingsSize) {
    int candy[ratingsSize];
    long long candySum = 0;
    // 初始化
    for (int i = 0; i < ratingsSize; i++) {
        candy[i] = 1;
    }
    // 从前往后，遍历右孩子评分 > 左孩子评分的情况
    for (int i = 1; i < ratingsSize; i++) {
        if (ratings[i] > ratings[i - 1]) {
            // 相邻两个孩子评分更高的孩子会获得更多的糖果
            if (candy[i] <= candy[i - 1]) {
                candy[i] = candy[i - 1] + 1;
            }
        }
    }
    // 从前往后，遍历左孩子评分 > 右孩子评分的情况
    for (int i = ratingsSize - 2; i >= 0; i--) {
        if (ratings[i] > ratings[i + 1]) {
            // 相邻两个孩子评分更高的孩子会获得更多的糖果
            if (candy[i] <= candy[i + 1]) {
                candy[i] = candy[i + 1] + 1;
            }
        }
    }
    // 求糖果数量
    for (int i = 0; i < ratingsSize; i++) {
        candySum += candy[i];
    }
    return candySum;
}
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

[860] 柠檬水找零

题目描述

860 柠檬水找零

解题思路

前提：
思路：维护5，10，20三种金额的数量。
重点：贪心思维，优先消耗10的数量。

代码实现

C语言

贪心思维

bool lemonadeChange(int* bills, int billsSize) {
    int coin5 = 0;
    int coin10 = 0;
    int coin20 = 0;
    for (int i = 0; i < billsSize; i++) {
        if (bills[i] == 5) {
            coin5++;
        }
        if (bills[i] == 10) {
            if (coin5 < 1) {
                return false;
            }
            coin5--;
            coin10++;
        }
        if (bills[i] == 20) {
            if (coin10 > 0) {
                if (coin5 < 1) {
                    return false;
                }
                coin10--;
                coin5--;
            } else {
                if (coin5 < 3) {
                    return false;
                }
                coin5 -= 3;
            }
        }
    }
    return true;
}
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

[406] 根据身高重建队列

题目描述

406 根据身高重建队列

解题思路

前提：两个维度：身高h， 数量k。
思路：贪心思维：按照身高从高到低，k值从小到大排序后，按照k的值，插入数组中的位置。
重点：确定一边然后贪心另一边，两边一起考虑，就会顾此失彼。。

代码实现

C语言

贪心思维

身高一定是从大到小排（身高相同的话则k小的站前面），让高个子在前面。
按照身高排序之后，优先按身高高的people的k来插入，后序插入节点也不会影响前面已经插入的节点，最终按照k的规则完成了队列。。
局部最优：优先按身高高的people的k来插入。插入操作过后的people满足队列属性
全局最优：最后都做完插入操作，整个队列满足题目队列属性

/**
 * Return an array of arrays of size *returnSize.
 * The sizes of the arrays are returned as *returnColumnSizes array.
 * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
 */

int cmp(const void *p1, const void *p2)
{
    int *pp1 = *(int **)p1;
    int *pp2 = *(int **)p2;
    // 按照身高从高到低，k值从小到大排序
    return pp1[0] == pp2[0] ? pp1[1] - pp2[1] : pp2[0] - pp1[0];
}

void moveNum(int **people, int idx)
{
    int loc = people[idx][1];
    int *tmp = people[idx];
    // 移动loc后元素,即移动
    for (int j = idx - 1; j >= loc; j--) {
        people[j + 1] = people[j];
    }
    people[loc] = tmp;
    return;
}

int** reconstructQueue(int** people, int peopleSize, int* peopleColSize, int* returnSize, int** returnColumnSizes) {
    // 按照身高从高到低，k值从小到大排序
    qsort(people, peopleSize, sizeof(int *), cmp);

    // 按照k的值，插入数组中的位置
    int start = 0;
    int end = 0;
    for (int i = 0; i < peopleSize; i++) {
        moveNum(people, i);
    }
    // 输出
    *returnSize = peopleSize;
    *returnColumnSizes = (int *)malloc(sizeof(int) * peopleSize);
    for (int k = 0; k < peopleSize; k++) {
        (*returnColumnSizes)[k] = 2;
    }
    return people;
}
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

今日收获

1. 贪心算法：艰难的应用。