做网站外包公司名称,网站开发小组分工,哪个网站做视频钱多,企业网站怎么做中英文切换题目#xff1a;
给你一个字符串 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 500 s 仅由小写英文字母组成
思路
题目要求同一字母最多出现在一个片段中那么如何把同一个字母的都圈在同一个区间里呢
如果没有接触过这种题目的话还挺有难度的。
在遍历的过程中相当于是要找每一个字母的边界如果找到之前遍历过的所有字母的最远边界说明这个边界就是分割点了。此时前面出现过所有字母最远也就到这个边界了。
可以分为如下两步
统计每一个字符最后出现的位置从头遍历字符并更新字符的最远出现下标如果找到字符最远出现位置下标和当前下标相等了则找到了分割点
以S ababcbacadefe为例进行详细分析如何切割。 首先进行遍历遍历到第一个字符串为a, a的最后出现位置的下标为8因为题目要求同一字母最多出现在一个片段所以为了第一个片段包含所有的a继续向下进行遍历遍历到bb的最后出现的位置的下标为5继续遍历 此时需要包含a的同时包含所有的b因为b的最远下标小于a所以只要包含了所有的a则必定包含所有的b继续向下遍历又新加入了a和b之后又加入了c同理接下来的遍历需要包含a,b的同时包含c。直到包含了所有遍历时加入的元素时开始进行切割这就是所求的一个片段的长度。下一个片段切割同理。
理解了切割过程代码依然不好写如何得知字符最后出现的位置得知了位置又人如何切割
这里需要用到哈希来获得字符最后出现的位置通过字符串的ASCLL减去a的ASCLL每次遍历来更新字符串最后出现的位置。 代码如下 # 初始化一个长度为26的数组用于存储每个字母最后出现的位置path [0] * 26for i in range(len(s)):# 更新字母最后出现的位置path[ord(s[i]) - ord(a)] iord()函数的作用是获取字母的ASCLL值
接下来进行切割 每次遍历更新当前区间的右边界直到右边界等于当前节点的值则找到了切割点。 代码如下 result []left 0right 0for i in range(len(s)):# 更新当前区间的右边界right max(path[ord(s[i]) - ord(a)], right)# 如果右边界等于当前位置说明找到了一个划分点将当前区间长度加入结果中并更新左边界if right i:result.append(right - left 1)left i 1本题还有一个思路跟之前的452. 用最少数量的箭引爆气球和435. 无重叠区间一样的思路不过写起来很麻烦这里就不进行详细说明代码和注释在下面完整代码中给出思路见452. 用最少数量的箭引爆气球贪心
完整代码
class Solution:def partitionLabels(self, s: str) - List[int]:# 初始化一个长度为26的数组用于存储每个字母最后出现的位置path [0] * 26for i in range(len(s)):# 更新字母最后出现的位置path[ord(s[i]) - ord(a)] iresult []left 0right 0for i in range(len(s)):# 更新当前区间的右边界right max(path[ord(s[i]) - ord(a)], right)# 如果右边界等于当前位置说明找到了一个划分点将当前区间长度加入结果中并更新左边界if right i:result.append(right - left 1)left i 1return result
贪心版本二与452.用最少数量的箭引爆气球 、 435.无重叠区间相同的思路。
class Solution:def countLabels(self, s):# 初始化一个长度为26的区间列表初始值为负无穷hash [[float(-inf), float(-inf)] for _ in range(26)]hash_filter []# 遍历字符串s更新每个字母的区间范围for i in range(len(s)):if hash[ord(s[i]) - ord(a)][0] float(-inf):hash[ord(s[i]) - ord(a)][0] ihash[ord(s[i]) - ord(a)][1] i# 将没有出现过的字母的区间过滤掉for i in range(len(hash)):if hash[i][0] ! float(-inf):hash_filter.append(hash[i])return hash_filterdef partitionLabels(self, s):res []hash self.countLabels(s)hash.sort(keylambda x: x[0]) # 按左边界从小到大排序rightBoard hash[0][1] # 记录当前区间的最大右边界leftBoard 0for i in range(1, len(hash)):if hash[i][0] rightBoard: # 如果出现分割点将当前区间长度加入结果中并更新左边界res.append(rightBoard - leftBoard 1)leftBoard hash[i][0]rightBoard max(rightBoard, hash[i][1]) # 更新当前区间的最大右边界res.append(rightBoard - leftBoard 1) # 将最后一个区间的长度加入结果中return res
复杂度分析
时间复杂度O(n)空间复杂度O(1)使用的hash数组是固定大小
