seo站长工具是什么,天津做网站哪家公司好,怎么做查询网站吗,邢台做网站动态763. 划分字母区间
题目描述
给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段#xff0c;同一字母最多出现在一个片段中。
注意#xff0c;划分结果需要满足#xff1a;将所有划分结果按顺序连接#xff0c;得到的字符串仍然是 s 。
返回一个表示每个字符串…763. 划分字母区间
题目描述
给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段同一字母最多出现在一个片段中。
注意划分结果需要满足将所有划分结果按顺序连接得到的字符串仍然是 s 。
返回一个表示每个字符串片段的长度的列表。
示例 1 输入s “ababcbacadefegdehijhklij” 输出[9,7,8] 解释 划分结果为 “ababcbaca”、“defegde”、“hijhklij” 。 每个字母最多出现在一个片段中。 像 “ababcbacadefegde”, “hijhklij” 这样的划分是错误的因为划分的片段数较少。 示例 2 输入s “eccbbbbdec” 输出[10] 提示
1 s.length 500s 仅由小写英文字母组成
贪心算法
一想到分割字符串就想到了回溯但本题其实不用回溯去暴力搜索。
题目要求同一字母最多出现在一个片段中那么如何把同一个字母的都圈在同一个区间里呢
如果没有接触过这种题目的话还挺有难度的。
在遍历的过程中相当于是要找每一个字母的边界如果找到之前遍历过的所有字母的最远边界说明这个边界就是分割点了。此时前面出现过所有字母最远也就到这个边界了。
可以分为如下两步
统计每一个字符最后出现的位置从头遍历字符并更新字符的最远出现下标如果找到字符最远出现位置下标和当前下标相等了则找到了分割点
如图
rfind函数
以下是对于给出的代码的详细注释解释了它是如何解决问题的
#include vector
#include string
using namespace std;class Solution {
public:vectorint partitionLabels(string s) {vectorint res; // 用于存储每个片段的长度int end0; // 记录当前遍历到的所有字符中最远的出现位置int cnt0; // 当前片段的长度计数器// 遍历给定的字符串for(int i0; is.size(); i) {cnt; // 每遍历一个字符当前片段的长度加1// 更新当前片段中字符最远出现位置的最大值// s.rfind(s[i]) 返回字符s[i]最后一次出现的位置// 因为s.rfind的返回类型为size_t可能与int类型的end不匹配所以要进行类型转换end max(end, (int)s.rfind(s[i]));// 如果当前字符是当前片段中最远出现位置的字符// 则说明到目前为止的这一段可以独立为一个片段if (end i) {// 将当前片段的长度添加到结果列表中res.push_back(cnt);// 重置计数器为下一个片段做准备cnt 0;}}// 返回结果列表包含了每个片段的长度return res;}
};这段代码核心在于通过遍历字符串并使用end变量跟踪当前遍历到的所有字符中最远的出现位置。每当end与当前遍历的索引i相等时说明到目前为止的这一段字符串可以划分为一个片段因为它包含了一组字符这些字符之后不再出现。然后记录下这个片段的长度并重置计数器和end变量以便计算下一个片段的长度。最终所有片段的长度被添加到结果列表中并返回。
易错rfind函数返回值问题
在我没进行强制类型转换时代码报错
Line 10: Char 17: error: no matching function for call to max10 | endmax(end,s.rfind(s[i]));| ^~~
/usr/bin/../lib/gcc/x86_64-linux-gnu/11/../../../../include/c/11/bits/algorithmfwd.h:407:5: note: candidate template ignored: deduced conflicting types for parameter _Tp (int vs. size_type (aka unsigned long))398 | max(const _Tp, const _Tp);| ^
/usr/bin/../lib/gcc/x86_64-linux-gnu/11/../../../../include/c/11/bits/stl_algo.h:3467:5: note: candidate template ignored: could not match initializer_list_Tp against int3458 | max(initializer_list_Tp __l, _Compare __comp)| ^这个错误信息表明max函数无法匹配到合适的重载版本原因是传递给max的两个参数end和s.rfind(s[i])具有不同的类型。在C中rfind返回的是size_type类型这通常是一个无符号整数类型比如unsigned long而end被定义为int类型是一个有符号整数。
在C标准库中max要求两个参数具有相同的类型因为它需要能够比较这两个参数并返回其中较大的一个。当你尝试使用两个不同类型的参数调用max时编译器无法决定应该使用哪个类型来比较因此会报错。
解决这个问题的一种方法是确保max的两个参数类型一致。如果你确认end变量不会存储超过int类型能表示的范围的值可以通过强制类型转换将rfind的返回值转换为int类型如下所示
end max(end, (int)s.rfind(s[i]));哈希表
这段代码是一个解决上述问题的C实现。我将在代码的每一部分提供详细的注释来解释它的作用。
#include vector
#include stringusing namespace std;class Solution {
public:vectorint partitionLabels(string s) {vectorint res; // 创建一个空的整数向量来存储最后的片段长度结果// 数组用于记录每个字符最后出现的索引位置// 因为输入字符串只包含小写字母所以只需要大小为26的数组int index[26];// 第一个循环遍历字符串s的每个字符for(int i 0; i s.size(); i)// 计算字符到a的距离作为数组索引并更新这个字符对应的最后出现位置// a的ASCII码将被用作基准点所以任何字符都可以通过减去a得到一个0到25的索引值index[s[i] - a] i;// 初始化用于追踪当前片段最右端字符的索引int right 0;int cnt 0; // 计数器用于记录当前片段的长度// 第二个循环同样遍历字符串的每个字符for(int i 0; i s.size(); i) {// 增加当前片段的计数器cnt;// 通过字符索引找到当前片段最右端字符的索引与当前的right比较取较大者// 这样可以确保当前片段包含所有已遍历字符的最后出现right max(right, index[s[i] - a]);// 如果当前字符的位置i与right相等说明当前片段不会再扩展了if(right i) {// 把当前片段的长度加入到结果集res.push_back(cnt);// 重置计数器为下一个片段准备cnt 0;}}// 返回分段的长度数组return res;}
};该代码分为两个主要部分第一部分遍历字符串记录每个字符最后出现的位置第二部分再次遍历字符串根据每个字符的最后出现位置确定每个片段的边界并记录其长度。
这种方法能够确保每个字符仅出现在一个片段中且得到的片段数目是最大化的。最终我们得到一个数组记录了根据给定规则得到的每个片段的长度。
