🌟前言
摆烂太久,好久没有更文了,小九和大家一起看看题写写题找回手感吧,也希望这篇文章可以帮助正在寻找解题答案的朋友,你们的支持就是我最大的动力!求三连!求关注呀!
🌟题目
去除重复字母,给你一个仅包含小写字母的字符串,请你去除字符串中重复的字母,使得每个字母只出现一次。需保证返回结果的字典序最小 (要求不能打乱其他字符的相对位置)示例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; }