☆☆☆☆☆leetcode 452. 用最少数量的箭引爆气球
题目链接:leetcode 452. 用最少数量的箭引爆气球
题目分析
首先对points各个范围按左端点升序排列,依次比力每一个范围左端点与前一个范围右端点。若该范围左端点大于前一个范围右端点,阐明没有重叠,需要计划次数count加一;若该范围左端点小于前一个范围右端点,阐明有重叠,仅需更新右端点为该范围右端点与前一范围右端点的最小值。
代码
- class Solution {
- public int findMinArrowShots(int[][] points) {
- Arrays.sort(points,(a,b)->Integer.compare(a[0],b[0]));
- int count=1;
- for(int i=1;i<points.length;i++){
- if(points[i][0]>points[i-1][1]){
- count++;
- }else{
- points[i][1]=Math.min(points[i-1][1],points[i][1]);
- }
- }
- return count;
- }
- }
复制代码 提示:
Arrays.sort(points, (a, b) -> { return a[0] - b[0]; });
使用了简单的减法来比力两个点的x坐标。虽然这在大多数情况下可以工作,但它有一个潜伏的问题:假如a[0]和b[0]的差值非常大,那么返回的结果大概会是一个大的整数,这大概会导致整数溢出(Integer Overflow)。
Arrays.sort(points, (a, b) -> Integer.compare(a[0], b[0]));
使用了Integer.compare方法。这个方法担当两个整数作为参数,并返回一个整数,表示第一个参数与第二个参数的比力结果。假如第一个参数小于第二个参数,则返回负数;假如它们相等,则返回0;假如第一个参数大于第二个参数,则返回正数。使用Integer.compare方法的好处是它制止了整数溢出的问题,在处置惩罚大数时更安全,并且由于它是专门为比力整数而计划的,以是代码的可读性也更好。
☆☆☆☆☆leetcode 435. 无重叠区间
题目链接:leetcode 435. 无重叠区间
题目分析
首先对intervals各个区间按左端点升序排列,依次比力每一个区间左端点与前一个区间右端点。若该区间左端点大于前一个范围右端点,阐明没有重叠,无需操纵;若该区间左端点小于前一个区间右端点,阐明有重叠,计数count加一,同时更新右端点为该区间右端点与前一区间右端点的最小值。
代码
- class Solution {
- public int eraseOverlapIntervals(int[][] intervals) {
- Arrays.sort(intervals,(a,b)->Integer.compare(a[0],b[0]));
- int count=0;
- for(int i=1;i<intervals.length;i++){
- if(intervals[i][0]<intervals[i-1][1]){
- count++;
- intervals[i][1]=Math.min(intervals[i-1][1],intervals[i][1]);
- }
- }
- return count;
- }
- }
复制代码 ☆☆☆☆☆leetcode 763.划分字母区间
题目链接:leetcode 763.划分字母区间
题目分析
首先接纳哈希数组记录每个字母在该字符串中最后出现的位置,即遍历后序号覆盖。初始left和right赋值为0,依次遍历字符串的每个元素,若遍历到的元素最后出现位置大于当前right值,则更新right值;若遍历到right,则阐明得到了一个符合发起的区间,记录该区间长度right-left+1并加到res数组中,同时更新left值为right+1,直至遍历竣事。
代码
- class Solution {
- public List<Integer> partitionLabels(String s) {
- List<Integer> res=new ArrayList<>();
- int last[]=new int[26];
- int left=0,right=0;
- for(int i=0;i<s.length();i++)
- last[s.charAt(i)-'a']=i;
- for(int i=0;i<s.length();i++){
- right=Math.max(right,last[s.charAt(i)-'a']);
- if(i==right){
- res.add(right-left+1);
- left=right+1;
- }
- }
- return res;
- }
- }
复制代码 免责声明:如果侵犯了您的权益,请联系站长,我们会及时删除侵权内容,谢谢合作!更多信息从访问主页:qidao123.com:ToB企服之家,中国第一个企服评测及商务社交产业平台。 |