JLUVicent

1005K次取反后最大化的数组和&134加油站&135分发糖果

 
  • 2023年 03月20日
  • 0 阅读

day34

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

题目链接：1005. K 次取反后最大化的数组和

解题思路： 参考 视频

第一步：将数组按照绝对值大小从大到小排序

第二步：从前向后遍历，遇到负数变为正数，同时k–；

第三步：如果k还大于0，反复转变数值最小的元素，将K用完

第四步：求和

// 注意比较函数写法
class Solution {
static bool cmp(int a, int b){
    return abs(a) > abs(b);
}
public:
    int largestSumAfterKNegations(vector<int>& nums, int k) {
        int result = 0;
        sort(nums.begin(),nums.end(),cmp);  //第一步
        // 第二步
        for( int i = 0; i < nums.size(); i++){
            if( nums[i] < 0 && k > 0){
                nums[i] *= -1;
                k--;
            }
        }
        if( k%2 == 1) nums[nums.size()-1] *= -1;    //第三步
        for( int i = 0; i < nums.size(); i++){  // 第四步
            result += nums[i];
        }
        return result;

    }
};

134.加油站

题目链接：134. 加油站

解题思路：参考 视频

如果总油量减去总消耗大于等于零那么一定可以跑完一圈，说明 各个站点的加油站 剩油量rest[i]相加一定是大于等于零的。

每个加油站的剩余量rest[i]为gas[i] - cost[i]。

img

那么局部最优：当前累加rest[i]的和curSum一旦小于0，起始位置至少要是i+1，因为从i之前开始一定不行。全局最优：找到可以跑一圈的起始位置。

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 ){
                cursum = 0;
                start = i + 1;
            }
        }
        if( totalsum < 0) return -1;
        return start;
    }  
};

135.分发糖果

题目链接：135. 分发糖果

解题思路：参考 视频

1.先从前向后遍历，如果右边大于左边就加1

2.从后向前遍历，如果左边大于右边就加1

  • 一次是从左到右遍历，只比较右边孩子评分比左边大的情况。
  • 一次是从右到左遍历，只比较左边孩子评分比右边大的情况。

这样从局部最优推出了全局最优，即：相邻的孩子中，评分高的孩子获得更多的糖果

class Solution {
public:
    int candy(vector<int>& ratings) {
        vector<int> candy( ratings.size(),1);   //初始每个人都有糖果
        // 从左向右遍历
        for( int i = 1; i < ratings.size(); i++){
            if( ratings[i - 1] < ratings[i]){
                candy[i] = candy[i-1] + 1;
            }
        }
        // 从右向左
        for( int i = ratings.size()-2; i >=0; i--){
            if( ratings[i] > ratings[i+1]){
                candy[i] = max( candy[i] , candy[i+1] + 1);
            }
        }
        int result = 0;
        for( int i = 0; i < candy.size(); i++){
            result += candy[i];
        }
        return result;
    }
};
搜索