当前位置：首页 > article >正文

力扣第763题划分字母区间 c++ 哈希 + 双指针 + 小小贪心

article 2024/9/23 9:31:10

题目

763. 划分字母区间

中等

思路和解题方法

当我们遍历字符串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;
    }
};

觉得有用的话可以点点赞，支持一下。

如果愿意的话关注一下。会对你有更多的帮助。

每天都会不定时更新哦 >人< 。

查看全文

http://www.kler.cn/news/108062.html