代码随想录训练营第36天|435. 无重叠区间，763.划分字母区间，56. 合并区间

  • 435.无重叠区间
    • 文章
    • 思路
    • 代码
  • 763.划分字母区间
    • 文章
    • 思路
    • 代码
  • 56.合并区间
    • 文章
    • 思路
    • 代码
  • 总结

435.无重叠区间

文章

代码随想录|0435.无重叠区间

思路

我的思路：按区间左端点升序排列，左端点相同则按区间长度升序排列，相同左端点的区间只留最短的，剩下全是左端点不同的，发生重叠时保留右端点较小的
卡哥思路：按区间右端点升序排列，寻找不重叠的区间，每次找到不重叠区间则更新右端点，需要移除的数量则为总数减不重叠数量。

代码

class Solution {public int eraseOverlapIntervals(int[][] intervals) {Arrays.sort(intervals, (x, y) -> {return Integer.compare(x[0], y [0]) == 0 ? Integer.compare(x[1], y [1]) : Integer.compare(x[0], y[0]);});int i, j, n, count;n = intervals.length;i = 0;count = 0;j = 1;while (j < n) {if (intervals[j][0] < intervals[i][1]) {++count;i = intervals[i][1] <= intervals[j][1] ? i : j; } else { i = j;}++j;}return count;}}

763.划分字母区间

文章

代码随想录|0763.划分字母区间

思路

我的思路：先遍历整个字符串，将每个字符的数量统计在Map中
再遍历字符串，将当前访问字符在Map中对应数量减1
检查当前截取的区间中的字符是否都不在Map中，如果确实都不在map中则将这段区间长度加入结果并清空区间
直至全部遍历

卡哥思路：统计每个字符最后出现的位置
从头遍历字符串，并更新字符的最远出现下标，如果出现相等则找到了分割点

代码

class Solution {public List<Integer> partitionLabels(String s) {int i, n;n = s.length();Map<Character, Integer> map = new HashMap<>();int composition = 0;for (i = 0; i < n; ++i) {if (!map.containsKey(s.charAt(i))) {map.put(s.charAt(i), 1);} else {map.put(s.charAt(i), map.get(s.charAt(i)) + 1);}}// for (Map.Entry entry: map.entrySet()) {// System.out.println("key: " + entry.getKey() + ", value: " + entry.getValue());// }List<Integer> ans = new ArrayList<>();int span = 0;for (i = 0; i < n; ++i) {composition |= 1 << (s.charAt(i) - 'a');// System.out.println("i: " + i +", character: " + s.charAt(i));map.put(s.charAt(i), map.get(s.charAt(i)) - 1);++span;if (check(map, composition)) {ans.add(span);composition = 0;span = 0;}}return ans;}public boolean check(Map<Character, Integer> map, int composition) {int times = 26;char ch = 'a';while (times > 0) {if (composition % 2 == 1) {if (map.get(ch) > 0) {return false;}}ch = (char) (ch + 1);composition = composition >> 1;--times;}return true;}}

56.合并区间

文章

代码随想录|0056.合并区间

思路

按区间左端点升序排列
将区间加入结果队列，如果队尾同待插入区间有交集则合并
反而这道题成了今天最好做的

代码

class Solution {public int[][] merge(int[][] intervals) {Arrays.sort(intervals, (x, y) -> {return Integer.compare(x[0], y[0]);});List<int[]> list = new ArrayList<>();int i, n;n = intervals.length;for (i = 0; i < n; ++i) {if (list.isEmpty() || list.get(list.size() - 1)[1] < intervals[i][0]) {list.add(intervals[i]);} else {list.get(list.size() - 1)[1] = list.get(list.size() - 1)[1] > intervals[i][1] ? list.get(list.size() - 1)[1] : intervals[i][1];}}n = list.size();int[][] res = new int[n][2];for (i = 0; i < n; ++i) {res[i] = list.get(i);}return res;}}

总结

3道重叠区间
似乎排序非常重要
435的减法思路很值得学习
763的最远出现位置暂时还不知道怎样能想到这种思路