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

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

讓客戶滿意是我們工作的目標(biāo)，不斷超越客戶的期望值來(lái)自于我們對(duì)這個(gè)行業(yè)的熱愛(ài)。我們立志把好的技術(shù)通過(guò)有效、簡(jiǎn)單的方式提供給客戶，將通過(guò)不懈努力成為客戶在信息化領(lǐng)域值得信任、有價(jià)值的長(zhǎng)期合作伙伴，公司提供的服務(wù)項(xiàng)目有：申請(qǐng)域名、虛擬主機(jī)、營(yíng)銷軟件、網(wǎng)站建設(shè)、舞鋼網(wǎng)站維護(hù)、網(wǎng)站推廣。

給出了一個(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]，而沒(méi)有改變其余字符的位置。

3，當(dāng) K > 2 時(shí)，我們可以完成 K = 2 時(shí)的所有操作。

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

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

B，K>1  當(dāng)我們可以交換任意兩個(gè)相鄰的字母后，就可以使用冒泡排序的方法，僅通過(guò)交換相鄰兩個(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í)，如果覺(jué)得文章不錯(cuò)，可以把它分享出去讓更多的人看到吧！

當(dāng)前題目：golang刷leetcode技巧之如何實(shí)現(xiàn)有序隊(duì)列
當(dāng)前鏈接：http://muchs.cn/article26/gjscjg.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供外貿(mào)建站、企業(yè)建站、虛擬主機(jī)、做網(wǎng)站、網(wǎng)站導(dǎo)航、搜索引擎優(yōu)化

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)