Letcode刷题记录

125. 验证回文串

如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后，短语正着读和反着读都一样。则可以认为该短语是一个 回文串 。

字母和数字都属于字母数字字符。

给你一个字符串 s，如果它是 回文串 ，返回 true ；否则，返回 false 。

示例 1：

输入: s = “A man, a plan, a canal: Panama”
输出：true
解释：”amanaplanacanalpanama” 是回文串。
示例 2：

输入：s = “race a car”
输出：false
解释：”raceacar” 不是回文串。
示例 3：

输入：s = “ “
输出：true
解释：在移除非字母数字字符之后，s 是一个空字符串 “” 。
由于空字符串正着反着读都一样，所以是回文串。

提示：

1 <= s.length <= 2 * 105
s 仅由可打印的 ASCII 字符组成

注意点：
i–

class Solution {
    public boolean isPalindrome(String s) {
        s = s.replace(" ","").toLowerCase();
        for(int i=0;i<s.length();i++){
            if(s.charAt(i) >='a' && s.charAt(i) <='z'){
                continue;
            }
            if(s.charAt(i) >= '0' && s.charAt(i) <='9'){
                continue;
            }
            s = s.substring(0,i) + s.substring(i+1);
            i--;
        }

        if(s.length()==0) return true;

        int last = s.length()-1;
        for (int i=0;i<s.length();i++){
            if(s.charAt(i) != s.charAt(last)){
                return false;
            }
            if(i >= last) return true;
            last--;
        }
        return false;
    }
}

392. 判断子序列

给定字符串 s 和 t ，判断 s 是否为 t 的子序列。

字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，”ace”是”abcde”的一个子序列，而”aec”不是）。

进阶：

如果有大量输入的 S，称作 S1, S2, … , Sk 其中 k >= 10亿，你需要依次检查它们是否为 T 的子序列。在这种情况下，你会怎样改变代码？

致谢：

特别感谢 @pbrother 添加此问题并且创建所有测试用例。

示例 1：

输入：s = “abc”, t = “ahbgdc”
输出：true
示例 2：

输入：s = “axc”, t = “ahbgdc”
输出：false

思路：

• 双指针法，一起喝成。

  class Solution {
      public boolean isSubsequence(String s, String t) {
          int p1 = 0;
          int p2 = 0;
          while(true){
              if(p1 > s.length()-1) return true;
              if(p2 > t.length()-1) return false;
              if(s.charAt(p1) == t.charAt(p2)){
                  p1++;
                  p2++;
              }else{
                  p2++;
              }
          }
      }
  }

167. 两数之和 II - 输入有序数组

给你一个下标从 1 开始的整数数组 numbers ，该数组已按 非递减顺序排列 ，请你从数组中找出满足相加之和等于目标数 target 的两个数。如果设这两个数分别是 numbers[index1] 和 numbers[index2] ，则 1 <= index1 < index2 <= numbers.length 。

以长度为 2 的整数数组 [index1, index2] 的形式返回这两个整数的下标 index1 和 index2。

你可以假设每个输入 只对应唯一的答案 ，而且你 不可以 重复使用相同的元素。

你所设计的解决方案必须只使用常量级的额外空间。

示例 1：

输入：numbers = [2,7,11,15], target = 9
输出：[1,2]
解释：2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 。
示例 2：

输入：numbers = [2,3,4], target = 6
输出：[1,3]
解释：2 与 4 之和等于目标数 6 。因此 index1 = 1, index2 = 3 。返回 [1, 3] 。
示例 3：

输入：numbers = [-1,0], target = -1
输出：[1,2]
解释：-1 与 0 之和等于目标数 -1 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 。

思路：
双指针法，一气呵成

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int p1=0;
        int p2= numbers.length-1;
        while(true){
            if(numbers[p1]+numbers[p2] > target){
                p2--;
                continue;
            }else if(numbers[p1]+numbers[p2] < target){
                p1++;
                continue;
            }else{
                return new int[]{p1+1,p2+1};
            }
        }
    }
}

11. 盛最多水的容器

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。

找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。

说明：你不能倾斜容器。

示例 1：

输入：[1,8,6,2,5,4,8,3,7]
输出：49
解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。
示例 2：

