Greedy

55. Jump Game

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Determine if you are able to reach the last index.

For example:
A = [2,3,1,1,4], return true.
A = [3,2,1,0,4], return false.

class Solution {
public:
    bool canJump(vector<int>& nums) {
        size_t len = nums.size();
        if (!len) return true;
        if (nums[0] == 0) return len == 1;

        int start = 0;
        int end = nums[0];
        if (end >= len - 1) return true;
        while (end < len) {
            int next = start;
            for (int i = start; i < len && i <= end; ++i) {
                next = max(next, i + nums[i]);
            }
            if (next >= len - 1) return true;
            if (next == start) return false;
            start = end;
            end = next;
        }

        return false;
    }
};

134. Gas Station

here 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, otherwise return -1.

Note: The solution is guaranteed to be unique.

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int tank(0), total(0), index(0);
        for (size_t i = 0; i < gas.size(); ++i) {
            tank += gas[i] - cost[i];
            total += tank;
            if (tank < 0) {
                tank = 0;
                index = i + 1;
            }
        }
        if (total < 0) return -1;
        return index == gas.size() ? 0 : index;
    }
};

135. Candy

There are N children standing in a line. Each child is assigned a rating value.

You are giving candies to these children subjected to the following requirements:

Each child must have at least one candy. Children with a higher rating get more candies than their neighbors. What is the minimum candies you must give?

class Solution {
public:
    int candy(vector<int>& ratings) {
        size_t n = ratings.size();
        if (n < 2) return n;
        vector<int> num(n, 1);
        for (size_t i = 1; i < n; ++i) {
            if (ratings[i] > ratings[i-1]) num[i] = num[i-1] + 1;
        }

        for (size_t i = n - 1; i != 0; --i) {
            if (ratings[i-1] > ratings[i] && num[i-1] <= num[i]) num[i-1] = num[i] + 1;
        }

        int res = 0;
        for (auto m : num) res += m;

        return res;
    }
};

330. Patching Array

Given a sorted positive integer array nums and an integer n, add/patch elements to the array such that any number in range [1, n] inclusive can be formed by the sum of some elements in the array. Return the minimum number of patches required.

Example 1: nums = [1, 3], n = 6 Return 1.

Combinations of nums are [1], [3], [1,3], which form possible sums of: 1, 3, 4. Now if we add/patch 2 to nums, the combinations are: [1], [2], [3], [1,3], [2,3], [1,2,3]. Possible sums are 1, 2, 3, 4, 5, 6, which now covers the range [1, 6]. So we only need 1 patch.

Example 2: nums = [1, 5, 10], n = 20 Return 2. The two patches can be [2, 4].

Example 3: nums = [1, 2, 2], n = 5 Return 0.

class Solution {
public:
    int minPatches(vector<int>& nums, int n) {
        long long sum = 1;
        int i = 0;
        int cnt = 0;
        while (sum <= n) {
            if (i < nums.size() && sum >= nums[i]) {
                sum += nums[i++];
            } else {
                sum += sum;
                cnt ++;
            }
        }

        return cnt;
    }
};