Re: [閒聊] 每日LeetCode已回收
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
推
11/06 10:21,
3年前
, 1F
11/06 10:21, 1F
→
11/06 10:39,
3年前
, 2F
11/06 10:39, 2F
推
11/06 10:43,
3年前
, 3F
11/06 10:43, 3F
推
11/06 15:06,
3年前
, 4F
11/06 15:06, 4F
推
11/06 19:57,
3年前
, 5F
11/06 19:57, 5F
討論串 (同標題文章)
完整討論串 (本文為第 87 之 719 篇)：