Leetcode 1370:上升下降字符串(超详细的解法!!!)
发布日期:2021-06-29 15:58:44
浏览次数:2
分类:技术文章
本文共 1446 字,大约阅读时间需要 4 分钟。
给你一个字符串 s
,请你根据下面的算法重新构造字符串:
- 从
s
中选出 最小 的字符,将它 接在 结果字符串的后面。 - 从
s
剩余字符中选出 最小 的字符,且该字符比上一个添加的字符大,将它 接在 结果字符串后面。 - 重复步骤 2 ,直到你没法从
s
中选择字符。 - 从
s
中选出 最大 的字符,将它 接在 结果字符串的后面。 - 从
s
剩余字符中选出 最大 的字符,且该字符比上一个添加的字符小,将它 接在 结果字符串后面。 - 重复步骤 5 ,直到你没法从
s
中选择字符。 - 重复步骤 1 到 6 ,直到
s
中所有字符都已经被选过。
在任何一步中,如果最小或者最大字符不止一个 ,你可以选择其中任意一个,并将其添加到结果字符串。
请你返回将 s
中字符重新排序后的 结果字符串 。
示例 1:
输入:s = "aaaabbbbcccc"输出:"abccbaabccba"解释:第一轮的步骤 1,2,3 后,结果字符串为 result = "abc"第一轮的步骤 4,5,6 后,结果字符串为 result = "abccba"第一轮结束,现在 s = "aabbcc" ,我们再次回到步骤 1第二轮的步骤 1,2,3 后,结果字符串为 result = "abccbaabc"第二轮的步骤 4,5,6 后,结果字符串为 result = "abccbaabccba"
示例 2:
输入:s = "rat"输出:"art"解释:单词 "rat" 在上述算法重排序以后变成 "art"
示例 3:
输入:s = "leetcode"输出:"cdelotee"
示例 4:
输入:s = "ggggggg"输出:"ggggggg"
示例 5:
输入:s = "spo"输出:"ops"
提示:
1 <= s.length <= 500
s
只包含小写英文字母。
解题思路
可以先统计s
中每个字符的个数(采用字典cnt
存储),然后对s
中出现的所有字符进行排序(也就是对cnt.keys()
排序)。接着正向遍历cnt.keys()
一遍,再反向遍历cnt.keys()
一遍。遍历的过程中,如果cnt[c]
(c
表示遍历到的字符)大于0
,表示当前字符可以使用,添加到结果中去。重复此操作直到结果字符串的长度和s
一致时返回结果。
class Solution: def sortString(self, s: str) -> str: cnt, res = collections.Counter(s), [] st = sorted(cnt.keys()) while len(res) < len(s): for c in st: if cnt[c]: res.append(c) cnt[c] -= 1 for c in st[::-1]: if cnt[c]: res.append(c) cnt[c] -= 1 return ''.join(res)
我将该问题的其他语言版本添加到了我的
如有问题,希望大家指出!!!
转载地址:https://coordinate.blog.csdn.net/article/details/104747990 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
留言是一种美德,欢迎回访!
[***.207.175.100]2024年04月19日 05时58分12秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
Django实战---商城购物车的增删改、显示和合并购物车
2019-04-29
Django项目实战----添加支付宝支付
2019-04-29
DRF框架---前言(简单使用)
2019-04-29
字符串外面是b“ “的转换 -亲测有效
2019-04-29
单通道和多通道卷积
2019-04-29
npy文件和pkl文件的保存和读取
2019-04-29
买卖股票的最佳时机
2019-04-29
AUC粗浅理解笔记记录
2019-04-29
torch 模型运行时间与forward没对应的可能原因
2019-04-29
JavaScript 的addEventListener() 事件监听详解!
2019-04-29
上传图片到阿里云OSS和获取上传图片的url的详解 !
2019-04-29
Kafka为什么这么快?
2019-04-29
Java 生产者和消费者面试题
2019-04-29
生产者消费者问题
2019-04-29
本机电脑连接虚拟机redis失败解决方法
2019-04-29
DM365 应用层gpio控制
2019-04-29
linux i2c子系统abc
2019-04-29
CSS3 帧动画(Sprite,直译叫雪碧图)
2019-04-29
Java 父线程与子线程相互通信的方法
2019-04-29
Redis 六种淘汰策略和三种删除策略
2019-04-29