输入：height = [1,1]
输出：1

思路：
双指针法，一气呵成

class Solution {
    public int maxArea(int[] height) {
        int p1 = 0;
        int p2 = height.length-1;
        int max = 0;
        while(true){
            int newMax = (p2-p1)*(height[p1]<height[p2]?height[p1]:height[p2]);
            max = max > newMax?max:newMax;
            if(height[p1]<height[p2]){
                p1++;
            }else{
                p2--;
            }
            if(p1>=p2) break;
        }
        return max;
    }
}

15. 三数之和

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。

注意：答案中不可以包含重复的三元组。

示例 1：

输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
解释：
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意，输出的顺序和三元组的顺序并不重要。
示例 2：

输入：nums = [0,1,1]
输出：[]
解释：唯一可能的三元组和不为 0 。
示例 3：

输入：nums = [0,0,0]
输出：[[0,0,0]]
解释：唯一可能的三元组和为 0 。

思路：

1. 先排序 ，排序复杂度 nlogn
2. 三指针法,最左指针从左往右暴力走
3. 第二三指针，参考二指针法，左右移动，复杂度N
4. 重复问题，最左指针，跟前指针比较，相同则跳过
5. 重复问题，第二指针第三指针，重复问题。如果第三指针重复，理应跳过，再次向左。
6. 如果第二指针重复，理应跳过，再次向右。
7. 但是，第三指针重复并非一定要跳过，因为不一定满足和为0的条件，
8. 所以只需要考虑和为0的时候
9. 和为0则向右移，所以只需要考虑和为0的时候需要不需要跳过即可。

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> rst = new ArrayList();
        for(int i=0;i<nums.length-2;i++){
            if(i>0&&nums[i] == nums[i-1]){
                continue;
            }
            int left = i+1; int right = nums.length-1;
            while(true){
                if(left >= right) break;
                if(nums[i] + nums[left] + nums[right] <0){
                    left++;
                    continue;
                }else if(nums[i] + nums[left] + nums[right] ==0){
                    if(left-i>1 && nums[left]==nums[left-1]){
                        left++;
                        continue;
                    }
                    List<Integer> d = new ArrayList();
                    d.add(nums[i]);d.add(nums[left]);d.add(nums[right]);
                    rst.add(d);
                    left++;
                    continue;
                }else{
                    right--;
                    continue;
                }
            }
        }
        return rst;
    }
}

209. 长度最小的子数组

给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其总和大于等于 target 的长度最小的 子数组 [numsl, numsl+1, …, numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

示例 1：

输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。
示例 2：

输入：target = 4, nums = [1,4,4]
输出：1
示例 3：

输入：target = 11, nums = [1,1,1,1,1,1,1,1]
输出：0

思路：

1. 双指针滑动窗口法
2. 左右指针之间窗口求和，
3. 如果大于target，则右左指针滑动，窗口减左值
4. 如果小于target，则右指针滑动，窗口加右值

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int left = 0;int right=0;
        int minLen = Integer.MAX_VALUE;
        int count=nums[0];
        // if(count >= target) return 1;
        while(true){
            if(count>=target) {
                minLen = minLen < right-left+1? minLen:right-left+1;
                count-=nums[left];
                left++;
            }else if(count<target){
                right++;
                if(right > nums.length-1 && count<target) break;
                if(right > nums.length-1){
                    continue;
                }
                count+=nums[right];
            }
        }
        return minLen == Integer.MAX_VALUE?0:minLen;
    }
}

3. 无重复字符的最长子串

给定一个字符串 s ，请你找出其中不含有重复字符的 最长 子串 的长度。

示例 1:

输入: s = “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。
示例 2:

输入: s = “bbbbb”
输出: 1
解释: 因为无重复字符的最长子串是 “b”，所以其长度为 1。
示例 3:

输入: s = “pwwkew”
输出: 3
解释: 因为无重复字符的最长子串是 “wke”，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，”pwke” 是一个子序列，不是子串。

解题思路：

1. 左右双指针法，滑动窗口

