网站建设要学哪些东西,做类似返利网的网站,wordpress08教程,外链建设原则目录 无重叠区间划分字母区间合并区间 LeetCode 435. 无重叠区间 LeetCode 763.划分字母区间 LeetCode 56. 合并区间
无重叠区间
给定一个区间的集合 intervals #xff0c;其中 intervals[i] [starti, endi] 。返回 需要移除区间的最小数量#xff0c;使剩余区间互不重叠… 目录 无重叠区间划分字母区间合并区间 LeetCode 435. 无重叠区间 LeetCode 763.划分字母区间 LeetCode 56. 合并区间
无重叠区间
给定一个区间的集合 intervals 其中 intervals[i] [starti, endi] 。返回 需要移除区间的最小数量使剩余区间互不重叠 。
和用最少数量的箭引爆气球很像唯一的区别是引爆气球记录的是非重叠数量 本题记录的是重叠数量。 在 if else 内操作会有所不同。
另外本题对左区间和右区间均可排序可以计算非重叠数量用总数量减去非重叠得到重叠数量也可以按下面代码直接计算重叠数量。
class Solution {// [1,2],[2,3],[3,4],[1,3]// [1,2],[1,3],[2,3],[3,4] [1,2],[1,2],[2,3],[3,4]// 1 2 重叠 记录删除 result// 重叠记录最小右区间 // 直到遍历完数组public int eraseOverlapIntervals(int[][] intervals) {Arrays.sort(intervals, (a, b) - {if (a[0] b[0]) return a[1] - b[1];return a[0] - b[0];});int result 0;for (int i 1; i intervals.length; i) {if (intervals[i][0] intervals[i - 1][1]) { // 重叠步骤intervals[i][1] Math.min(intervals[i][1], intervals[i - 1][1]); result; } }return result;}
}划分字母区间
字符串 S 由小写字母组成。我们要把这个字符串划分为尽可能多的片段同一字母最多出现在一个片段中。返回一个表示每个字符串片段的长度的列表。
题目要求同一字母最多出现在一个片段中。
在遍历的过程中相当于是要找每一个字母的边界如果找到之前遍历过的所有字母的最远边界Math.max()说明这个边界就是分割点了。此时前面出现过所有字母最远也就到这个边界了。
统计每一个字符最后出现的位置从头遍历字符并更新字符的最远出现下标如果找到字符最远出现位置下标和当前下标相等了则找到了分割点
class Solution {public ListInteger partitionLabels(String s) {ListInteger result new ArrayList();int[] hash new int[26];for (int i 0; i s.length(); i) {char c s.charAt(i);hash[c - a] i;}// s - [8, 5, 8, ... ]int idx 0;int last -1;for (int i 0; i s.length(); i) {char c s.charAt(i);idx Math.max(idx, hash[c - a]);if (i idx) {result.add(i - last);last i;}}return result;}
}class Solution {public int[][] findPartitions(String s) {// ababcbacadefegdehijhklijListInteger temp new ArrayList();int[][] hash new int[26][2]; // 26 个字母 2 列 表示该字母对应的区间// 哈希数组// [[0,8], [1,5], [4,7], [9,14], [10, 15] ...]for (int i 0; i s.length(); i) {char c s.charAt(i);if (hash[c - a][0] 0) hash[c - a][0] i;hash[c - a][1] i;hash[s.charAt(0) - a][0] 0; }ListListInteger h new LinkedList();// 去除字符串中未出现的字母所占用区间// 组装区间到集合for (int i 0; i 26; i) {// if (hash[i][0] ! hash[i][1]) {temp.clear();temp.add(hash[i][0]);temp.add(hash[i][1]);h.add(new ArrayList(temp));// }}// 存入数组int[][] res new int[h.size()][2];for (int i 0; i h.size(); i) {ListInteger list h.get(i);res[i][0] list.get(0);res[i][1] list.get(1);}return res;}public ListInteger partitionLabels(String s) {int[][] partitions findPartitions(s);ListInteger result new ArrayList();// [[0,8], [1,5], [4,7], [9,14], [10, 15] ...]Arrays.sort(partitions, (o1, o2) - Integer.compare(o1[0], o2[0]));int right partitions[0][1];int left 0;for (int i 0; i partitions.length; i) {if (partitions[i][0] right) { // 一旦下一区间左边界大于当前右边界即可认为出现分割点result.add(right - left 1);left partitions[i][0];}right Math.max(right, partitions[i][1]);}result.add(right - left 1);return result;}
}合并区间
这几道题都是判断区间重叠区别就是判断区间重叠后的逻辑本题是判断区间重贴后要进行区间合并。
所以一样的套路先排序让所有的相邻区间尽可能的重叠在一起按左边界或者右边界排序都可以处理逻辑稍有不同。 class Solution {public int[][] merge(int[][] intervals) {Arrays.sort(intervals, (o1, o2) - Integer.compare(o1[0], o2[0]));Listint[] res new ArrayList();int start intervals[0][0];// int rightMaxBound intervals[0][1];for (int i 1; i intervals.length; i) {// if (intervals[i][0] rightMaxBound) {if (intervals[i][0] intervals[i - 1][1]){res.add(new int[]{start, intervals[i - 1][1]});// res.add(new int[]{start, rightMaxBound});start intervals[i][0];// rightMaxBound intervals[i][1];} else{// rightMaxBound Math.max(rightMaxBound, intervals[i][1]);intervals[i][1] Math.max(intervals[i][1], intervals[i - 1][1]);}}// res.add(new int[]{start, rightMaxBound});res.add(new int[]{start, intervals[intervals.length - 1][1]});return res.toArray(new int[res.size()][]);}
}
