企业官网建设流程全解析

seo网站设计营销工具,重庆大渡口营销型网站建设价格,网站建设公司厂,界面设计心得题目#xff1a;给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段#xff0c;同一字母最多出现在一个片段中。例如#xff0c;字符串 ababcc 能够被分为 [abab, cc]#xff0c;但类似 [aba, bcc] …题目给你一个字符串s。我们要把这个字符串划分为尽可能多的片段同一字母最多出现在一个片段中。例如字符串ababcc能够被分为[abab, cc]但类似[aba, bcc]或[ab, ab, cc]的划分是非法的。注意划分结果需要满足将所有划分结果按顺序连接得到的字符串仍然是s。返回一个表示每个字符串片段的长度的列表。解答1️⃣ 问题本质题目要求把字符串划分成若干连续区间使得每个字母只出现在其中一个区间内并返回每个区间的长度。2️⃣ 关键观察如果某个字母在字符串中最右一次出现的位置是pos那么只要当前区间里包含了这个字母这个区间最少要延伸到pos。➡️区间的右边界由区间内所有字符的“最后出现位置”的最大值决定3️⃣ 预处理核心准备先遍历一次字符串记录每个字母最后一次出现的下标这样后续在遍历时可以随时知道“当前字符最远会把区间拉到哪里”。4️⃣ 贪心划分区间核心思想从左到右遍历字符串维护一个变量right表示当前区间必须到达的最右边界每遇到一个字符更新right为当前right和该字符最后出现位置的最大值当遍历位置i right时说明当前区间内的所有字符都不会再出现在后面可以安全地切分一个区间记录区间长度从下一个位置开始新一段这是一个一次扫描 局部最优即全局最优的贪心过程。class Solution { public: vectorint partitionLabels(string s) { int last[26]; vectorint length; for (int i 0; i s.size(); i) last[s[i] - a] i; int right -1; int start 0; for (int i 0; i s.size(); i) { right max(right, last[s[i] - a]); if (i right) { length.push_back(i - start 1); start i 1; } } return length; } };