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 len, int[][] updates) {
        int[] ans = new int[len];
        for(int[] u : updates){
            ans[u[0]] += u[2];
            if(u[1]+1<len)
                ans[u[1]+1] -= u[2];
        }

        for(int i=1;i<len;i++){
            ans[i] += ans[i-1];
        }

        return ans;
    }
}

Range Addition II

分析后实际求最小重合矩形。

public class Solution {
    public int maxCount(int m, int n, int[][] ops) {
        int minRow = m; int minCol = n;
        for(int[] o : ops){
            minRow = Math.min(minRow, o[0]);
            minCol = Math.min(minCol, o[1]);
        }
        return minRow*minCol;
    }
}

Longest Consecutive Sequence

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

hash map维护边界

public class Solution {
    public int longestConsecutive(int[] nums) {
        int ans = 0;
        HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
        for(int num:nums){
            if(!map.containsKey(num)){
                int left = map.getOrDefault(num-1, 0);
                int right = map.getOrDefault(num+1, 0);
                int sum = left+right+1;
                map.put(num, sum);
                ans = Math.max(ans, sum);
                map.put(num-left, sum);
                map.put(num+right, sum);
            }
            else continue;
        }
        return ans;
    }
}

union find

public class Solution {

    class WeightedUnionFind{
            HashMap<Integer, Integer> parent = new HashMap<Integer, Integer>();
            HashMap<Integer, Integer> size = new HashMap<Integer, Integer>();
            int maxSize = 1;
            public WeightedUnionFind(int[] nums){
                int n = nums.length;
                for(int i=0;i<n;i++){
                    parent.put(nums[i], nums[i]);
                    size.put(nums[i],1);
                }
            }

            public Integer root(Integer i){
                if(!parent.containsKey(i)) return null;
                while(i!=parent.get(i))
                    i=parent.get(i);
                return i;
            }

            public void union(int p, int q){
                Integer rootp = root(p);
                Integer rootq = root(q);
                if(rootp==null || rootq==null) return;
                if(rootp == rootq) return;

                int sizep = size.get(rootp);
                int sizeq = size.get(rootq);
                if(sizep<sizeq){
                    parent.put(rootp, rootq);
                    size.put(rootq, sizep+sizeq);
                }
                else{
                    parent.put(rootq, rootp);
                    size.put(rootp, sizep+sizeq);
                }

                maxSize = Math.max(maxSize, sizep + sizeq);
                System.out.println(maxSize+ " " + sizep+" "+sizeq);
            }

        }

    public int longestConsecutive(int[] nums) {
        if(nums == null || nums.length == 0) return 0;
        WeightedUnionFind uf = new WeightedUnionFind(nums);
        for(int num : nums){
            uf.union(num, num-1);
            uf.union(num, num+1);
        }
        return uf.maxSize;
    }
}