做哪个视频网站赚钱,上海金融网站建设,京东商城的网站建设,佛山网站建设费用预算LeetCode 1005.K次取反后最大化的数组和
题目链接#xff1a;1005.K次取反后最大化的数组和
踩坑#xff1a;没有
思路#xff1a;数组里有正有负#xff0c;肯定先对负数进行取反#xff0c;且从小开始。如果所有负数都为正后还可以取反#xff0c;则如果此时次数为奇…LeetCode 1005.K次取反后最大化的数组和
题目链接1005.K次取反后最大化的数组和
踩坑没有
思路数组里有正有负肯定先对负数进行取反且从小开始。如果所有负数都为正后还可以取反则如果此时次数为奇数将最小整数取反如果为偶数可以直接求和。
代码
class Solution {
public:int largestSumAfterKNegations(vectorint nums, int k) {sort(nums.begin(), nums.end());for(int i 0; i nums.size(); i){if(k ! 0){if(nums[i] 0){nums[i] -nums[i];k--;}}else break;}sort(nums.begin(), nums.end());if(k % 2 ! 0) nums[0] -nums[0];int result 0;for(int i 0; inums.size(); i){result result nums[i];}return result;}
};LeetCode 134.加油站
题目链接134.加油站
踩坑看了视频
思路感觉有点像钻了数学的空子因为第一所有gas-cost的差值的和小于0的话不会有解。第二除了第一种情况其他情况一定有解。所以解题过程就可以表示为如果当前站点会使计划失败剩余的油为负数那么只能将下一个站点作为起点。但是其中还是有很多隐藏逻辑以及节省的步骤可以辨析的。
代码
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){start i1;curSum 0;}}if(totalSum 0) return -1;return start;}
};LeetCode 135.分发糖果
题目链接135.分发糖果
踩坑以为分开考虑是以最小值为中心向左向右。
思路从左向右遍历处理右孩子大于左孩子的情况从右向左遍历处理左孩子大于右孩子的情况。初始的孩子分配一个糖果。最后取两种情况下的较大值因为较小值肯定不满足另一种情况至于为什么较大的值肯定满足两种情况并没有解释。。。
代码
class Solution {
public:int candy(vectorint ratings) {vectorint result(ratings.size(), 0);vectorint t(ratings.size(), 0);result[0] 1;t[t.size()-1] 1;for(int i 1; i ratings.size(); i){if(ratings[i] ratings[i-1]) result[i] result[i-1] 1;else result[i] 1;}for(int i ratings.size()-2; i 0; i--){if(ratings[i] ratings[i1]){result[i] max(result[i], t[i1] 1);t[i] t[i1] 1;}else t[i] 1;}int sum 0;for(int i: result) sum i;return sum;}
};
