数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究Python 中不同字符的最小子序列
假设我们有一个文本，我们需要找到包含文本中所有不同字符且按字典序最小的子序列。因此，如果输入类似于“cdadabcc”，则输出将为“adbc”。
为了解决这个问题，我们将遵循以下步骤：
- 定义一个栈 st，两个映射 last_o 和 considered，它们最初为空
- 对于范围从文本长度 - 1 到 0 的 i
- 如果 text[i] 不存在于 last_o 中：
- last_o[text[i]] := i
- considered[text[i]] := false
- i := 0
- 当 i < 文本长度时
- 如果栈为空
- 将 text[i] 推入栈
- considered[text[i]] := true
- 将 i 增加 1
- 否则栈顶 > text[i] 且 considered[text[i]] 为假
- 如果 last_o[栈顶] > i
- considered[栈顶元素] := false
- 从栈中弹出
- 否则
- considered[tex[i]] = true
- 将 text[i] 插入栈
- 将 i 增加 1
- 如果 last_o[栈顶] > i
- 否则当栈顶元素 < temp[i] 且 considered[text[i]] = false 时
- 将 text[i] 插入栈
- considered[text[i]] := true
- 将 i 增加 1
- 否则将 i 增加 1
- 如果栈为空
- 如果 text[i] 不存在于 last_o 中：
- 以反向顺序返回栈中所有元素作为字符串
让我们看看下面的实现以更好地理解：
示例
class Solution(object):
def smallestSubsequence(self, text):
"""
:type text: str
:rtype: str
"""
stack = []
last_o = {}
considered = {}
for i in range(len(text)-1,-1,-1):
if text[i] not in last_o:
last_o[text[i]] = i
considered[text[i]] = False
print(last_o)
i = 0
while i < len(text):
print(stack,i,text[i])
if len(stack) == 0:
stack.append(text[i])
considered[text[i]] = True
i+=1
elif stack[-1]>text[i] and considered[text[i]] == False:
if last_o[stack[-1]]>i:
considered[stack[-1]]=False
stack.pop()
else:
considered[text[i]] = True
stack.append(text[i])
i+=1
elif stack[-1]<text[i] and considered[text[i]] == False:
stack.append(text[i])
considered[text[i]] = True
i+=1
else:
i+=1
return "".join(i for i in stack)输入
"cdadabcc"
输出
"adbc"
更新于: 2020年3月5日
142 次浏览
广告