题解 | #分品种#
分品种
https://www.nowcoder.com/practice/9af4e93b04484df79d4cc7a863343b0b
考察的知识点:贪心;
解答方法分析:
- 遍历字符串 s,记录每个字母最后出现的位置。
- 使用双指针 start 和 end 表示当前片段的起始位置和结束位置,初始化为 0。
- 再次遍历字符串 s,更新当前片段的结束位置 end如果当前位置 i 等于 end,则表示当前位置是段的结束位置,将当前片段的长度加入结果中,start 更新为 end+1,表示下一个片段的起始位置。
- 返回结果。
所用编程语言:C++;
完整编程代码:↓
class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param s string字符串 * @return int整型vector */ vector<int> partitionLabels(string s) { vector<int> result; if (s.empty()) return result; int n = s.length(); vector<int> last(26, 0); for (int i = 0; i < n; i++) { last[s[i] - 'a'] = i; } int start = 0; int end = 0; for (int i = 0; i < n; i++) { end = max(end, last[s[i] - 'a']); if (i == end) { result.push_back(end - start + 1); start = end + 1; } } return result; } };