企业官网建设流程全解析

题目描述

给你一个字符串s，要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。例如ababcc能够被分为["abab", "cc"]。

示例 1：

输入：s = "ababcbacadefegdehijhklij" 输出：[9,7,8] 解释：划分为 "ababcbaca"、"defegde"、"hijhklij"

示例 2：

输入：s = "eccbbbbdec" 输出：[10]

解题思路总览

算法一：哈希表存储

思路

第一遍用哈希表记录每个字符最后出现的位置。第二遍遍历时，维护当前片段中所有字符的最远边界。

代码

classSolution{public:vector<int>partitionLabels(string s){unordered_map<char,int>last;for(inti=0;i<s.size();i++){last[s[i]]=i;}vector<int>ans;intstart=0,end=0;for(inti=0;i<s.size();i++){end=max(end,last[s[i]]);if(end==i){ans.push_back(end-start+1);start=end+1;}}returnans;}};

算法二：数组优化（最优解）

思路

用数组代替哈希表记录每个字符最后出现的位置。数组下标对应字母，值为最后出现位置。

代码

classSolution{public:vector<int>partitionLabels(string s){intn=s.size();intlast[26];for(inti=0;i<n;i++){last[s[i]-'a']=i;}vector<int>ans;intstart=0,end=0;for(inti=0;i<n;i++){end=max(end,last[s[i]-'a']);if(end==i){ans.push_back(end-start+1);start=end+1;}}returnans;}};

算法流程

输入: s = "ababcbacadefegdehijhklij" 第一步：统计每个字符最后出现的位置 +-------------------------------------------------------------+ | 字符 | a | b | c | d | e | f | h | l | | 最后 | 8 | 9 | 7 | 14 | 15 | 11 | 19 | 22 | +-------------------------------------------------------------+ 第二步：遍历字符串，维护片段边界 +-------------------------------------------------------------+ | i=0 | s[0]='a', end=max(0,8)=8 | end!=i, 继续 | | i=1 | s[1]='b', end=max(8,9)=9 | end!=i, 继续 | | i=2 | s[2]='a', end=max(9,8)=9 | end!=i, 继续 | | i=3 | s[3]='b', end=max(9,9)=9 | end!=i, 继续 | | i=4 | s[4]='c', end=max(9,7)=9 | end!=i, 继续 | | i=5 | s[5]='b', end=max(9,9)=9 | end!=i, 继续 | | i=6 | s[6]='a', end=max(9,8)=9 | end!=i, 继续 | | i=7 | s[7]='c', end=max(9,7)=9 | end!=i, 继续 | | i=8 | s[8]='a', end=max(9,8)=9 | end==i! 切片段 | | | ans.push(8-0+1)=9 | start=9 | +-------------------------------------------------------------+ | i=9 | s[9]='d', end=max(9,14)=14 | end!=i, 继续 | | ... | ... | end!=i, 继续 | | i=15 | s[15]='e', end=max(15,15)=15 | end==i! 切片段 | | | ans.push(15-9+1)=7 | start=16 | +-------------------------------------------------------------+ | i=16 | s[16]='f', end=22 | end!=i, 继续 | | ... | ... | end!=i, 继续 | | i=22 | s[22]='l', end=22 | end==i! 切片段 | | | ans.push(22-16+1)=7? 不对 | 实际是8 | +-------------------------------------------------------------+ 输出: ans = [9, 7, 8]

复杂度分析

核心思想

s = "ababcbacadefegdehijhklij" 为什么 end == i 时就能切片段？ +-------------------------------------------------------------+ | 位置 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 ... | | 字符 a b a b c b a c a d e f e g d e | | 最后 8 9 8 9 7 9 8 7 8 14 15 11 15 14 14 15 ... | +-------------------------------------------------------------+ 在位置 i，如果 end == i，意味着： - 到位置 i 为止，当前片段中的所有字符都已经出现过最后一次了 - 不会再有字符需要跨越 i 才能出现 - 所以位置 i 必须是片段的结束位置 片段 1 分析（位置 0-8）： - 包含的字符: a, b, c - a 的最后位置: 8 - b 的最后位置: 9 - c 的最后位置: 7 - 当前 end = max(8,9,7) = 9 - 但位置 8 时，虽然 end=9 != 8，但到了位置 8 之后 - 'a' 的最后位置是 8，就在当前位置，不需要再延伸 - 所以 end == i = 8，切片段！

复杂度对比总结

面试追问 FAQ

相关题目

总结