class Solution {
    public int lengthOfLongestSubstring(String s) {
        if("".equals(s)) return 0;
        int left=0;int right=0;
        int maxLen = 1;
        while(right < s.length()){
            if(right == left){
                right++;
                continue;
            }else if (left < right){
                int tmp = left;
                while(true){
                    if(s.charAt(tmp) == s.charAt(right)){
                        maxLen = maxLen > right-left?maxLen:right-left;
                        left = tmp+1;
                        break;
                    }else if(tmp == right-1){
                        right++;
                        break;
                    }else if(tmp < right){
                        tmp++;
                    }
                }
            }
        }
        maxLen = maxLen > right-left? maxLen:right-left;
        return maxLen;
    }
}

36. 有效的数独

请你判断一个 9 x 9 的数独是否有效。只需要 根据以下规则 ，验证已经填入的数字是否有效即可。

数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）

注意：

一个有效的数独（部分已被填充）不一定是可解的。
只需要根据以上规则，验证已经填入的数字是否有效即可。
空白格用 ‘.’ 表示。

示例 1：

输入：board =
[[“5”,”3”,”.”,”.”,”7”,”.”,”.”,”.”,”.”]
,[“6”,”.”,”.”,”1”,”9”,”5”,”.”,”.”,”.”]
,[“.”,”9”,”8”,”.”,”.”,”.”,”.”,”6”,”.”]
,[“8”,”.”,”.”,”.”,”6”,”.”,”.”,”.”,”3”]
,[“4”,”.”,”.”,”8”,”.”,”3”,”.”,”.”,”1”]
,[“7”,”.”,”.”,”.”,”2”,”.”,”.”,”.”,”6”]
,[“.”,”6”,”.”,”.”,”.”,”.”,”2”,”8”,”.”]
,[“.”,”.”,”.”,”4”,”1”,”9”,”.”,”.”,”5”]
,[“.”,”.”,”.”,”.”,”8”,”.”,”.”,”7”,”9”]]
输出：true
示例 2：

输入：board =
[[“8”,”3”,”.”,”.”,”7”,”.”,”.”,”.”,”.”]
,[“6”,”.”,”.”,”1”,”9”,”5”,”.”,”.”,”.”]
,[“.”,”9”,”8”,”.”,”.”,”.”,”.”,”6”,”.”]
,[“8”,”.”,”.”,”.”,”6”,”.”,”.”,”.”,”3”]
,[“4”,”.”,”.”,”8”,”.”,”3”,”.”,”.”,”1”]
,[“7”,”.”,”.”,”.”,”2”,”.”,”.”,”.”,”6”]
,[“.”,”6”,”.”,”.”,”.”,”.”,”2”,”8”,”.”]
,[“.”,”.”,”.”,”4”,”1”,”9”,”.”,”.”,”5”]
,[“.”,”.”,”.”,”.”,”8”,”.”,”.”,”7”,”9”]]
输出：false
解释：除了第一行的第一个数字从 5 改为 8 以外，空格内其他数字均与 示例1 相同。 但由于位于左上角的 3x3 宫内有两个 8 存在, 因此这个数独是无效的。

提示：

board.length == 9
board[i].length == 9
board[i][j] 是一位数字（1-9）或者 ‘.’

思路：
朴素的按按照逻辑走，用三个数组来存放状态，三个数组都没有，则满足条件

class Solution {
    public boolean isValidSudoku(char[][] board) {
    
        int[][] line = new int[9][128];
        int[][] row = new int[9][128];
        int[][] panel = new int[9][128];
        for(int i=0;i<9;i++){
            for(int j=0;j<9;j++){
                if(board[i][j] == '.') continue;
                if(row[i][board[i][j]] !=0) return false;
                row[i][board[i][j]] = 1;
                if(line[j][board[i][j]] !=0) return false;
                line[j][board[i][j]] = 1;
                int p = (i/3)*3+(j/3);
                if(panel[p][board[i][j]] != 0) return false;
                panel[p][board[i][j]] = 1;
            }
        }
        return true;
    }
}

290. 单词规律

给定一种规律 pattern 和一个字符串 s ，判断 s 是否遵循相同的规律。

这里的 遵循 指完全匹配，例如， pattern 里的每个字母和字符串 s 中的每个非空单词之间存在着双向连接的对应规律。

