給你一個(gè)僅包含小寫(xiě)字母的字符串盆偿，請(qǐng)你去除字符串中重復(fù)的字母听哭，使得每個(gè)字母只出現(xiàn)一次。需保證返回結(jié)果的字典序最小（要求不能打亂其他字符的相對(duì)位置）
示例1:
input:"bcabc"
output:"abc"
示例2:
輸入:"cbacdcbc"
輸出:"acdb"
概念
一骤星、字典序
字典序，就是按照字典中出現(xiàn)的先后順序進(jìn)行排序爆哑。
1洞难、單個(gè)字符
在計(jì)算機(jī)中，字母以及數(shù)字字符揭朝，字典排序如下：
'0' < '1' < '2' < ... < '9' < 'a' < 'b' < ... < 'z'
2队贱、多個(gè)字符
這是單個(gè)字符的大小情況，那么如果是兩個(gè)字符串比較大小呢潭袱？在計(jì)算機(jī)中柱嫌，兩個(gè)字符串比較大小，是按照從左到右的順序進(jìn)行比較屯换，如果第1位相等编丘，就比較第2位与学，直至有一位可以比較出大小來(lái)，則不再繼續(xù)比較嘉抓。
使用計(jì)算機(jī)屬于來(lái)描述：
對(duì)于任意兩個(gè)序列 (a,b) 和 (a’,b’)索守，字典序定義為： (a,b) ≤ (a′,b′) 當(dāng)且僅當(dāng) a < a′ 或 (a = a′ 且 b ≤ b′).
3、全排列的字典序
給定多個(gè)字符抑片，可以按照任意順序進(jìn)行排列卵佛，所有排列稱為全排列。每一種排列對(duì)應(yīng)一個(gè)字符串敞斋，如果這些字符串按照字符串大小的順序進(jìn)行排序截汪，那么就這種排序是基于字典序的全排列。
比如給定三個(gè)字符 a,b,c渺尘，則他們基于字典序的全排列為：
abc > acb > bac > bca > cab > cba
解題
注意點(diǎn)
字典序要最小挫鸽，并且不能更改相對(duì)位置，字母互換
思路
- 字符串S為空鸥跟，長(zhǎng)度為1丢郊，不需要處理
- 使用一個(gè)數(shù)組記錄每個(gè)字母出現(xiàn)次數(shù) record [26]
- 字符串棧stack，用來(lái)去除重復(fù)字母的結(jié)果医咨，并且找到正確最小的字典序
- 遍歷字符串
- 從0~top,遍歷stack 判斷當(dāng)前字符s[i]是否存在于棧stack中如果當(dāng)前字符是否存在于棧的定義一個(gè)falg 標(biāo)記isExist, 0表示不存在, 1表示存在
- 如果isExist存在,record[s[i]]位置上的出現(xiàn)次數(shù)減一枫匾，并繼續(xù)遍歷下一個(gè)字符; 表示當(dāng)前的stack已經(jīng)有這個(gè)字符了沒(méi)有必要處理這個(gè)重復(fù)的字母
- 如果isExist不存在,則
- 如果不存在,則需要循環(huán)一個(gè)找到一個(gè)正確的位置,然后在存儲(chǔ)起來(lái);
- 如果不存在，跳過(guò)棧中所有比當(dāng)前字符大拟淮、且后面還會(huì)出現(xiàn)的元素干茉，然后將當(dāng)前字符入棧
- top > -1表示棧非空
- stack[top] > s[i]表示棧頂元素比當(dāng)前元素大
- record[stack[top]] > 1表示后面還會(huì)出現(xiàn)
通過(guò)一個(gè)while循環(huán)找到將棧中位置錯(cuò)誤的數(shù)據(jù),出棧. 找當(dāng)前合適的位置,則結(jié)束while循環(huán);找到合理的位置后,則將當(dāng)前字符s[i]入棧
- 遍歷完成后，在stack 后添加'\0',返回當(dāng)前字符串首地址
代碼
char *removeCharacter(char *string) {
// 1很泊、特殊情況 s為空角虫，長(zhǎng)度為0
//2、s長(zhǎng)度為1
if (string == NULL || strlen(string) == 0 ) {
return "";
}
if (strlen(string) == 1) {
return string;
}
char record[26] = {0};
// 字符串長(zhǎng)度
int len = (int)strlen(string);
// 存儲(chǔ)不用字符
char *stack = (char *)malloc(len * 2 *sizeof(char));
memset(stack, 0, len * 2 *sizeof(char));
int top = -1;
// 統(tǒng)計(jì)每個(gè)字母出現(xiàn)次數(shù)
// string[i] - 'a' 利用asc碼得道每個(gè)字母的位置委造，記錄到record中
int i = 0;
for (i = 0; i < len; i++) {
record[string[i] - 'a']++;
}
// 遍歷字符串s戳鹅，把不相同的字母進(jìn)棧
for (i = 0; i < len; i++) {
int isExist = 0;
// 判斷當(dāng)前字符在棧里面是否存在
for (int j = 0; j <= top; j++) {
if (string[i] == stack[j]) {
isExist = 1;
break;
}
}
if (isExist == 1) {
record[string[i] - 'a']--;
} else {
while (top > -1 && stack[top] > string[i] && record[stack[top] - 'a'] > 1) {
record[stack[top] - 'a']--;
top--;
}
top++;
stack[top] = string[i];
}
}
stack[++top] = '\0';
return stack;
}
