溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
這篇文章給大家分享的是有關golang刷leetcode技巧之如何實現有序隊列的內容。小編覺得挺實用的，因此分享給大家做個參考，一起跟隨小編過來看看吧。
給出了一個由小寫字母組成的字符串 S。然后，我們可以進行任意次數的移動。
在每次移動中，我們選擇前 K 個字母中的一個（從左側開始），將其從原位置移除，并放置在字符串的末尾。
返回我們在任意次數的移動之后可以擁有的按字典順序排列的最小字符串。
示例 1：
輸入：S = "cba", K = 1輸出："acb"解釋：在第一步中，我們將第一個字符（“c”）移動到最后，獲得字符串 “bac”。在第二步中，我們將第一個字符（“b”）移動到最后，獲得最終結果 “acb”。
示例 2：
輸入：S = "baaca", K = 3輸出："aaabc"解釋：在第一步中，我們將第一個字符（“b”）移動到最后，獲得字符串 “aacab”。在第二步中，我們將第三個字符（“c”）移動到最后，獲得最終結果 “aaabc”。
提示：
1 <= K <= S.length <= 1000
S 只由小寫字母組成。
解題思路
1，當 K = 1 時，每次操作只能將第一個字符移動到末尾，因此字符串 S 可以看成一個頭尾相連的環。如果 S 的長度為 NN，我們只需要找出這 NN 個位置中字典序最小的字符串即可。
2，當 K = 2 時，可以發現，我們能夠交換字符串中任意兩個相鄰的字母。具體地，設字符串 S 為 S[1], S[2], ..., S[i], S[i + 1], ..., S[N]，我們需要交換 S[i] 和 S[j]。首先我們依次將 S[i] 之前的所有字符依次移到末尾，得到
S[i], S[i + 1], ..., S[N], S[1], S[2], ..., S[i - 1]
隨后我們先將 S[i + 1] 移到末尾，再將 S[i] 移到末尾，得到
S[i + 2], ..., S[N], S[1], S[2], ..., S[i - 1], S[i + 1], S[i]
最后將 S[i + 1] 之后的所有字符依次移到末尾，得到
S[1], S[2], ..., S[i - 1], S[i + 1], S[i], S[i + 2], ..., S[N]
這樣就交換了 S[i] 和 S[i + 1]，而沒有改變其余字符的位置。
3，當 K > 2 時，我們可以完成 K = 2 時的所有操作。
4，上述問題轉化成兩個子問題
A，K==1 我們從每一個位置剪切然后拼接字符串，求字典序最小的字符串。
B，K>1 當我們可以交換任意兩個相鄰的字母后，就可以使用冒泡排序的方法，僅通過交換相鄰兩個字母，使得字符串變得有序。因此當 K >= 2 時，我們可以將字符串移動得到最小的字典序。
代碼
func orderlyQueue(S string, K int) string {if K==1{s:=Sfor i:=0;i<len(S);i++{tmp:=S[i:]+S[:i]//fmt.Println(s,tmp,large(s,tmp))if large(s,tmp){s=tmp}}return s}return sort(S)}func sort(s string)string{sa:=[]byte(s)for i:=0;i<len(s);i++{for j:=i;j<len(s);j++{if sa[i]>sa[j]{sa[i],sa[j]=sa[j],sa[i]}}}return string(sa)}func large(s1,s2 string)bool{for i:=0;i<len(s1);i++{if s1[i]>s2[i]{return true}if s1[i]<s2[i]{return false}}return false}
感謝各位的閱讀！關于“golang刷leetcode技巧之如何實現有序隊列”這篇文章就分享到這里了，希望以上內容可以對大家有一定的幫助，讓大家可以學到更多知識，如果覺得文章不錯，可以把它分享出去讓更多的人看到吧！
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
