简述网站建设步骤,做基因功能注释的网站,网站开发需要客户做什么,商标设计大全435. 无重叠区间
本题简单一些#xff0c;估计大家不用想着贪心 #xff0c;用自己直觉也会有思路。
代码随想录
力扣题目链接(opens new window)
给定一个区间的集合#xff0c;找到需要移除区间的最小数量#xff0c;使剩余区间互不重叠。
注意: 可以认为区间的终… 435. 无重叠区间
本题简单一些估计大家不用想着贪心 用自己直觉也会有思路。
代码随想录
力扣题目链接(opens new window)
给定一个区间的集合找到需要移除区间的最小数量使剩余区间互不重叠。
注意: 可以认为区间的终点总是大于它的起点。 区间 [1,2] 和 [2,3] 的边界相互“接触”但没有相互重叠。
看到题目的第一想法 移除区间 先排序使用linkedList把排序好的存入遍历看是否重叠若重叠则移除前一个从前往后移除 且count,i-- [[1,100],[11,22],[1,11],[2,12]] 这个案例没实现
看到代码随想录之后的想法 若重叠则把两者的右区间更新为两个的最小的右区间看与下面是否重叠,result 若不重叠则往下走
自己实现过程中遇到的困难 记住这种操作方式如果重叠则更新两者的最右边 有时候可以倒过来想问题比如说重叠做什么操作我们可以先想一下若不重叠我们先做什么操作 这道题若不重叠则跳过若重叠则更新右边界
class Solution {//public int eraseOverlapIntervals(int[][] intervals) {/*//移除后不重叠//找到一个和多个区间重叠的//先排序 若右边界下一个左边界 则不重叠//若前一个右边界下一个左边界则重叠移除前一个 //第一个值升序排列第二个值降序//[[1,100],[11,22],[1,11],[2,12]] 这个案例没实现Arrays.sort(intervals,(a,b)-{if(a[0]b[0]) return b[1]-a[1];return a[0]-b[0];});int remove0;LinkedListint[] list new LinkedList();for(int[] in:intervals){list.add(in);}for(int i1;ilist.size();i){//我这种做法没办法判断两个重叠区间的后续区间是否也重叠if(list.get(i-1)[1]list.get(i)[0]){list.remove(i-1);i--;remove;}}return remove;}*///卡哥做法和上一题一样//若inteval[i][1]inteval[i1][0] 则count且把inteval[i1][1]替换为inteval[i][1]public int eraseOverlapIntervals(int[][] intervals) {Arrays.sort(intervals,(a,b)-{if(a[0]b[0]) return b[1]-a[1];return a[0]-b[0];});int remove0;for(int i1;iintervals.length;i){ if(intervals[i-1][1]intervals[i][0]){intervals[i][1] Math.min(intervals[i-1][1],intervals[i][1]);remove;}}return remove;}
}763.划分字母区间
字符串 S 由小写字母组成。我们要把这个字符串划分为尽可能多的片段同一字母最多出现在一个片段中。返回一个表示每个字符串片段的长度的列表。
示例
输入S ababcbacadefegdehijhklij输出[9,7,8] 解释 划分结果为 ababcbaca, defegde, hijhklij。 每个字母最多出现在一个片段中。 像 ababcbacadefegde, hijhklij 的划分是错误的因为划分的片段数较少。
看到题目的第一想法 需要把字符串分割开来 如何才能按照提议来分片呢
用map 看到代码随想录之后的想法 使用一个长度为26的int 数组遍历一边字符串存放当前字符的最大下标 哈希的办法 然后再遍历字符串同时记录一下当前区间字符对应的最大下标若当前区间字符对应的最大下标和当前下标相同代表前面区间的所有字符的最大下标都比当前下标要小则划分 然后指针继续往下走继续划分
自己实现过程中遇到的困难 1 没有想到字符对应哈希数组0~25 用于记录最大下标 2 字符转int 下标来记录值 int[s.charAt(i)-0]i 3 使用一个left 和right left记录分割字符串的第一个下标right代表当前区间内元素的最大下标
若righti 则可以进行分割 class Solution {public ListInteger partitionLabels(String s) {//先把第一个元素分完看区间里包括了哪些元素一起代替//用一个map 来判断 是否包括这个//卡哥思路先用一个数组记录每个元素的最远距离//若当前区域内的最远距离当前遍历到的下标则证明当前子串里所有的元素后面都不会出现则切分一个字串//存放每个区间的最大下标int[] chars new int[26];for(int i0;is.length();i){chars[s.charAt(i)-a]i;}int left0;//往后遍历,存放当前区间的最大下标int right 0;ListInteger list new ArrayList();for(int i0;is.length();i){//遍历这个获取字串rightMath.max(right,chars[s.charAt(i)-a]);//若当前字符的下标当前区间的最大下标if(iright){list.add(right-left1);leftright1;}}return list;}
} 56. 合并区间
力扣题目链接(opens new window)
给出一个区间的集合请合并所有重叠的区间。
示例 1:
输入: intervals [[1,3],[2,6],[8,10],[15,18]]输出: [[1,6],[8,10],[15,18]]解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
示例 2:
看到题目的第一想法 先排序然后把所有的数组放入一个linkedList中 看linkedlist中是否有重叠区间 若重叠了则把linkedList中的那个元素移除同时修改第一个元素 然后再继续
看到代码随想录之后的想法 list先存放第一个元素 若不重叠则add若重叠则把当前list中的最后一个元素右边界修改再继续往下遍历(右边界不是修改为当前元素的右边界而是两者中的最大值) 自己实现过程中遇到的困难 list转成int list.toArray(new int[list.size()][]) 先考虑不重叠的再考虑重叠的倒过来想一下如果一开始想重叠的就会比较繁琐
class Solution {/*public int[][] merge(int[][] intervals) {//如果重叠则把第一个的第二个元素换成第二个的第二个元素删除第二个元素Arrays.sort(intervals,(a,b)-{return a[0]-b[0];});LinkedListint[] list new LinkedList();for(int[] i:intervals){list.add(i);}for(int i0;ilist.size()-1;i){if(list.get(i)[1]list.get(i1)[0]){list.get(i)[1]Math.max(list.get(i)[1],list.get(i1)[1]);list.remove(i1);i--;}}return list.toArray(new int[list.size()][]);}*///卡哥做法不需要删除(时间复杂度比我的提升了70ms)public int[][] merge(int[][] intervals) {//如果重叠则把第一个的第二个元素换成第二个的第二个元素删除第二个元素Arrays.sort(intervals,(a,b)-{return a[0]-b[0];});ArrayListint[] list new ArrayList();//卡哥做法不需要把所有元素放到数组里只需要放第一个list.add(intervals[0]);//判断如果重叠了则更新上一个如果没重叠则加入到数组中for(int i1;iintervals.length;i){if(list.get(list.size()-1)[1]intervals[i][0]){//前一个永远在list中前一个的右边界换成前后两者右边界的最大值list.get(list.size()-1)[1]Math.max(list.get(list.size()-1)[1],intervals[i][1]);}else{list.add(intervals[i]);}}return list.toArray(new int[list.size()][]);}
}
