数据结构 3.貪心

pipidi

zhujingdi1998@gmail.com

455. Assign Cookies

Assume you are an awesome parent and want to give your children some cookies. But, you should give each child at most one cookie. Each child i has a greed factor gi, which is the minimum size of a cookie that the child will be content with; and each cookie j has a size sj. If sj >= gi, we can assign the cookie j to the child i, and the child i will be content. Your goal is to maximize the number of your content children and output the maximum number.

Example 1:

Input: [1,2,3], [1,1]

Output: 1

Explanation: You have 3 children and 2 cookies. The greed factors of 3 children are 1, 2, 3. 
And even though you have 2 cookies, since their size is both 1, you could only make the child whose greed factor is 1 content.
You need to output 1

Example 2:

Input: [1,2], [1,2,3]

Output: 2

Explanation: You have 2 children and 3 cookies. The greed factors of 2 children are 1, 2. 
You have 3 cookies and their sizes are big enough to gratify all of the children, 
You need to output 2.

一眼就是貪心算法,首先我們可以這樣想,我們需要返回的是滿足的數目。由於list1 是升序的所以我們只要滿足前面的孩子就行了,後面的需要付出更高的代價

class Solution {
    public int findContentChildren(int[] g, int[] s) {
        Arrays.sort(g);
        Arrays.sort(s);
         int i = 0, j = 0;
        while(i < g.length && j < s.length) {
            if(s[j]>=g[i]){
                i++;
                j++;
            }
            else j++;
        }
        return i;
    }
}

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 in the clockwise direction, otherwise return -1.

Note: If there exists a solution, it is guaranteed to be unique. Both input arrays are non-empty and have the same length. * Each element in the input arrays is a non-negative integer.

Example 1:

Input:

gas  = [1,2,3,4,5]
cost = [3,4,5,1,2]

Output: 3

Explanation:
Start at station 3 (index 3) and fill up with 4 unit of gas. Your tank = 0 + 4 = 4
Travel to station 4. Your tank = 4 - 1 + 5 = 8
Travel to station 0. Your tank = 8 - 2 + 1 = 7
Travel to station 1. Your tank = 7 - 3 + 2 = 6
Travel to station 2. Your tank = 6 - 4 + 3 = 5
Travel to station 3. The cost is 5. Your gas is just enough to travel back to station 3.
Therefore, return 3 as the starting index.

基于一个数学定理

如果一个数组的总和非负,那么一定可以找到一个起始位置,从他开始绕数组一圈,累加和一直都是非负的```



有了这个定理,判断到底是否存在这样的解非常容易,只需要把全部的油耗情况计算出来看看是否大于等于0即可。那么如何求开始位置在哪?注意到这样一个现象:
1. 假如从位置i开始,i+1,i+2...,一路开过来一路油箱都没有空。说明什么?说明从i到i+1,i+2,...肯定是正积累。
2. 现在突然发现开往位置j时油箱空了。这说明什么?说明从位置i开始没法走完全程(废话)。那么,我们要从位置i+1开始重新尝试吗?不需要!为什么?因为前面已经知道,位置i肯定是正积累,那么,如果从位置i+1开始走更加没法走完全程了,因为没有位置i的正积累了。同理,也不用从i+2,i+3,...开始尝试。所以我们可以放心地从位置j+1开始尝试。
class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int start = 0; // 起始位置
        int remain = 0; // 当前剩余燃料
        int debt = 0; // 前面没能走完的路上欠的债
        for(int i = 0;i<gas.length;i++){
            remain += gas[i]-cost[i];
            if(remain<0){
                start = i+1;
                debt +=remain;
                remain=0;
            }
        }
        return remain+debt>=0?start:-1;

    }
}

阅读量