美文网首页
有序序列

有序序列

作者: 天涯的尽头s风沙 | 来源:发表于2019-09-16 18:40 被阅读0次

    给出了一个由小写字母组成的字符串 S。然后,我们可以进行任意次数的移动。
    在每次移动中,我们选择前 K 个字母中的一个(从左侧开始),将其从原位置移除,并放置在字符串的末尾。
    返回我们在任意次数的移动之后可以拥有的按字典顺序排列的最小字符串。


    image.png

    首先,这道题可以根据case得出两种情况

    1. cba这种情况,k=1,那么一次只能移动最前面的字符,没有考虑的余地,所以我们只需求出没转移一次前面的字符,然后作比较,找出字典序最小的字符串,需要转移len-1次,可以把s后面在拼接一个s,逐步比较。
      2.aaec//它最小的状态为aace
      当k=2时,aaec/aeca/ecaa/eaac/aace
      由此可见当k>=2时,我们可以把任意字符换到任何位置。
      st.abcddce.第二个c应该在第一个d的前面,
      k = 2,bcddcea/这样每次挪最前面的一个字符,直到可以挪c的时候,dceabcd/deabcdc/deabcdcd/abcdcdde这样c就往前挪了一个位置。所以在做一次就可以把c挪成abccdde,所以发现只要k>=2,就都可以变成字典序最小的字符串。
      具体见以下代码
    
    

    相关文章

      网友评论

          本文标题:有序序列

          本文链接:https://www.haomeiwen.com/subject/jsqfuctx.html