代码随想录 Day36 - 贪心算法（五）
作者：jjn0703
- 2023-08-02 江苏
本文字数：2087 字
阅读完需：约 7 分钟
435. 无重叠区间
本题的关键在于判断重复的区间的起止，需要通过不断比较当前区间和下一个区间的起止值。若当前区间的起始大于上一个区间的结束值，则统计的无重叠区间+1.
package jjn.carl.greedy;
import java.util.Arrays;import java.util.Scanner;
/** * @author Jjn * @since 2023/8/2 09:43 */public class LeetCode435 { public int eraseOverlapIntervals(int[][] intervals) { Arrays.sort(intervals, (i1, i2) -> { if (i1[0] == i2[0]) { return Integer.compare(i1[1], i2[1]); } return Integer.compare(i1[0], i2[0]); }); int count = 0; int end = intervals[0][1]; for (int i = 1; i < intervals.length; i++) { if (intervals[i][0] >= end) { end = intervals[i][1]; continue; } end = Math.min(end, intervals[i][1]); count++; } return count; } public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int total = scanner.nextInt(); int[][] intervals = new int[total][2]; for (int i = 0; i < total; i++) { for (int j = 0; j < 2; j++) { intervals[i][j] = scanner.nextInt(); } } int count = new LeetCode435().eraseOverlapIntervals(intervals); System.out.println(count); }}
复制代码
763. 划分字母区间
遍历一遍，更新字母和其出现的最大的下标 index，构建为一个 Map。随后遍历字符串，若字符串是区间的最大下标，则将结果加到 result 数组里，否则继续往后遍历。
package jjn.carl.greedy;
import java.util.*;
/** * @author Jjn * @since 2023/8/2 12:33 */public class LeetCode763 { public List<Integer> partitionLabels(String s) { List<Integer> parts = new ArrayList<>(); int[] dict = new int[26]; for (int i = 0; i < s.length(); i++) { dict[s.charAt(i) - 'a'] = i; } int start = 0, end = 0; for (int i = 0; i < s.length(); i++) { end = Math.max(end, dict[s.charAt(i) - 'a']); if (i == end) { parts.add(end - start + 1); start = end + 1; } } return parts; } public static void main(String[] args) { Scanner scanner = new Scanner(System.in); while (scanner.hasNext()) { String s = scanner.nextLine(); List<Integer> list = new LeetCode763().partitionLabels(s); System.out.println(list.toString()); } }}
复制代码
56. 合并区间
排序后，不断更新其区间内的右端点。
package jjn.carl.greedy;
import java.util.*;
/** * @author Jjn * @since 2023/8/2 14:40 */public class LeetCode56 { public int[][] merge(int[][] intervals) { Arrays.sort(intervals, Comparator.comparingInt(i -> i[0])); Deque<int[]> result = new LinkedList<>(); for (int i = 0; i < intervals.length; i++) { int left = intervals[i][0], right = intervals[i][1]; if (result.isEmpty() || result.peekLast()[1] < left) { result.offer(new int[]{left, right}); continue; } result.peekLast()[1] = Math.max(result.peekLast()[1], right); } return result.toArray(new int[result.size()][]); } public static void main(String[] args) { Scanner scanner = new Scanner(System.in); while (scanner.hasNext()) { int total = scanner.nextInt(); int[][] intervals = new int[total][2]; for (int i = 0; i < total; i++) { for (int j = 0; j < 2; j++) { intervals[i][j] = scanner.nextInt(); } } int[][] merge = new LeetCode56().merge(intervals); StringBuilder stringBuilder = new StringBuilder(); stringBuilder.append("["); for (int[] ints : merge) { stringBuilder.append(Arrays.toString(ints)); stringBuilder.append(","); } stringBuilder.deleteCharAt(stringBuilder.length() - 1); stringBuilder.append("]"); System.out.println(stringBuilder); } }}
复制代码
划线
评论
复制
发布于: 刚刚阅读数: 3
版权声明: 本文为 InfoQ 作者【jjn0703】的原创文章。
原文链接:【http://xie.infoq.cn/article/60391375bcfcea7b379b22254】。
本文遵守【CC-BY 4.0】协议，转载请保留原文出处及本版权声明。
jjn0703
关注
Java工程师/终身学习者 2018-03-26 加入
USTC硕士/健身健美爱好者/Java工程师.
评论