golang刷leetcode技巧之如何实现有序队列

这篇文章给大家分享的是有关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:=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}

感谢各位的阅读！关于“golang刷leetcode技巧之如何实现有序队列”这篇文章就分享到这里了，希望以上内容可以对大家有一定的帮助，让大家可以学到更多知识，如果觉得文章不错，可以把它分享出去让更多的人看到吧！