当前位置:   article > 正文

算法训练营第34天|LeetCode 1005.K取反后最大化的数组和 134.加油站 135.分发糖果

算法训练营第34天|LeetCode 1005.K取反后最大化的数组和 134.加油站 135.分发糖果

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

题目链接:

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

解题思路:

先处理负数,在处理最小的数。

代码:

  1. class Solution {
  2. public:
  3. int largestSumAfterKNegations(vector<int>& nums, int k) {
  4. sort(nums.begin(), nums.end());
  5. int result = 0;
  6. for (int i = 0; i < nums.size(); i++) {
  7. if (nums[i] < 0 && k > 0) {
  8. nums[i] = -nums[i];
  9. k--;
  10. }
  11. result += nums[i];
  12. }
  13. sort(nums.begin(), nums.end());
  14. result -= nums[0] * (k % 2 == 0 ? 0 : 2);
  15. return result;
  16. }
  17. };

LeetCode 134.加油站

题目链接:

LeetCode 134.加油站

解题思路:

total_sum记录能否走到终点,cur_sum为判断起始点位置为小于0的后一个点。

代码:

  1. class Solution {
  2. public:
  3. int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
  4. int size = gas.size();
  5. int total_sum = 0, cur_sum = 0;
  6. int Index = 0;
  7. for (int i = 0; i < size; i++) {
  8. cur_sum += gas[i] - cost[i];
  9. total_sum += gas[i] - cost[i];
  10. if (cur_sum < 0) {
  11. cur_sum = 0;
  12. Index = i+1;
  13. }
  14. }
  15. if (total_sum < 0)
  16. return -1;
  17. return Index;
  18. }
  19. };

LeetCode 135.分发糖果

题目链接:

LeetCode 135.分发糖果

解题思路:

左右两边分别计算应该满足的糖果数量。先从左往右,如果比前面的大,就加一,否则则置一。

从右往左,如果比前面的大,就加一,否则取和原来相比的最大的。

代码:

  1. class Solution {
  2. public:
  3. int candy(vector<int>& ratings) {
  4. int size = ratings.size();
  5. vector<int> candy(size, 1);
  6. for (int i = 1; i < size; i++) {
  7. if (ratings[i - 1] < ratings[i]) {
  8. candy[i] = candy[i - 1] + 1;            
  9. }
  10.        
  11. }
  12. for (int i = size - 2; i >= 0; i--) {
  13. if (ratings[i] > ratings[i + 1]) {
  14. candy[i] = max(candy[i], candy[i + 1] + 1);
  15. }
  16. }
  17. int result = 0;
  18. for (int i = 0; i < size; i++)
  19. result += candy[i];
  20. return result;
  21. }
  22. };

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/我家小花儿/article/detail/406377
推荐阅读
相关标签
  

闽ICP备14008679号