本文主要是介绍代码随想录算法训练营Day36|LC435 无重叠区间LC763 划分字母区间LC56 合并区间，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
一句话总结：都是和昨天的用最少箭引爆气球类似的题。
原题链接：435 无重叠区间
计数不重叠的区间的个数，然后用总长度减去这个值即可。
class Solution {public int eraseOverlapIntervals(int[][] intervals) {Arrays.sort(intervals, (a, b) -> Integer.compare(a[1], b[1]));int n = intervals.length;int cnt = 1;int right = intervals[0][1];for (int i = 1; i < n; ++i) {if (right <= intervals[i][0]) {right = intervals[i][1];cnt++;}}return n - cnt;}
}原题链接：763 划分字母区间
利用一个长为26的数组记录每个字母最后出现的位置，然后一趟遍历更新该区间所有字母最后的出现位置，如果right == i，即表明该段区间内所有字母都仅在该区间内出现，而不会在区间外。将该区间长度加入答案即可。
class Solution {public List<Integer> partitionLabels(String s) {List<Integer> ans = new ArrayList<>();int n = s.length();int[] lastPos = new int[26];for (int i = 0; i < n; ++i) {lastPos[s.charAt(i) - 'a'] = i; }int left = 0, right = 0;for (int i = 0; i < n; ++i) {right = Math.max(right, lastPos[s.charAt(i) - 'a']);if (i == right) {ans.add(right - left + 1);left = right + 1;}}return ans;}
}原题链接：56 合并区间
区间的经典题了。排序后先将第一段区间加入答案，然后往后遍历，如果右端点大于当前遍历区间左端点，那么将该段区间右端点更新为当前遍历区间的右端点与原本右端点的最大值，否则将新的区间加入答案，同时更新右端点值为该遍历端点的右端点。
class Solution {public int[][] merge(int[][] intervals) {Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));List<int[]> ans = new ArrayList<>();for (int i = 0; i < intervals.length; ++i) {int left = intervals[i][0], right = intervals[i][1];if (ans.isEmpty() || ans.get(ans.size() - 1)[1] < left) {ans.add(new int[]{left, right});} else ans.get(ans.size() - 1)[1] = Math.max(right, ans.get(ans.size() - 1)[1]);}return ans.toArray(new int[ans.size()][]);}
}这篇关于代码随想录算法训练营Day36|LC435 无重叠区间LC763 划分字母区间LC56 合并区间的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