示例1:

输入: pattern = “abba”, s = “dog cat cat dog”
输出: true
示例 2:

输入:pattern = “abba”, s = “dog cat cat fish”
输出: false
示例 3:

输入: pattern = “aaaa”, s = “dog cat cat dog”
输出: false

注意点：
string比较用equals
char 比较用 ==

class Solution {
    public boolean wordPattern(String pattern, String s) {
        Map<Character,String> dic1= new HashMap();
        Map<String,Character> dic2 = new HashMap();
        char[] ca = pattern.toCharArray();
        String[] sa = s.split(" ");
        if(ca.length !=sa.length) return false;
        for(int i=0;i<ca.length;i++){
            if(dic1.get(ca[i])==null){
                dic1.put(ca[i],sa[i]);
            }
            if(dic2.get(sa[i]) == null){
                dic2.put(sa[i],ca[i]);
            }
            if(!dic1.get(ca[i]).equals(sa[i])) return false;
            if(dic2.get(sa[i]) != ca[i]) return false;
        }
        return true;
    }
}

242. 有效的字母异位词

给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的 字母异位词。

示例 1:

输入: s = “anagram”, t = “nagaram”
输出: true
示例 2:

输入: s = “rat”, t = “car”
输出: false

class Solution {
    public boolean isAnagram(String s, String t) {
        char[] ca = s.toCharArray();
        char[] ta = t.toCharArray();
        if(ca.length != ta.length) return false;
        Map<Character,Integer> dic = new HashMap();
        for(int i=0;i<ca.length;i++){
            dic.put(ca[i],dic.getOrDefault(ca[i],0) +1);
        }
        for(int i=0;i<ta.length;i++){
            dic.put(ta[i],dic.getOrDefault(ta[i],0) -1);
            if(dic.get(ta[i]) <0)return false;
        }
        return true;

    }
}

49. 字母异位词分组

给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。

字母异位词 是由重新排列源单词的所有字母得到的一个新单词。

示例 1:

输入: strs = [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”]
输出: [[“bat”],[“nat”,”tan”],[“ate”,”eat”,”tea”]]
示例 2:

输入: strs = [“”]
输出: [[“”]]
示例 3:

输入: strs = [“a”]
输出: [[“a”]]

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String,List<String>> dic = new HashMap();
        for(int i =0;i<strs.length;i++){
            char[] tmp = strs[i].toCharArray();
            Arrays.sort(tmp);
            String key = new String(tmp);
            List<String> l =  dic.getOrDefault(key,new ArrayList());
            l.add(strs[i]);
            dic.put(key,l);
        }
        List<List<String>> rst = new ArrayList();
        for(List<String> s :dic.values()){
            rst.add(s);
        }
        return rst;
    }
}

1. 两数之和

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。

你可以按任意顺序返回答案。

示例 1：

输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
示例 2：

输入：nums = [3,2,4], target = 6
输出：[1,2]
示例 3：

输入：nums = [3,3], target = 6
输出：[0,1]

接题思路：

1. hash存放数组的值，和角标， 复杂度N
2. 核心原理，利用了hash的 唯一性 set ，同时比set还多一个存储空间value

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer,Integer> dic = new HashMap();  // key 是值，  value是 脚标
        for(int i =0;i<nums.length;i++){
            Integer val = dic.get(target-nums[i]);
            if (val != null){
                return new int[]{i, val};
            }
            dic.put(nums[i],i);
        }
        return new int[]{};
    }
}

202. 快乐数

编写一个算法来判断一个数 n 是不是快乐数。

「快乐数」 定义为：

对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。
如果这个过程 结果为 1，那么这个数就是快乐数。
如果 n 是 快乐数 就返回 true ；不是，则返回 false 。

示例 1：

输入：n = 19
输出：true
解释：
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1
示例 2：

输入：n = 2
输出：false

思路：

