代码随想录算法训练营第二十九天| 134. 加油站 、135. 分发糖果 、860.柠檬水找零、406.根据身高重建队列。c++转java

134. 加油站

思路：因为答案是唯一的，所以是不是可以试试，如果遇到了gas[i] - cost[i] > 0,就试试,AC了，但是耗时还挺多的。代码如下：

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int n = gas.length;
        if(n == 1){
            return gas[0] >= cost[0] ? 0 : -1;
        }
        
        int result = -1;
        for(int i = 0;i < n;i++){
            // 候选点
            if(gas[i] - cost[i] > 0){
                int sum = 0;
                //先遍历后部分
                for(int j = i;j < n;j++){
                    sum += (gas[j] - cost[j]);
                    if(sum < 0)
                        break;
                }
                //遍历后部分
                if(sum >= 0){
                    for(int j = 0;j < i;j++){
                        sum += (gas[j] - cost[j]);
                        if(sum < 0)
                            break;
                    }
                    if(sum >= 0)
                        return i;
                }
            }
        }
        return result;
    }
}

贪心：代码随想录

这里其实感觉自己没理解透，就是说不清楚，但是有想不出反例 (⊙﹏⊙)

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int currentSum = 0;
        int total = 0;
        int result = 0;
        for(int i = 0;i < gas.length;i++){
            currentSum += gas[i] - cost[i];
            total += gas[i] - cost[i];
            if(currentSum < 0){
                currentSum = 0;
                result = i + 1;
            }
        }
        if(total < 0) return -1;
        return result;
    }
}

135. 分发糖果

思路：贪两次心，代码随想录

class Solution {
    public int candy(int[] ratings) {
        int len = ratings.length;
        int[] candys = new int[len];
        int result = 0;
        //先处理第一趟
        candys[0] = 1;
        for(int i = 1;i < len;i++){
            candys[i] = ratings[i] > ratings[i - 1] ? candys[i - 1] + 1 : 1;
        }
        //逆着再处理一趟
        for(int i = len - 2;i >= 0 ;i--){
            if((ratings[i] > ratings[i + 1]) && candys[i] <= candys[i + 1])
                candys[i] = candys[i + 1] + 1;
        }
        for(int candy:candys){
            result += candy;
        }
            
        return result;
    }
}

860.柠檬水找零

思路：这里就三种情况，模拟一下找零的过程就好了。

class Solution {
    public boolean lemonadeChange(int[] bills) {
        if(bills[0] != 5)
            return false;
        int n_5 = 0,n_10 = 0;
        for(int i = 0;i < bills.length;i++){
            if(bills[i] == 5) 
                n_5++;
            else if(bills[i] == 10){
                if(n_5 < 0) return false;

                n_5--;
                n_10++;
            }
            else{
                //优先消耗n_10
                if(n_5 > 0 && n_10 > 0){
                    n_5--;
                    n_10--;
                }else if(n_5 >= 3 && n_10 == 0){
                    n_5 -=3;
                }
                else
                    return false;
            }
        }
        return true;
    }
}

406.根据身高重建队列

思路：开始想到了排序，但是想的是按照k进行排序，发现没法做下去，就没进一步得想，原来真的是先排序，不过是先按照身高降序排，然后根据ki调整，好牛，详解看这里：代码随想录

class Solution {
    public int[][] reconstructQueue(int[][] people) {
        // 根据身高降序排列，身高相等，根据k升序排列
        Arrays.sort(people,(a,b) ->{
            if(a[0] == b[0]) return a[1] - b[1];
            return b[0] - a[0];
        });
        List<int[]> re = new LinkedList<>();
        for(int[] p:people){
            re.add(p[1],p);
        }
        return re.toArray(new int[people.length][]);
    }
}