每题一日❌每日一题✔之LeetCode56合并区间（java版）

这道题的大概意思是给定若干个区间合并重叠的区间这个区间其实就是个一维数组,长这样比如[2,3]就表示2为左边界3为右边界的闭区间输入篇输入格式41 32 68 1015 18先输入一个数字表示要输入多少个区间然后输入区间每个区间换一次行就这样我们的输入思路就可以想好了首先输入readLine读区间数量n,然后再跑n次循环把每个区间读进去用二维数组来存储这些区间代码import java.io.*; import java.util.*; public class Main{ public static void main(String[] args) throws IOException{ BufferedReader br new BufferedReader(new InputStreamReader(System.in); int n Integer.parseInt(br.readLine().trim()); StringTokenizer st; int[][] seg new int[n][2];//每个区间存两个数字 for(int i 0; i n; i){ st new StringTokenizer(br.readLine()); seg[i][0] Integer.parseInt(st.nextToken()); seg[i][1] Integer.parseInt(st.nextToken()); } //...balabala(后续逻辑代码) } }给萌新的留言为什么用BufferedReader不用Scanner,很简单因为Scanner他慢。Scanner的nextInt等等方法底层都是基于正则表达式来匹配和切割的CPU开销大慢BufferedReader只做纯字符流读取快。StringTokenizer呢就是负责切割这个我们BufferedReader读到的字符串把他们按空格换行符制表符\t)等切割我们BufferedReader读到一行字符串的时候交给我们StringTokenizer只要使用nextToken,他就能立即给你切到下一个token块比如读到的字符串是1 2 3,你使用nextToken他给你返回字符串1再用一次返回2再用一次返回 3。非常方便输入的内容是数组一般就用它来切割读数字。如果输入的是字符串可以直接用BufferedReader,br.readLine()就能返回那一行的字符串。对于一行只有一个数字比如数组类型的题目一般输入会先给数组的长度n再给数组本体我们要直接处理 输入的 一维数组的长度n使用Integer.parseInt(br.readLine().trim())就能快速获取(这里之所以用trim是因为有的神人输入会在一行的数字后面多打一个空格算法解决篇思路要解决这道题目关键要弄清楚遍历这个二维数组区间集合什么时候有重叠需要合并什么时候不该合并没有重叠。合并 的条件是有区间[a,b],和区间 [c,d],假如a c 那么 c 必须小于等于b.他们才可能有重叠项我们的思路就简单多了首先对区间集合这个二维数组按照左边界做从小到大从大到小也一样反过来思路这个你自己试一个排序这样遍历区间一定是的顺序一定有先遍历的区间的左边界小于等于后遍历的左左边界这样只需要比较后续的区间的左边界的大小如果后遍历的区间的左区间小于等于前面的右边界那就有重叠可以合并合并之后的右边界就是他们右边界的最大值。否则不能合并算进新区间。代码Listint[] res new ArrayList(); for(int[] s : seg){ if(!res.isEmpty() res.get(res.size()-1)[1] s[0]){ res.get(res.size()-1)[1] Math.max(res.get(res.size()-1)[1],s[1]); }else{ res.add(s); } }补充说明为什么使用res的最后一个res.get(res.size()-1)作为比较依据。因为遍历的顺序是左边界从小到大res的顺序也是左边界从小到大对于res的结果他会add的只有两个完全没有重叠的后一个数组的左边界比前一个数组的右边界还大的。比如res是{[1,2],[3,4]},后面遍历的肯定是[4,5],[5,6]之类的[3,4]的左边界都比[1,2]的大了完全没有比较肯定左边界比他大的后续遍历的[4,5][5,6]之类的跟前面的res的区间[1,2]比较的必要。他的最后一个区间肯定是现有的右区间最大的输出篇预期输出格式1 68 1015 18即每个区间换行一次每行只有一个区间的左右边界元素也就是一个数组思路输出的思路很简单使用StringBuilder遍历res拼接字符串即可两个数字之间加一个空格每行之后加一个换行符StringBuilder sb new StringBuilder(); for(int[] s : res){ sb.append(s[0]).append( ).append(s[1]).append(\n) } System.out.print(sb);注意事项因为我们给每行都打了换行符所以这里不需要输出再写一个println,否则末尾就有两个\n了平时我们输出一维数组的时候一般是这样for(int x : a) sb.append(x).append( )即每两个数字之间有一个空格这样我们的末尾输出也有一个空格输出的时候就可以通过System.out.println(sb.toString().trim())来防止最后多输出一个空格。这里没有加换行符就用的println)