1. 借助set结构不重复特性，存储已经出现过的

   class Solution {
       //2     4
       // 4*4   16
       // 1+36   37
       // 9+ 49   58
       // 25 64    89
       // 64 81     145
       //  1 16 25    42
       //  16 4      20
       // 2       4
       //         16
       public boolean isHappy(int n) {
           Set<Integer> set = new HashSet();
           while(true){
               int key = 0;
               int d=0;
               // 3 9 81 65 61 37 58 89 145 42 20 4 
               while(true){
                   if(n==0) {
                       n = key;
                       break;
                   }
                   d = n%10;
                   key+=d*d;
                   n = n/10;
               }
               if(key == 1) return true;
               if(set.contains(key)){
                   return false;
               }
               set.add(key);
           }
       }
   }

219. 存在重复元素 II

给你一个整数数组 nums 和一个整数 k ，判断数组中是否存在两个 不同的索引 i 和 j ，满足 nums[i] == nums[j] 且 abs(i - j) <= k 。如果存在，返回 true ；否则，返回 false 。

示例 1：

输入：nums = [1,2,3,1], k = 3
输出：true
示例 2：

输入：nums = [1,0,1,1], k = 1
输出：true
示例 3：

输入：nums = [1,2,3,1,2,3], k = 2
输出：false

class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        Map<Integer,List<Integer>> dic = new HashMap();
        for(int i=0;i<nums.length;i++){
            List<Integer> val = dic.getOrDefault(nums[i], new ArrayList<Integer>());
            for(Integer index:val){
                if(Math.abs(index-i)<= k) return true;
            }
            val.add(i);
            dic.put(nums[i],val);
        }
        return false;
    }
}

128. 最长连续序列

给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。

请你设计并实现时间复杂度为 O(n) 的算法解决此问题。

示例 1：

输入：nums = [100,4,200,1,3,2]
输出：4
解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。
示例 2：

输入：nums = [0,3,7,2,5,8,4,6,0,1]
输出：9
示例 3：

输入：nums = [1,0,1,2]
输出：3

思路：

1. 利用set唯一性，o(1)复杂度记录有的数字
2. 每个节点向前向后找连续的，找不到为止，记录连续长度
3. 统计最长长度

class Solution {
    public int longestConsecutive(int[] nums) {
        Set<Integer> set = new HashSet();
        for(int i=0;i<nums.length;i++){
            set.add(nums[i]);
        }
        int maxLen = 0;
        for(int i=0;i<nums.length;i++){
            int cur = nums[i];
            set.remove(cur);
            int curLen = 1;
            int curLeft = cur-1;
            while(set.contains(curLeft)){
                curLen++;
                set.remove(curLeft);
                curLeft-=1;
            }
            int curRight = cur+1;
            while(set.contains(curRight)){
                curLen++;
                set.remove(curRight);
                curRight+=1;
            }
            maxLen = maxLen>curLen?maxLen:curLen;
        }
        return maxLen;
    }
}

228. 汇总区间

给定一个 无重复元素 的 有序 整数数组 nums 。

返回 恰好覆盖数组中所有数字 的 最小有序 区间范围列表 。也就是说，nums 的每个元素都恰好被某个区间范围所覆盖，并且不存在属于某个范围但不属于 nums 的数字 x 。

列表中的每个区间范围 [a,b] 应该按如下格式输出：

“a->b” ，如果 a != b
“a” ，如果 a == b

示例 1：

输入：nums = [0,1,2,4,5,7]
输出：[“0->2”,”4->5”,”7”]
解释：区间范围是：
[0,2] –> “0->2”
[4,5] –> “4->5”
[7,7] –> “7”
示例 2：

输入：nums = [0,2,3,4,6,8,9]
输出：[“0”,”2->4”,”6”,”8->9”]
解释：区间范围是：
[0,0] –> “0”
[2,4] –> “2->4”
[6,6] –> “6”
[8,9] –> “8->9”

注意：
case里面有个边界，要注意

