K次取反后最大化的数组和
leetcode：1005. K 次取反后最大化的数组和
贪心法
思路
两次贪心：（每次取反k--）
- 排序，一次遍历，按绝对值从大到小地把负数取反。
- 如果K次取反没用完，再排序一次，反复取反最小元素。
（或者一开始就按绝对值从大到小排序，只需排序一次）
复杂度分析
时间复杂度：O(NlogN)。
空间复杂度：O(1)。
注意点
-
sort排序规则函数可以通过声明一个普通函数的方式来写。
// 比较函数，用于比较两个整数的大小 bool compareInt(int a, int b) { return a < b; // 从小到大排序 } int main() { std::vector<int> numbers = {3, 1, 4, 1, 5, 9}; // 使用自定义的比较函数进行排序 std::sort(numbers.begin(), numbers.end(), compareInt); for (int num : numbers) { std::cout << num << " "; } return 0; }
代码实现
初次实现：
class Solution {
public:
// 排序，一次遍历，按绝对值从大到小地把负数取反
// 如果K次取反没用完，再排序一次，反复取反最小元素
int largestSumAfterKNegations(vector<int>& nums, int k) {
sort(nums.begin(),nums.end());
if(nums[0] < 0){ // 如果没有负数，跳过这步
for(int i = 0;i < nums.size() && k > 0;i++){
if(nums[i] < 0){
nums[i] = -nums[i];
k--;
}
}
}
if(k > 0){
sort(nums.begin(),nums.end());
while(k > 0){
nums[0] = -nums[0];
k--;
}
}
int result = 0;
for(int i : nums) result += i;
return result;
}
};
优化版：（其实都差不多）
class Solution {
static bool cmp(int a,int b){
return abs(a) > abs(b); // 按绝对值从大到小排序
}
public:
int largestSumAfterKNegations(vector<int>& nums, int k) {
sort(nums.begin(),nums.end(),cmp);
for(int i = 0;i < nums.size() && k > 0;i++){
if(nums[i] < 0){
nums[i] *= -1;
k--;
}
}
while(k > 0){
nums[nums.size() - 1] *= -1;
k--;
}
int result = 0;
for(int num:nums) result += num;
return result;
}
};
加油站
leetcode：134. 加油站
贪心法
思路
遍历一遍，计算当前油量（从开始点到当前点的累计油量），一旦为负，则移动开始点到i+1，油量归零，从i+1为开始点重新累计（油量为负肯定过不去）。一轮遍历过后，总油量如果为负数，那无论如何都过不去；如果不为负，那么当前的开始节点即为可通过的开始点。
复杂度分析
时间复杂度：O(N)。
空间复杂度：O(1)。
注意点
略
代码实现
class Solution {
public:
// 类似股票题，如果净入油量为负，一开始肯定走不过去，把它排在最后面。
// 遍历每个站，计算净入油量，如果为负就从下一个点开始
int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
int curSum = 0; // 净入
int total = 0; // 总油量
int start = 0;
for(int i = 0;i < gas.size();i++){
curSum += gas[i] - cost[i];
total += gas[i] - cost[i];
if(curSum < 0){
start = i + 1;
curSum = 0;
}
}
// 如果整体为负，那无论如何都过不去
if(total < 0) return -1;
return start;
}
};
分发糖果
leetcode：135. 分发糖果
第二道hard，Σ(っ °Д °;)っ
贪心法
思路
每次只处理一边，分两次处理。
创建糖果数组，默认每人为1
从左往右遍历一次，若右边比左边大，右边等于左边加1
从右往左遍历一次，若左边比右边大，左边等于右边加1和原值取最大
复杂度分析
时间复杂度：O(N)。
空间复杂度：O(N)。
注意点
略
代码实现
class Solution {
public:
// 默认每人为1
// 从左往右遍历一次，若右边比左边大，右边等于左边加1
// 从右往左遍历一次，若左边比右边大，左边等于右边加1和原值取最大
int candy(vector<int>& ratings) {
int total = 0;
vector<int> candies(ratings.size(),1);
for(int i = 1;i < ratings.size();i++){
if(ratings[i - 1] < ratings[i]) candies[i] = candies[i - 1] + 1;
}
for(int i = ratings.size()-2;i >= 0;i--){
if(ratings[i] > ratings[i + 1]) candies[i] = max(candies[i + 1] + 1,candies[i]);
}
for(int i : candies) total += i;
return total;
}
};