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

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

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

k次取反，我们的第一思路是将负值最大的元素优先进行取反，如果都变成了正数，我们将绝对值最小的进行反复取反将剩余取反的次数用完即可。
因此，我们可以先对数组进行按绝对值大小排序。

static bool cmp(int a,int b)
    {return abs(a)>abs(b);}
sort(nums.begin(),nums.end(),cmp);

之后从前向后进行遍历，碰到负值就将这个负值取反，并将k–，直到最后的k的次数用完。如果没用完，就将最后绝对值最小的元素进行反复取反。

代码

class Solution {
public:
static bool cmp(int a,int b)
    {return abs(a)>abs(b);}
int largestSumAfterKNegations(vector<int>& nums, int k) {
    sort(nums.begin(),nums.end(),cmp);
    for(int ii =0;ii<nums.size();ii  )
    {
        if(k<=0) break;
        if(nums[ii]<0)
        {
            nums[ii]*=(-1);
            k--;
        }
    }
    if(k%2==1) nums[nums.size()-1]*=(-1);
    int result = 0;
    for(int ii =0;ii<nums.size();ii  )
        result =nums[ii];
        return result;
    }
};

134.加油站

加油站这道题目要求我们求出可以满足旅行一周的加油站下标，显然我们可以用暴力解法，从每一个结点进行模拟，如果加油站的油量出现负数就不行，不然就可以。改方法用了两层for循环，时间复杂度为O（n²）在力扣上超时，不推荐使用。

全局最优解法

我们可以从前向后遍历一边加油站点，记录这一圈中油量最低的时候的情况（可以为负数），也就意味着，从零节点出发时，我们必须有着这么多的油量。否则就无法绕行一周，因此，我们从后向前遍历，如果存在某个节点可以满足使油量填补这个坑，说明该节点就是我们所求。

代码

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;  
        if (min >= 0) return 0;     
        for (int i = gas.size() - 1; i >= 0; i--) {
            int rest = gas[i] - cost[i];
            min  = rest;
            if (min >= 0) {
                return i;
            }
        }
        return -1;
    }
};

贪心算法

如果加油站总油量小于耗费的量，显然无法满足，我们返回-1。

我们记录起始的出发站点start，当前的油箱油量，以及总的油箱油量。
如果从start到遍历的ii，如果这段路使得当前油量小于零说明从start到节点ii都无法满足环形一周。因此，我们使start=ii，就从ii 1出发，如果ii 1到某个站点k依旧小于零了，我们就继续更新start=k 1，直到结束。
因为油箱可以无限大，所以只要有加油站总油量大于耗费的量，就一定可以环形一周，因此，我们排除不满足的节点即可。

代码

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

135.分发糖果

对于分发糖果，我们初始化一个糖果数组，容量为成员个数，值为1，表示初始都有一个糖果。
我们从前向后遍历，如果某个孩子比前一个孩子表现好，就让他的糖果数等于前一个人的糖果数加一。这样我们就可以使得后一个表现好的人一定比前一个人多一个糖果。
并且，我们需要给与比后排表现好的人更多糖果，因此，我们从后向前遍历，如果前一个孩子表现更好，我们就让他的糖果数比后一个人多，同时也不能低于当前值，因为如果低于的话，就无法满足前一次遍历的情况。因此，我们取两个数的最大值。
最后统计糖果数即可。

代码

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

这篇好文章是转载于：学新通技术网