• 原題鏈接🔗：劃分字母區(qū)間
• 難度：中等????

題目

給你一個(gè)字符串 s 。我們要把這個(gè)字符串劃分為盡可能多的片段，同一字母最多出現(xiàn)在一個(gè)片段中。

注意，劃分結(jié)果需要滿足：將所有劃分結(jié)果按順序連接，得到的字符串仍然是 s 。

返回一個(gè)表示每個(gè)字符串片段的長(zhǎng)度的列表。

示例 1：
輸入：s = “ababcbacadefegdehijhklij”
輸出：[9,7,8]
解釋：
劃分結(jié)果為 “ababcbaca”、“defegde”、“hijhklij” 。
每個(gè)字母最多出現(xiàn)在一個(gè)片段中。
像 “ababcbacadefegde”, “hijhklij” 這樣的劃分是錯(cuò)誤的，因?yàn)閯澐值钠螖?shù)較少。

示例 2：

輸入：s = “eccbbbbdec”
輸出：[10]

提示：

• 1 <= s.length <= 500
• s 僅由小寫英文字母組成

貪心算法

貪心算法是一種在每一步選擇中都采取在當(dāng)前狀態(tài)下最好或最優(yōu)的選擇，從而希望導(dǎo)致結(jié)果是全局最好或最優(yōu)的算法策略。它在有最優(yōu)子結(jié)構(gòu)的問(wèn)題中尤為有效。最優(yōu)子結(jié)構(gòu)的意思是局部最優(yōu)解能決定全局最優(yōu)解。

貪心算法不保證會(huì)得到最優(yōu)解，但在某些問(wèn)題上貪心算法的解是足夠好的。以下是貪心算法的一些關(guān)鍵特性：

1. 貪心選擇性質(zhì)：算法在每一步都選擇當(dāng)前看起來(lái)最優(yōu)的選項(xiàng)，而不考慮未來(lái)的選擇。
2. 最優(yōu)子結(jié)構(gòu)：問(wèn)題可以分解為子問(wèn)題，子問(wèn)題的最優(yōu)解能組成原問(wèn)題的最優(yōu)解。
3. 可行性：貪心選擇必須在當(dāng)前狀態(tài)下可行。

貪心算法通常用于求解以下類型的問(wèn)題：

• 資源分配問(wèn)題
• 調(diào)度問(wèn)題
• 網(wǎng)絡(luò)流問(wèn)題
• 集合覆蓋問(wèn)題
• 最小生成樹問(wèn)題（如 Prim 算法和 Kruskal 算法）

貪心算法的實(shí)現(xiàn)步驟通常包括：

1. 定義問(wèn)題的一個(gè)解決方案。
2. 遍歷所有候選解。
3. 選擇當(dāng)前狀態(tài)下的最優(yōu)候選解，并將其添加到當(dāng)前解決方案中。
4. 重復(fù)步驟2和3，直到達(dá)到問(wèn)題的結(jié)束條件。

貪心算法的優(yōu)點(diǎn)是簡(jiǎn)單、直觀，且在某些情況下效率很高。然而，缺點(diǎn)是它不總是能得到全局最優(yōu)解，特別是當(dāng)問(wèn)題不具有最優(yōu)子結(jié)構(gòu)時(shí)。

題解

1. 解題思路：

這個(gè)問(wèn)題是一個(gè)典型的貪心算法問(wèn)題，我們可以通過(guò)以下步驟來(lái)解決：

• 初始化：創(chuàng)建一個(gè)空列表 result 用來(lái)存儲(chǔ)每個(gè)片段的長(zhǎng)度。

• 遍歷字符串：從左到右遍歷字符串 s。

• 記錄當(dāng)前字母：使用一個(gè)變量 current_char 記錄當(dāng)前遍歷到的字母。

• 計(jì)數(shù)：使用一個(gè)變量 count 來(lái)記錄當(dāng)前字母連續(xù)出現(xiàn)的次數(shù)。

• 更新片段長(zhǎng)度：每當(dāng)遇到一個(gè)新的字母，或者到達(dá)字符串的末尾時(shí)，將 count 加入到 result 列表中，并重置 count 和 current_char。

• 特殊情況處理：如果當(dāng)前字母和下一個(gè)字母相同，則 count 自增，繼續(xù)遍歷；如果不同，將當(dāng)前 count 存入 result 并更新 current_char 和 count。

• 返回結(jié)果：遍歷結(jié)束后，返回 result 列表。

2. c++ demo：

#include <iostream>
#include <vector>
#include <unordered_map>using namespace std;class Solution {
public:vector<int> partitionLabels(string s) {vector<int> result;unordered_map<char, int> last_position;int start = 0, end = -1, length = 0;// 記錄每個(gè)字符最后一次出現(xiàn)的位置for (int i = 0; i < s.length(); ++i) {last_position[s[i]] = i;}for (int i = 0; i < s.length(); ++i) {// 更新當(dāng)前片段的結(jié)束位置end = max(end, last_position[s[i]]);length++;// 如果當(dāng)前位置是當(dāng)前片段的結(jié)束位置，則添加到結(jié)果中if (i == end) {result.push_back(length);start = i + 1; // 重置片段開始位置end = -1; // 重置片段結(jié)束位置length = 0; // 重置片段長(zhǎng)度}}return result;}
};int main() {Solution solution;string s = "ababcbacadefegdehijhklij";vector<int> result = solution.partitionLabels(s);for (int length : result) {cout << length << " ";}cout << endl;return 0;
}

• 輸出結(jié)果：

9 7 8

3. 代碼倉(cāng)庫(kù)地址：partitionLabels