資料結構
網路
關係型資料庫管理系統
作業系統
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 次瀏覽
廣告