怎么把网站地图上传,桂林北站地图,公司注册的公司,网站建设陆金手指谷哥7刷题记录 *452. 用最少数量的箭引爆气球435. 无重叠区间*763. 划分字母区间笨拙版进阶版 *452. 用最少数量的箭引爆气球
leetcode题目地址
先对气球的坐标按照Xstart进行升序排序#xff0c;只要两个气球之间挨着就可以一箭射穿#xff0c;因此排序后查看后一个气球的起始坐… 刷题记录 *452. 用最少数量的箭引爆气球435. 无重叠区间*763. 划分字母区间笨拙版进阶版 *452. 用最少数量的箭引爆气球
leetcode题目地址
先对气球的坐标按照Xstart进行升序排序只要两个气球之间挨着就可以一箭射穿因此排序后查看后一个气球的起始坐标是否与前一个气球的结束坐标挨着挨着后一个起始坐标前一个结束坐标。
时间复杂度 O ( n l o g n ) O(nlogn) O(nlogn) 空间复杂度 O ( 1 ) O(1) O(1)
// java
class Solution {public int findMinArrowShots(int[][] points) {// 按照起始坐标从小到大排序 // 使用Integer内置比较方法不会溢出Arrays.sort(points, (a, b) - Integer.compare(a[0], b[0]));int cnt 1;for(int i1; ipoints.length; i){if(points[i][0] points[i-1][1]){cnt;}else{points[i][1] Math.min(points[i][1], points[i-1][1]); }// System.out.println(points[i][0] points[i][1]);}return cnt;}
}435. 无重叠区间
leetcode题目地址
和上题思路类似。本题是找到有重叠的区间然后删除覆盖范围较大的那一个。先对区间进行排序按照区间起始位置升序排序若起始位置相同则按照结束位置升序排序。
然后遍历数组若后一个区间的起始位置小于前一个区间的结束位置等于不算重叠则两区间有重叠删除后面的区间。这里的删除不是物理删除是逻辑删除更新后一个区间的结束区间即可后一个区间的结束位置等于前一个区间的结束位置和后一个区间结束位置较小的那个。
时间复杂度 O ( n l o g n ) O(nlogn) O(nlogn) 空间复杂度 O ( 1 ) O(1) O(1)
// java
class Solution {public int eraseOverlapIntervals(int[][] intervals) {Arrays.sort(intervals, (a, b) - {if(a[0] b[0]){return Integer.compare(a[1], b[1]);}return Integer.compare(a[0], b[0]);});int cnt 0;for(int i1; iintervals.length; i){// 重叠if(intervals[i][0] intervals[i-1][1]){cnt;intervals[i][1] Math.min(intervals[i][1], intervals[i-1][1]);}}return cnt;}
}*763. 划分字母区间
leetcode题目地址
笨拙版
先统计字符串中每个字母的出现次数。 记录目前子串中出现的字母若子串中的字母均已访问过则切分为一个子串记录长度。
使用map记录子串中的字母以及对应字母的剩余个数当字母剩余0个时即当前字母访问结束从map中移除。
时间复杂度 O ( n ) O(n) O(n) 空间复杂度 O ( n ) O(n) O(n)
// java
class Solution {public ListInteger partitionLabels(String s) {int[] chars new int[26];for(int i0; is.length(); i){chars[s.charAt(i) - a];}ListInteger result new ArrayList();MapCharacter, Integer hash new HashMap();int start 0;for(int i0; is.length(); i){chars[s.charAt(i) - a]--;if(hash.containsKey(s.charAt(i))) hash.put(s.charAt(i), hash.get(s.charAt(i))-1);else hash.put(s.charAt(i), chars[s.charAt(i) - a]);if(hash.get(s.charAt(i)) 0) hash.remove(s.charAt(i));if(hash.isEmpty()){result.add(i-start1);start i1;}}return result;}
}进阶版
先统计每个字符的最后出现的位置当访问字符串时若已到达子串中所有字符的最后位置则记录当前子串长度。
时间复杂度 O ( n ) O(n) O(n) 空间复杂度 O ( 1 ) O(1) O(1)
// java
class Solution {public ListInteger partitionLabels(String s) {int[] hash new int[26];for(int i0; is.length(); i){// 记录最后出现的位置hash[s.charAt(i) - a] i;}ListInteger result new ArrayList();int start 0;int end 0;for(int i0; is.length(); i){end Math.max(end, hash[s.charAt(i) - a]);if(i end){// 到达当前子串最右端result.add(end-start1);start i1;}}return result;}
}
