字串的最大分割長度，使得字串中的每個字元都出現在一個子字串中-C++-PHP中文網

字串的最大分割長度，使得字串中的每個字元都出現在一個子字串中

WBOY

發布： 2023-08-25 14:41:18

轉載

976 人瀏覽過

字串的最大分割長度，使得字串中的每個字元都出現在一個子字串中

在本文中，我們將探討如何找到具有唯一字元的字串的最大化分區的長度問題。我們首先了解問題陳述，然後研究解決這個問題的樸素和高效方法，包括它們各自的演算法和時間複雜度。最後，我們將在C 中實現解決方案。

問題陳述

給定一個字串，將字串分割成盡可能多的子字串，使得字串中的每個字元只出現在一個子字串中。傳回這些最大化分割的長度。

天真的方法

天真的方法是透過字串迭代，記錄每個字元的最後出現位置。然後，再次迭代字串，並在找到當前字元的最後出現位置時建立分區。

演算法（樸素）

初始化一個陣列以儲存字串中每個字元的最後出現位置。
遍歷字串並記錄每個字元的最後出現。
初始化一個向量來儲存分割區的長度。
再次遍歷字串，並在找到目前字元的最後出現時建立分割區。

C 程式碼（樸素）

Example

的中文翻譯為：

範例

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

std::vector<int> partitionLengths(std::string s) {
   std::vector<int> lastOccurrence(26, -1);
   
   for (size_t i = 0; i < s.size(); i++) {
      lastOccurrence[s[i] - 'a'] = i;
   }
   
   std::vector<int> partitionLengths;
   int start = 0, end = 0;
   
   for (size_t i = 0; i < s.size(); i++) {
      end = std::max(end, lastOccurrence[s[i] - 'a']);
      if (i == end) {
         partitionLengths.push_back(end - start + 1);
         start = i + 1;
      }
   }
   
   return partitionLengths;
}

int main() {
   std::string s = "abacdc";
   std::vector<int> lengths = partitionLengths(s);
   
   std::cout << "Lengths of maximized partitions: ";
   for (int length : lengths) {
      std::cout << length << " ";
   }
   
   return 0;
}

登入後複製

輸出

Lengths of maximized partitions: 3 3

登入後複製

時間複雜度（樸素演算法） - O(n)，其中n是字串的長度。

高效的方法

高效的方法類似於簡單的方法，但我們可以建立分區，同時記錄單次迭代中每個字元的最後一次出現，而不是迭代字串兩次。

演算法（高效）

初始化一個陣列以儲存字串中每個字元的最後出現位置。
初始化一個向量來儲存分割區的長度。
遍歷字串，記錄每個字元的最後出現位置，並在找到目前字元的最後出現位置時建立分區。

C 程式碼（高效）

範例

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

std::vector<int> partitionLengths(std::string s) {
   std::vector<int> lastOccurrence(26, -1);
   std::vector<int> partitionLengths;
   int start = 0, end = 0;
   
   for (size_t i = 0; i < s.size(); i++) {
      lastOccurrence[s[i] - 'a'] = i;
   }
   
   for (size_t i = 0; i < s.size(); i++) {
      end = std::max(end, lastOccurrence[s[i] - 'a']);
   
      if (i == end) {
         partitionLengths.push_back(end - start + 1);
         start = i + 1;
      }
   }
   
   return partitionLengths;
}

int main() {
   std::string s = "abacdc";
   std::vector<int> lengths = partitionLengths(s);
   
   std::cout << "Lengths of maximized partitions: ";
   for (int length : lengths) {
      std::cout << length << " ";
   }
   
   return 0;
}

登入後複製