golang刷leetcode技巧之如何實(shí)現(xiàn)有序隊(duì)列

這篇文章給大家分享的是有關(guān)golang刷leetcode技巧之如何實(shí)現(xiàn)有序隊(duì)列的內(nèi)容。小編覺得挺實(shí)用的，因此分享給大家做個(gè)參考，一起跟隨小編過來看看吧。

給出了一個(gè)由小寫字母組成的字符串 S。然后，我們可以進(jìn)行任意次數(shù)的移動(dòng)。

在每次移動(dòng)中，我們選擇前 K 個(gè)字母中的一個(gè)（從左側(cè)開始），將其從原位置移除，并放置在字符串的末尾。

返回我們?cè)谌我獯螖?shù)的移動(dòng)之后可以擁有的按字典順序排列的最小字符串。

示例 1：

輸入：S = "cba", K = 1輸出："acb"解釋：在第一步中，我們將第一個(gè)字符（“c”）移動(dòng)到最后，獲得字符串 “bac”。在第二步中，我們將第一個(gè)字符（“b”）移動(dòng)到最后，獲得最終結(jié)果 “acb”。

示例 2：

輸入：S = "baaca", K = 3輸出："aaabc"解釋：在第一步中，我們將第一個(gè)字符（“b”）移動(dòng)到最后，獲得字符串 “aacab”。在第二步中，我們將第三個(gè)字符（“c”）移動(dòng)到最后，獲得最終結(jié)果 “aaabc”。

提示：

1 <= K <= S.length <= 1000

S 只由小寫字母組成。

解題思路

1，當(dāng) K = 1 時(shí)，每次操作只能將第一個(gè)字符移動(dòng)到末尾，因此字符串 S 可以看成一個(gè)頭尾相連的環(huán)。如果 S 的長(zhǎng)度為 NN，我們只需要找出這 NN 個(gè)位置中字典序最小的字符串即可。

2，當(dāng) K = 2 時(shí)，可以發(fā)現(xiàn)，我們能夠交換字符串中任意兩個(gè)相鄰的字母。具體地，設(shè)字符串 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，當(dāng) K > 2 時(shí)，我們可以完成 K = 2 時(shí)的所有操作。

4，上述問題轉(zhuǎn)化成兩個(gè)子問題

A，K==1 我們從每一個(gè)位置剪切然后拼接字符串，求字典序最小的字符串。

B，K>1  當(dāng)我們可以交換任意兩個(gè)相鄰的字母后，就可以使用冒泡排序的方法，僅通過交換相鄰兩個(gè)字母，使得字符串變得有序。因此當(dāng) K >= 2 時(shí)，我們可以將字符串移動(dòng)得到最小的字典序。

代碼

func orderlyQueue(S string, K int) string {    if K==1{        s:=S       for 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}

感謝各位的閱讀！關(guān)于“golang刷leetcode技巧之如何實(shí)現(xiàn)有序隊(duì)列”這篇文章就分享到這里了，希望以上內(nèi)容可以對(duì)大家有一定的幫助，讓大家可以學(xué)到更多知識(shí)，如果覺得文章不錯(cuò)，可以把它分享出去讓更多的人看到吧！