56. Merge Intervals

链接

https://leetcode.com/problems/merge-intervals/
#Array, #Sort, #Medium

思路

先排序，然后挨个看后一个点的begin是不是比当前hold的那个range的end要小，如果小的话就修改当前range的end，否则就开一个新的range。

代码

/**
 * Definition for an interval.
 * public class Interval {
 *     int start;
 *     int end;
 *     Interval() { start = 0; end = 0; }
 *     Interval(int s, int e) { start = s; end = e; }
 * }
 */
class Solution {
    public List<Interval> merge(List<Interval> intervals) {
        intervals.sort((a, b) -> a.start - b.start);
        if (intervals.size() < 2) {
            return intervals;
        }
        List<Interval> res = new ArrayList<>();
        res.add(new Interval(intervals.get(0).start, intervals.get(0).end));
        int now = 0;
        for (int i = 1; i < intervals.size(); i++) {
            Interval cur = intervals.get(i);
            Interval pre = res.get(now);
            if (cur.start <= pre.end) {
                res.get(now).end = Math.max(res.get(now).end, cur.end);
            } else {
                now++;
                res.add(new Interval(intervals.get(i).start, intervals.get(i).end));
            }
        }
        return res;
    }
}

112. Path Sum

链接

https://leetcode.com/problems/path-sum/
#Tree, #Depth-first Search, #Easy

思路

极其简单，直接递归向下走即可。

代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean hasPathSum(TreeNode root, int sum) {
        if (root == null) {
            return false;
        } else {
            if (root.left == null && root.right == null) {
                return sum == root.val;
            } else {
                return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);
            }
        }
    }
}

223. Rectangle Area

链接

https://leetcode.com/problems/rectangle-area/
#Math, #Medium

思路

求两个矩形一共的占地面积，实际上等于两个矩形分别的面积的和再减去重合部分。重合部分的话是需要矩形左下角两个点坐标里x, y里的最大值，和矩形右上角两个点坐标x, y里的最小值。

代码

public int computeArea(int A, int B, int C, int D, int E, int F, int G, int H) {
        int x1 = A > E ? A : E;
        int y1 = B > F ? B : F;
        int x2 = C > G ? G : C;
        int y2 = D > H ? H : D;
        int total = (C - A) * (D - B) + (G - E) * (H - F);
        if (x2 <= x1 || y2 <= y1) {
            return total;
        } else {
            return total - (y2 - y1) * (x2 - x1);
        }
    }

273. Integer to English Words

链接

https://leetcode.com/problems/integer-to-english-words/
#Math, #String, #Hard

思路

三位取一个来算。思路很简单。

代码

public String numberToWords(int num) {
    Map<Integer, String> map = new HashMap<>();
    map.put(1, "One");
    map.put(2, "Two");
    map.put(3, "Three");
    map.put(4, "Four");
    map.put(5, "Five");
    map.put(6, "Six");
    map.put(7, "Seven");
    map.put(8, "Eight");
    map.put(9, "Nine");
    map.put(10, "Ten");
    map.put(11, "Eleven");
    map.put(12, "Twelve");
    map.put(13, "Thirteen");
    map.put(14, "Fourteen");
    map.put(15, "Fifteen");
    map.put(16, "Sixteen");
    map.put(17, "Seventeen");
    map.put(18, "Eighteen");
    map.put(19, "Nineteen");
    map.put(20, "Twenty");
    map.put(30, "Thirty");
    map.put(40, "Forty");
    map.put(50, "Fifty");
    map.put(60, "Sixty");
    map.put(70, "Seventy");
    map.put(80, "Eighty");
    map.put(90, "Ninety");
    Map<Integer, String> due = new HashMap<>();
    due.put(1, "Thousand");
    due.put(2, "Million");
    due.put(3, "Billion");
    String res = "";
    List<List<String>> list = new ArrayList<>();
    if (0 == num) {
        return "Zero";
    }
    int i = 0;
    while (num != 0) {
        List<String> l = new ArrayList<>();
        int k = num % 1000;
        num = num / 1000;
        int hundred = k / 100;
        if (hundred != 0) {
            l.add(map.get(hundred));
            l.add("Hundred");
            k = k % 100;
        }
        if (k == 0) {
            
        } else if (k <= 20) {
            l.add(map.get(k));
        } else {
            int shi = k / 10;
            if (shi != 0) {
                l.add(map.get(shi * 10));
            }
            int ge = k % 10;
            if (ge != 0) {
                l.add(map.get(ge));
            }
        }
        if (l.size() != 0 && i != 0) {
            l.add(due.get(i));
        }
        i++;
        list.add(0, l);
    }
    return list.stream().flatMap(e -> e.stream()).collect(Collectors.joining(" "));
}

