网站专题框架怎么做,西安本地十家做网站建设的公司,石排仿做网站,用php做一网站有哪些今天的题目尊嘟好难…除了第三题没看视频#xff0c;其他的题目都是看了视频才做出来的。二刷等我。
134. 加油站
感觉这道题和之前的53. 最大子序和有点像#xff0c;最大子序和是一旦当前总和为负数则立即抛弃当前的总和#xff0c;从下个位置重新开始计算#xff0c;而…今天的题目尊嘟好难…除了第三题没看视频其他的题目都是看了视频才做出来的。二刷等我。
134. 加油站
感觉这道题和之前的53. 最大子序和有点像最大子序和是一旦当前总和为负数则立即抛弃当前的总和从下个位置重新开始计算而这道题是一旦遇到当前剩余的燃油小于0则立马抛弃当前的燃油总和以下个位置为新起点当然这道题还需要计算遍历过的所有节点的燃油与损耗之差万一循环结束current_sum0但是total_sum0也是不行的所以在循环结束以后并不是判断current_sum是否大于0因为有可能出现从0出发到不了第i个节点从第i 1个节点遍历到结束时current_sum 0但是剩下的燃油i节点前面的燃油坚持不到第i个节点的情况综上在循环结束以后应该判断total_sum是否大于等于0。
class Solution {
public:int canCompleteCircuit(vectorint gas, vectorint cost) {int result 0; //记录起始位置int current_sum 0; //到达某个站点后剩余的油量int total_sum 0; //记录所有能得到的油与消耗量之间的差值for(int i 0; i gas.size(); i){current_sum (gas[i] - cost[i]); //执行完这条语句后车子已经到达第i 1个站点了total_sum (gas[i] - cost[i]);if(current_sum 0){result i 1;current_sum 0;} }if(total_sum 0) return -1; //已经遍历到末尾了不可能跑一圈return result;}
};135. 分发糖果
这道题我思路想到了先从左往右遍历处理一遍再从后往前遍历一遍再处理一遍但是我在一些代码细节上没有想清楚所以老是写不对就很气。。。首先第一个代码细节是明确两次遍历的处理对象是谁第一次从左往右遍历应该处理左边的值还是右边的值呢我这里处理的是右边的值代码是这么写的
//从左往右遍历(右边比左边大的情况)
for(int i 1; i ratings.size(); i){if(ratings[i] ratings[i - 1])v[i] v[i - 1] 1;
}第二次遍历从右往左由于前面遍历处理的是右值反过来遍历的时候就必须处理左值为什么因为如果倒过来遍历还是处理右值的话相当于做无用功上一次遍历的时候已经对右值赋值过了没有必要再用一次循环。处理左值的代码我是这么写的
//从右往左遍历(左边比右边大的情况)
for(int i ratings.size() - 1; i 0; i--){if(ratings[i] ratings[i - 1])v[i - 1] max(v[i] 1, v[i - 1]);
}第二个细节就是第二次遍历的时候的赋值操作并不是简单地在旁边的较小值的糖果数上加1就完事了有可能在第一次遍历的时候已经满足大小关系了第二遍再处理一遍的话会导致重复处理糖果一定会多发所以一定要取赋值过后与之前的值之间的较大值。 这是完整的代码
class Solution {
public:int candy(vectorint ratings) {vectorint v(ratings.size(), 1);//从左往右遍历(右边比左边大的情况)for(int i 1; i ratings.size(); i){if(ratings[i] ratings[i - 1])v[i] v[i - 1] 1;}//从右往左遍历(左边比右边大的情况)for(int i ratings.size() - 1; i 0; i--){if(ratings[i] ratings[i - 1])v[i - 1] max(v[i] 1, v[i - 1]); }return accumulate(v.begin(), v.end(), 0);}
};860.柠檬水找零
这个比较简单收5块钱不找零收10块钱只能找5块的零收20块的优先用105找零其次再用555找零按照这个规则去遍历数组在钞票数够用的情况下一定可以找零return true如果出现钞票不够的情况直接return false。
class Solution {
public:mapint, int money;bool lemonadeChange(vectorint bills) {for(int i 0; i bills.size(); i){if(bills[i] 5)money[5];else if(bills[i] 10){ if(money[5] 0) //必须要有5元零钱return false;money[5]--;money[10];}else{if(money[5] 0 || (money[10] * 10 money[5] * 5 15)) //找不起钱return false;if(money[10] 0){money[10]--;money[5]--;}else money[5] - 3;}}return true;}
};406.根据身高重建队列
说是说这个题目和分发糖果的思路很像但是我还是做不出来┭┮﹏┭┮被自己菜哭了。这道题有两个维度一个是身高h一个是前面比本人高的人数k这道题并不能先选择任意一个维度进行排序因为先按照k排序过后得到的数组依旧没什么逻辑性很混乱但是按照身高降序排列的话能得到一些比较好的性质那就是后面的元素插到前面时该元素前面的元素的相对位置无需变动因为从后面插进来的人身高一定会比前面的人矮并不会影响前面的人的k值这个性质就非常好。 这道题的原理想清楚以后还没有那么容易写出来这个题目还比较考验C基本功需要对vectorvector自定义排序规则首先按身高进行降序排列身高相同的则k值小的排前面。第二个就是要将元素插入到指定位置其余元素相对位置不变vector并没有现成的函数可以调用所以要自己手搓一个这里主要还是用swap函数来实现当某个元素需要插入到前面时就将该元素与前一个元素交换位置如此循环直到该元素被交换到指定位置。
class Solution {
public:static bool compareVectors(const std::vectorint a, const std::vectorint b) { // 按照身高降序排列,若身高相同则k值小的靠前if(a[0] b[0]) return true;else if(a[0] b[0]) return false;else return a[1] b[1];} vectorvectorint reconstructQueue(vectorvectorint people) {sort(people.begin(), people.end(), compareVectors);for(int i 0; i people.size(); i){int j i;int target people[i][1];while(j target){iter_swap(people.begin() j, people.begin() j - 1);j--;}}return people;}
};好难啊。。今天这个博客是我写的篇幅最大的博客之一了。
