Leetcode-763-划分字母区间

题目链接


题目描述

字符串 S 由小写字母组成。
把这个字符串划分为尽可能多的片段,
同一字母最多出现在一个片段中
返回一个表示每个字符串片段的长度的列表。

要求

时间复杂度:O(n)

思路

  1. 先遍历一遍 s ,用 map 记录每一个字母出现的区间。
    问题就转化成了对区间的合并操作。

  2. 再遍历一遍 s ,一边遍历,一边处理当前字符所出现的区间。
    若区间有重叠,直接合并,
    若无重叠,更新答案。


C++代码

class Solution {
public:
    vector<int> partitionLabels(string s) {
        vector<int> ans;
        unordered_map<char, pair<int, int>> mp;
        int len  = s.length();
        for (int i = 0; i < len; i++) {
            if (mp.count(s[i]) == 0)
                mp[s[i]].first = mp[s[i]].second = i;
            else 
                mp[s[i]].second = i;
        }

        int L= 0, R = 0;
        for (int i = 0; i < len; i++) {
            if (mp[s[i]].first > R) {
                ans.push_back(R-L+1);
                L = i;
                R = mp[s[i]].second; 
            } else if (mp[s[i]].second > R) {
                R = mp[s[i]].second;
            }
        }
        ans.push_back(R-L+1);
        return ans;
    }
};
上一篇:保姆级《Python编程——从入门到实践》第三章学习笔记(上)分享啦!!!


下一篇:shared_ptr:资源管理利器