590. N-ary Tree Postorder Traversal

链接

https://leetcode.com/problems/n-ary-tree-postorder-traversal/
#Tree, #Easy

思路

多叉树的后序遍历，和二叉树一个道理。

代码

/*
// Definition for a Node.
class Node {
    public int val;
    public List<Node> children;

    public Node() {}

    public Node(int _val,List<Node> _children) {
        val = _val;
        children = _children;
    }
};
*/
class Solution {
    public List<Integer> postorder(Node root) {
        List<Integer> arr = new ArrayList<>();
        if (null == root) {
            return arr;
        }
        if (root.children != null) {
            root.children.forEach(e ->
                arr.addAll(postorder(e))
            );
        }
        arr.add(root.val);
        return arr;
    }
}

795. Number of Subarrays with Bounded Maximum

链接

https://leetcode.com/problems/number-of-subarrays-with-bounded-maximum/
#Array, #Medium

思路

小于上界的各线段的自由连续组合数，减去小于夏桀的各线段的自由组合连续组合数。

代码

public int numSubarrayBoundedMax(int[] A, int L, int R) {
    for (int i = 0; i < A.length; i++) {
        if (A[i] < L) {
            A[i] = -1;
        } else if (A[i] > R) {
            A[i] = -2;
        }
    }
    int total = 0;
    boolean isLess = false;
    boolean isGreat = true;
    boolean isOK = false;
    int lessCount = 0;
    int okCount = 0;
    for (int i = 0; i < A.length; i++) {
        if (A[i] == -1) {
            if (isGreat) {
                isGreat = false;
            }
            isOK = true;
            okCount++;
            if (isLess) {
                lessCount++;
            } else {
                isLess = true;
                lessCount = 1;
            }
        } else if (A[i] == -2) {
            isGreat = true;
            if (isOK) {
                total += okCount * (okCount + 1) / 2;
                isOK = false;
                okCount = 0;
            }
            if (isLess) {
                total -= lessCount * (lessCount + 1) / 2;
                lessCount = 0;
                isLess = false;
            }
        } else {
            if (isGreat) {
                isGreat = false;
                isOK = true;
                okCount = 1;
            } else if (isOK) {
                okCount++;
            } 
            if (isLess) {
                total -= lessCount * (lessCount + 1) / 2;
                lessCount = 0;
                isLess = false;
            }
        }
    }
    total += okCount * (okCount + 1) / 2;
    total -= lessCount * (lessCount + 1) / 2;
    return total;
}

848. Shifting Letters

链接

https://leetcode.com/problems/shifting-letters/
#String, #Medium

思路

这道题比较简单明了。每一位的shift要模26，因为是循环shifting。然后数组后面的shift size要依次向前加。

代码

public String shiftingLetters(String S, int[] shifts) {
    for (int i = 0; i < shifts.length; i++) {
        shifts[i] = shifts[i] % 26;
    }
    for (int i = 1; i < shifts.length; i++) {
        for (int j = 0; j < i; j++) {
            shifts[j] = shifts[j] + shifts[i];
        }
    }
    String res = "";
    for (int i = 0; i < shifts.length; i++) {
        int shift = shifts[i];
        char tc = S.charAt(i);
        tc = (char) (tc + (shift % 26));
        if (tc > 'z') {
            tc = (char) (tc - 26);
        }
        res += tc;
    }
    return res;
}

849. Maximize Distance to Closest Person

链接

https://leetcode.com/problems/maximize-distance-to-closest-person/
#Array, #Easy

思路

找到两边的连续空位数，然后再找出中间的最长连续空位数。然后再对比一下，即可得到最大的离有人座位的最短距离。

代码

public int maxDistToClosest(int[] seats) {
    int now = 0;
    int maxi = 0;
    boolean start = false;
    int startCount = 0;
    for (int i = 0; i < seats.length; i++) {
        if (seats[i] != 1) {
            now++;
            maxi = maxi > now ? maxi : now;
        } else {
            if (!start) {
                start = true;
                startCount = now;
            }
            now = 0;
        }
    }
    now = now > startCount ? now : startCount;
    int a = (maxi + 1) / 2;
    return a > now ? a : now;
}

851. Loud and Rich

链接

https://leetcode.com/problems/loud-and-rich/
#Depth-first Search, #Medium

思路

