企业网站制作步骤,珠宝网站策划,谷歌广告联盟网站,远洋国际建设有限公司网站题目描述
给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段#xff0c;同一字母最多出现在一个片段中。
注意#xff0c;划分结果需要满足#xff1a;将所有划分结果按顺序连接#xff0c;得到的字符串仍然是 s 。
返回一个表示每个字符串片段的长度的列表。…题目描述
给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段同一字母最多出现在一个片段中。
注意划分结果需要满足将所有划分结果按顺序连接得到的字符串仍然是 s 。
返回一个表示每个字符串片段的长度的列表。
示例 1 输入 s “ababcbacadefegdehijhklij” 输出 [9,7,8] 解释 划分结果为 “ababcbaca”、“defegde”、“hijhklij” 。 每个字母最多出现在一个片段中。 像 “ababcbacadefegde”, “hijhklij” 这样的划分是错误的因为划分的片段数较少。
示例 2
输入 s “eccbbbbdec” 输出 [10]
提示
1 s.length 500s 仅由小写英文字母组成
代码及注释
func partitionLabels(s string) []int {// 创建一个数组来存储每个字符最后出现的位置lastPos : make([]int, 26)// 结果数组用于存储每个分区的长度res : make([]int, 0)// 遍历字符串记录每个字符最后出现的位置for i, c : range s {lastPos[c - a] i}// 初始化分区的开始和结束位置start, end : 0, 0// 再次遍历字符串来确定分区for i, c : range s {// 更新当前分区的结束位置为当前字符的最后出现位置end max(end, lastPos[c - a])// 如果当前位置i等于当前分区的结束位置说明找到了一个分区if i end {// 计算当前分区的长度并添加到结果数组中res append(res, end - start 1)// 更新下一个分区的开始位置start end 1}}// 返回结果数组return res
}// 返回两个数的最大值
func max(a, b int) int {if a b {return a}return b
}
代码解释 记录每个字符的最后出现位置 for i, c : range s {lastPos[c - a] i
}这里我们遍历字符串s并记录每个字符最后出现的位置。这样当我们遍历字符串以确定子串边界时我们可以直接查找每个字符的最后出现位置。 确定子串的边界 for i, c : range s {end max(end, lastPos[c - a])if i end {res append(res, end - start 1)start end 1}
}在这个循环中我们遍历字符串s。对于每个字符我们更新当前子串的结束位置end为当前字符的最后出现位置。当i end时意味着我们找到了一个子串其边界是start到end。我们计算这个子串的长度并将其添加到结果数组res中然后更新start为end 1以寻找下一个子串。 返回结果数组 return res最后我们返回结果数组res其中包含了所有子串的长度。
通过这种方法我们可以有效地找到字符串s中所有满足条件的子串其中每个字母只出现在一个子串中。
