数组与贪心算法——179、56、57、228（2简2中）

179. 最大数（简单）

给定一组非负整数 nums，重新排列每个数的顺序（每个数不可拆分）使之组成一个最大的整数。

注意：输出结果可能非常大，所以你需要返回一个字符串而不是整数。

解法一、自定义比较器

大的排前面然后进行一个比较jpg一开始想的其实是字典序，但是测试里就败了。例如3,30,9，字典序组出来是9033，但9330更大

class Solution {public String largestNumber(int[] nums) {Integer[] boxedArr = Arrays.stream(nums).boxed().toArray(Integer[]::new);Arrays.sort(boxedArr, (o1, o2) -> {String s1 = String.valueOf(o1);String s2 = String.valueOf(o2);String order1 = s1 + s2; // o1o2String order2 = s2 + s1; // o2o1return order2.compareTo(order1);});StringBuilder res = new StringBuilder();for (int num : boxedArr) {res.append(num);}while(res.charAt(0) == '0' && res.length() > 1){res.delete(0,1);}return res.toString();}
}

56. 合并区间（中等）

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。

解法一、自定义比较器+分类讨论

兄弟你好难

看了官方也能按第一张图那么写，我的写法慢挺多的。搜了一下问题在于用comparingInt的内部类，会涉及Integer操作，所以会涉及一大堆自动装箱

当然做完57才发现，比起判断数组合理了再加入（这里的做法），更合适的做法是取出ans最后一个，和当前待加入的那个数组比较，以current的开头是否在pre的结尾之前为标杆。若在其中，则更改最后一个；若不在其中，则直接加入该数组。无论是代码简洁度还是思路讨论，都会轻松很多。

  Arrays.sort(intervals, new Comparator<int[]>() {public int compare(int[] interval1, int[] interval2) {return interval1[0] - interval2[0];}});作者：力扣官方题解
链接：https://leetcode.cn/problems/merge-intervals/solutions/203562/he-bing-qu-jian-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

class Solution {public int[][] merge(int[][] intervals) {Arrays.sort(intervals, Comparator.comparingInt(o -> o[0]));if(intervals.length == 1)return intervals;List<int[]> list = new LinkedList<>();int start = intervals[0][0],end = intervals[0][1];for(int i = 1;i < intervals.length;i++){if(end < intervals[i][0]){list.add(new int[]{start,end});start = intervals[i][0];end = intervals[i][1];}else if(end < intervals[i][1]){end = intervals[i][1];}}if(list.isEmpty() || start != list.get(list.size()-1)[0]){list.add(new int[]{start,end});}return list.toArray(new int[0][0]);}
}

解法一优化

原地数组操作

class Solution {public int[][] merge(int[][] intervals) {Arrays.sort(intervals, new Comparator<int[]>() {@Overridepublic int compare(int[] o1, int[] o2) {return o1[0] - o2[0];}});int[] pre = intervals[0];// 原地操作节省空间：已经确定的区间，直接存储在intervals的前面，k记录序号。int k = 0;for (int i = 1; i < intervals.length; i++) {int[] cur  = intervals[i];if(cur[0] <= pre[1]){// 当前区间的左边界小于前一个区间的右边界时，可以合并，用pre记录int e = Math.max(pre[1], cur[1]);pre = new int[]{pre[0], e};}else{// 和前一个不能合并时，将pre记录在intervals的前面，更新pre为curintervals[k++] = pre;pre = cur;}}// 记录最后一个区间intervals[k++] = pre;// 对intervals截断，只取前面的结果部分return Arrays.copyOfRange(intervals,0, k);}
}

57. 插入区间（中等）

给你一个 无重叠的 ，按照区间起始端点排序的区间列表 intervals，其中 intervals[i] = [starti, endi] 表示第 i 个区间的开始和结束，并且 intervals 按照 starti 升序排列。同样给定一个区间 newInterval = [start, end] 表示另一个区间的开始和结束。

在 intervals 中插入区间 newInterval，使得 intervals 依然按照 starti 升序排列，且区间之间不重叠（如果有必要的话，可以合并区间）。

返回插入之后的 intervals。

注意你不需要原地修改 intervals。你可以创建一个新数组然后返回它。

解法一、分类讨论

用gpt写了一些注释。这个讨论也太杂乱了。。。

class Solution {public int[][] insert(int[][] intervals, int[] newInterval) {// 如果原来的 intervals 是空的，直接返回包含 newInterval 的二维数组// 这样避免了后续的复杂逻辑if(intervals.length == 0) return new int[][]{newInterval};// merge 数组保存合并后的区间，初始值为 intervals.length 和 -1// merge[0] 用于存储合并区间的起始值，merge[1] 用于存储合并区间的结束值// merge[1] 初始为 -1 表示还没有需要合并的结束区间int[] merge = new int[]{intervals.length, -1};// wait 标志用于判断是否已经找到了合并区间的起始部分（即 newInterval 和当前区间有重叠）boolean wait = false;// 用 LinkedList 来存储结果，方便后续进行插入操作List<int[]> res = new LinkedList<>();// 遍历 intervals 数组for(int i = 0; i < intervals.length; i++) {if(wait) { // 如果已经找到需要合并的区间的起始部分// 情况1：newInterval 的结束小于当前区间的开始，说明 newInterval 不与当前区间重叠if (newInterval[1] < intervals[i][0] || newInterval[1] <= intervals[i][1]) {merge[1] = Math.max(newInterval[1], intervals[i][1]); // 合并区间的结束为较大值wait = false; // 合并结束res.add(merge); // 添加合并后的区间if(newInterval[1] < intervals[i][0]) { // 如果 newInterval 完全不与当前区间重叠i--; // 回退索引，继续处理当前区间}}  else if(i == intervals.length - 1) {merge[1] = newInterval[1]; // 合并区间的结束为 newInterval 的结束res.add(merge); // 将合并后的区间添加到结果中}} else { // 如果还没找到需要合并的起始部分// 如果 newInterval 的开始小于等于当前区间的结束，且 merge[1] 还没有确定合并结束// 说明 newInterval 和当前区间有重叠，需要开始合并if(newInterval[0] <= intervals[i][1] && merge[1] == -1) {merge[0] = Math.min(newInterval[0], intervals[i][0]); // 合并后的区间起点取两者的较小值wait = true; // 设置 wait，表示正在等待合并结束i--; // 将 i 减回去，以便下一次循环还能处理当前区间} else {// 如果当前区间和 newInterval 无重叠，直接将当前区间添加到结果中res.add(intervals[i]);}}}// 如果在遍历完 intervals 后，merge[1] 仍然为 -1，说明 newInterval 没有与任何区间合并// 直接将 newInterval 添加到结果中if(merge[1] == -1) res.add(newInterval);// 将结果列表转化为二维数组并返回return res.toArray(new int[0][0]);}
}

解法二、简化然后合并区间

class Solution {public int[][] insert(int[][] intervals, int[] newInterval) {// 创建一个列表用于保存结果区间List<int[]> ans = new ArrayList<>();// 将新的区间 newInterval 添加到 intervals 数组末尾// 首先需要将二维数组 intervals 转换为 List 以便添加新元素List<int[]> intervalsList = new ArrayList<>(Arrays.asList(intervals));intervalsList.add(newInterval);// 对所有区间按起点进行排序，使用 lambda 表达式对起点进行比较intervalsList.sort((a, b) -> Integer.compare(a[0], b[0]));// 将排序后的第一个区间加入到结果集合 ans 中ans.add(intervalsList.get(0));// 遍历排序后的所有区间for (int i = 1; i < intervalsList.size(); i++) {int[] currentInterval = intervalsList.get(i);int[] lastIntervalInAns = ans.get(ans.size() - 1); // 获取 ans 中最后一个区间// 如果当前区间的起点小于等于 ans 中最后一个区间的终点，说明它们有重叠，需要合并if (currentInterval[0] <= lastIntervalInAns[1]) {// 合并时，更新 ans 中最后一个区间的终点，取两个区间终点中的较大值lastIntervalInAns[1] = Math.max(lastIntervalInAns[1], currentInterval[1]);} else {// 如果没有重叠，直接将当前区间加入到结果集合 ans 中ans.add(currentInterval);}}// 将结果集合转换为二维数组并返回return ans.toArray(new int[ans.size()][]);}
}

228. 汇总区间(简单)

给定一个 无重复元素 的有序整数数组 nums 。

返回 恰好覆盖数组中所有数字 的 最小有序 区间范围列表。也就是说，nums 的每个元素都恰好被某个区间范围所覆盖，并且不存在属于某个范围但不属于 nums 的数字 x 。

列表中的每个区间范围 [a,b] 应该按如下格式输出：

"a->b" ，如果 a != b
"a" ，如果 a == b

解法一、遍历

if和while的边界设置比较特殊，通过while一路通向区间最尾端

class Solution {public static List<String> summaryRanges(int[] nums) {List<String> res = new LinkedList<>();int start,end,len = nums.length;if(len < 2){if(len == 1)res.add(String.valueOf(nums[0]));return res;}for(int i = 0;i < len;i++){start = nums[i];while(i < len - 1 && (nums[i] == nums[i+1] - 1)){i++;}end = nums[i];if(start == end){res.add(String.valueOf(start));}else{StringBuilder sb = new StringBuilder();sb.append(start).append("->").append(end);res.add(sb.toString());}}return res;}
}