Greedy

Greedy for Beginners https://leetcode.com/discuss/general-discussion/669996/greedy-for-beginners-problems-sample-solutions

122. Best Time to Buy and Sell Stock II

Add all slope of between the peeks and valleys when the second number is larger than the first one.

T: O(n) S: O(1)

    public int maxProfit(int[] prices) {
        if (prices == null || prices.length == 0) return 0;
        int profit = 0;
        for (int i = 1; i < prices.length; i++) {
            if (prices[i] - prices[i - 1] >= 0) {
                profit += prices[i] - prices[i - 1];
            }
        }
        return profit;
    }

55. Jump Game

Maintain the farest point it can jump, if i is larger than farest it means it is not possible to jump to i.

T: O(n) S: O(1)

    public boolean canJump(int[] nums) {
        if (nums == null || nums.length == 0) return true;
        int farest = 0;
        for (int i = 0; i < nums.length; i++) {
            if (i > farest) return false;
            farest = Math.max(farest, i + nums[i]);
        }
        return true;
    }

45. Jump Game II

Initiate the maximum position that one could reach starting from the current index i or before: max_pos = nums[0]. Initiate number of steps: at least one, if array has more than 1 cell.

Iterate over number of elements in the input array:

• If max_step < i, one needs one more jump: jumps += 1. To minimize the number of jumps, choose the longest possible one: max_steps = max_pos.

• Update max_pos = max(max_pos, i + nums[i]).

    public int jump(int[] nums) {
        if (nums.length < 2) return 0;
        int maxPos = nums[0], maxSteps = nums[0];
        int step = 1;
        for (int i = 1; i < nums.length; i++) {
            if (maxSteps < i) {
                step++;
                maxSteps = maxPos;
            }
            maxPos = Math.max(maxPos, i + nums[i]);
        }
        return step;
    }

134. Gas Station

"The algorithm is pretty easy to understand. Imagine we take a tour around this circle, the only condition that we can complete this trip is to have more fuel provided than costed in total. That's what the first loop does.

If we do have more fuel provided than costed, that means we can always find a start point around this circle that we could complete the journey with an empty tank. Hence, we check from the beginning of the array, if we can gain more fuel at the current station, we will maintain the start point, else, which means we will burn out of oil before reaching to the next station, we will start over at the next station." @pigwall

T: O(n) S: O(1)

    public int canCompleteCircuit(int[] gas, int[] cost) {
        int total = 0;
        int n = gas.length;
        for (int i = 0; i < n; i++) {
            total += gas[i] - cost[i];
        }
        if (total < 0) return -1;
        int startpos = 0, accumulate = 0;
        for (int i = 0; i < n; i++) {
            accumulate += gas[i] - cost[i];
            if (accumulate < 0) {
                accumulate = 0;
                startpos = i + 1;
            }
        }
        return startpos;
    }

763. Partition Labels

Record all last indicies of each character. Consider the first label, say it's 'a'. The first partition must include the last occurrence of 'a'. However, before the last 'a' there might be a different label makes the partition bigger. For example, in "abccaddbeffe", the minimum first partition is "abccaddb". This gives us the idea for the algorithm: For each letter encountered, process the last occurrence of that letter, extending the current partition [anchor, j] appropriately.

public List<Integer> partitionLabels(String S) {
    int[] last = new int[26];
    for (int i = 0; i < S.length(); i++) {
        last[S.charAt(i) - 'a'] = i;
    }
    List<Integer> res = new ArrayList<>();
    int j = 0, anchor = 0;
    for (int i = 0; i < S.length(); i++) {
        j = Math.max(j, last[S.charAt(i) - 'a']);
        if (i == j) {
            res.add(i - anchor + 1);
            anchor = i + 1;
        }
    }
    return res;
}

843. Guess the Word

Narrow down the answer by guessing the score and update the list to ONLY keep the ones that have exact x matches with word. In this way, we narrow the candidates after we call master.guess(), and guarantee that secret is in candidates left. Full explanation.

T: O(n^2)

public void findSecretWord(String[] wordlist, Master master) {
    Arrays.sort(wordlist);
    List<String> list = new ArrayList<>(Arrays.asList(wordlist));
    int score = -1;
    for (int i = 0; i < 10; i++) {
        score = master.guess(list.get(0));
        if (score == 6) return;
        list = updateList(list, list.get(0), score);
    }
}

private List<String> updateList(List<String> list, String target, int score) {
    List<String> res = new ArrayList<>();
    for (String s : list) {
        if (getSimilarityScore(s, target) == score) {
            res.add(s);
        }
    }
    return res;
}

private int getSimilarityScore(String s, String target) {
    int count = 0;
    for (int i = 0; i < Math.min(s.length(), target.length()); i++) {
        if (s.charAt(i) == target.charAt(i)) count++;
    }
    return count;
}