class Solution {
    public List<String> summaryRanges(int[] nums) {
        Set<Integer> set = new HashSet();
        for(int i=0;i<nums.length;i++){
            set.add(nums[i]);
        }
        List<String> rst = new ArrayList();
        for(int i=0;i<nums.length;i++){
            int cur = nums[i];
            if(!set.contains(cur)) continue;
            set.remove(cur);
            int curLeft = cur;
            int curRight = cur;
            while(true){
                if(curLeft == Integer.MIN_VALUE) {
                    set.remove(curLeft);
                    break;
                }
                if(set.contains(curLeft-1)){
                    curLeft = curLeft-1;
                    set.remove(curLeft);
                }else{
                    break;
                }
            }
            while(true){
                if(curRight == Integer.MAX_VALUE){
                    set.remove(curRight);
                    break;
                }
                if(set.contains(curRight+1)){
                    curRight = curRight+1;
                    set.remove(curRight);
                }else{
                    break;
                }
               
            }
            if(curLeft == curRight){
                rst.add(""+curLeft);
            }else{
                rst.add(curLeft+"->"+curRight);
            }
        }
        return rst;
    }
}

56. 合并区间

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。

示例 1：

输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
示例 2：

输入：intervals = [[1,4],[4,5]]
输出：[[1,5]]
解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。

解题思路：

1. Array.sort(Comparetor) 对首位排序，然后合并
2. 注意类名是 Comparator， 方法名是compare 别写错了

class Solution {
    public int[][] merge(int[][] intervals) {
        Arrays.sort(intervals, new Comparator<int[]>(){
            public int compare(int[] a,int[] b){
                return a[0] - b[0];
            }
        });

        int start = intervals[0][0];
        int stop = intervals[0][1];
        List<int[]> rst = new ArrayList();
        for(int i=1;i<intervals.length;i++){
           if(stop < intervals[i][0]){
                rst.add(new int[]{start,stop});
                start=intervals[i][0];
                stop = intervals[i][1];
                continue;
           }

           stop = stop > intervals[i][1]? stop: intervals[i][1];
        }
        rst.add(new int[]{start,stop});
        int[][] ans = new int[rst.size()][2];
        for(int i=0;i<rst.size();i++){
            ans[i] = rst.get(i);
        }
        return ans;
    }
}

57. 插入区间

给你一个 无重叠的 ，按照区间起始端点排序的区间列表 intervals，其中 intervals[i] = [starti, endi] 表示第 i 个区间的开始和结束，并且 intervals 按照 starti 升序排列。同样给定一个区间 newInterval = [start, end] 表示另一个区间的开始和结束。

在 intervals 中插入区间 newInterval，使得 intervals 依然按照 starti 升序排列，且区间之间不重叠（如果有必要的话，可以合并区间）。

返回插入之后的 intervals。

注意 你不需要原地修改 intervals。你可以创建一个新数组然后返回它。

示例 1：

输入：intervals = [[1,3],[6,9]], newInterval = [2,5]
输出：[[1,5],[6,9]]
示例 2：

输入：intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
输出：[[1,2],[3,10],[12,16]]
解释：这是因为新的区间 [4,8] 与 [3,5],[6,7],[8,10] 重叠。

提示：

0 <= intervals.length <= 104
intervals[i].length == 2
0 <= starti <= endi <= 105
intervals 根据 starti 按 升序 排列
newInterval.length == 2
0 <= start <= end <= 105

解题思路：

1. 朴素的按照思路来， 合并的过程中，无非在左边，在右边，或者重叠合并
2. needLast标记最后一个是否需要添加进来，这里为了保持有序，break的时候，先添加了leftright数组，其他情况需要补充left right数组

class Solution {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        List<int[]> tmp = new ArrayList();
        int left = newInterval[0];
        int right = newInterval[1];
        boolean needLast = true;
        for(int i=0;i<intervals.length;i++){
            if(intervals[i][1] < left){
                //没交集，在右边
                tmp.add(intervals[i]);
                continue;
            }
            if(intervals[i][0] > right){
                //没交集，在左边
                tmp.add(new int[]{left,right});
                for(int j=i;j<intervals.length;j++){
                    tmp.add(intervals[j]);
                }
                needLast = false;
                break;
            }

            //有交集,合并交集
            if(intervals[i][0] < left){
                left = intervals[i][0];
            }
            right = intervals[i][1] > right? intervals[i][1]:right;
        }
        if(needLast){
            tmp.add(new int[]{left,right});
        }
        int[][] rst = new int[tmp.size()][2];
        for(int i=0;i<tmp.size();i++){
            rst[i] = tmp.get(i);
        }
        return rst;
    }
}