写资料的网站有哪些,世界各国gdp排名,企业风险查询平台,网站开发需要多少钱app代码随想录算法训练营
—day29 文章目录 代码随想录算法训练营前言一、134. 加油站暴力解法贪心算法 二、135. 分发糖果三、860. 柠檬水找零四、406.根据身高重建队列vector版list版 总结 前言
今天是算法营的第29天#xff0c;希望自己能够坚持下来#xff01; 今日任务希望自己能够坚持下来 今日任务 ● 134. 加油站 ● 135. 分发糖果 ● 860.柠檬水找零 ● 406.根据身高重建队列 一、134. 加油站 题目链接 文章讲解 视频讲解 暴力解法
class Solution {
public:int canCompleteCircuit(vectorint gas, vectorint cost) {for (int i 0; i cost.size(); i) {int rest gas[i] - cost[i]; // 记录剩余油量int index (i 1) % cost.size();while (rest 0 index ! i) { // 模拟以i为起点行驶一圈如果有rest0那么答案就不唯一了rest gas[index] - cost[index];index (index 1) % cost.size();}// 如果以i为起点跑一圈剩余油量0返回该起始位置if (rest 0 index i) return i;}return -1;}
};贪心算法
思路
如果总油量减去总消耗大于等于零那么一定可以跑完一圈说明 各个站点的加油站 剩油量rest[i]相加一定是大于等于零的。每个加油站的剩余量rest[i]为gas[i] - cost[i]。i从0开始累加rest[i]和记为curSum一旦curSum小于零说明[0, i]区间都不能作为起始位置因为这个区间选择任何一个位置作为起点到i这里都会断油那么起始位置从i1算起再从0计算curSum。
解释第三点 有没有可能 [0i] 区间 选某一个作为起点累加到 i这里 curSum是不会小于零呢 如果是区间2开始累加不小于0但从区间1区间2是小于0的可以得出区间1是小于0的。 但根据我们的代码逻辑只要小于0就会更新起始位置那么在遍历到区间1和区间2之间的时候就已经更新起始位置了不会一直加到当前这个位置。
class Solution {
public:int canCompleteCircuit(vectorint gas, vectorint cost) {int curSum 0;int totalSum 0;int start 0;for (int i 0; i gas.size(); i ) {curSum gas[i] - cost[i]; //计算当前累加值totalSum gas[i] - cost[i]; //计算整个数组的累加值if (curSum 0) { //当前累加值小于0start i 1; //更新起始位置到i1curSum 0; //重新累加}}if (totalSum 0) return -1; //说明不可能跑完一圈return start; //totalSum0时,将start之前的累加看作A, 之后的累加看作B, 已知AB total0A0,B0,//那么B|A|也就是B-A, 所以BA0, 从start点出发可以跑完}
};二、135. 分发糖果 题目链接 文章讲解 视频讲解 思路 当有两个维度需要考虑的时候先考虑其中一边再考虑另一边。 本题是先考虑右孩子是否评分比较高再考虑做孩子是否评分比较高。 1.创建一个糖果数数组初始化为1每个小孩至少有一个糖果 2.从第二个元素开始从前往后遍历判断当前元素是否比左边元素大 3.是则当前元素需要比左边元素糖果1 4.从倒数第二个元素开始从后往前遍历判断当前元素是否比右边元素大 5.是则当前元素比右边元素糖果1与第一次遍历的结果做比较取两者最大值 6.遍历糖果数组计算糖果总数。
对于第二次遍历为什么要从后往前遍历 因为取糖果1的时候是取右边的糖果1如果是从前往后的话右边的糖果是一直更新的那么就导致当前正确的糖果数也一直需要更新。
代码如下
class Solution {
public:int candy(vectorint ratings) {vectorint candys(ratings.size(), 1);//从第二个元素开始从前往后遍历判断当前元素是否比左边元素大for (int i 1; i ratings.size(); i ) {if (ratings[i] ratings[i - 1]) candys[i] candys[i - 1] 1;}//从倒数第二个元素开始从后往前遍历判断当前元素是否比右边元素大for (int i ratings.size() - 2; i 0; i --) {if (ratings[i] ratings[i 1]) {candys[i] max(candys[i], candys[i 1] 1);} }int result 0;for (int candy:candys) {result candy;}return result;}
};三、860. 柠檬水找零 题目链接 文章讲解 视频讲解 思路 记录拿到的5美金10美金的张数。分三种情况处理 1.收到5美金直接5美金数量1 2.收到10美金10美金数量1,5美金数量-1 3.收到20美金优先找一张10美金和5美金当没有10美金时找3张5美金。
代码如下 class Solution {public:bool lemonadeChange(vectorint bills) {int num5 0;int num10 0;for (int i 0; i bills.size(); i) {if (bills[i] 5) num5; //5美金else if (bills[i] 10) { //找5美金10美金num5--;num10;}else { //20美金if (num10) { //优先给一张10美金和一张5美金num10--;num5--;} else { //不够的话就用3张5美金num5 - 3;}}if (num5 0) return false; //5美金不够}return true;}};四、406.根据身高重建队列 题目链接 文章讲解 视频讲解 思路 跟135. 分发糖果 一样本题也需要考虑两个情况身高和排在前面的人数。 那么先试试先按其中一个元素来排序。
如果按照k来从小到大排序排完之后会发现k的排列并不符合条件身高也不符合条件两个维度哪一个都没确定下来。如果按身高h来排序身高一定是从大到小排身高相同的话则k小的站前面让高个子在前面。那么此时优先按身高高的people的k来插入后序插入节点也不会影响前面已经插入的节点最终按照k的规则完成了队列。
vector版
代码如下
class Solution {
public://people[i] [hi, ki]//按身高从高到低排列身高相等时k值小的排前面static bool cmp(const vectorint a, const vectorint b) {if (a[0] b[0]) return a[1] b[1];return a[0] b[0];}vectorvectorint reconstructQueue(vectorvectorint people) {sort(people.begin(), people.end(), cmp);vectorvectorint result;for (int i 0; i people.size(); i) {int pos people[i][1]; //获取people[i]的k值result.insert(result.begin() pos, people[i]); //按照k值插入到结果集中}return result;}
};list版
因为vector是动态数组在插入的时候会触发扩容且数组的插入效率低。而list底层是链表插入的效率高得多。 但是需要注意的是vector是连续内存所以可以用vector.begin()pos的方式直接插入。 而链表不是连续内存所以只能通过迭代器it的形式找到要插入的位置再调用insert插入。
class Solution {
public:static bool cmp(const vectorint a, const vectorint b) {if (a[0] b[0]) return a[1] b[1];return a[0] b[0];}vectorvectorint reconstructQueue(vectorvectorint people) {sort(people.begin(), people.end(), cmp);listvectorint result; //list底层是链表实现插入效率比vector高得多for (int i 0; i people.size(); i) {int pos people[i][1];auto it result.begin(); //listvectorint iterator it result.begin();while (pos--) { //寻找插入位置it;}result.insert(it, people[i]);} return vectorvectorint(result.begin(), result.end());}
};总结
贪心算法第三天当遇到需要考虑两个维度的条件时先处理好其中一个条件再处理另一个条件。
明天继续加油
