C++ 中的分区标签

假设提供了一个小写字母字符串 S。我们将此字符串尽可能多地划分为多个部分，以便每个字母仅出现在一个部分中，最后返回一个整数列表表示这些部分的大小。因此，如果字符串类似于“ababcbacadefegdehijhklij”，输出为 [9,7,8]，因为分区为“ababcbaca”、“defegde”、“hijhklij”。因此，这是一个分区，使得每个字母都最多出现在一部分中。类似于“ababcbacadefegde”、“hijhklij”的分区不正确，因为它会将 S 分成更少的部分。

为了解决这个问题，我们将遵循以下步骤 -

• 定义一个名为 cnt 的映射
• 对于 i 从 0 到 s，令 cnt[s[i]] := i
• 令 j := 0，start := 0，i := 0，n := s 的大小
• 定义一个数组 ans
• 当 i < n 时
  • 令 j := j 和 cnt[s[i]] 的最大值
  • 如果 i = j，则将 i – start + 1 插入 ans 并且 start := i + 1
  • 将 i 增加 1
• 返回 ans

示例 (C++)

让我们看看以下实现以获得更好的理解 -

 在线演示

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
   cout << "[";
   for(int i = 0; i<v.size(); i++){
      cout << v[i] << ", ";
   }
   cout << "]"<<endl;
}
class Solution {
public:
   vector<int> partitionLabels(string s) {
      map <char, int> cnt;
      for(int i = 0; i < s.size(); i++)cnt[s[i]] = i;
      int j = 0, start = 0;
      int i = 0;
      int n = s.size();
      vector <int> ans;
      while(i < n){
         j = max(j, cnt[s[i]]);
         if( i == j){
            ans.push_back(i-start+ 1);
            start = i + 1;
         }
         i++;
      }
      return ans;
   }
};
main(){
   Solution ob;
   print_vector(ob.partitionLabels("ababcbacadefegdehijhklij"));
}

输入

"ababcbacadefegdehijhklij"

输出

[9,7,8]

Arnab Chakraborty

更新时间：2020 年 4 月 29 日

306 次浏览

开启你的 事业

完成课程获得认证

开始