这道题需要找到不比自己穷的人里最低调（有个quiet值）的那个。最原始的想法是，存一个Map<Integer, Set<Integer>>的map，然后记录所有比自己有钱的人的全集。但是这样的话空间复杂度和时间复杂度都会增高。实际上给定一个单向无环图（也是一棵树），当我们想去看第i个人的对应解的时候，我们可以用深度优先搜索去遍历，对应着把下游结点也计算出来并且做缓存，下次再来拿的时候会节约时间。

代码

class Solution {
    
    private int[] a = null;
    
    public int[] loudAndRich(int[][] richer, int[] quiet) {
        Map<Integer, Set<Integer>> map = new HashMap<>();
        for (int i = 0; i < richer.length; i++) {
            Set<Integer> set = map.getOrDefault(richer[i][1], new HashSet<>());
            set.add(richer[i][0]);
            map.put(richer[i][1], set);
        }
        a = new int[quiet.length];
        for (int i = 0; i < a.length; i++) {
            a[i] = -1;
        }
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < quiet.length; i++) {
            list.add(findSmall(i, map, quiet));
        }
        return list.stream().mapToInt(Integer::valueOf).toArray();
    }
    
    private int findSmall(int index, Map<Integer, Set<Integer>> map, int[] quiet) {
        if (a[index] != -1) {
            return a[index];
        } else {
            Set<Integer> set = map.getOrDefault(index, new HashSet<>());
            if (set.size() == 0) {
                a[index] = index;
                return index;
            } else {
                int kk = set.stream().map(e -> findSmall(e, map, quiet)).reduce((a, b) -> quiet[a] > quiet[b] ? b : a).get();
                int val = quiet[kk] > quiet[index] ? index : kk;
                a[index] = val;
                return val;
            }
        }
    }
}

850. Rectangle Area II

链接

https://leetcode.com/problems/rectangle-area-ii/
Segment Tree, #Hard, #TODO

思路

a. 集合方法

求多个集合的数量和，是可以用诡异的|A| + |B| - |A & B|方法求出。这道题也可以这么搞，但是时间复杂度为O(n*2^n)，无法接受。

b. Y轴扫描法

从Y轴下向上看，一共有很多个Y轴上的顶点值。把Y轴坐标值从小向大排序时，每一次突变的delta(Y)乘以这段范围内X轴上线段的长度即为这段内的面积。依次类推得到最终面积。

代码

// Y轴扫描法
class Solution {
    public int rectangleArea(int[][] rectangles) {
        int[][] ps = new int[rectangles.length * 2][4];
        for (int i = 0; i < rectangles.length; i++) {
            ps[i * 2][0] = rectangles[i][1];
            ps[i * 2][1] = rectangles[i][0];
            ps[i * 2][2] = rectangles[i][2];
            ps[i * 2][3] = 1;
            ps[i * 2 + 1][0] = rectangles[i][3];
            ps[i * 2 + 1][1] = rectangles[i][0];
            ps[i * 2 + 1][2] = rectangles[i][2];
            ps[i * 2 + 1][3] = -1;
        }
        Arrays.sort(ps, Comparator.comparingInt(a -> a[0]));
        List<int[]> curLevel = new ArrayList<>();
        long res = 0;
        int lastY = -1;
        for (int i = 0; i < ps.length; i++) {
            if (ps[i][0] != lastY && lastY != -1) {
                if (curLevel.size() != 0) {
                    long len = 0;
                    curLevel.sort(Comparator.comparingInt(a -> a[0]));
                    int begin = curLevel.get(0)[0];
                    int end = curLevel.get(0)[1];
                    for (int ii = 1; ii < curLevel.size(); ii++) {
                        if (curLevel.get(ii)[0] <= end) {
                            end = Math.max(end, curLevel.get(ii)[1]);
                        } else {
                            len = len + end - begin;
                            begin = curLevel.get(ii)[0];
                            end = curLevel.get(ii)[1];
                        }
                    }
                    res = (res + (len - begin + end) * (ps[i][0] - lastY)) % 1_000_000_007;
                }
            }
            handlingRange(curLevel, ps[i]);
            lastY = ps[i][0];
        }
        return (int) res;
    }

    private void handlingRange(List<int[]> curLevel, int[] vector) {
        if (vector[3] == 1) {
            curLevel.add(new int[]{vector[1], vector[2]});
        } else {
            int index = -1;
            for (int ii = 0; ii < curLevel.size(); ii++) {
                if (curLevel.get(ii)[0] == vector[1] && curLevel.get(ii)[1] == vector[2]) {
                    index = ii;
                    break;
                }
            }
            curLevel.remove(index);
        }
    }
}