編輯：因為我不清楚我只是要復制問題（我的答案是代碼）。
給定一個字串，通過交換相鄰的 'a' 和 'b' 字符或相鄰的 'b' 和 'c' 字符任意次數來獲得按字母順序排列的最小字串。
示例：s = "abaacbac" 通過應用以下操作獲得按字母順序排列的最小可能字串：
'c' 廣告索引 5 與 'b' 廣告索引 6 交換，因此“abaacbac”變為“abaabcac”。
然后將索引 2 處的 'b' 與索引 3 處的 'a' 交換，因此 'abaabcac' 變為 "aababac"。
最后將索引 3 處的“b”與索引 4 處的“a”交換，以獲得最終答案“aaabbcac”。
另一個例子：輸入baacba 輸出aabbca
這是我的代碼
def smallestString(s):
# Write your code here
cons = 10 ** 5
if len(s) > cons:
return False
s = list(s)
counter = 0
while counter < len(s):
for i in range(len(s)):
if i 1 < len(s):
if s[i] == "b" and s[i 1] == "a":
s[i], s[i 1] = s[i 1], s[i]
elif s[i] == "a" and s[i 1] == "b" and "c" in s[:i]:
s[i 1], s[i] = s[i], s[i 1]
elif s[i] == "c" and s[i 1] == "b":
s[i], s[i 1] = s[i 1], s[i]
counter = 1
return ''.join(s)
無論如何，我優化了我的代碼，以便它適用于非常大的輸入（最多 10 秒或超時）。ps對不同方法/修改的任何建議也很好
uj5u.com熱心網友回復：
我假設a,b并且c是唯一的字符（我會在最后評論）。
本質上，bs 可以自由移動，但as 和cs 不能相對移動。因此，一個簡單的線性時間解決方案是洗掉所有bs，而是將它們放在as 開頭的 s 之后但在第一個c（如果有的話）之前。
例如： a b aac b ac → aaacac → aaa bb cac
兩種實作：
import re
def smallestString(s):
bs = 'b' * s.count('b')
s = s.replace('b', '')
return re.sub('(?=c|$)', bs, s, count=1)
def smallestString(s):
bs = 'b' * s.count('b')
s = s.replace('b', '')
c = s.find('c')
return s bs if c < 0 else s[:c] bs s[c:]
對于長度為 1000 的隨機字串，我得到如下時間：
542.781 ms yours
0.038 ms my regex-solution
0.022 ms my find-solution
對你來說，隨機可能甚至不是最壞的情況，我得再考慮一下。
關于我假設字串僅包含a,b和c字符：您的任務描述使它看起來像這樣，并且可能由 LeetCode 的實際規范保證，因為允許其他字符只會使它變得更丑，而不是更難或更有趣。您只需找到a/ b/c字符的條紋并解決上述每個這樣的條紋。
uj5u.com熱心網友回復：
因為我不能完全說出你在這里要做什么，所以我需要指出你擁有的兩個回圈
while counter < len(s):
是
for i in range(len(s)):
完全相同的。所以基本上你在 for 回圈中做“邏輯位” len(s)。這可能一直是你的意圖，但似乎是一種奇怪的方式。而是洗掉while回圈和counter變數，看看你是否得到了想要的結果。
否則可能會修改代碼，以便您可以在一個回圈中完成所有操作（for i in range(len(s) ** 2)例如。第一個if i 1 < len(s)陳述句也是不必要的，可能是 for 回圈宣告的一部分（range(len(s) - 1)）
轉載請註明出處，本文鏈接：https://www.uj5u.com/net/430974.html
上一篇：排除ntile()中的例外值