当前位置: 首页> 财经> 股票 > 搭建一个论坛有什么要求_网站策划运营方案_关键词优化怎么操作_百度百度一下你就知道主页

搭建一个论坛有什么要求_网站策划运营方案_关键词优化怎么操作_百度百度一下你就知道主页

时间:2025/7/11 23:04:40来源:https://blog.csdn.net/qq_51726003/article/details/143661170 浏览次数:1次
搭建一个论坛有什么要求_网站策划运营方案_关键词优化怎么操作_百度百度一下你就知道主页

目录

452. 用最少数量的箭引爆气球

435. 无重叠区间

763.划分字母区间


今天的题目都算是 重叠区间 问题。

452. 用最少数量的箭引爆气球

为了让气球尽可能的重叠,需要对数组进行排序。

如果气球重叠了,重叠气球中右边边界的最小值 之前的区间一定需要一个弓箭。

    class Solution {public int findMinArrowShots(int[][] points) {
//            Arrays.sort(points, (a, b) -> {
//                if (a[0] == b[0]) {
//                    return Integer.compare(a[1], b[1]);
//                }
//                return Integer.compare(a[0], b[0]);
//            });Arrays.sort(points, (a, b) -> Integer.compare(a[0], b[0]));int count = 1; // points 不为空至少需要一支箭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;}}
  • 时间复杂度:O(nlog n),排序需要 O(NlogN) 的复杂度
  • 空间复杂度:O( log n),java所使用的内置函数用的是快速排序需要 logN 的空间

注意,排序这块需要用 Integer.compare(a[0], b[0])

因为一开始我用的是:

if (a[0] == b[0]) {return a[1] - b[1];
}
return a[0] - b[0];

当数组包含极大或极小的整数(如 Integer.MIN_VALUEInteger.MAX_VALUE)时,直接使用减法计算差值可能导致 整数溢出,则会产生溢出错误。

为了避免溢出,可以使用 Integer.compare 方法代替减法,因为它可以安全地比较两个整数而不会产生溢出。Integer.compare(a[0], b[0]):会返回一个负值、零或正值,分别表示 a[0] 小于、等于或大于 b[0]

435. 无重叠区间

按左边排序,不管右边顺序。相交的时候取最小的右边。

与452很类似,简单。

class Solution {public int eraseOverlapIntervals(int[][] intervals) {if (intervals.length == 1) {return 0;}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]){intervals[i][1] = Math.min(intervals[i][1], intervals[i-1][1]);count++;}}return count;}
}

763.划分字母区间

在遍历的过程中相当于是要找每一个字母的边界,如果找到之前遍历过的所有字母的最远边界,说明这个边界就是分割点了。此时前面出现过所有字母,最远也就到这个边界了。

可以分为如下两步:

  • 统计每一个字符最后出现的位置(很妙,这个记录法,详见代码部分)
  • 从头遍历字符,并更新字符的最远出现下标,如果找到字符最远出现位置下标和当前下标相等了,则找到了分割点

代码部分注意看下面那个简洁部分,注释的部分for循环中有点麻烦。但是思路逻辑什么的都是一样的。

    class Solution {public List<Integer> partitionLabels(String s) {
//            int[] str = new int[26];
//            for (int i = 0; i < s.length(); i++) {
//                str[s.charAt(i) - 'a'] = i; // 记录每个字符出现的最后一次的index
//            }
//            List<Integer> result = new LinkedList<>();
//            for (int i = 0, start = 0, end = str[s.charAt(0)-'a']; i < s.length(); i++) {
//                if (i == end){
//                    result.add(end-start+1);
//                    if (i == s.length()-1){
//                        break;
//                    }
//                    end = str[s.charAt(i+1)-'a'];
//                    start = i+1;
//                }else {
//                    end = Math.max(end,str[s.charAt(i)-'a']);
//                }
//            }
//            return result;//简洁版本int[] str = new int[27];for (int i = 0; i < s.length(); i++) {str[s.charAt(i) - 'a'] = i; // 记录每个字符出现的最后一次的index}List<Integer> result = new LinkedList<>();for (int i = 0, start = -1, end = 0; i < s.length(); i++) {end = Math.max(end,str[s.charAt(i)-'a']);if (i == end){result.add(end-start);start = i;}}return result;}}

第三十天的总算是结束了,直冲Day31!

关键字:搭建一个论坛有什么要求_网站策划运营方案_关键词优化怎么操作_百度百度一下你就知道主页

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: