实验室暑假学习第六周算法总结

古城微笑少年丶 2022-11-28 13:35 182阅读 0赞

## LeetCode 316. 去除重复字母 ##

**难度** 困难

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

**示例1**

输入: "bcabc"
    输出: "abc"

**示例2**

输入: "cbacdcbc"
    输出: "acdb"

--------------------

**解法** 贪心+栈  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NTU0MDEw_size_16_color_FFFFFF_t_70_pic_center]

语言：C

char * removeDuplicateLetters(char* s) { 
        // 两种特殊情况，字符串为空或长度为0，以及字符串长度为1
        if (s == NULL || strlen(s) == 0)
            return "";
        if (strlen(s) == 1)
            return s;
    
        // 记录每个字母在字符串中出现的次数
        int len = (int)strlen(s);
        int flag[26] = { 0};
        for (int i = 0; i < len; i++)
            flag[s[i] - 'a']++;
    
        // 初始化栈以及栈顶指针
        // 分配sizeof(char) * (len + 1)的空间，用于最后存放'\0'
        char* stack = (char*)malloc(sizeof(char) * (len + 1));
        int top = -1;
    
        // 对栈的相关操作
        int exist;
        for (int i = 0; i < len; i++) { 
            exist = 0;
            for (int j = 0; j < top + 1; j++) { 
                if (s[i] == stack[j]) { 
                    exist = 1;
                    break;
                }
            }
            if (exist) { 
                flag[s[i] - 'a']--;
            } else { 
                // 如果栈顶字符比当前字符大，并且后边还会出现，出栈
                while (top > -1 && stack[top] > s[i] && flag[stack[top] - 'a'] > 1) { 
                    flag[stack[top] - 'a']--;
                    top--;
                }
                // 否则入栈
                top++;
                stack[top] = s[i];
            }
        }
    
        // 在栈顶添加'\0'
        top++;
        stack[top] = '\0';
    
        return stack;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NTU0MDEw_size_16_color_FFFFFF_t_70_pic_center]: /images/20221124/850d1a335f3d434fb01d9a0e30792e22.png