定制企业网站建设,十大免费网站推广,wordpress提示ftp,西安专业网页制作Leetcode: 1005 K次取反后最大化的数组和
基本思路
这道题的思路比较简单#xff0c;如果有负数#xff0c;就先把最大的负数转化成正数#xff0c;如果全部转换完之后还有k剩余#xff0c;就将最小的正数反复正负变化。但是需要注意一点代码的写法。
代码注意点
定义绝…Leetcode: 1005 K次取反后最大化的数组和
基本思路
这道题的思路比较简单如果有负数就先把最大的负数转化成正数如果全部转换完之后还有k剩余就将最小的正数反复正负变化。但是需要注意一点代码的写法。
代码注意点
定义绝对值从大到小的排序写法判断k--条件的时候需要加上k0k剩余的时候最小的正数反复变化的代码不需要用循环直接求余数判断就可以。不然会超出时间限制。
时间复杂度: O(nlogn)
空间复杂度: O(1)
class Solution {
static bool cmp(int a, int b) {return abs(a) abs(b);
}
public:int largestSumAfterKNegations(vectorint nums, int k) {sort(nums.begin(), nums.end(), cmp);for(int i 0; i nums.size(); i){if(nums[i] 0 k 0){k--;nums[i] -nums[i];}}if (k % 2 1) nums[nums.size() - 1] * -1;int result 0;for(int i 0; i nums.size(); i){result nums[i];}return result;}
};
Leetcode: 134 加油站
首先能想到的时候如果消耗的油量比汽油量大那肯定是没办法开到的。如果小于的话肯定有办法开到但是对于起点就需要讲究了。
因此思路是每个加油站的剩余量rest[i]为gas[i] - cost[i]。i从0开始累加rest[i]和记为curSum一旦curSum小于零说明[0, i]区间都不能作为起始位置因为这个区间选择任何一个位置作为起点到i这里都会断油那么起始位置从i1算起再从0计算curSum。
时间复杂度O(n)
空间复杂度O(1)
class Solution {
public:int canCompleteCircuit(vectorint gas, vectorint cost) {int totalgas 0;int totalcost 0;for(int i 0; i gas.size();i) totalgas gas[i];for(int i 0; i cost.size();i) totalcost cost[i];if(totalcost totalgas) return -1;int currest 0;int start 0;for(int i 0; i gas.size(); i){currest gas[i] - cost[i];if(currest 0) {start i 1;//更新起始位置currest 0;//更新剩余油量}}return start;}
};
Leetcode: 135 分发糖果
这题乍一看题目都没有理解是啥意思只能学习一下题解
代码随想录
采用了两次贪心的策略
一次是从左到右遍历只比较右边孩子评分比左边大的情况。一次是从右到左遍历只比较左边孩子评分比右边大的情况。
在先确定右边评分比左边评分大的情况下从前向后遍历的过程中candy[i] candy[i-1]1是一种代码的写法
在确定左边评分比右边评分大的情况下从后向前的过程中cand[i] max(candy[i], cand[i1] 1);
时间复杂度O(N)
空间复杂度O(N)
class Solution {
public:int candy(vectorint ratings) {vectorint candy(ratings.size(), 1);for(int i 1; i candy.size() ; i){if(ratings[i] ratings[i - 1]) candy[i] candy[i - 1] 1;}for(int i candy.size() - 2; i 0; i--){if(ratings[i] ratings[i 1]) candy[i] max(candy[i], candy[i 1] 1);}int result 0;for(int i 0; i candy.size(); i){result candy[i];}return result;}
};
