1005.K次取反后最大化的数组和
本题简单一些,估计大家不用想着贪心 ,用自己直觉也会有思路。
题目讲解 | 题目链接
自己的想法,也通过了
class Solution {
public:
int sumMax(vector<int>& nums) {
int sum = 0;
for (int i = 0; i < nums.size(); i++) {
cout << nums[i] << endl;
sum += nums[i];
}
return sum;
}
int largestSumAfterKNegations(vector<int>& nums, int k) {
while (k--)
{
// 每次优先把最小的数取反
int min = INT32_MAX, min_idx = 0;
for (int i = 0; i < nums.size(); i++) {
if (nums[i] < min) {
min = nums[i];
min_idx = i;
}
}
nums[min_idx] *= -1;
}
return sumMax(nums);
}
};
134. 加油站
本题有点难度,不太好想,推荐大家熟悉一下方法二
题目讲解 | 题目链接
这题自己做不出来
class Solution {
public:
int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
for (int i = 0; i < cost.size(); i++) {
int rest = gas[i] - cost[i]; // 记录剩余油量
int index = (i + 1) % cost.size();
while (rest > 0 && index != i) { // 模拟以i为起点行驶一圈(如果有rest==0,那么答案就不唯一了)
rest += gas[index] - cost[index];
index = (index + 1) % cost.size();
}
// 如果以i为起点跑一圈,剩余油量>=0,返回该起始位置
if (rest >= 0 && index == i) return i;
}
return -1;
}
};
135. 分发糖果
本题涉及到一个思想,就是想处理好一边再处理另一边,不要两边想着一起兼顾,后面还会有题目用到这个思路
https://programmercarl.com/0135.%E5%88%86%E5%8F%91%E7%B3%96%E6%9E%9C.html
class Solution {
public:
int candy(vector<int>& ratings) {
if (ratings.size() == 1)
return 1;
vector<int> nums(ratings.size(), 1);
// 从前向后,右是否比左大
for (int i = 0; i <= ratings.size() - 2; i++) {
if (ratings[i + 1] > ratings[i]) {
nums[i + 1] = nums[i] + 1;
}
}
// 从后向前,左是否比右大
for (int i = ratings.size() - 2; i >= 0; i--) {
if (ratings[i + 1] < ratings[i]) {
nums[i] = max(nums[i + 1] + 1, nums[i]);
}
}
int result = 0;
for (int i = 0; i < nums.size(); i++) {
cout << nums[i] << " ";
result += nums[i];
}
return result;
}
};