LeetCode C++ 1370. Increasing Decreasing String【String/Hash Table】简单
发布日期:2021-07-01 02:57:00
浏览次数:2
分类:技术文章
本文共 2428 字,大约阅读时间需要 8 分钟。
Given a string s
. You should re-order the string using the following algorithm:
- Pick the smallest character from
s
and append it to the result. - Pick the smallest character from
s
which is greater than the last appended character to the result and append it. - Repeat step 2 until you cannot pick more characters.
- Pick the largest character from
s
and append it to the result. - Pick the largest character from
s
which is smaller than the last appended character to the result and append it. - Repeat step 5 until you cannot pick more characters.
- Repeat the steps from 1 to 6 until you pick all characters from
s
.
In each step, If the smallest or the largest character appears more than once you can choose any occurrence and append it to the result.
Return the result string after sorting s
with this algorithm.
Example 1:
Input: s = "aaaabbbbcccc"Output: "abccbaabccba"Explanation: After steps 1, 2 and 3 of the first iteration, result = "abc"After steps 4, 5 and 6 of the first iteration, result = "abccba"First iteration is done. Now s = "aabbcc" and we go back to step 1After steps 1, 2 and 3 of the second iteration, result = "abccbaabc"After steps 4, 5 and 6 of the second iteration, result = "abccbaabccba"
Example 2:
Input: s = "rat"Output: "art"Explanation: The word "rat" becomes "art" after re-ordering it with the mentioned algorithm.
Example 3:
Input: s = "leetcode"Output: "cdelotee"
Example 4:
Input: s = "ggggggg"Output: "ggggggg"
Example 5:
Input: s = "spo"Output: "ops"
Constraints:
1 <= s.length <= 500
s
contains only lower-case English letters.
题意:给出一个字符串 s
,返回将 s
中字符重新排序后的结果字符串 。
解法 哈希计数
计算每个小写字母的频数。然后循环所有字符,从 'a'
到 'z'
,如果该字符存在则添加,同时减少其频数;接着从 'z'
到 'a'
,做同样的工作。直至所有字母的频数归零。
class Solution { public: string sortString(string s) { int cnt[26] = { 0}; for (const char &c : s) ++cnt[c - 'a']; int n = s.size(); string ans; while (n) { for (int i = 0; i < 26; ++i) { if (cnt[i]) { --cnt[i]; --n; ans.push_back(i + 'a'); } } for (int i = 25; i >= 0; --i) { if (cnt[i]) { --cnt[i]; --n; ans.push_back(i + 'a'); } } } return ans; }};
执行效率如下:
执行用时:4 ms, 在所有 C++ 提交中击败了97.13% 的用户内存消耗:7.7 MB, 在所有 C++ 提交中击败了45.07% 的用户
转载地址:https://memcpy0.blog.csdn.net/article/details/110103351 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
感谢大佬
[***.8.128.20]2024年05月04日 09时16分13秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
Request_继承体系
2019-05-01
前端权限控制:获取用户信息接口构造数据
2019-05-01
有状态服务和无状态服务
2019-05-01
七牛云存储:断点续传
2019-05-01
字节流复制文本文件【应用】
2019-05-01
字节流复制图片
2019-05-01
其他数字摘要算法实现
2019-05-01
私钥加密私钥解密
2019-05-01
锁的释放流程-ReentrantLock.unlock
2019-05-01
Java判断字符串是否为数字(浮点类型也包括)
2019-05-01
Err:11 https://developer.download.nvidia.cn/compute/cuda/repos/ubuntu2004/x86_64 Packages 404 No
2019-05-01
ubuntu opencv-python 安装很慢问题
2019-05-01
MySQL5.7版本修改了my.ini配置文件后mysql服务无法启动问题
2019-05-01
【大数据开发】Java基础 -总结21-Hashmap和HashTable的区别
2019-05-01
Azkaban体系结构
2019-05-01
机器学习之重头戏-特征预处理
2019-05-01
synchronized底层实现及锁的升级、降级
2019-05-01
PermGen space-永久区内存溢出
2019-05-01