LeetCode 56-60

56. Merge Intervals

分析：

给出一个区间的集合，请合并所有重叠的区间。
先把二维数组按照左区间从小到大的顺序排序，初始左区间为第一个数组的左区间，右区间为第一个数组的右区间。然后按顺序遍历剩余的所有数组，当某个数组的左区间比之前右区间大时，肯定合并不了了，加入到list中。
否则更新右区间的大小，取当前右区间与之前右区间的较大值。
最后将list<int[]>转换为二维数组即可。

Java：

class Solution {
    public int[][] merge(int[][] intervals) {
        if (intervals.length == 0) {
            return new int[0][2];
        }
        Arrays.sort(intervals, Comparator.comparingInt(a -> a[0]));
        List<int[]> list = new ArrayList<>();
        int left = intervals[0][0], right = intervals[0][1];
        for (int i = 1; i < intervals.length; i++) {
            int L = intervals[i][0], R = intervals[i][1];
            if (L > right) {
                list.add(new int[]{left, right});
                left = L;
                right = R;
            } else {
                right = Math.max(right, R);
            }
        }
        list.add(new int[]{left, right});
        return list.toArray(new int[list.size()][]);
    }
}

57. Insert Interval

分析：

给出一个无重叠的 ，按照区间起始端点排序的区间列表。
在列表中插入一个新的区间，你需要确保列表中的区间仍然有序且不重叠（如果有必要的话，可以合并区间）。
遍历原有的区间，如果和新区间没有交集，那么直接加到结果集中，如果有交集，新区间更新为并集的左端点和右端点。然后再将后面的区间与更新之后的新区间进行比较。
最后使用 Collections.sort解决区间仍然有序的问题。

Java:

class Solution {
    public boolean isIntersection(int[] interval, int[] newInterval) {
        int L1 = interval[0], R1 = interval[1], L2 = newInterval[0], R2 = newInterval[1];
        if (Math.max(L1, L2) <= Math.min(R1, R2)) {
            return true;
        } else {
            return false;
        }
    }


    public int[][] insert(int[][] intervals, int[] newInterval) {
        if (intervals.length == 0) {
            return new int[][]{newInterval};
        }
        List<int[]> res = new ArrayList<>();
        for (int[] interval : intervals) {
            if (isIntersection(interval, newInterval) == true) {
                newInterval[0] = Math.min(interval[0], newInterval[0]);
                newInterval[1] = Math.max(interval[1], newInterval[1]);
            } else {
                res.add(interval);
            }
        }
        res.add(newInterval);
        Collections.sort(res, Comparator.comparingInt(a -> a[0]));
        return res.toArray(new int[res.size()][]);
    }
}

58. Length of Last Word

分析：

先用trim()把空格去掉。然后用空格分隔字符串，直接输出最后一个单词的长度。

Java：

class Solution {
    public int lengthOfLastWord(String s) {
        s = s.trim();
        if ("".equals(s)) {
            return 0;
        }
        String[] strs = s.split(" ");
        return strs[strs.length - 1].length();
    }
}

59. Spiral Matrix II

分析：

使用L,R,U,D代表左右上下四个边界。
然后从1数到n*n，不断将数字填充进去。

Java:

class Solution {
    public int[][] generateMatrix(int n) {
        int L = 0, R = n - 1, U = 0, D = n - 1;
        int[][] res = new int[n][n];
        int count = 1, len = n * n;
        while (count <= len) {
            for (int i = L; i <= R; i++) {
                res[U][i] = count++;
            }
            U++;
            for (int i = U; i <= D; i++) {
                res[i][R] = count++;
            }
            R--;
            for (int i = R; i >= L; i--) {
                res[D][i] = count++;
            }
            D--;
            for (int i = D; i >= U; i--) {
                res[i][L] = count++;
            }
            L++;
        }
        return res;
    }
}

60. Permutation Sequence

分析：

使用回溯，当达到第k个时，存储结果。

Java：

class Solution {
    boolean[] isVisit;
    StringBuilder temp = new StringBuilder();
    int count = 0;
    StringBuilder res;

    void generate(int index, int n, int k) {
        if (index == n + 1) {
            count++;
            if (count == k) {
                res = new StringBuilder(temp);
            }
            return;
        }
        for (int i = 1; i <= n; i++) {
            if (isVisit[i] == false) {
                temp.append(i);
                isVisit[i] = true;
                generate(index + 1, n, k);
                isVisit[i] = false;
                temp.deleteCharAt(temp.length() - 1);
            }
        }
    }

    public String getPermutation(int n, int k) {
        isVisit = new boolean[n + 1];
        generate(1, n, k);
        return res.toString();
    }
}