哪里找做网站的,郑州制作网站电话133,wordpress创建wiki页面,做设计去哪些网站下载素材一、贪心Ⅲ
1、加油站 134
这道题直接想法是采用二重循环暴力搜索#xff0c;简单粗暴但是会超时#xff0c;是因为以每个点为起点最坏的情况可能都要遍历完全部的序列#xff0c;有大量重复的操作#xff0c;那有没有优化的地方呢#xff1f;有一个结论#xff1a;如果…一、贪心Ⅲ
1、加油站 134
这道题直接想法是采用二重循环暴力搜索简单粗暴但是会超时是因为以每个点为起点最坏的情况可能都要遍历完全部的序列有大量重复的操作那有没有优化的地方呢有一个结论如果以 i i i位置出发最远可达 j j j位置那么在在这段区间里的任意一点出发都不可能达到比 j j j位置更远的地方。反证法可以得出。可以通过这个结论避免大量重复搜索每个位置只会经过一次。 代码如下
class Solution {
public:int canCompleteCircuit(vectorint gas, vectorint cost) {int n gas.size(), s 0;for(int i0; in; i){s gas[i] - cost[i];int j (i 1) % n;while(s 0 i ! j){s gas[j] - cost[j];j (j 1) % n;}if(ji s 0)return i;if(j i)return -1;i j - 1;}return -1;}
};2、分发糖果 135
分发糖果需要满足其左右孩子的评分高低直接想着满足两边的条件比较困难可以先满足一边的条件在此基础上再满足另一边的条件。 先满足与左边孩子的条件从前往后看如果当前孩子评分高于左孩子则当前孩子的糖果是左孩子的糖果数加1如果不高于则给最少的糖果1个。 在此基础上再去从后往前看每个孩子的右孩子如果当前孩子评分高于右孩子则 当前孩子糖果是在已有糖果 和 右孩子糖果1之间取最大值这样可以满足左右孩子两个条件。 代码如下
class Solution {
public:int candy(vectorint ratings) {int n ratings.size();vectorint ans(n, 1);// 从前往后for(int i1; in; i)if(ratings[i] ratings[i-1])ans[i] ans[i-1] 1;// 从后往前int s ans[n-1];for(int in-2; i0; --i){if(ratings[i] ratings[i1])ans[i] max(ans[i], ans[i1] 1);s ans[i];}return s;}
};3、柠檬水找零 860
这题逻辑比较清楚10美元只能用5美元找零20美元可以用3个5美元 或者 1个5美元1个10美元找零。但10美元只能用于20美元找零5美元可用于10、20美元找零用处更多所以应该优先使用10美元5美元去找零20美元如果没有10美元再全用5美元找零。
class Solution {
public:bool lemonadeChange(vectorint bills) {int num_5 0, num_10 0; // 5/10美元数量for(int bill : bills){switch(bill){case 5:num_5;break;case 10:{num_5--;num_10;break;}case 20:{// 优先使用10美元if(num_10 0)num_10--;elsenum_5 - 2;num_5--;}}if(num_10 0 || num_5 0)return false;}return true;}
};4、根据身高重建队列 406
有两个元素一个是身高h一个是前面不小于当前高度的人数k。可以先按考虑按身高h排序确定之后再按 k进行插入
class Solution {static bool cmp(const vectorint a, const vectorint b) {if (a[0] b[0]) return a[1] b[1];return a[0] b[0];}
public:vectorvectorint reconstructQueue(vectorvectorint people) {sort(people.begin(), people.end(), cmp);vectorvectorint ans;for(auto p : people)ans.insert(ans.begin()p[1], p);return ans;}
};二、写在后面
加油站这题比较巧妙如果能想到那个结论就很容易进行优化。分发糖果和根据身高重建队列这题主要是当需要满足两边条件时同时兼顾两边处理起来麻烦 可以先处理一边再处理另一边。
