一、題目大意
標簽: 貪心
https://leetcode.cn/problems/partition-labels
字串 S 由小寫字母組成，我們要把這個字串劃分為盡可能多的片段，同一字母最多出現在一個片段中，回傳一個表示每個字串片段的長度的串列，
示例：
輸入：S = "ababcbacadefegdehijhklij"
輸出：[9,7,8]
解釋：
劃分結果為 "ababcbaca", "defegde", "hijhklij"，
每個字母最多出現在一個片段中，
像 "ababcbacadefegde", "hijhklij" 的劃分是錯誤的，因為劃分的片段數較少，
提示：
- S的長度在[1, 500]之間，
- S只包含小寫字母 'a' 到 'z' ，
二、解題思路
一個字串S，將其盡可能多的分割為子字串，條件是每種字符最多只能出現在一個子串中，上面的示例中，字串S中有多個a，這些a必須只能在第一個子串中，字母e出現在第二個子串中，這道題難點就是如何找到字串的斷點，即拆分成為子串的位置，觀察上述例子，一旦某個字母多次出現，那么其最后一個出現位置必須要在當前子串中，字母a，e，j分別是三個子串中的結束字母，所以我們關注的是每個字母最后的出現位置，我們可以使用一個Map來建立字母和其最后出現位置之間的映射，建立好映射之后，就需要開始遍歷字串S，我們維護一個start變數，是當前子串的起始位置，還有一個last變數，是當前子串的結束位置，每當我們遍歷到一個字母，需要在Map中提取出其最后一個位置，因為一旦當前子串飲食了一個字母，其必須飲食所有的相同字母，所以我們要不停的用當前字母的最后一個位置來更新last變數，只有當i和last相同了，即i=last時，當前子串飲食了所有已出現過的字母的最后一個位置，即之后的字串不會有之前出現過的字母了，此時就應該是斷開的位置，我們將子串長度加入到結果中，
三、解題方法
3.1 Java實作
public class Solution {
public List<Integer> partitionLabels(String s) {
Map<Character, Integer> map = new HashMap<>();
char[] cArr = s.toCharArray();
for (int i = 0; i < cArr.length; i++) {
map.put(cArr[i], i);
}
List<Integer> res = new ArrayList<>();
int start = 0;
int last = 0;
for (int i = 0; i < cArr.length; i++) {
last = Math.max(map.get(cArr[i]), last);
if (i == last) {
res.add(last - start + 1);
start = last + 1;
}
}
return res;
}
}
四、總結小記
- 2022/7/28 把思路理清了，代碼就順理成章出來了
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/500543.html
標籤：其他