Leetcode刷题笔记 763. 划分字母区间-白红宇

Leetcode刷题笔记 763. 划分字母区间

阅读量：3749 次

发布时间：2019-05-22

本文共 2542 字，大约阅读时间需要 8 分钟。

763. 划分字母区间

知识点：贪心、指针

时间：2020年10月22日

题目链接：

题目

字符串 S 由小写字母组成。我们要把这个字符串划分为尽可能多的片段，同一个字母只会出现在其中的一个片段。返回一个表示每个字符串片段的长度的列表。

示例 1：

输入

S = “ababcbacadefegdehijhklij”

输出：

[9,7,8]

解释：

划分结果为 “ababcbaca”, “defegde”, “hijhklij”。

每个字母最多出现在一个片段中。

像 “ababcbacadefegde”, “hijhklij” 的划分是错误的，因为划分的片段数较少。

提示：

S的长度在[1, 500]之间。

S只包含小写字母 ‘a’ 到 ‘z’ 。

解法

方法一：

遍历字符串找到每个字符开始以及结束的位置

对这些字符按照 开始位置小的排序

使用贪心的思想，遍历每个字符结构体
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

方法二：

遍历字符串找到每个字符结束的位置

从左到右遍历字符串 对于每个访问到的字母x，切分的位置end一定要大于等于他最后结束的位置x_end，更新标记end=max(end,x_end)

如果访问到结束位置，说明这段结束,放入答案

代码

#include 
   
    #include 
    
     #include 
     
      #include 
      
       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
       
         partitionLabels(string S) {
           vector
        
          ans; vector
         
           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
          
            partitionLabels(string S) { int last[26]; for (int i = 0; i < S.length(); i++) { last[S[i]-'a'] = i; } vector
           
             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
            
              ans = s.partitionLabels(S); for(int x:ans) cout<
             
              <