深圳网站建设 设计创公司,外贸自主建站平台,网站代码需要注意什么问题,宁波网站建站模板本题我首先分享我的思路#xff0c;再在补充中说明贪心算法。
题目描述#xff1a; 给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段#xff0c;同一字母最多出现在一个片段中。 注意#xff0c;划分结果需要满足#xff1a;将所有划分结果按顺序连接#x… 本题我首先分享我的思路再在补充中说明贪心算法。
题目描述 给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段同一字母最多出现在一个片段中。 注意划分结果需要满足将所有划分结果按顺序连接得到的字符串仍然是 s 。 返回一个表示每个字符串片段的长度的列表。
示例 1
输入s ababcbacadefegdehijhklij
输出[9,7,8]
解释
划分结果为 ababcbaca、defegde、hijhklij 。
每个字母最多出现在一个片段中。
像 ababcbacadefegde, hijhklij 这样的划分是错误的因为划分的片段数较少。
示例 2
输入s eccbbbbdec
输出[10]提示
1 s.length 500s 仅由小写英文字母组成
解题准备 1.了解可能存在的基础操作首先要求划分字符串那么划分得到的字符串就题意不要求真正出新字符串并返回需要进行记录所以可能有添加其次既然涉及数组所以大概率涉及遍历即查找总之可能有添加、查找两个基本操作。 2.了解字符串字符串的本质是字符数组对字符串的操作归根结底是对字符数组的操作因此需要知道字符串转字符数组str.toCharArray(); 3.理顺题目要求题目其实有三个要求第一划分得到的字符串段如S1、S2……SN必须有S1S2……SN原字符串不能缺、不能多、顺序不能乱变 第二要求Si与Sjij属于1到N并且ij之间不能有相同字符比如Si是“abcd”有字符aSj如果是“aef”则不满足因为同样有字符‘a’ 第三要求划分后字符串段尽可能多。 4.模拟操作去掉所有条件从原始开始组合第一个条件比较基础第二个条件引出以下疑问如果我们只要求划分出两个字符串段S1和S2要求S1和S2中没有相同字符怎么做
解题难点1分析 难点1 在解题准备“4”中如果只要求划分两个字符串段S1、S2且S1和S2中没有相同字符可以怎么操作 思路1分析更简单的角度 如果我们提供两个不同的字符串S1、S2要求找到S1、S2中是否有相同字符如果有返回true没有返回false怎么做【S1、S2中只有小写字符】 思路1解 【思路1的题目用boolean数组即可因为只判断有没有本题用int数组是为接下来做准备】 第一用一个长度为26的int[]数组A1先遍历一次S1记录每个字符出现的个数有这个字符对应的位置。 第二同理创建长度为26的int[]数组A2遍历S2记录字符个数如果有对应字符那么对应位置。 第三遍历数组A1但凡有A1[i]0判断A2[i]0如果等于0继续遍历不等于0说明二者有重复返回false。 思路2分析从难点1角度出发 对于输入字符串S如果已经划分为两部分那么可以用思路1求解目前问题是要求你划分。 所以需要动态的变化动态的记录。【使用一个指针下标ptr】 思路2解 第一步继续创建长度为26的int数组A1、A2首先将S的字符记录进A1中。 第二步移动指针ptr将第一个字符记录进A2从A1删除第一个字符对应字符-- 第三步通过A1、A2判断是否有重复字符如果无重复则将S划分。 比如S是“abdb”直接划分成【“a”“bcb”】即可。 当然很可能S是“abdafe”这种类型。 那么第四步进行迭代每次ptr向前移动一步将S.charAt(ptr)记录进A2同时删除A1数据。然后进行第三步判断 直到1.找到无重复字符。2.遍历完整个字符串S都没有符合题意。才返回数据。
解题难点2分析 由“解题难点1分析”我们容易知道如何划分一个字符串S使S1和S2中没有相同字符并且使S1尽可能短【因为一旦遇到S1、S2无相同字符就立刻返回S1如果从0开始那么S1一定是最短的】 不过题目要求划分尽可能多的字符串段。 难点2 对于一个字符串S如何划分出尽可能多的、字符不重复的字符串段 思路1分析用迭代的思想 我们已经知道从S划分S1、S2那么对于原始输入S我们划分出S1、S2后S1必定和S2无相同字符、并且但凡S1减少一位就会有相同字符所以S1是最基础输出【也一定是第一个输出】。 那么想找到第二个输出必然要从S2中找。 不妨把S2看成S从S2中拿到S1’ 和 S2’ 拿到第二个输出后又得考虑S2’中是否存在…… 就此迭代……直到遍历完整个字符数组即可返回完整输出。 迭代结束条件这里需要考虑指针ptr是否越界一旦越界必然出错所以ptr最多指向s.length-1至此迭代结束。
代码
class Solution {public ListInteger partitionLabels(String s) {int[] tempnew int[26];int[] datanew int[26];char[] xs.toCharArray(); // 用s.charAt(i)也一样;int ptr0; // 指针ListInteger resnew ArrayList();for(char a:x){temp[a-a]; // 首先记录A1}while(ptrx.length){ // 只要不遍历结束就一直遍历// 这一部分属于初始化否则一开始data中为null必然与temp不相交data[x[ptr]-a]; // A2temp[x[ptr]-a]--; // A1--ptr; //ptrwhile(isFalse(temp, data)){data[x[ptr]-a];temp[x[ptr]-a]--;ptr;}// ttt用于确定前面已划分出的字符串长度int ttt0;for(int n:res){tttn;}res.add(ptr-ttt); // 重置A2for(int i0; i26; i){data[i]0;}}return res;}// 判断是否有重复元素private boolean isFalse(int[] temp, int[] data){for(int i0; i26; i){if(data[i]!0){if(temp[i]!0){return true; // 有重复元素返回true}}}return false;}
}
补充贪心算法 本题的题解使用贪心算法思路也比较简单。 1.利用HashMap哈希表记录所有字符最晚出现的位置key是字符value是Integer表示最晚的位置。比如baabcbacadefegdehijhklij记录a8 b5…… 2.采用for循环遍历s的字符数组拿到s.charAt(i)最晚出现的位置hashMap.get(s.charAt(i)如果最晚出现晚于目前最晚的位置比如a8b5首先遍历到b记录最晚等于5然后遍历到a记录最晚为8…… 3.如果一直遍历到8没有出现更晚的数据返回8这个就是最小的满足题意的答案。 4.解释第一个是b5也就是说S1起码到5这个位置否则不可能出现S1、S2没有相交字符。然后是a8也就是说S1至少到8否则必定有……选取最大的即可
以上内容即我想分享的关于力扣热题12的一些知识。 我是蚊子码农如有补充欢迎在评论区留言。个人也是初学者知识体系可能没有那么完善希望各位多多指正谢谢大家。
