🌟前言
摆烂太久，好久没有更文了，小九和大家一起看看题写写题找回手感吧，也希望这篇文章可以帮助正在寻找解题答案的朋友，你们的支持就是我最大的动力！求三连！求关注呀！
🌟题目
去除重复字母,给你一个仅包含小写字母的字符串，请你去除字符串中重复的字母，使得每个字母只出现一次。需保证返回结果的字典序最小 (要求不能打乱其他字符的相对位置)示例1:
输入:"bcabc"
输出:"abc"
示例2:
输入:"cbacdcbc"
输出:"acdb" cbad,bacd,adcb
字典序: apple book
- 字典序最小，不能出现打乱字母相对位置;
🌟解题前捋清思路
特殊条件
在写代码时要考虑会遇到的特殊情况，例如题目所指的“给你一个仅包含小写字母的字符串”，这个字符串它可能会给一个空字符，或者甚至一个字符，长度为1，这种情况我们就可以不用再进行去重这操作了写代码时，我们也要有这种意识，例如在写链表时，考虑链表为空
记录字母出现频率
用一个数组record记录字符串中字母出现的次数，次数我们遍历一遍字符串即可，因为要统计的是小写字母，而有且只有26个，所以我们的数组定义26个空间即可，record[26]
建字符栈stack
这里的栈呢，本质上就是一个连续的数组，用来模拟栈的思想，但不用完全按照栈的格式去写，我们只需要参考栈的一个特点：“先进后出”，作用：存储去除重复字母的结果，利用栈来正确次序。
遍历字符串
遍历字符串会有一个特殊的地方，那就是当前字符，对其进行判断，在0~top的空间里，判断当前字符是否存在栈中，用一个标记即可
如果已经存在，就让record[s[i]]--,代表去除了一个重复的s[i]位置上对应的字母，表示stack已经有了这个字符，不需要再进行存入又取出，然后继续遍历下一个字符；
若不存在，则通过while循环找到正确位置。以bcabc字符串为例，此时的字符a，通过循环，判断栈中元素是否要出栈，找到a的正确位置
判断条件
- 栈不能为空top>-1
- 栈顶元素要大于遍历到的当前字符 stack[top]>s[i]
- 栈顶字符对应的record>0,(为0代表字符串后面不再有此元素，所以不能出栈)
🌟代码实现
判断特殊直接输出条件
s为空，长度为0；s长度为1，直接输出
if(s ==NULL || strlen(s) == 0){ return ""; } if(strlen(s) == 1){ return s; }
实现两个数组，一个用来计数一个用来做栈
//写两个数组，一个record一个stack char record[26] = {0}; int len = (int)strlen(s); //先看字符串长度是多少 //申请一个空间，指向字符数组 char *stack = (char *)malloc(len * sizeof(char)+1); //对stack赋初值 memset(stack, 0, len * sizeof(char)+1); int top = -1;
此处的空间开辟有伏笔，末尾的+1是为了输出成字符串，在程序运行的最后会让stack的最后一个位置加上‘\0’,所以此时+1空间正好
//统计字母出现次数 int i; for(i = 0;i< len; i++){ /*s[i]若为a,则s[i]-'a'=0，所表达的意思就是record[0]这个位置 +1,就这样记录下了a的个数，同理，s[i]为b，则s[i]-'a'=1，record[1]++*/ record[s[i]-'a']++; } //遍历字符串s for(i = 0; i<len;i++){ //定义一个标记，标记当前字母是否已经存在在stack里，0表示不存在 int isExist = 0; for(int j = 0; j<=top; j++){ if(s[i] == stack[j]){ isExist = 1; break; } } }
给字符元素标记，标记与栈中相同时就把它的record移除一位，然后若不存在于栈中，就进行while循环给它找出合适的位置（字典序最小）
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--; } top++; stack[top] = s[i]; } } //此时stack只是一个字符数组，要变成字符串还要进行如下操作 stack[++top] = '\0'; return stack;
附上leetcode运行结果，可能是卡bug了，不应该是0ms哈哈
完整代码如下：
#include <stdio.h> #include <stdlib.h> char *removeDuplicateLetters(char *s){ /*s为空，长度为0；s长度为1，直接输出*/ if(s ==NULL || strlen(s) == 0){ return ""; } if(strlen(s) == 1){ return s; } //写两个数组，一个record一个stack char record[26] = {0}; int len = (int)strlen(s); //先看字符串长度是多少 //申请一个空间，指向字符数组 char *stack = (char *)malloc(len * sizeof(char)+1); //对stack赋初值 memset(stack, 0, len * sizeof(char)+1); int top = -1; //统计字母出现次数 int i; for(i = 0;i< len; i++){ /*s[i]若为a,则s[i]-'a'=0，所表达的意思就是record[0]这个位置 +1,就这样记录下了a的个数，同理，s[i]为b，则s[i]-'a'=1，record[1]++*/ record[s[i]-'a']++; } //遍历字符串s for(i = 0; i<len;i++){ //定义一个标记，标记当前字母是否已经存在在stack里，0表示不存在 int isExist = 0; for(int j = 0; j<=top; j++){ if(s[i] == stack[j]){ isExist = 1; break; } } 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--; } top++; stack[top] = s[i]; } } //此时stack只是一个字符数组，要变成字符串还要进行如下操作 stack[++top] = '\0'; return stack; } int main(int argc,const char * argv[]){ system("pause"); return 0; }
