C 去除字符串中重复字母(LeetCode)

简介: 摆烂太久,好久没有更文了,小九和大家一起看看题写写题找回手感吧,也希望这篇文章可以帮助正在寻找解题答案的朋友,你们的支持就是我最大的动力!求三连!求关注呀!🌟。

🌟前言

摆烂太久,好久没有更文了,小九和大家一起看看题写写题找回手感吧,也希望这篇文章可以帮助正在寻找解题答案的朋友,你们的支持就是我最大的动力!求三连!求关注呀!


🌟题目

去除重复字母,给你一个仅包含小写字母的字符串,请你去除字符串中重复的字母,使得每个字母只出现一次。需保证返回结果的字典序最小 (要求不能打乱其他字符的相对位置)示例1:

输入:"bcabc"

输出:"abc"

示例2:

输入:"cbacdcbc"

输出:"acdb" cbad,bacd,adcb

字典序: apple book

  1. 字典序最小,不能出现打乱字母相对位置;

网络异常,图片无法展示
|

🌟解题前捋清思路

特殊条件

在写代码时要考虑会遇到的特殊情况,例如题目所指的“给你一个仅包含小写字母的字符串”,这个字符串它可能会给一个空字符,或者甚至一个字符,长度为1,这种情况我们就可以不用再进行去重这操作了写代码时,我们也要有这种意识,例如在写链表时,考虑链表为空


记录字母出现频率

用一个数组record记录字符串中字母出现的次数,次数我们遍历一遍字符串即可,因为要统计的是小写字母,而有且只有26个,所以我们的数组定义26个空间即可,record[26]


建字符栈stack

这里的栈呢,本质上就是一个连续的数组,用来模拟栈的思想,但不用完全按照栈的格式去写,我们只需要参考栈的一个特点:“先进后出”,作用:存储去除重复字母的结果,利用栈来正确次序。


遍历字符串

遍历字符串会有一个特殊的地方,那就是当前字符,对其进行判断,在0~top的空间里,判断当前字符是否存在栈中,用一个标记即可

如果已经存在,就让record[s[i]]--,代表去除了一个重复的s[i]位置上对应的字母,表示stack已经有了这个字符,不需要再进行存入又取出,然后继续遍历下一个字符;


网络异常,图片无法展示
|


若不存在,则通过while循环找到正确位置。以bcabc字符串为例,此时的字符a,通过循环,判断栈中元素是否要出栈,找到a的正确位置

判断条件

  1. 栈不能为空top>-1
  2. 栈顶元素要大于遍历到的当前字符  stack[top]>s[i]
  3. 栈顶字符对应的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;
}
相关文章
|
3月前
|
存储 算法
LeetCode第49题字母异位词分组
LeetCode第49题"字母异位词分组"的解题方法,通过将每个字符串的字符排序后作为键存储在HashMap中,有效地将所有字母异位词分组。
LeetCode第49题字母异位词分组
|
16天前
|
JavaScript
力扣3333.找到初始输入字符串Ⅱ
【10月更文挑战第9天】力扣3333.找到初始输入字符串Ⅱ
30 1
|
30天前
|
C++
Leetcode第43题(字符串相乘)
本篇介绍了一种用C++实现的字符串表示的非负整数相乘的方法,通过逆向编号字符串,将乘法运算转化为二维数组的累加过程,最后处理进位并转换为字符串结果,解决了两个大数相乘的问题。
23 9
|
30天前
|
存储
Leetcode第49题(字母异位词分组)
LeetCode第49题要求将字符串数组中的字母异位词分组,可以通过将每个字符串排序后作为键存入哈希表,最后将哈希表中的值添加到结果列表中来实现。
14 1
|
30天前
|
算法
Leetcode第十七题(电话号码的字母组合)
这篇文章介绍了如何使用深度优先搜索(DFS)算法来解决LeetCode第17题——电话号码的字母组合问题,通过递归方法生成所有可能的字母组合。
15 0
Leetcode第十七题(电话号码的字母组合)
|
30天前
|
索引
【LeetCode 11】242.有效的字母异位词
【LeetCode 11】242.有效的字母异位词
13 0
【LeetCode 11】242.有效的字母异位词
|
29天前
|
算法
【LeetCode 52】17.电话号码的字母组合
【LeetCode 52】17.电话号码的字母组合
30 0
|
30天前
|
算法 C++
Leetcode第八题(字符串转换整数(atoi))
这篇文章介绍了LeetCode上第8题“字符串转换整数(atoi)”的解题思路和C++的实现方法,包括处理前导空格、正负号、连续数字字符以及整数溢出的情况。
15 0
|
30天前
【LeetCode 22】459.重复的子字符串
【LeetCode 22】459.重复的子字符串
27 0
|
30天前
【LeetCode 20】151.反转字符串里的单词
【LeetCode 20】151.反转字符串里的单词
18 0