資料結構
網路
關係型資料庫管理系統
作業系統
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 次瀏覽
廣告