- 921. Minimum Add to Make Parentheses Valid 使括号有效的最少添加
- 915. Partition Array into Disjoint Intervals 分割数组
- 932. Beautiful Array 漂亮数组
- 940. Distinct Subsequences II 不同的子序列 II
题目地址:https://leetcode.com/problems/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 1:
Input: "bcabc"
Output: "abc"
Example 2:
Input: "cbacdcbc"
Output: "acdb"
从一组字符串中取字符,使得生成结果中每个字符必须出现一次而且只出现一次,并且要求所得结果是字符串顺序最小的。
这个题的难点在于使得结果是字符串顺序最小。解题思路也是围绕这个展开。
先顺一下思路,首先,每个字符都必须要出现一次,那么当这个字符只有一次机会的时候,必须添加到结果字符串结尾中去,反之,如果这个字符的次数没有降为0,即后面还有机会,那么可以先把优先级高的放进来,把这个字符放到后面再处理。所以,我们可以使用一个栈,有点类似单调递增栈的意思,但其实并不是单调栈。我们的思路就是把还可以放到后面的字符弹出栈,留着以后处理,字符序小的插入到对应的位置。
首先,为了知道每个字符出现了多少次,必须做一次次数统计,这个步骤大家都是知道的。
然后,需要借助一个栈来实现字符串构造的操作。具体操作如下:
从输入字符串中逐个读取字符c,并把c的字符统计减一。
1、 如果当前字符c已经在栈里面出现,那么跳过;
2、 如果当前字符c在栈里面,那么:
1、 如果当前字符c小于栈顶,并且栈顶元素有剩余(后面还能再添加进来),则出栈栈顶,标记栈顶不在栈中重复该操作直到栈顶元素不满足条件或者栈为空;
2、 入栈字符c,并且标记c已经在栈中;
python代码如下:
class Solution(object):
def removeDuplicateLetters(self, s):
"""
:type s: str
:rtype: str
"""
count = collections.Counter(s)
stack = []
visited = collections.defaultdict(bool)
for c in s:
count[c] -= 1
if visited[c]:
continue
while stack and count[stack[-1]] and stack[-1] > c:
visited[stack[-1]] = False
stack.pop()
visited[c] = True
stack.append(c)
return "".join(stack)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
C++代码如下:
class Solution {
public:
string removeDuplicateLetters(string s) {
unordered_map<char, bool> visited;
unordered_map<char, int> counter;
string res = "";
for (char c : s) ++counter[c];
for (char c : s) {
--counter[c];
if (visited[c]) {
continue;
}
while (!res.empty() && counter[res.back()] && c < res.back()) {
visited[res.back()] = false;
res.pop_back();
}
res += c;
visited[c] = true;
}
return res;
}
};
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
参考资料:
https://www.jiuzhang.com/solution/remove-duplicate-letters/ https://www.jianshu.com/p/8d75723657ad https://blog.csdn.net/u012050154/article/details/51604942 http://www.cnblogs.com/grandyang/p/5085379.html
2022
DDKK.COM 弟弟快看-教程,程序员编程资料站,版权归原作者所有
本文经作者:负雪明烛 授权发布,任何组织或个人未经作者授权不得转发
我正在使用 .remove() 方法删除一个 html 元素,同时对于这个元素,我有一个事件处理程序,但它没有被触发。为什么会这样呢?这是jsFiddle和代码:HTML Delete I'm goi
所以我尝试从另一篇文章中编写此代码: while(fscanf(orderFile," %49[^;];%d; %49[^\n]",fileName,&seconds,timeValue) == 3)
我正在阅读 Nicolai M.Josuttis 撰写的“The C++ STL. A Tutorial and References”一书,在专门介绍 STL 算法的一章中,作者陈述如下:如果你调用
是否有一种简单的机制来确定 DownloadManager remove() 何时完成,因为它看起来是部分异步的。该函数几乎立即返回下载表中已删除的条目计数,但实际的文件系统管理似乎被插入了某个后台线
我愿意: getActionBarToolbar().removeView(logoImage); getActionBarToolbar().addView(logoImage, lp); 我得到:
我有类(class)评论一对多关系。在类(class)表中有 id 和 title 列。在 Review 表中,有 id、comment 和 course_id,其中“course_id”作为指向类(
我在 stackoverflow 上阅读了不同的答案,了解如何销毁 wigdet/jQueryObject 并取消绑定(bind)其上的所有事件。 这就是我的想法。 $('选择器').remove()
我有一个由一个线程填充的 byte[] 列表,然后我有另一个线程正在从该列表中读取并通过网络发送项目。 每次我读取线程 2 中的项目时,我都想将其从内存中清除。但是因为我正在使用线程,如果我使用 .r
就算法而言,从连续数组中删除一组元素可以分两部分有效地完成。 将所有不删除的元素移到数组的前面。 将数组标记得更小。 这可以在 C++ 中使用 erase-remove 习惯用法来完成。 vector
我尝试删除包含在 map 中渲染的制造商的 View 。当我单击按钮时,事件 click .ver 被激活,但没有任何反应,并且我收到以下错误:Uncaught TypeError: undefine
场景: 使用 jQuery 2.0.1 构建的应用程序。 您的团队更喜欢原生 JavaScript。 选项有jQuery .remove()和 ChildNode.remove() . 您需要删除节点
最初我有一个像这样的删除功能: function ViewWorkflowDetail(btn, workflowId) { $("#workflowDetailPanel").remov
我正在编写 C++ 代码来解决 Leetcode 中的这个问题:https://leetcode.com/problems/remove-element/ Given an array nums an
根据太阳, "Iterator.remove is the only safe way to modify a collection during iteration; the behavior is
众所周知,从 std::vector 中完全删除所需项的一种好方法是 erase-remove idiom . 如以上链接中所述(截至本文发布日期),在代码中,erase-remove 习惯用法如下所
我在 HashSet 上调用 Iterator.remove() 时遇到问题。 我有一组带有时间戳的对象。在将新项目添加到集合之前,我会遍历集合,识别该数据对象的旧版本并将其删除(在添加新对象之前)。
这段代码: Collection col = new ArrayList(); col.add("a"); col.add("b"); col.add("c");
我试图通过在下面输入来卸载 conda 环境基础, conda env remove -n base 正如我所建议的那样,我尝试通过使用来停用基地 conda deactivate base 我再次尝
我已经对我的 IOS 应用程序进行了质量扫描分析。我收到以下警告: The binary has Runpath Search Path (@rpath) set. In certain cases
这个问题已经有答案了: Properly removing an Integer from a List (8 个回答) 已关闭 4 年前。 我是java新手。看起来很简单,但我不明白为什么会发生这种
我是一名优秀的程序员,十分优秀!