数组 2016-09-01

[zhaokuohaha]

66. Plus One 134. Gas Station

[wolfogre]

// [AC] 66. Plus One
public class Solution {
    public int[] plusOne(int[] digits) {
        int carry = 1;
        for(int i = digits.length - 1; i >= 0 && carry != 0; --i){
            digits[i] += carry;
            carry = digits[i] / 10;
            digits[i] = digits[i] % 10;
        }
        if(carry == 0)
            return digits;
        int[] result = new int[digits.length + 1];
        result[0] = 1;
        for(int i = 0; i < digits.length; ++i){
            result[i + 1] = digits[i];
        }
        return result;
    }
}

[wolfogre]

// [AC] 134. Gas Station
public class Solution {

    public int canCompleteCircuit(int[] gas, int[] cost) {
        if(gas.length == 1){
            if(gas[0] >= cost[0])
                return 0;
            else
                return -1;
        }

        int[] gasNeededToEnd = new int[gas.length];
        for(int i = 1; i < gas.length; ++i){
            gasNeededToEnd[i] = gasNeededToEnd[i - 1] + cost[i - 1] - gas[i - 1];

        }
        for(int i = 0; i < gas.length; ++i){
            int remain = 0;
            int j = i;
            for(; j < gas.length; ++j){
                remain += gas[j] - cost[j];
                if(remain < 0)
                    break;

            }
            if(remain >= 0 && remain - gasNeededToEnd[i] >= 0)
                return i;
            if(i != j)
                i = j - 1;
        }
        return -1;
    }

}

[zhaokuohaha]

66 - C

public class Solution
{
    public int[] PlusOne(int[] digits)
    {
        int sign = 1;
        for (int i = digits.Length - 1; i >= 0; i--)
        {
            digits[i] = (digits[i] + sign);

            sign = digits[i] / 10;
            digits[i] %= 10;
            if (sign == 0) break;
        }
        if (sign == 0) return digits;
        else return cat(sign, digits);
    }
    private int[] cat(int e, int[] a)
    {
        int[] res = new int[a.Length + 1];
        res[0]=e;
        for(int i = 1; i<res.Length; i++)
        {
            res[i] = a[i - 1];
        }
        return res;
    }
}

[dayang]

// [AC] LeetCode 66. Plus One
var plusOne = function(digits) {
    var carry = 1, i;
    for(i = digits.length - 1; i >= 0 && carry; i--){
        carry = digits[i] === 9 ? 1 : 0;
        digits[i] = carry ? 0 : ++digits[i];
    }

    if(carry){
        digits.unshift(1);
    }

    return digits;
};

[SnackMen]

/*
*[AC]LeetCode 66. Plus One
*/
public class Solution {
    public int[] plusOne(int[] digits) {
        int digistLength = digits.length;
        int []newDigista = null;
        if(digits[digistLength-1]<9){
            digits[digistLength-1]+=1;
            return digits;
        }
        boolean isCarry = true;
        for(int i=digistLength-1;i>=0;i--){
            if(!isCarry)
                break;
            if(digits[i]==9){
                isCarry=true;
                digits[i]=0;
                if(i==0){
                    newDigista = new int[digits.length+1];
                    System.arraycopy(digits,0,newDigista,1,digistLength);
                    newDigista[0]=1;
                }
            }else{
                isCarry=false;
                digits[i]+=1;
                newDigista = digits;
            }
        }
        return newDigista;
    }
}

[SnackMen]

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

[zhaokuohaha]

134 - C# -> 来自王舒代码

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;
    }
}