做机械的专业外贸网站有哪些,简单个人网站设计,体育西网站开发,wordpress主题编辑刷题记录 134. 加油站135. 分发糖果860. 柠檬水找零406. 根据身高重建队列 134. 加油站
leetcode题目地址
记录全局剩余油量和当前剩余油量#xff0c;当前剩余小于0时#xff0c;其实位置是当前位置的后一个位置。若全局剩余油量为负#xff0c;则说明整体油量不足以走完… 刷题记录 134. 加油站135. 分发糖果860. 柠檬水找零406. 根据身高重建队列 134. 加油站
leetcode题目地址
记录全局剩余油量和当前剩余油量当前剩余小于0时其实位置是当前位置的后一个位置。若全局剩余油量为负则说明整体油量不足以走完全程。
小trick可以加速c程序运行。
// c
cin.tie(nullptr) - sync_with_stdio(false);cin.tie(nullptr)避免调用cin时自动刷新cout。 sync_with_stdio(false)关闭 C 标准流与 C 标准流同步例如cin和scanf同步。
下面另一种写法
// c
std::ios::sync_with_stdio(false); // 关闭 C 和 C 流的同步
std::cin.tie(nullptr); // 解开 cin 和 cout 的绑定时间复杂度 O ( n ) O(n) O(n) 空间复杂度 O ( 1 ) O(1) O(1)
// c
class Solution {
public:int canCompleteCircuit(vectorint gas, vectorint cost) {cin.tie(nullptr) - sync_with_stdio(false);int start0, rest0, all0;for(int i0; igas.size(); i){rest gas[i]-cost[i];all gas[i]-cost[i]; if(rest0) {rest0;start i1;}}if(all0) return -1;return start;}
};135. 分发糖果
leetcode题目地址
先初始化糖果列表均为1因为每个人至少发一个。先从前向后检查若后一个大于前一个则后一个糖果等于前一个糖果1。 再从后向前检查若后一个小于前一个将前一个糖果赋值为max(当前糖果后一个糖果1)。
时间复杂度 O ( n ) O(n) O(n) 空间复杂度 O ( 1 ) O(1) O(1)
// c
class Solution {
public:int candy(vectorint ratings) {cin.tie(nullptr) - sync_with_stdio(false);int all0;vectorint candies(ratings.size(), 1);for(int i1; iratings.size(); i){if(ratings[i-1]ratings[i]){candies[i] candies[i-1]1;}}for(int iratings.size()-2; i0; i--){if(ratings[i1]ratings[i]){candies[i] max(candies[i1]1, candies[i]);}}for(int i0; icandies.size(); i){all candies[i];}return all;}
};860. 柠檬水找零
leetcode题目地址
记录5元和10元的个数当出现找不开就返回false。
时间复杂度 O ( n ) O(n) O(n) 空间复杂度 O ( 1 ) O(1) O(1)
// c
class Solution {
public:bool lemonadeChange(vectorint bills) {int rest10, rest20;for(int i0; ibills.size(); i){if(bills[i]5) rest1;else if(bills[i]10){if(rest1 0) {rest1--;rest2;}else{return false;}}else if(bills[i]20){if(rest20 rest10) {rest1--;rest2--;}else if(rest13){rest1-3;}else return false;}}return true;}
};406. 根据身高重建队列
leetcode题目地址
思路来源
时间复杂度 O ( n ) O(n) O(n) 空间复杂度 O ( n ) O(n) O(n)
// c
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);vectorvectorint result;for(int i0; ipeople.size(); i){int pos people[i][1];result.insert(result.begin()pos, people[i]);}return result;}
};
