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

题目

解法

1. 考虑绝对值

class Solution {
public:
    int largestSumAfterKNegations(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end(), [](int a, int b){return abs(a) > abs(b);} ); // 按绝对值大小排序
        int sum = 0;
        for (int i = 0; k > 0; i++) {
            if(nums[i] < 0 && i < nums.size()-1 ) {
                nums[i] = -nums[i];
                k--;
            }
            if(i == nums.size()-1){
                nums[i] = k % 2 == 0 ? nums[i] : -nums[i];
                k=-1;
            }
        }
        for (int num : nums) {
            sum += num;
        }
        return sum;

    }
};

134. 加油站

题目

解法

1. 暴力解法：超时

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        // 从各个加油站出发
        int idx ; // 加油站索引
        int curgas; // 目前的油量
        for (int i = 0; i < gas.size(); i++) {
            if(gas[i] < cost[i] ) continue; // 过滤 
            idx = i;
            curgas = 0;
            for (int j = idx; j < gas.size(); j++) {
                curgas += gas[j];
                curgas -= cost[j];
                if (curgas < 0) {
                    break;
                }  
                if (idx == 0 && j == gas.size() -1 && curgas >= 0) return idx;
                if (j == gas.size() -1) {
                    for (int k = 0; k < idx; k++) {
                        curgas += gas[k];
                        curgas -= cost[k];
                        if (curgas < 0) {
                             break;
                        }
                        if (k == idx -1 && curgas >= 0) return idx;
                    }
                }
            }   
        }
        return -1;
            // 看是否可以
    }
};

使用while来模拟环形：

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
          for (int i = 0; i < cost.size(); i++) {
            int rest = gas[i] - cost[i]; // 记录剩余油量
            int index = (i + 1) % cost.size();
            while (rest > 0 && index != i) { // 模拟以i为起点行驶一圈（如果有rest==0，那么答案就不唯一了）
                rest += gas[index] - cost[index];
                index = (index + 1) % cost.size();
            }
            // 如果以i为起点跑一圈，剩余油量>=0，返回该起始位置
            if (rest >= 0 && index == i) return i;
        }
        return -1;
    }
};

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int curSum = 0;
        int min = INT_MAX; // 从起点出发，油箱里的油量最小值
        for (int i = 0; i < gas.size(); i++) {
            int rest = gas[i] - cost[i];
            curSum += rest;
            if (curSum < min) {
                min = curSum;
            }
        }
        if (curSum < 0) return -1;  // 情况1 gas的总和小于cost总和
        if (min >= 0) return 0;     // 情况2 0就是起点
                                    // 情况3 min前面已经遍历了， 这里遍历min后面的
        for (int i = gas.size() - 1; i >= 0; i--) {
            int rest = gas[i] - cost[i];
            min += rest;
            if (min >= 0) {
                return i;
            }
        }
        return -1;
    }
};

3.贪心算法：前面的出现剩余出现负数，说明起点一定不在这里的范围内

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. 分发糖果

题目

解法

1. 贪心

class Solution {
public:
    int candy(vector<int>& ratings) {
        vector<int> candys(ratings.size(),1);
        for (int i = 1; i < ratings.size(); i++) {
            if (ratings[i] > ratings[i-1]) candys[i] = candys[i-1]+1; //比左边的多一个
        }
        for (int i = ratings.size()-2; i >= 0; i--) { //之所以从后往前，是为了保证 从前往后的第一次遍历有效
            if (ratings[i] > ratings[i+1]) candys[i] = max(candys[i], candys[i+1]+1);
        }
        int result = 0;
        for (int num : candys) result += num;
        return result;
    }
};

感悟

贪心有点难想