Range Addition & LCS

Range Addition

数组长度为 n ，更新次数为 k 的话，比较 trivial 的做法就是 O(nk) 的暴力解。

然而最优解是 O(n + k)，利用的算法逻辑类似 meetings rooms 的扫描线算法。

仔细思考的时候用的是类似构造法： 先想只有一个 update 操作的时候，然后逐个叠加，寻找新的共同性质。

不难看出我们可以用一个 "carry" 来表示我们目前 interval 的覆盖结果；比如 +4 和 -2 覆盖的地方，净增长一定是 +2，就像扫描线的时候带着当前的 interval / building 一样。同时我们需要定义一个 “起始” 和 “结束” ，代表着当前区间的覆盖结果，对 carry 值进行修正。

因此，只要在起始的位置 +val ，在终止的后一个位置 -val，两次操作就可以保证整个范围的正确更新。

public class Solution {
    public int[] getModifiedArray(int length, int[][] updates) {
        if(length <= 0) return new int[0];
        int[] rst = new int[length];
        for(int[] update : updates){
            int start = update[0];
            int end = update[1];
            int val = update[2];

            rst[start] += val;
            if(end + 1 < length) rst[end + 1] -= val;
        }

        int carry = 0;
        for(int i = 0; i < length; i++){
            rst[i] += carry;
            carry = rst[i];
        }

        return rst;
    }
}

Longest Consecutive Sequence

把 LCS 这题放这题放这边是因为两题的思路上有异曲同工之妙。

• 一维 interval 什么的，只关心 start 和 end 就好了。

就这意思。

    public int longestConsecutive(int[] nums) {
        if(nums == null || nums.length == 0) return 0;

        HashMap<Integer, Integer> map = new HashMap<>();
        int maxLen = 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);
            maxLen = Math.max(sum, maxLen);

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