【代码随想录】【算法训练营】【第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;
}

局部贪心算法

局部贪心算法：
局部最优：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;
}

[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;
}

[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;
}

[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. 贪心算法：艰难的应用。