当前位置：首页 > news >正文

代码随想录算法训练营第二十六天

news 来源：原创 2025/7/3 16:24:43

LeetCode题目:

452. 用最少数量的箭引爆气球
435. 无重叠区间
763. 划分字母区间
2799. 统计完全子数组的数目(每日一题)

其他:

今日总结
往期打卡

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

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

学习: 代码随想录公开讲解

问题:

有一些球形气球贴在一堵用 XY 平面表示的墙面上。墙面上的气球记录在整数数组 points ，其中points[i] = [xstart, xend] 表示水平直径在 xstart 和 xend之间的气球。你不知道气球的确切 y 坐标。

一支弓箭可以沿着 x 轴从不同点 完全垂直 地射出。在坐标 x 处射出一支箭，若有一个气球的直径的开始和结束坐标为 x``start，x``end，且满足 xstart ≤ x ≤ x``end，则该气球会被引爆。可以射出的弓箭的数量 没有限制 。弓箭一旦被射出之后，可以无限地前进。

给你一个数组 points ，返回引爆所有气球所必须射出的最小弓箭数 。

思路:

贪心,某区间结尾断一定可以选出最大(重叠区间中最短的那个的结尾)

复杂度:

时间复杂度: $O (n l o g n)$
空间复杂度: $O (1)$

代码:

class Solution {public int findMinArrowShots(int[][] points) {Arrays.sort(points,(a, b) -> Integer.compare(a[1],b[1]));int end = points[0][1];int ans = 1;for(int i=1;i<points.length;i++){if(points[i][0]<=end) continue;ans++;end = points[i][1];}return ans;}
}

435. 无重叠区间

跳转: 435. 无重叠区间

学习: 代码随想录公开讲解

问题:

给定一个区间的集合 intervals ，其中 intervals[i] = [starti, endi] 。返回 需要移除区间的最小数量，使剩余区间互不重叠 。

注意只在一点上接触的区间是 不重叠的。例如 [1, 2] 和 [2, 3] 是不重叠的。

思路:

贪心,按区间尾部从小到大排序(保证和下一个值冲突的可能性最小),看前尾部大于后头部,重叠就去除后面的(因为其区间更靠近后面的其他元素,更有可能冲突)

复杂度:

时间复杂度: $O (n l o g n)$
空间复杂度: $O (1)$

代码:

class Solution {public int eraseOverlapIntervals(int[][] intervals) {Arrays.sort(intervals,Comparator.comparingInt(a -> a[1]));int pre = intervals[0][1];int count = intervals.length-1;for(int i=1;i<intervals.length;i++){if(intervals[i][0]<pre) continue;pre = intervals[i][1];count--;}return count;}
}

763. 划分字母区间

跳转: 763. 划分字母区间

学习: 代码随想录公开讲解

问题:

给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。例如，字符串 “ababcc” 能够被分为 [“abab”, “cc”]，但类似 [“aba”, “bcc”] 或 [“ab”, “ab”, “cc”] 的划分是非法的。

注意，划分结果需要满足：将所有划分结果按顺序连接，得到的字符串仍然是 s 。

返回一个表示每个字符串片段的长度的列表。

思路:

贪心,遍历起点更新终点,追上就收集.也可以记录起点和终点转换成区间合并问题求解

复杂度:

时间复杂度: $O (n)$
空间复杂度: $O (1)$

代码:

class Solution {public List<Integer> partitionLabels(String s) {int n = s.length();int[] last = new int[26];int length = s.length();for (int i = n - 1; i >= 0; i--) {int tmp = s.charAt(i) - 'a';if (last[tmp] == 0) {last[tmp] = i;}}List<Integer> res = new ArrayList<>();int start = 0;int end = 0;for (int i = 0; i < n; i++) {end = Math.max(end, last[s.charAt(i) - 'a']);if (i == end) {res.add(end - start + 1);start = end + 1;}}return res;}
}

2799. 统计完全子数组的数目(每日一题)

跳转: 2799. 统计完全子数组的数目

问题:

给你一个由正整数组成的数组 nums 。

如果数组中的某个子数组满足下述条件，则称之为完全子数组：

子数组中不同元素的数目等于整个数组不同元素的数目。
返回数组中完全子数组的数目。

子数组是数组中的一个连续非空序列。

思路:

遍历起点滑动窗口,找到全包含再往后都合法

复杂度:

时间复杂度: $O (n)$
空间复杂度: $O (1)$

代码:

class Solution {public int countCompleteSubarrays(int[] nums) {int n = nums.length;int[] hash = new int[2001];int end = 0;for (int i = 0; i < n; i++) {int tmp = nums[i];if (hash[tmp] == 0) {end = i;}hash[tmp]++;}for(int i=end+1;i<n;i++){hash[nums[i]]--;}int ans = n-end;for(int i=0;i<=end&&end<n;i++){int tmp = nums[i];hash[tmp]--;while(hash[tmp]<=0&&++end<n){hash[nums[end]]++;}if(end>=n) break;ans+=n-end;}return ans;}
}

总结

今天练习了区间贪心+滑动窗口

往期打卡

代码随想录算法训练营第二十五天

代码随想录算法训练营第二十四天

代码随想录算法训练营第二十三天

代码随想录算法训练营周末四

代码随想录算法训练营第二十二天(补)

代码随想录算法训练营第二十一天

代码随想录算法训练营第二十天

代码随想录算法训练营第十九天

代码随想录算法训练营第十八天

代码随想录算法训练营第十七天

代码随想录算法训练营周末三

代码随想录算法训练营第十六天

代码随想录算法训练营第十五天

代码随想录算法训练营第十四天

代码随想录算法训练营第十三天

代码随想录算法训练营第十二天

代码随想录算法训练营第十一天

代码随想录算法训练营周末二

代码随想录算法训练营第十天

代码随想录算法训练营第九天

代码随想录算法训练营第八天

代码随想录算法训练营第七天

代码随想录算法训练营第六天

代码随想录算法训练营第五天

代码随想录算法训练营周末一

代码随想录算法训练营第四天

代码随想录算法训练营第三天

代码随想录算法训练营第二天

代码随想录算法训练营第一天

LeetCode题目:

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

问题:

思路:

复杂度:

代码:

435. 无重叠区间

问题:

思路:

复杂度:

代码:

763. 划分字母区间

问题:

思路:

复杂度:

代码:

2799. 统计完全子数组的数目(每日一题)

问题:

思路:

复杂度:

代码:

总结

往期打卡

相关文章：