Day 34 贪心算法

1005. K次取反后最大化的数组和

class Solution {
public:int largestSumAfterKNegations(vector<int>& nums, int k) {sort(nums.begin(), nums.end());int idx = 0;for (; idx < nums.size(); ++idx){if (nums[idx] < 0 && k > 0){nums[idx] = -nums[idx];k--;}else break;}sort(nums.begin(), nums.end()); // 这里需要重新排序一遍，因为前面调整了符号，所以现在最小值可能不是原来的最小正值if (k % 2){nums[0] = -nums[0];}int sum = 0;for (auto num : nums){sum += num;}return sum;}
};

代码随想录里面是按照绝对值从大到小进行排序的，这样就不用进行两次排序

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 (auto &num : nums){if (num < 0 && k > 0){num = -num;k--;}}if (k % 2){nums[nums.size() - 1] = -nums.back();}int sum = 0;for (auto num : nums){sum += num;}return sum;}
};

134. 加油站

暴力解法

模拟的思想很重要，暴力解法模拟跑一圈的过程其实比较考验代码技巧的，要对while使用的很熟练。虽然会超时

class Solution {
public:int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {int totalGas = 0, totalCost = 0, len = gas.size();totalGas = accumulate(gas.begin(), gas.end(), 0);totalCost = accumulate(cost.begin(), cost.end(), 0);if (totalCost > totalGas) return -1;for (int i = 0; i < len; i++){int rest = gas[i] - cost[i];int loop = (i + 1) % len;while (rest > 0 && loop != i){rest += gas[loop] - cost[loop];loop = (loop + 1) % len;}if (rest >= 0 && loop == i){return i;}}return -1;}
};

贪心算法

class Solution {
public:int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {int totalSum = 0, curSum = 0, start = 0;for (int i = 0; i < cost.size(); i++){int rest = gas[i] - cost[i];curSum += rest;totalSum += rest;if (curSum < 0){start = i + 1;curSum = 0;}}if (totalSum < 0) return -1;return start;}
};

135. 分发糖果

class Solution {
public:int candy(vector<int>& ratings) {vector<int> candies(ratings.size(), 1); // 注意：这里的初始值是1for (int i = 1; i < ratings.size(); i++){if (ratings[i - 1] < ratings[i]){candies[i]++;}}for (int i = ratings.size() - 2; i >= 0; i--){if (ratings[i + 1] < ratings[i]){candies[i] = max(candies[i + 1] + 1, candies[i]);}}return accumulate(candies.begin(), candies.end(), 0);}
};