细节&智商 2016-08-29

[SnackMen]

135. Candy 134. Gas Station

[SnackMen]

/*
*[AC]134. Gas Station
*/
public class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int sum=0;
        int total=0;
        int j=-1;
        for(int i=0;i<gas.length;i++){
            sum+=gas[i]-cost[i];
            total+=gas[i]-cost[i];
            if(sum<0){
                sum=0;
                j=i;
            }
        }
        if(total<0)
            return -1;
        return j+1;

    }
}

[SnackMen]

/*
*[AC]135. Candy 
*/
public class Solution {
    public int candy(int[] ratings) {
        if(ratings.length==0)
            return 0;
        int sum=0;
        int [ ]num = new int[ratings.length];
        for(int i=0;i<num.length;i++)
            num[i]=1;
        for(int i=1;i<ratings.length;i++){
            if(ratings[i]>ratings[i-1])
                num[i]=num[i-1]+1;
        }
        for(int j=ratings.length-2;j>=0;j--){
            if(ratings[j+1]<ratings[j] && num[j+1]>=num[j])
                num[j]=num[j+1]+1;
            sum+=num[j];
        }
        return sum+num[num.length-1];
    }
}

[dayang]

/**
 * [AC] LeetCode 135. Candy 
 * @param {number[]} ratings
 * @return {number}
 */
var candy = function(ratings) {
    if(ratings.length < 1) return 0;
    if(ratings.length === 1) return 1;

    var nums = [],i,j,carry;
    for(i = 0; i < ratings.length; i++){
        if(i === 0 && ratings[i] <= ratings[i+1]){
            nums[i] = 1;
        }else if(i === ratings.length - 1 && ratings[ratings.length - 1] <= ratings[ratings.length - 2]){
            nums[i] = 1;
        }else if(ratings[i-1] >= ratings[i] && ratings[i+1] >= ratings[i]){
            nums[i] = 1;
        }else{
            nums[i] = 0;
        }
    }
    for(i = 0; i < ratings.length;){
        if(nums[i] === 1){
            for(j = i - 1; j >= 0 && ratings[j] > ratings[j + 1];j--){
                nums[j] = Math.max(nums[j+1] + 1,nums[j]);
            }
            for(j = i + 1; j < ratings.length && ratings[j] > ratings[j-1];j++){
                nums[j] = Math.max(nums[j-1] + 1,nums[j]);
            }
            i = j;
        }else{
            i++;
        }
    }

    var res = 0;
    for(i = 0; i < nums.length; i++){
        res += nums[i];
    }

    return res;
};

[dayang]

/**
 * [AC] LeetCode 134. Gas Station
 * @param {number[]} gas
 * @param {number[]} cost
 * @return {number}
 */
var canCompleteCircuit = function(gas, cost) {
    var i,j,len = gas.length,gasleft;
    for(i = 0; i < len; i++){
        if(gas[i] >= cost[i]){
            gasleft = gas[i] - cost[i];
            j = (i + 1) % len;
            for(; j != i; j = (j + 1) % len){
                if(gasleft + gas[j] < cost[j])
                    break;
                gasleft = gasleft + gas[j] - cost[j];
            }
            if(j === i){
                return i;
            }
            if(j < i){
                return -1;
            }

            i = j;
        }
    }
    return -1;
};

[zhaokuohaha]

135 - C

public class Solution {
    public int Candy(int[] ratings) {
        int[] candies = new int[ratings.Length];
        for(int i=0; i<candies.Length; i++){
            candies[i]=1;
        }
        for(int i=1; i<ratings.Length; i++){
            if(ratings[i]>ratings[i-1])
                candies[i] = candies[i-1]+1;
        }
        for(int i=ratings.Length-2; i>=0; i--){
            if(ratings[i]>ratings[i+1])
                candies[i] = Math.Max(candies[i],(candies[i+1]+1));
        }
        int res = 0;
        foreach(int candy in candies){
            res += candy;
        }
        return res;
    }
}

[zhaokuohaha]

C# - 134

public class Solution {
    public int CanCompleteCircuit(int[] gas, int[] cost) {
        int total = 0;
        int index = -1;
        for(int i=0, sum = 0; i < gas.Length; i++){
            total += gas[i] - cost[i];
            sum += gas[i] - cost[i];
            if(sum < 0){
                sum = 0; 
                index = i;
            }
        }
        return total >= 0 ? index + 1 : -1;
    }
}