宜宾市网站建设,windows系统安装wordpress,网站建立需要什么技术,北京网站被处罚763.划分字母区间 字符串 S 由小写字母组成。我们要把这个字符串划分为尽可能多的片段#xff0c;同一字母最多出现在一个片段中。返回一个表示每个字符串片段的长度的列表。 示例#xff1a; 输入#xff1a;S ababcbacadefegdehijhklij输出#xff1a;[9,7… 763.划分字母区间 字符串 S 由小写字母组成。我们要把这个字符串划分为尽可能多的片段同一字母最多出现在一个片段中。返回一个表示每个字符串片段的长度的列表。 示例 输入S ababcbacadefegdehijhklij输出[9,7,8] 解释 划分结果为 ababcbaca, defegde, hijhklij。 每个字母最多出现在一个片段中。 像 ababcbacadefegde, hijhklij 的划分是错误的因为划分的片段数较少 之前在回溯部分有用回溯算法分割过字符串但是属于暴力搜索时间复杂度较高。 题目要求同一字母最多出现在一个片段中并且划分尽可能多的片段那么如何把同一个字母的都圈在同一个区间里呢就是找到出现过的字母的最大终止位置。 可以分为如下两步 统计每一个字符最后出现的位置从头遍历字符并更新字符的最远出现下标如果找到字符最远出现位置下标和当前下标相等了则找到了分割点 class Solution {public ListInteger partitionLabels(String s) {LinkedListInteger listnew LinkedList();int[] edgenew int[26]; char[] charss.toCharArray(); //将一个字符串转换成一个字符char数组。//比如abecadf 那么edge[0]存储的就是a出现的次数for(int i0;ichars.length;i){edge[chars[i]-a]i; //统计每个字符出现的最后位置 ,按照字母的顺序存储}int idx0, last-1;for(int i0; ichars.length;i){idxMath.max(idx, edge[chars[i]-a]); //遍历出现过的元素更新最远位置if(iidx){ //如果已经走到了前面出现过的覆盖的最远位置list.add(i-last);// 记录当前子串的长度 lasti; //更新起点}}return list;}
} 56. 合并区间 给出一个区间的集合请合并所有重叠的区间。 示例 1: 输入: intervals [[1,3],[2,6],[8,10],[15,18]]输出: [[1,6],[8,10],[15,18]]解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6]. 示例 2: 输入: intervals [[1,4],[4,5]]输出: [[1,5]]解释: 区间 [1,4] 和 [4,5] 可被视为重叠区间。注意输入类型已于2019年4月15日更改。 请重置默认代码定义以获取新方法签名。 依旧是重叠区间问题先按照start排序再进行重叠判断本题相邻区域也算重叠因此若intervals[i][0]intervals[i-1][1]则有重叠。若有重叠则将区间的左右边界判断更新end使之成为两个区间的最远end加入result数组若不重合更新start和end直接加入原区间。 class Solution {public int[][] merge(int[][] intervals) {Listint[] resnew LinkedList();Arrays.sort(intervals, (a,b)-Integer.compare(a[0], b[0]));int startintervals[0][0];int end intervals[0][1];for(int i1;iintervals.length;i){if(intervals[i][0]end){//不重叠res.add(new int[]{start, end});//将当前节点加入resstartintervals[i][0]; //更新startendintervals[i][1];}else{endMath.max(end, intervals[i][1]); //更新最大右边界}}res.add(new int[]{start, end});return res.toArray(new int[res.size()][]);}
} 这里要注意一个语法基础⚠️在链表list里面添加值然后把list链表添加进res链表中在做算法题的时候如果使用res.add(list)输出打印为空因此需要res.add(new LinkedListInteger(list))。同理在这里如果想要给链表res添加新的数组一定也要res.add(new int[]{start, end});
