leetcode 贪心

本次题解包括

134 Gas Station
135 Candy

134. Gas Station

There are N gas stations along a circular route, where the amount of gas at station i is gas[i].

You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from station i to its next station (i+1). You begin the journey with an empty tank at one of the gas stations.

Return the starting gas station's index if you can travel around the circuit once, otherwise return -1.

题目地址：leetcode Gas Station

题意：已知每个加油站能加的汽油gas[i]，还有第i个加油站到i+1个站点需要花费cost[i]的汽油。假设初始油箱为空，且油箱容量无限，求从哪个站点开始，可以绕一圈。不存在返回-1

思路：首先想想朴素的算法，对于每个点，如果gas[i] - cost[i] >=0，那么以该点x为起点，向后判断。路途中若出现油箱为负，说明该起点不对。起点x +1重复过程。。。

这样显然复杂度为o(n^2)，如何做到更好呢？

上面的过程在起点错误的时候直接进行了+1，就是初始起点的下一个。就是说，假如abcdefg 这么多个加油站，a为一开始的站点，遍历到d发现不行了。接着从b开始。

然而这没有必要。因为在过程中，有：

gas[a] - cost[a] >=0 （这是枚举的条件）
gas[a] - cost[a] + gas[b] - cost[b] >=0
gas[a] - cost[a] + gas[b] - cost[b] + gas[c] - cost[c] >=0
gas[a] - cost[a] + gas[b] - cost[b] + gas[c] - cost[c] + gas[d] - cost[d] < 0

在d之前的每一步都是不小于0的。然而他们的累加过不了d这个站点，也就是说，abc都不会是解。（比0大的数加上去都过不了了何况不加）

而d也不会是解，因为必然有gas[d] - cost[d] < 0

因此接下来从e开始最好。

C++

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

Python

class Solution(object):
    def canCompleteCircuit(self, gas, cost):
        """
        :type gas: List[int]
        :type cost: List[int]
        :rtype: int
        """
        start = remain = total = 0
        for i in range(len(gas)):
            remain += gas[i] - cost[i]
            total += gas[i] - cost[i]
            if remain < 0:
                remain = 0
                start = i + 1
        return -1 if total < 0 else start

135. Candy

There are N children standing in a line. Each child is assigned a rating value.

You are giving candies to these children subjected to the following requirements:

Each child must have at least one candy.

Children with a higher rating get more candies than their neighbors.

What is the minimum candies you must give?

题目地址：leetcode Candy

题意：有N个孩子站成一排，每个孩子都有一个分数，求最少的糖果数目使得：

每个孩子至少需要一颗糖
如果一个孩子的分数大于旁边的孩子，那么他的糖果要比旁边的多一颗。

思路：贪心。

code1:

一开始觉得先排好序，先给低的孩子1颗糖果，分数高的只要比较两边即可。

需要注意的是122 这种数据只要4颗糖，糖果分发情况为第1个1颗，第2个2颗，第3个1颗。（因此WA一次）

class Solution:
    # @param ratings, a list of integer
    # @return an integer
    def candy(self, ratings):
        if not ratings: return 0
        temp , n = [] ,len(ratings)
        for i in xrange(n):
            temp.append((ratings[i],i))
        temp.sort() 
        ans = [0]*n
        lastCandy ,lastMin = 1 ,temp[0]
        for i in xrange(n):
            index = temp[i][1]
            maxCandy = 1
            if index + 1 < n and ratings[index] > ratings[index+1]:
                maxCandy = ans[index+1] + 1
            if index - 1 >=0 and ratings[index] > ratings[index-1]:
                if maxCandy <= ans[index-1]: maxCandy=ans[index-1]+1
            ans[index] = maxCandy 
        return sum(ans)

code2:

O(nlogn)太慢，虽然可以过。但是可以优化到O(n)。

初始化所有孩子糖果为1颗，接下来从做到右扫描进行“修正”。

假设我们只考虑左边孩子的情况，如果当前孩子大于左边孩子，那么糖果要在左边孩子基础上+1.

这样扫描一遍以后，我们可以保证，对于任意的 i > 0 有 ans[i]>ans[i-1] ( if ratings[i] >rating[i-1])

接下来从右向左扫描，如果当前孩子大于右边的孩子，并且糖果数少于右边的，要在右边的孩子基础上+1

总结如下：第一次扫描保证了每个比左边高分的孩子比左边的糖果多，第二次则是右边。

Python

class Solution(object):
    def candy(self, ratings):
        """
        :type ratings: List[int]
        :rtype: int
        """
        if not ratings: return 0
        n = len(ratings)
        ans = [1] * n
        for i in range(1, n):
            if ratings[i] > ratings[i - 1]:
                ans[i] = ans[i - 1] + 1

        for i in range(n - 2, -1, -1):
            if ratings[i] > ratings[i + 1] and ans[i] <= ans[i + 1]:
                ans[i] = ans[i + 1] + 1
        return sum(ans)

C++

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