数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会科学
时尚研究
法律研究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]
更新时间：2020 年 4 月 29 日
306 次浏览
广告