湖南自考网站建设与管理,建站之星网站建设下载版,广州学习做网站建设的学校,专业网站建设顾问题目
763. 划分字母区间
中等
相关标签
贪心 哈希表 双指针 字符串
给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段#xff0c;同一字母最多出现在一个片段中。
注意#xff0c;划分结果需要满足#xff1a;将所有划分结果按顺序连接#xff0c;得…题目
763. 划分字母区间
中等
相关标签
贪心 哈希表 双指针 字符串
给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段同一字母最多出现在一个片段中。
注意划分结果需要满足将所有划分结果按顺序连接得到的字符串仍然是 s 。
返回一个表示每个字符串片段的长度的列表。 示例 1
输入s ababcbacadefegdehijhklij
输出[9,7,8]
解释
划分结果为 ababcbaca、defegde、hijhklij 。
每个字母最多出现在一个片段中。
像 ababcbacadefegde, hijhklij 这样的划分是错误的因为划分的片段数较少。
示例 2
输入s eccbbbbdec
输出[10]提示
1 s.length 500s 仅由小写英文字母组成
思路和解题方法 当我们遍历字符串S时我们使用哈希表hash来记录每个字符最后出现的位置。这样在遍历过程中我们可以通过查询哈希表来获取每个字符的最远边界。接下来我们使用两个指针left和right来表示当前分段的起始位置和结束位置。初始时它们都指向字符串的开头。在遍历过程中对于每个字符S[i]我们更新right的值为当前字符的最远边界即max(right, hash[S[i] - a])。这样right始终表示当前分段的结束位置。当我们遍历到一个位置i时如果i等于right说明当前位置是当前分段的结束位置。此时我们可以确定当前分段的长度为right - left 1将该长度加入结果数组并将left更新为下一个分段的起始位置即i 1。最终当遍历完成后我们得到了所有分段的长度将它们存储在结果数组中并返回。通过这种方法我们可以将字符串S划分为多个由不重叠子串组成的分段每个分段中的字符只会出现在该分段中。返回的结果数组即为每个分段的长度。这种解法的时间复杂度是O(n)其中n是字符串S的长度。因为我们需要遍历整个字符串S一次并在每个位置查询哈希表哈希表的查询操作时间复杂度是O(1)。总结起来该算法通过使用哈希表和双指针的方式实现了对字符串S的划分找到了所有不重叠的子串并返回了每个子串的长度。 复杂度 时间复杂度: O(n) 时间复杂度是O(n)其中n是字符串S的长度。代码中有两个循环第一个循环用于统计每个字符最后出现的位置第二个循环用于遍历字符串S并找到每个分割点。 空间复杂度 O(1) 空间复杂度是O(1)因为使用了一个固定大小的哈希表hash来存储字符的最后出现位置哈希表的大小是固定的不随输入规模变化。另外返回的结果是一个vector其大小取决于输入字符串中的分割点数量但不会超过字符串S的长度。因此可以将空间复杂度视为常数级别。 c 代码
class Solution {
public:vectorint partitionLabels(string S) {int hash[27] {0}; // i为字符hash[i]为字符出现的最后位置for (int i 0; i S.size(); i) { // 统计每一个字符最后出现的位置hash[S[i] - a] i;}vectorint result;int left 0; // 当前分段的起始位置int right 0; // 当前分段的结束位置for (int i 0; i S.size(); i) {right max(right, hash[S[i] - a]); // 找到字符出现的最远边界if (i right) { // 当前位置是当前分段的结束位置result.push_back(right - left 1); // 将当前分段的长度加入结果数组left i 1; // 更新下一个分段的起始位置}}return result;}
};觉得有用的话可以点点赞支持一下。
如果愿意的话关注一下。会对你有更多的帮助。 每天都会不定时更新哦 人 。
