Leetcode刷題筆記 763. 劃分字母區間

763. 劃分字母區間

知識點：貪心、指針

時間：2020年10月22日

題目連結：https://leetcode-cn.com/problems/partition-labels/

題目

字元串 S 由小寫字母組成。我們要把這個字元串劃分為盡可能多的片段，同一個字母隻會出現在其中的一個片段。傳回一個表示每個字元串片段的長度的清單。

示例 1：

輸入

S = “ababcbacadefegdehijhklij”

輸出：

[9,7,8]

解釋：

劃分結果為 “ababcbaca”, “defegde”, “hijhklij”。

每個字母最多出現在一個片段中。

像 “ababcbacadefegde”, “hijhklij” 的劃分是錯誤的，因為劃分的片段數較少。

提示：

1. S的長度在[1, 500]之間。
2. S隻包含小寫字母 ‘a’ 到 ‘z’ 。

解法

方法一：

1. 周遊字元串 找到每個字元開始以及結束的位置
2. 對這些字元按照 開始位置小的排序
3. 使用貪心的思想，周遊每個字元結構體
   1. 如果接下來的字元start位置已經超過現在的end位置，這個開始位置到結束位置的距離放入答案
   2. 如果這個字元end位置比現在的end位置大，更新，切的距離變多

a[0,8] b[1,5] c[4,7]  start = 0 end = 8
	d[9,14] e[10,15] f[11,11] g[13,13] start = 9 end = 15
	h[16,19] i[17,22] j[18,23] k[20,20] l[21,21] start = 16 end = 23
           

方法二：

1. 周遊字元串 找到每個字元結束的位置
2. 從左到右周遊字元串 對于每個通路到的字母x，切分的位置end一定要大于等于他最後結束的位置x_end，更新标記end=max(end,x_end)
3. 如果通路到結束位置，說明這段結束,放入答案

代碼

#include <stdio.h>
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
struct node{
    int start;
    int end;
    node():start(600),end(600){}//初始化為最大值 題中S長度最大為500
    node(int s,int e):start(s),end(e){}
};
bool cmp(struct node x,struct node y){
    return x.start < y.start;
}
class Solution {
public:
    vector<int> partitionLabels(string S) {
        vector<int> ans;
        vector<node> dic(26);
        for(int i = 0; i < S.length();i++){
            int index = S[i] - 'a';
            //如果第一次讀到此字元
            if(dic[index].start == 600 && dic[index].end == 600){dic[index].start = i;dic[index].end = i;}
            else if(dic[index].start > i){dic[index].start = i;}
            else if(dic[index].end < i ){dic[index].end = i;}
        }
        //按照第一次出現的位置排序
        sort(dic.begin(), dic.end(),cmp);
        int begin = dic[0].start, end = dic[0].end;
        for(int i=1;i<26;i++){
            //如果接下來的字元start位置已經超過現在的end位置，這個開始位置到結束位置的距離放入答案
            if(dic[i].start > end){
                ans.emplace_back(end-begin+1);
                begin = dic[i].start;
                end = dic[i].end;
            //如果這個字元end位置比現在的end位置大，更新，切的距離變多
            }else if(dic[i].end > end){
                end = dic[i].end;
            }
        }
        //注意邊界
        if(end-begin!=0)
            ans.emplace_back(end-begin+1);
        return ans;
    }
};
/*
class Solution {
public:
    vector<int> partitionLabels(string S) {
        int last[26];
        for (int i = 0; i < S.length(); i++) {
            last[S[i]-'a'] = i;
        }
        vector<int> ans;
        int start = 0, end = 0;
        for (int i = 0; i < S.length(); i++) {
            end = max(end, last[S[i] - 'a']);
            if (i == end) {
                ans.emplace_back(end - start + 1);
                start = end + 1;
            }
        }
        return ans;
    }
};
 */
int main()
{
    string S{"ababcbacadefegdehijhklij"};
    Solution s;
    vector<int> ans = s.partitionLabels(S);
    for(int x:ans)
        cout<<x<<endl;
    return 0;
}

           

今天也是愛zz的一天哦！