14.Greedy

Candy

• 给定一堆小孩的评分

• 要求每个小孩至少有一颗糖果

• 如果小孩的评分比左右邻居的评分都高，就应该有更多的糖果

• using 1 array, 2 pass

• first pass compare with left neighbor

• second pass, compare with right neighbor

class Solution {
    /*
    using 1 array, 2 pass
    first pass, compare with left neighbor
    second pass, compare with right neighbor
    */
    public int candy(int[] ratings) {
        if (ratings == null || ratings.length == 0) return 0;
        int N = ratings.length;
        int[] candies = new int[N];
        Arrays.fill(candies, 1);
        //first pass, compare with left neighbor
        for (int i = 1; i < N; i++) {
            if (ratings[i] > ratings[i - 1]) {
                candies[i] = candies[i - 1] + 1;
            }
        }
        //second pass, compare with right neighbor
        for (int i = N - 2; i >= 0 ; i--) {
            if (ratings[i] > ratings[i + 1]) {
                candies[i] = Math.max(candies[i+1] + 1, candies[i]); //要保证新的值不能比原来的值更小
            }
        }
        //collect sum
        int sum = 0;
        for (int candy : candies) {
            sum += candy;
        }
        return sum;
    }
}

Partition Labels

• 给定string, 要求每个char最多只能在一个parition里出现

• 并且要求partition 越多越好

• try to find start and end index for each partition

• int last = S.lastIndexOf(S.charAt(start));

• loop next pointer from start to last, find and update end idx

• end = Math.max(end, S.lastIndexOf(S.charAt(next)));

public List<Integer> partitionLabels(String S) {
        List<Integer> res = new ArrayList<>();
        int len = S.length();
        int start = 0;
        while (start < len) {
            int last = S.lastIndexOf(S.charAt(start));
            int next = start + 1;
            int end = last;
            while (next < end) {
                end = Math.max(end, S.lastIndexOf(S.charAt(next)));
                next++;
            }
            res.add(end - start + 1);
            start = end + 1;
        }
        return res;
    }