A string S of lowercase letters is given. We want to partition this string into as many parts as possible so that each letter appears in at most one part, and return a list of integers representing the size of these parts.
Example 1:
Input: S = "ababcbacadefegdehijhklij"
Output: [9,7,8]
Explanation:
The partition is "ababcbaca", "defegde", "hijhklij".
This is a partition so that each letter appears in at most one part.
A partition like "ababcbacadefegde", "hijhklij" is incorrect, because it splits S into less parts.
Note:
S will have length in range [1, 500].
S will consist of lowercase letters ('a' to 'z') only.
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/partition-labels
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
面试中遇到的题
面试中的第一道题是两数求和问题由于给的例子很好理解 所以解题思路想的比较快 （面试官只让说思路就可以）
面试中的第二道面试题 也就是这个题 英语不太好 读的有点久加上例子不太能理解 就想的慢 然后看面试官有点不耐烦了 就直接告诉面试官这个题我没看懂 面试官以为我骗他 可能是因为面试官刚开始就给我说出得都是easy的题 面试就不了了之（内心我是真的没有看懂这个题啊）面试完之后就自己想了一下这个题 的解法
1: 用的暴力解法 获取每个字符出现的区间 然后合并区间 时间复杂度高
2:用的map 实现 获取每个字符出现的最后位置 然后遍历字符串
这俩种解法都发给了面试官 面试官还是不满意 觉得这个题用map 没有必要 然后问面试官 要了他的解题方法 如下：
int* partitionLabels(char * S, int* returnSize) {
if (S == NULL)
{
*returnSize = 0;
return NULL;
}
long lengthS = strlen(S);
if (lengthS == 0)
{
*returnSize = 0;
return NULL;
}
int lastIndexOfChar[26];
for (int i=0; i<26; ++i) lastIndexOfChar[i] = -1;
for (int i=lengthS-1; i>=0; --i)
{
int charCode = S[i] - 'a';
if (-1 == lastIndexOfChar[charCode])
{
lastIndexOfChar[charCode] = i;
}
}
int* result = (int*) malloc(sizeof(int) * lengthS);
int resultSize = 0;
int currentSegmentEndIndex = 0, lastSegmentEndIndex = -1;
for (int i=0; i<lengthS; ++i)
{
int charCode = S[i] - 'a';
if (lastIndexOfChar[charCode] > currentSegmentEndIndex)
{
currentSegmentEndIndex = lastIndexOfChar[charCode];
}
if (i == currentSegmentEndIndex)
{
result[resultSize++] = i - lastSegmentEndIndex;
lastSegmentEndIndex = currentSegmentEndIndex;
}
}
*returnSize = resultSize;
return result;
}
思路和用map 实现的思路一致 但是确实比我用的实现简便 （内心大佬就是大佬但是就不能包容包容我English不好啊）
分析一下这个代码 纯属自己的理解不对的地方希望指出 小弟马上修改
这里-1是因为编程中的正常的遍历是从0开始的
for (int i=0; i<26; ++i) lastIndexOfChar[i] = -1;
倒叙获取这个字符串的ASCII码的差值 并赋值lastIndexOfChar[charCode]内容为当前的i这样就能获取到每个字符串最后一次出现的位置
for (int i=lengthS-1; i>=0; --i)
{
int charCode = S[i] - 'a';
if (-1 == lastIndexOfChar[charCode])
{
lastIndexOfChar[charCode] = i;
}
}
这个循环是核心 正序遍历字符串 根据字符串的ASCII值charCode在 取出当前字符的最后出现位置的下标 currentSegmentEndIndex 并判断currentSegmentEndIndex之前是否有字符出现的最后位置大于currentSegmentEndIndex 如果有则更新 currentSegmentEndIndex
如果当i等于currentSegmentEndIndex时证明currentSegmentEndIndex之前没有字符出现的最后位置大于currentSegmentEndIndex 所以就可以获取到[lastSegmentEndIndex,currentSegmentEndIndex]之间为一段所求
重复上述就可以求出解
for (int i=0; i<lengthS; ++i)
{
int charCode = S[i] - 'a';
if (lastIndexOfChar[charCode] > currentSegmentEndIndex)
{
currentSegmentEndIndex = lastIndexOfChar[charCode];
}
if (i == currentSegmentEndIndex)
{
result[resultSize++] = i - lastSegmentEndIndex;
lastSegmentEndIndex = currentSegmentEndIndex;
}
}
