leetcode Remove Duplicate Letters

leetcode Remove Duplicate Letters

Given a string which contains only lowercase letters, remove duplicate letters so that every letter appear once and only once. You must make sure your result is the smallest in lexicographical order among all possible results.

Example:

Given "bcabc"
Return "abc"

Given "cbacdcbc"
Return "acdb"

传送门:leetcode Remove Duplicate Letters

题意: 给定一个全部由小写组成的字符串,要求删除它重复的元素,使得字典序最小

思路:

方法一

用栈。

首先对字符串出现的个数进行统计。

然后对字符串扫描,每遇到一个字符串,判断其是否在栈中,如果在则跳过。(计数 – 1)

如果不在栈中,和栈顶的元素判断,要是当前栈顶的元素比较大而且cnt不为0(也就是说之后还有这个元素),就把栈顶弹出。然后把当前的元素入栈。

 

Python 52ms

 

方法二

和这个差不多https://leetcode.com/discuss/73777/easy-to-understand-iterative-java-solution

找每个字符出现的最后的位置, 取其中最小的作为end。(这个元素必须在end或者end以前出现,否则就没了= =)

从start(一开始设为0)枚举到end,最小的那个作为当前的字符。如此循环。

如:dcbacdcd

最后出现的位置:a:3 , b: 2, c : 6, d: 7

于是0~2中最小的元素为b

接着3~3 为a

接着 4~6 为c

接着 7~7 为d

所以为bacd

Python 108ms

 

方法三

每次对每个字母出现的次数进行统计 cnt

然后扫描数组,找最小的字符min_c,并对于经过的每一个元素 cnt – 1 ,直到数组扫描完毕或者遇到cnt = 0的(cnt = 0说明后面没有这个元素了,不能继续,否则就丢掉了这个元素)

然后把字符串s中 min_c 替换成空 如此循环。

Python 260ms

 

本博客若无特殊说明则由 hrwhisper 原创发布
转载请点名出处:细语呢喃 > leetcode Remove Duplicate Letters
本文地址:https://www.hrwhisper.me/leetcode-remove-duplicate-letters/

打赏一杯咖啡钱呗

Leetcode , , . permalink.

5 thoughts on “leetcode Remove Duplicate Letters

  1. 大神,一直在看你的blog,代码写的真好。
    想问个问题 python code里面是不是应该最再把栈里的元素放在res里面。而不是每一步都加到res上面

    for c in s:
    index = ord(c) – 97
    cnt[index] -= 1
    if vis[index]: continue
    while ans and ans[-1] > c and cnt[ord(ans[-1]) – 97]:
    vis[ord(ans.pop()) – 97] = False
    ans.append(c)
    vis[index] = True

Leave a Reply

Your email address will not be published. Required fields are marked *