博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
Leetcode之Remove Duplicate Letters
阅读量:2342 次
发布时间:2019-05-10

本文共 3128 字,大约阅读时间需要 10 分钟。

题目描述如下:

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"

这道题让我们移除重复字母,使得每个字符只能出现一次,而且结果要按字母顺序排,前提是不能打乱其原本的相对位置。

分析

方法一

这道题可以采用Greedy的思想,因为最后想要的结果是最小值,所以我们在满足要求的情况下不断append最小的字符, 最后便可得到最小的字符串.我们可以用一个数组记录每个字符出现的次数,用一个指针从左到右扫找当前最小字符,过程中减少对应字符次数, 找的过程中终止条件是发现某个字符次数等于0,因为继续扫的话最终结果很有可能缺那个字符.

java代码:

public class Solution {    public String removeDuplicateLetters(String s) {        if (s == null ||s.length() == 0)            return s;                    // 记录每个字符出现的次数            int[] cnt = new int[26];        for (int i = 0; i < s.length(); i++) {            cnt[s.charAt(i) - 'a']++;        }                // 找出当前最小字符        int pos = 0;        for (int i = 0; i < s.length(); i++) {            if (s.charAt(i) < s.charAt(pos))                pos = i;                        // 避免无字符可用            if (--cnt[s.charAt(i) - 'a'] == 0)                break;        }                // 除去字符串中已经append的字符的所有重复值        return s.charAt(pos) + removeDuplicateLetters(s.substring(pos + 1).replaceAll("" + s.charAt(pos), ""));    }}

方法二

其实跟上个方法差不多,但是可以优化下,用stack的话,最多每个字符过两遍就可以了。读字符的过程中,把字符存到stack里,当发现stack之前存的字符中比当前字符大而且频率还大于0就可以把那个字符pop出去。类似这种题目都可以用stack解决。基本思想就是在一定的限制条件下pop出比当前选择差的元素

java代码:

public class Solution {    public String removeDuplicateLetters(String s) {        int[] freqs = new int[26];                // 统计字符频率        for (int i = 0; i < s.length(); i++) {            freqs[s.charAt(i)]++;        }        boolean[] visited = new boolean[26]; // 用来标记存在stack里的字符        Deque
q = new ArrayDeque<>(); for (int i = 0; i < s.length(); i++) { char c = s.charAt(i); freqs[c]--; if (visited[c]) continue; // pop出stack当中比当前字符大但后面还存在的的字符, while (!q.isEmpty() && q.peek() > c && freqs[q.peek()] > 0) { visited[q.pop()] = false; } q.push(c); visited[c] = true; } StringBuilder sb = new StringBuilder(); for (char c : q) { sb.append(c); } return sb.reverse().toString(); }}

Python代码:
class Solution(object):    def removeDuplicateLetters(self, s):        """        :type s: str        :rtype: str        """        if s == None or len(s) <= 1:            return s                visit = [0] * 26        count = [0] * 26        length = len(s)                for i in range(length):            count[ord(s[i]) - 97] += 1                result = ""                for i in range(length):            c = s[i]            index = ord(c) - 97            count[index] -= 1            if visit[index] == 1:                continue            while len(result) != 0 and result[-1] > c and count[ord(result[-1]) - 97] > 0:                visit[ord(result[-1]) - 97] = 0                result = result[:len(result) - 1]            result = result + s[i]            visit[index] = 1                return result

转载地址:http://dmbvb.baihongyu.com/

你可能感兴趣的文章
扩展程序运行时的库路径
查看>>
【CUDA并行程序设计系列(4)】CUDA内存
查看>>
CPU、GPU、CUDA,CuDNN 简介
查看>>
U-boot如何引导Linux内核启动?
查看>>
程序各个段text,data,bss,stack,heap
查看>>
如何利用ROS MoveIt快速搭建机器人运动规划平台?
查看>>
catkin_make &amp;amp;catkin build
查看>>
Camera和IMU的标定过程之kalibr 源码编译
查看>>
在ubuntu下安装python的numpy和scipy模块
查看>>
Ubuntu下apt-get与pip安装命令的区别
查看>>
linux CMakeLists.txt 语法
查看>>
cmake 简介
查看>>
CMake学习笔记(1)——用CMake编译一个hello world程序
查看>>
cmake使用总结---工程主目录CMakeList文件编写
查看>>
CMake学习之路
查看>>
cmake学习笔记6-catkin的CmakeList.txt讲解
查看>>
cmake手册详解
查看>>
Maplab框架介绍(一)
查看>>
Maplab开源VI-SLAM框架介绍
查看>>
maplab(1):安装
查看>>