day35

1、leetcode435 无重叠区间

1. 代码

   class Solution {
       public int eraseOverlapIntervals(int[][] intervals) {
           Arrays.sort(intervals,(a,b)->(a[0]-b[0]));
   
           int count = 1;//记录非重叠区间
   
           for(int i=1; i<intervals.length; i++) {
               if(intervals[i][0] < intervals[i-1][1]) {
                   intervals[i][1] = Math.min(intervals[i - 1][1], intervals[i][1]);
                   continue;
               } else {
                   count++;
               }
           }
   
           return intervals.length - count;
       }
   }
   

2、leetcode763 划分字母区间

1. 步骤

   1. 统计每一个字符最后出现的位置
   2. 从头遍历字符，并更新字符的最远出现下标，如果找到字符最远出现位置下标和当前下标相等了，则找到了分割点

2. 代码

   1. class Solution {
          public List<Integer> partitionLabels(String s) {
              int[] last = new int[26];
              int len = s.length();
      
              for(int i=0; i<len; i++) { // 统计每一个字符最后出现的位置
                  last[s.charAt(i)-'a'] = i; 
              }
      
              List<Integer> res = new ArrayList<Integer>();
              int start = 0, end = 0;
      
              for(int i=0; i < len; i++) {
                  end = Math.max(end, last[s.charAt(i)-'a']); // 找到字符出现的最远边界
                  if( i == end) {
                      res.add(end - start + 1);
                      start = end + 1;
                  }
              }
      
              return res;
          }
      }
      

3、leetcode56 合并区间

1. 代码

   class Solution {
       public int[][] merge(int[][] intervals) {
           LinkedList<int[]> res = new LinkedList<>();
   
           Arrays.sort(intervals, (o1, o2) -> (o1[0] - o2[0]));
           // 第一个区间就可以放进结果集里，后面如果重叠，在res上直接合并
           res.add(intervals[0]);
   
           for(int i=0; i<intervals.length; i++) {
                if (intervals[i][0] <= res.getLast()[1]) { //发现重叠区间
                   // 合并区间，只更新右边界就好，因为res.getLast()的左边界一定是最小值，因为按照左边界排序的
                   res.getLast()[1] = Math.max(res.getLast()[1], intervals[i][1]);
               } else {
                   res.add(intervals[i]); //区间不重叠
               }
           }
   
           return res.toArray(new int[res.size()][]);
   
       }
   }