Range Addition & LCS

Range Addition

在起始位置+val，在终止位置的后一个位置-val，最后再一次pass的时候，把累加的sum赋值给当前的位置。

public class Solution {
    public int[] getModifiedArray(int length, int[][] updates) {
        int[] result = new int[length];
        for (int i = 0; i < updates.length; i++) {
            int start = updates[i][0], end = updates[i][1], val = updates[i][2];
            result[start] += val;
            if (end < length - 1) {
                result[end + 1] -= val;
            }
        }

        int sum = 0;
        for (int i = 0; i < result.length; i++) {
            sum += result[i];
            result[i] = sum;
        }
        return result;
    }
}

Longest Consecutive Sequence

一维的interval，只关心start和end就好了

public class Solution {
    public int longestConsecutive(int[] nums) {
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();

        int max = 0;
        for (int i = 0; i < nums.length; i++) {
            int num = nums[i];
            if (map.containsKey(num)) {
                continue;
            }

            int leftBound = map.containsKey(num - 1) ? map.get(num - 1) : 0;
            int rightBound = map.containsKey(num + 1) ? map.get(num + 1) : 0;
            int sum = leftBound + rightBound + 1;
            map.put(num, sum);
            max = Math.max(max, sum);

            if (leftBound != 0) {
                map.put(num - leftBound, sum);
            }
            if (rightBound != 0) {
                map.put(num + rightBound, sum);
            }
        }
        return max;
    }
}

Find the Celebrity

上两题没什么关系

第一轮pass找出candidate；第二轮pass再check一下这个candidate是不是celebrity。

/* The knows API is defined in the parent class Relation.
      boolean knows(int a, int b); */

public class Solution extends Relation {
    public int findCelebrity(int n) {
        int candidate = 0;
        for (int i = 1; i < n; i++) {
            if (knows(candidate, i)) {
                candidate = i;
            }
        }

        for (int i = 0; i < n; i++) {
            if (i != candidate && (knows(candidate, i) || !knows(i, candidate))) {
                return -1;
            }
        }
        return candidate;
    }
}