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.
來(lái)源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/partition-labels
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。
面試中遇到的題
面試中的第一道題是兩數(shù)求和問(wèn)題由于給的例子很好理解 所以解題思路想的比較快 （面試官只讓說(shuō)思路就可以）
面試中的第二道面試題 也就是這個(gè)題 英語(yǔ)不太好 讀的有點(diǎn)久加上例子不太能理解 就想的慢 然后看面試官有點(diǎn)不耐煩了 就直接告訴面試官這個(gè)題我沒(méi)看懂 面試官以為我騙他 可能是因?yàn)槊嬖嚬賱傞_始就給我說(shuō)出得都是easy的題? 面試就不了了之（內(nèi)心我是真的沒(méi)有看懂這個(gè)題?。┟嬖囃曛缶妥约合肓艘幌逻@個(gè)題 的解法
1: 用的暴力解法 獲取每個(gè)字符出現(xiàn)的區(qū)間 然后合并區(qū)間 時(shí)間復(fù)雜度高
2:用的map 實(shí)現(xiàn) 獲取每個(gè)字符出現(xiàn)的最后位置 然后遍歷字符串
這倆種解法都發(fā)給了面試官 面試官還是不滿意 覺得這個(gè)題用map 沒(méi)有必要 然后問(wèn)面試官 要了他的解題方法 如下：
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 實(shí)現(xiàn)的思路一致 但是確實(shí)比我用的實(shí)現(xiàn)簡(jiǎn)便 （內(nèi)心大佬就是大佬但是就不能包容包容我English不好?。?/p>
分析一下這個(gè)代碼 純屬自己的理解不對(duì)的地方希望指出 小弟馬上修改
這里-1是因?yàn)榫幊讨械恼５谋闅v是從0開始的
for (int i=0; i<26; ++i) lastIndexOfChar[i] = -1;
倒敘獲取這個(gè)字符串的ASCII碼的差值 并賦值lastIndexOfChar[charCode]內(nèi)容為當(dāng)前的i這樣就能獲取到每個(gè)字符串最后一次出現(xiàn)的位置
? ? for (int i=lengthS-1; i>=0; --i)
? ? {
? ? ? ? int charCode = S[i] - 'a';
? ? ? ? if (-1 == lastIndexOfChar[charCode])
? ? ? ? {
? ? ? ? ? ? lastIndexOfChar[charCode] = i;
? ? ? ? }
? ? }
? 這個(gè)循環(huán)是核心 正序遍歷字符串 根據(jù)字符串的ASCII值charCode在 取出當(dāng)前字符的最后出現(xiàn)位置的下標(biāo) currentSegmentEndIndex? 并判斷currentSegmentEndIndex之前是否有字符出現(xiàn)的最后位置大于currentSegmentEndIndex 如果有則更新 currentSegmentEndIndex
? 如果當(dāng)i等于currentSegmentEndIndex時(shí)證明currentSegmentEndIndex之前沒(méi)有字符出現(xiàn)的最后位置大于currentSegmentEndIndex 所以就可以獲取到[lastSegmentEndIndex,currentSegmentEndIndex]之間為一段所求
重復(fù)上述就可以求出解
? ? 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;
? ? ? ? }
? ? }
