力扣第763题 划分字母区间 c++ 哈希 + 双指针 + 小小贪心
题目
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:
vector<int> partitionLabels(string S) {
int hash[27] = {0}; // i为字符，hash[i]为字符出现的最后位置
for (int i = 0; i < S.size(); i++) { // 统计每一个字符最后出现的位置
hash[S[i] - 'a'] = i;
}
vector<int> 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;
}
};
觉得有用的话可以点点赞，支持一下。
如果愿意的话关注一下。会对你有更多的帮助。
每天都会不定时更新哦 >人< 。