代码训练营Day.34 | 1005. K次取反后最大化的数组和、134. 加油站、135. 分发糖果

发布时间:2024年01月15日

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

1. LeetCode链接

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

2. 题目描述

3. 解法

整体来说,就是把负数全部取反,然后如果有剩余反转次数都给绝对值最小的数。

我的解法:先从小到大排序,这个需要分析多种情况。略。

class Solution {
public:
    int largestSumAfterKNegations(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end());
        int i = 0;
        int sum = 0;
        for (; i < nums.size() && k > 0; i++) {
            if (nums[i] >= 0) break;
            nums[i] = 0 - nums[i];
            sum += nums[i];
            k--;
        }
        if (i != nums.size() && k != 0) {
            if (i > 0 && nums[i] > nums[i - 1]) {
                i--;
                sum -= nums[i];
            }
            if (k % 2 == 1) nums[i] = 0 - nums[i]; 
        } else if (i == nums.size() && k != 0) {
            if (k % 2 == 1) sum -= 2 *nums[nums.size() - 1];
        }
        for (; i < nums.size(); i++) {
            sum += nums[i];
        }
        return sum;
        // k <= nums中的非正数个数
        // k > nums中的非正数个数 && 有0
        // k > nums中的非正数个数 && no 0
        // nums中全是非正数
    }
};

简洁方法,直接按照绝对值大小排序。

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

134. 加油站

1. LeetCode链接

134. 加油站 - 力扣(LeetCode)

2. 题目描述

3. 解法

整体来说,如果gas的总量 < cost的总量,汽车无论如何都不可能循环一周。否则,必可以循环一周。

我的解法:

1. 判断两个数组总量是否合理。求得存储两数组对应元素差值的数组left(表示,空油箱从i节点出发,到i + 1节点还能剩多少油)。

2. 如果left总和 < 0,直接return -1.

3. 如果left综合 > =0。在left数组上执行类似于LeetCode题目53.最大子序和的操作。首先,记录最大子序的长度len,直到长度与原数组长度相等,return 当前下标;count持续记录连续序列和,如果<0,则刷新len和count。

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int count = 0;
        vector<int> left;
        for (int i = 0; i < gas.size(); i++) {
            left.push_back(gas[i] - cost[i]);
        }
        for (int i : left) count += i;
        if (count < 0) return -1;
        int len = gas.size();
        int i = 0;
        count = 0;
        while (1) {
            if (len == 0) return i;
            count += left[i];
            len--;
            if (count < 0) {
                count = 0;
                len = gas.size();
            }
            i = (i + 1) % gas.size();
        }
    }
};

还有更简单的是,记录累加和初始坐标start,这样可以在一遍遍历后得到答案,而且只需一次遍历。

因为如果在计算局部累加和时,count < 0,则说明其对应累加初始坐标一定不是循环起始点,累加和之间的坐标,也不是!这时,初始化count并记录start。

最后,因为是一次从前到后的完整遍历。判断记录后的累加差值是负数,则return -1。否则,return start。

start之后的是否可能也存在循环起点?因为start到末尾的累加和中,从来没有小于过0,所以,start一定是第一个。

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

135. 分发糖果

1. LeetCode链接

135. 分发糖果 - 力扣(LeetCode)

2. 题目描述

3. 解法

我的解法:

整体来说,就是每个孩子尽可能拿最少的糖果数量。

一般我们自己解这种题,都是先找极小值;然后,将极小值点设为1(颗糖果),从极小值开始,向左爬升到极大值点,糖果数量依次+1,向右爬升到极大值点,糖果数量一次+1。

编程时,需要先计算完所有极小值点向一侧爬升后,再考虑一起从另一侧爬升。这是因为一个极大值点,两侧各有一个极小值点;左侧极小值点向右爬升得到的糖果数量 和 右侧极小值点向左爬升得到的糖果数量,当前极大值点要取最大值。如果按极小值点先后顺序同时考虑两侧爬升,并不能考虑到这一点。

class Solution {
public:
    int candy(vector<int>& ratings) {
        int pre = ratings[0];
        int cur;
        int post = 0;
        vector<int> index;
        vector<int> candies(ratings.size(), 0);    // 记录每个孩子能分发到的最终糖果数量
        for (int i = 0; i < ratings.size(); i++) {    // 找极小值点,其中判断时,仅考虑非严格递增/递减
            if (i == ratings.size() - 1) post = ratings[i];
            else post = ratings[i + 1];
            cur = ratings[i];
            if (pre >= cur && cur <= post) index.push_back(i);
            pre = cur;
        }
        for (int i = 0; i < index.size(); i++) {   // 从所有极小值点出发,向左爬升
            candies[index[i]] = 1;
            int c = 2;
            for (int j = index[i] - 1; j >=0; j--) {
                if (ratings[j] <= ratings[j + 1]) break;
                candies[j] = c;
                c++;
            }
        }
        for (int i = 0; i < index.size(); i++) {   // 从所有极小值点出发,向右爬升
            int c = 2;
            for (int j = index[i] + 1; j < ratings.size(); j++) {
                if (ratings[j] <= ratings[j - 1]) break;
                if (candies[j] > c) break;
                candies[j] = c;
                c++;
            }
        }
        int sum = 0;
        for (int i : candies) sum += i;     // 求和
        return sum;
    }
};

巧妙解法:

局部最优:所有孩子的相邻右孩子如果评分比他高的话+1糖果;所有孩子的相邻左孩子如果评分比他高的话+1糖果。

全局最优:相邻两个孩子评分更高的孩子会获得更多的糖果。

1. 先设置数组记录每个孩子分到的糖果数,设置基数都为1,即每个孩子都分到一个。

2. 从左向右遍历,如果当前孩子评分比前一个高,前一个糖果数+1。

3. 从右向左遍历,如果当前孩子评分比后一个高,取他原本的数/后一个糖果数+1中最大的。

class Solution {
public:
    int candy(vector<int>& ratings) {
        vector<int> candies(ratings.size(), 1);
        for (int i = 1; i < ratings.size(); i++) {
            if (ratings[i] > ratings[i - 1]) {
                candies[i] = candies[i - 1] + 1;
            }
        }
        for (int i = ratings.size() - 2; i >= 0; i--) {
            if (ratings[i] > ratings[i + 1]) {
                candies[i] = max(candies[i], candies[i + 1] + 1);
            }
        }
        int sum = 0;
        for (int i : candies) sum += i;
        return sum;
    }
};

文章来源:https://blog.csdn.net/papilon_/article/details/135599577
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。