Re: [閒聊] 每日LeetCode

[pandix (麵包屌)]

899. Orderly Queue

龍大拿到了一組字串，他每次可以從前 k 個字元挑一個移到字串末，並且可以操作無限次

龍大希望這個字串的字典序越小越好，如果太大的話可能會有人一直討論他

為了龍大的心理健康，請你幫他找出這個最小字典序的字串。


Example 1:
Input: s = "cba", k = 1
Output: "acb"

可以由 cba->bac->acb 得到


Example 2:
Input: s = "baaca", k = 3
Output: "aaabc"

可以由 baaca->aacab->aaabc 得到


思路:

1.先從簡單版本開始想 如果 k=1  每次只能換第一個字元 可能性就只有 len(s) 種

就掃一次看誰最小就好


2.如果 k=2 可能性就多很多了 因為操作不限次數 可以想一下操作可以做到什麼地步?

有沒有辦法只交換任意相鄰兩個字元的位置 如果可以其實就能 bubble sort

考慮 1234ab5678 如果要交換 ab

可以先把1234依序換到最後: ab56781234

接著換 a56781234b -> 56781234ba -> 1234ba5678

所以 k=2 就足以交換任意相鄰字元的位置 也等同於能做到任意排列

最小的字典序字串只要直接 sort 就能得到


3.Python code:

class Solution:
    def orderlyQueue(self, s: str, k: int) -> str:
        if k > 1:
            return ''.join(sorted(s))
        return min([s[i:]+s[:i] for i in range(len(s))])


--

蛤?

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.251.193.176 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1667701082.A.829.html
推 pomelotea: 靠北
→ NTUEE2CS: B03
推 itoumashiro: 笑死
推 Rushia: 大師
推 NTHUlagka: 大師好強