給你一個僅包含小寫字母的字符串扎筒，請你去除字符串中重復(fù)的字母，使得每個字母只出現(xiàn)一次酬姆。需保證返回結(jié)果的字典序最惺茸馈（要求不能打亂其他字符的相對位置）。
示例1: 輸入:"bcabc"辞色， 輸出:"abc"
示例2: 輸入:"cbacdcbc"症脂， 輸出:"acdb"
字典序: 字符串之間比較和數(shù)字比較不一樣; 字符串比較是從頭往后挨個字符比較,那個字符串大取決于兩個字符串中第一個對應(yīng)不相等的字符; 例如 任意一個a開頭的字符串都大于任意一個b開頭的字符串;例如字典中apple 大于 book;
題目的意思,你去除重復(fù)字母后,需要按最小的字典序返回.并且不能打亂其他字母的相對位置;
例如 bcabc 你應(yīng)該返回abc, 而不是bca,cab;
例如 cbacdcbc 應(yīng)該返回acdb,而不是cbad,bacd,adcb
例如 zab,應(yīng)該返回zab,而不是abz;
思路:
- 判斷字符串可能出現(xiàn)的特殊情況
- 用一個record數(shù)組記錄字符串中字母出現(xiàn)的次數(shù);
- 申請一個字符串棧stack用來存儲去除重復(fù)字母的結(jié)果,并利用它的特性幫助我們找到正確的次序;
- 遍歷字符串s
- 從0~top,遍歷stack 判斷當(dāng)前字符s[i]是否存在于棧stack中
如果當(dāng)前字符是否存在于棧的定義一個falg 標(biāo)記isExist, 0表示不存在, 1表示存在
6.如果isExist存在,record[s[i]]位置上的出現(xiàn)次數(shù)減一，并繼續(xù)遍歷下一個字符; 表示當(dāng)前的stack已經(jīng)有這個字符了沒有必要處理這個重復(fù)的字母;
7.如果isExist不存在,則
如果不存在,則需要循環(huán)一個找到一個正確的位置,然后在存儲起來;
如果不存在淫僻，跳過棧中所有比當(dāng)前字符大诱篷、且后面還會出現(xiàn)的元素，然后將當(dāng)前字符入棧
top > -1表示棧非空
stack[top] > s[i]表示棧頂元素比當(dāng)前元素大
record[stack[top]] > 1表示后面還會出現(xiàn)
通過一個while循環(huán)找到將棧中位置錯誤的數(shù)據(jù),出棧. 找當(dāng)前合適的位置,則結(jié)束while循環(huán);
找到合理的位置后,則將當(dāng)前字符s[i]入棧;
8.直到遍歷完所有字符后,則為字符串棧stack 添加一個結(jié)束符'\0',并返回當(dāng)前字符串首地址;
char *removeDuplicateLetters(char *s) {
/*
① 特殊情況處理,s為空,或者字符串長度為0;
② 特殊情況,s的長度為1,則沒有必要后續(xù)的處理,則直接返回s;
*/
int len = (int)strlen(s);
if (len < 1) {
return "have no string";
}
if (len == 1) {
return s;
}
char record[26] = {0}; //record數(shù)組,用來記錄字符串s中每個字符未來會出現(xiàn)的次數(shù);
//申請一個字符串stack;(用棧的特性來進行stack字符串的數(shù)據(jù)進出)
char* stack = (char*)malloc((len+1) * sizeof(char));
//memset(void *s, int ch, size_t n) 將stack(len+1) *sizeof(char)長度范圍的空間填充0;
memset(stack, 0, (len+1) * sizeof(char));
//stack 棧頂賦初值為-1;
int top = -1;
int i;
for (i = 0; i < len; i++) { //1.統(tǒng)計每個字符的頻次
record[s[i] - 'a']++;
}
//2.遍歷s,入棧
for (i = 0; i < len; i++) {
//isExist 標(biāo)記, 判斷當(dāng)前字符是否存在棧中;
int isExist = 0;
//①從0~top,遍歷stack 判斷當(dāng)前字符s[i]是否存在于棧stack中
//如果當(dāng)前字符是否存在于棧的flag, 0表示不存在, 1表示存在
//top指向棧頂(也是執(zhí)行stack字符串最后一個字符的位置,表示字符串長度上限)
for (int j = 0; j <= top; j++) {
if (s[i] == stack[j]) {
isExist = 1;
break;
}
}
//② 如果存在,record[s[i]]位置上的出現(xiàn)次數(shù)減一雳灵，并繼續(xù)遍歷下一個字符
//③ 如果不存在,則需要循環(huán)一個正確位置存儲起來;
//④ 如果不存在棕所，跳過棧中所有比當(dāng)前字符大、且后面還會出現(xiàn)的元素悯辙，然后將當(dāng)前字符入棧
// top > -1表示棧非空
//stack[top] > s[i]表示棧頂元素比當(dāng)前元素大
//record[stack[top]] > 1表示后面還會出現(xiàn)
//例如b,c因為不符合以下條件會直接入棧.stack[] = "bc",但是當(dāng)當(dāng)前字符是"a"時,由于bcabc,a不應(yīng)該是在stack的順序是"bca",所以要把位置不符合的字符出棧;
//top = 1,stack[top] > s[i], c>a; 并且stack[top] 在之后還會重復(fù)的出現(xiàn),所以我們可以安心的把stack中的棧頂C出棧,所以stack[]="b",top減一后等于0; 同時也需要將record[c]出現(xiàn)次數(shù)減一;
//top=0,stack[top]>s[i],b>a,并且stack[top] 在之后還會出現(xiàn),所以stack把棧頂b出棧,所以此時棧stack[]="",top減一后等于-1, 此時棧中位置不正確的字符都已經(jīng)移除;
if (isExist == 1) {
record[s[i] - 'a']--;
} else {
while (top > -1 && stack[top] > s[i] && record[stack[top] - 'a'] > 1) {
// 跳過該元素琳省，頻次要減一
record[stack[top] - 'a']--;
// 出棧
top--;
}
//⑤ 結(jié)束while 循環(huán);
//循環(huán)結(jié)束的3種可能性:(1)移動到棧底(top == -1) ; (2)棧頂元素小于當(dāng)前元素(stack[top] <= s[i]) (3)棧頂元素后面不出現(xiàn)(record[stack[top]] == 1)
// 此時，當(dāng)前元素要插入到top的下一個位置
// top往上移動1位
top++;
// 入棧
stack[top] = s[i];
}
}
//結(jié)束棧頂添加字符結(jié)束符
stack[++top] = '\0';
return stack;
}
int main(int argc, const char * argv[]) {
// insert code here...
printf("去掉重復(fù)字母! LeetCode-困難 \n");
char *s ;
s = removeDuplicateLetters("bcabc");
printf("%s\n",s);//abc
s = removeDuplicateLetters("zab");
printf("%s\n",s);//zab
s = removeDuplicateLetters("cbacdcbc");
printf("%s\n",s);//acdb
printf("\n");
return 0;
}
