信阳网站开发,安卓app下载官方正式版,微信小程序cms系统,怎么推广产品最有效1005.K次取反后最大化的数组和 本题简单一些#xff0c;估计大家不用想着贪心 #xff0c;用自己直觉也会有思路。 代码随想录 Python: class Solution:def largestSumAfterKNegations(self, nums: List[int], k: int) - int:nums.sort(keylambda x: abs(x), reverseT…1005.K次取反后最大化的数组和 本题简单一些估计大家不用想着贪心 用自己直觉也会有思路。 代码随想录 Python: class Solution:def largestSumAfterKNegations(self, nums: List[int], k: int) - int:nums.sort(keylambda x: abs(x), reverseTrue) # 关键按绝对值降序排列for i in range(len(nums)):if nums[i]0 and k0:nums[i] -nums[i]k - 1if k%21: nums[-1] * -1return sum(nums) C 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); //注意这里cmp是static methodfor (int i0; inums.size(); i) {if (nums[i]0 k0) {nums[i] * -1;k--;}}if (k%21) nums[nums.size()-1] * -1;int ans 0;for (int a:nums) ansa;return ans;}
}; 134. 加油站 本题有点难度不太好想推荐大家熟悉一下方法二 代码随想录 Python: 情况三是比较难想到的从后向前看如何覆盖cum_sum of net gas. 情况三如果累加的最小值是负数汽车就要从非0节点出发从后向前看哪个节点能把这个负数填平能把这个负数填平的节点就是出发节点。 class Solution:def canCompleteCircuit(self, gas: List[int], cost: List[int]) - int:cum_sum 0min_net float(inf)for i in range(len(gas)):cum_sum gas[i] - cost[i]if cum_sum min_net:min_net cum_sumif cum_sum 0: return -1if min_net 0: return 0for i in reversed(range(len(gas))):min_net gas[i] - cost[i]if min_net 0:return ireturn -1 C class Solution {
public:int canCompleteCircuit(vectorint gas, vectorint cost) {int cumSum 0;int minCumSum INT_MAX;for (int i0; igas.size(); i) {cumSum gas[i] - cost[i];if (cumSum minCumSum) minCumSum cumSum;}if (cumSum 0) return -1;if (minCumSum 0) return 0;for (int igas.size()-1; i0; i--) {minCumSum gas[i] - cost[i];if (minCumSum 0) return i;}return -1;}
}; 135. 分发糖果 本题涉及到一个思想就是想处理好一边再处理另一边不要两边想着一起兼顾后面还会有题目用到这个思路 代码随想录 Python: class Solution:def candy(self, ratings: List[int]) - int:n len(ratings)if n 1: return 1ans [1] * n for i in range(1, n): # 从前往后if ratings[i] ratings[i-1]:ans[i] ans[i-1] 1for i in reversed(range(n-1)): # 从后往前if ratings[i] ratings[i1]:ans[i] max(ans[i], ans[i1]1)return sum(ans)C class Solution {
public:int candy(vectorint ratings) {if (ratings.size()1) return 1;vectorint candyVec(ratings.size(), 1); for (int i1; iratings.size(); i) {if (ratings[i] ratings[i-1]) candyVec[i] candyVec[i-1] 1;}for (int iratings.size()-2; i0; i--) {if (ratings[i] ratings[i1]) candyVec[i] max(candyVec[i], candyVec[i1]1);}int ans 0;for (int c: candyVec) ans c;return ans;}
};
