本文主要是介绍Leetcode--Java--316. 去除重复字母,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题目描述
给你一个字符串 s ,请你去除字符串中重复的字母,使得每个字母只出现一次。需保证 返回结果的字典序最小(要求不能打乱其他字符的相对位置)。
样例描述
示例 1:输入:s = "bcabc"
输出:"abc"
示例 2:输入:s = "cbacdcbc"
输出:"acdb"
思路
贪心 + 单调栈思想
- 用一个字符串来记录答案,每次判断答案的最后一个字符是否大于原串当前字符,如果大于并且该字符在原串后面还出现过,就可以不断删除。然后将原串当前字符加入到答案。
- 答案字符串本质上是一个栈结果,不断在一端进行插入删除操作。
- 用一个哈希表记录是否在答案出现过,用另一个哈希表记录某字母最后出现的位置。
- 数组版和哈希表版,其实都很复杂,注意哈希表在判断是否出现过的时候,首先要判断是否存在,不然会有空指针错误。
代码
class Solution {public String removeDuplicateLetters(String s) {String res = "";boolean inRes[] = new boolean[26]; //是否在答案中出现过int lastPos[] = new int[26]; //最后出现的位置int n = s.length();for (int i = 0; i < n; i
这篇关于Leetcode--Java--316. 去除重复字母的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!