leetcode -- 贪心

题目1  .汽车加油

https://leetcode.com/problems/gas-station/

题目描述，gas数组为每个站可以加油的量，cost数组为每个站到下一站的耗费。

题解： curGas += gas[i] -cost[i]   统计目前还剩油量，如果小于0则表示在i之前的所有站点都不可能是起点（因为累加到现在有负了），start = i+1,curGas清0.  本题思路中一个重要的点是每次只统计了上一个start到i之间的curGas是否大于0，那上个start之前的加油站怎么知道能不能走？  通过  总量来判断，当总加油量大于总耗油量时总存在一个方法能通过所有加油站， curGas>0 则保证了找到一个能走到最后的路径。

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
       int N = gas.length;
       int curGas=0;
       int balance = 0;
       int start = 0;
       for(int i=0;i<N;i++){
           curGas += gas[i] - cost[i] ;
           if(curGas <0){
               curGas = 0;
               start = (i+1)%N;
           }
           balance += gas[i] - cost[i] ;
       }
        return balance >=0 ? start :-1;
    }
}

---

 

题目2 . 分糖果问题

https://leetcode.com/problems/candy/

题目描述： 小朋友分糖果，每个小朋友都有一个分数，分数大的小朋友要比临近的小朋友糖果多，且每个小朋友至少一个糖果。

题解： ①先给每个小朋友一个糖果，②然后从左到右 比左边大的小朋友糖果数等于左边+1  ，③从右到左 比右边大的小朋友糖果等于  max(自身，右边+1）

class Solution {
    public int candy(int[] ratings) {
        
        int[] candys = new int[ratings.length];
        
        Arrays.fill(candys,1);
        
        for(int i=1;i<ratings.length;i++){
            if(ratings[i]>ratings[i-1]){
                candys[i] = candys[i-1]+1;
            }
        }
        
        for(int i= ratings.length-2;i>=0;i--){
            if(ratings[i] > ratings[i+1]){
                candys[i] = Math.max(candys[i],candys[i+1]+1);
            }
        }
        int count = 0;
        for(int i=0;i<candys.length;i++){
            count += candys[i];
        }
        return count;
    }
}

---

题目3. 修补数组  （前缀和问题）

https://leetcode.com/problems/patching-array/

题目描述： 增加元素使得数组中的元素通过组合可以得到    n  以内的所有数字【1-n】.数组为有序；

题解：前缀和问题，用一个变量记录此时能达到的 和  pre_max ，遍历数组，如果下一个数A[i] 大于前缀和，证明在A[i-1] 和A[i]之间需要补充其它数字，需要补充的数字应该为   pre_max+1 ,因为前面的数字已经保证了最大能拼凑出pre_max， 故下一个数字必须要为pre_max +1, 这样以后前缀和就更新为 pre_max += pre_max+1. 

class Solution {
    public int minPatches(int[] nums, int n) {
       if(n <= 0 )return 0;
       long pre_max = 0;
        int ans = 0;
        
        for(int i=0;i<nums.length ;i++){
            int e = nums[i];
            if(e >n || pre_max > n)break; 
            // 当e比n都大的时候无意义，pre_max比n大的时候早就达到要求了
            
            while(pre_max+1 <e ){
                ans++;
                pre_max += pre_max +1 ;
            }
            pre_max += e;
        }
        
        if(pre_max <n){
            while(pre_max < n){
                ans++;
                pre_max += pre_max +1;
            }
        }
        return ans;
    }
    
}

---