新手区 菜鸡刷算法之字典序排序

墨妖 · 2022年03月22日 · 1735 次阅读

大佬们看看有啥问题或者有其他思路

题目:最多只互换一次,使得字符串字典序最小

示例:baca = > aacb

思路:找每个元素后面的,最后一个最小元素位置,互换即可

str = 'baca'
str_list = list(str)

for i in range(len(str_list)):
    #在每个元素的后面找最小的元素
    min_str = min(str_list[i:])
    #找最小元素的位置,要取靠后的,所以需要从后往前找
    min_index =  str_list[::-1].index(min_str)
    min_index = len(str_list)-min_index-1

    #比最小元素大,则互换位置
    if str_list[i] > min_str:
        #互换位置,只换一次
        str_list[i],str_list[min_index] = str_list[min_index],str_list[i]
        #如果不中止一直换,就得到字典序最小的,但那可以用sorted()搞定
        break

print("".join(str_list))


暂无回复。
需要 登录 后方可回复, 如果你还没有账号请点击这里 注册