算法训练day36 1005.134.135.

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

题目

1005. K 次取反后最大化的数组和 - 力扣（LeetCode）

题解

代码随想录 (programmercarl.com)

• 将数字按绝对值大小排序

• 优先将绝对值最大的负数取反

• 剩余步骤将最小非负数取反

  • 注意数组大小顺序，以及处理剩余步骤的操作

• 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(); i++)
          {
              if (nums[i] < 0 && k > 0)
              {
                  nums[i] = -nums[i];
                  k--;
              }
          }
          if (k % 2 == 1)
              nums[nums.size() - 1] *= -1;
          int result = 0;
          for (int a : nums)
              result += a;
          return result;
      }
  };
  

134.加油站

题目

134. 加油站 - 力扣（LeetCode）

题解

代码随想录 (programmercarl.com)

• 对gas和cost做差可以得到每个站点净油量

• 从头累加净油量，如果全部累加之后为负值，则任何站点都不符合要求；如果某站点出现负值，那么从此站点之前任何站点开始都不能完成环路

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

135.分发糖果

题目

135. 分发糖果 - 力扣（LeetCode）

题解

代码随想录 (programmercarl.com)

• 先确定左边关系，再确定右边关系

• class Solution
  {
  public:
      int candy(vector<int> &ratings)
      {
          vector<int> candyVec(ratings.size(), 1);
          // 从前向后
          for (int i = 1; i < ratings.size(); i++)
          {
              if (ratings[i] > ratings[i - 1])
                  candyVec[i] = candyVec[i - 1] + 1;
          }
          // 从后向前
          for (int i = ratings.size() - 2; i >= 0; i--)
          {
              if (ratings[i] > ratings[i + 1])
              {
                  candyVec[i] = max(candyVec[i], candyVec[i + 1] + 1);
              }
          }
  
          int result = 0;
          for (int i : candyVec)
              result += i;
          return result;
      }
  };