参考前文
参考文章:
LeetCode刷题笔记【23】:贪心算法专题-1(分发饼干、摆动序列、最大子序和)
LeetCode刷题笔记【24】:贪心算法专题-2(买卖股票的最佳时机II、跳跃游戏、跳跃游戏II)
LeetCode链接:https://leetcode.cn/problems/maximize-sum-of-array-after-k-negations/description/
首先sort nums
, 然后统计其中的负数的数量为n
① n=k
, 将所有负数转为正数
② n>k
, 从小到大地处理k个负数, 然后结束
③ n
sort
数组, 对sort
后的数组最小数处理(k-n)
次
class Solution {
public:
int largestSumAfterKNegations(vector<int>& nums, int k) {
sort(nums.begin(), nums.end());
int n=0;
for(int num : nums){
if(num<0)
n++;
else
break;
}
if(n>=k){
for(int i=0; i<k; i++){
nums[i] = -nums[i];
}
}else{
for(int i=0; i<n; i++){
nums[i] = -nums[i];
}
sort(nums.begin(), nums.end());
int key = k-n;
if(key%2 != 0)
nums[0] = -nums[0];
}
int ans=0;
for(int num : nums){
ans += num;
}
return ans;
}
};
换一种实现方法: 先按照绝对值进行从大到小排序, 然后遍历加和
在k
没用完的时候遇到负数就加上其绝对值, k--
k
用完了就加上其本身值, 遍历到最后如果k
还有剩余, 且剩余k
为奇数, 就加上最后一个数的负数
class Solution {
public:
int largestSumAfterKNegations(vector<int>& nums, int k) {
sort(nums.begin(), nums.end(), [](int a, int b){
return abs(a)>abs(b);
});
int ans=0;
for(int i=0; i<nums.size(); ++i){
if(nums[i]<0 && k>0){
nums[i] = -nums[i];
k--;
}
}
if(k%2==1)
nums.back() = -nums.back();
for(int num : nums)
ans += num;
return ans;
}
};
LeetCode链接:https://leetcode.cn/problems/gas-station/description/
① 暴力解法, 把每个点都尝试跑一遍
class Solution {
public:
bool check(int index, vector<int>& diff){
int sum=diff[index], cur=index+1;
if(cur>=diff.size())
cur=0;
while(cur != index){
if(sum<0){
return false;
}else{
sum += diff[cur];
cur ++;
if(cur>=diff.size())
cur=0;
}
}
if(sum<0)
return false;
return true;
}
int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
int n=gas.size();
vector<int> diff(n);
for(int i=0; i<n; ++i){
diff[i] = gas[i] - cost[i];
}
for(int i=0; i<n; ++i){
if(check(i, diff))
return i;
}
return -1;
}
};
很遗憾, 暴力解法超出时间限制了
② 贪心算法, 过程中维护curSum
和totalSum
;
当curSum<0
时整个计数从i+1
开始(curSum
置为0
)(将ans
置为i+1
)
totalSum
记录所有的sum
, 如果最后totalSum<0
, 那么返回-1
class Solution {
public:
int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
int ans=0;
int curSum=0;
int totalSum=0;
for(int i=0; i<gas.size(); ++i){
totalSum += gas[i]-cost[i];
curSum += gas[i]-cost[i];
if(curSum<0){
ans = i+1;
curSum = 0;
}
}
if(totalSum<0)
return -1;
return ans;
}
};
暴力解法: 创建vector
, 记录给每个孩子分的糖, 初始每个孩子都有一颗糖
多次遍历, 发现一个孩子比相邻的孩子ratings
高, 但是candy
没有更多, 就candy++
, 同时ans++
循环遍历, 直到没有发现以上情况
class Solution {
public:
bool check(int i, vector<int>& ratings, vector<int>& candy){
if(i==0){
if(ratings[i]>ratings[i+1] && candy[i]<=candy[i+1])
return true;
else
return false;
}else if(i==ratings.size()-1){
if(ratings[i]>ratings[i-1] && candy[i]<=candy[i-1])
return true;
else
return false;
}else{
if((ratings[i]>ratings[i+1] && candy[i]<=candy[i+1]) || (ratings[i]>ratings[i-1] && candy[i]<=candy[i-1]))
return true;
else
return false;
}
return false;
}
int candy(vector<int>& ratings) {
vector<int> candy(ratings.size(), 1);
int ans=ratings.size();
if(ans<=1)
return ans;
bool changed=true;
while(changed==true){
changed = false;
for(int i=0; i<ratings.size(); ++i){
if(check(i, ratings, candy)){
candy[i] ++;
changed = true;
ans ++;
}
}
}
return ans;
}
};
很遗憾, 通过样例, 但是超出时间范围
参考<代>, 使用贪心算法, 具体操作如下
进行两次遍历, 一次从前往后, 一次从后往前
从前往后遍历过程中: 如果发现ratings[i+1]>ratings[i]
, 则candy[i+1] = max(candy[i+1], candy[i]+1);
从后往前遍历过程中: 如果发现ratings[i-1]>ratings[i]
, 则candy[i-1] = max(candy[i-1], candy[i]+1);
class Solution {
public:
int candy(vector<int>& ratings) {
vector<int> candy(ratings.size(), 1);
for(int i=0; i<ratings.size()-1; ++i){
if(ratings[i+1]>ratings[i])
candy[i+1] = max(candy[i+1], candy[i]+1);
}
for(int i=ratings.size()-1; i>0; --i){
if(ratings[i-1]>ratings[i])
candy[i-1] = max(candy[i-1], candy[i]+1);
}
int ans=0;
for(int c : candy)
ans += c;
return ans;
}
};
贪心, 讲真就是只有思想, 没有固定的套路.
现在做(被折磨)多了, 下意识的, 逐渐有一种"看看了解了解"的想法了.
如果笔试的时候真遇到类似的题目, 如果可以想到贪心, 那么最好;
如果一时半会儿没有想到很巧妙的方法, 最好先用暴力解法, 通过一部分测试用例, 分到手最好.
归根到底还是要代码实现能力过硬, 可不要感觉暴力解法是那么简单哦~
很多时候想的很清楚, 写出来就是很奇怪;
并且写的是一会儿, 往往在代码层面可以有优化很多的写法.
当然, 这样的功夫, 也只能在不断的练习过程中慢慢培养了.
本文参考:
K次取反后最大化的数组和
加油站
分发糖果