题目:
给你一个字符串 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 中出现的次数,利用数组排序来完成上面从大到小&从小到大的排序:
对 s 去重排序后直接整体拼接 整体拼接一次所有字符出现次数减 1,如果出现次数归 0,则将其从排序 list 中清除 翻转数组(从大到小-从小到大转换)待下次拼接
/**
* @param {string} s
* @return {string}
*/
var sortString = function(s) {
let map = new Map(),
list = [],
result = [],
len = s.length,
max = 1
// 初始化哈希计算和list无重复元素数组
for (let i = 0; i < len; i++) {
if (map.has(s[i])) {
const num = map.get(s[i]) + 1
map.set(s[i], num)
max = Math.max(max, num)
} else {
map.set(s[i], 1)
list.push(s[i])
}
}
// 对字符排序
list.sort()
// 最多拼接次数
while (max) {
// 完成一次拼接,哈希计算-1
result = [...result, ...list]
for (let [key, value] of map.entries()) {
const num = value - 1
if (num) {
map.set(key, num)
} else {
// 如果计算归0,则删除这个字符
map.delete(key)
list.splice(list.indexOf(key), 1)
}
}
// 翻转数组 转换排序
list.reverse()
max--
}
return result.join('')
}
桶计数
利用字符的 UTF-16 代码在数组中占位,记录元素数组(完成排序和计算两个逻辑) 循环多次拼接知道所有字符拼接完成
var sortString = function(s) {
let list = new Array(26).fill(0),
len = s.length
for (let i = 0; i < len; i++) {
list[s.charCodeAt(i) - 97]++
}
let result = ''
while (len) {
// 从小到大
for (let i = 0; i < 26; i++) {
if (list[i]) {
result += String.fromCharCode(i + 97)
list[i]--
len--
}
}
// 从大到小
for (let i = 25; i >= 0; i--) {
if (list[i]) {
result += String.fromCharCode(i + 97)
list[i]--
len--
}
}
}
return result
}
博客: 前端小书童
每天的每日一题,写的题解会同步更新到公众号一天一大 lee 栏目 欢迎关注留言
公众号:前端小书童
常见问题FAQ
- 免费下载或者VIP会员专享资源能否直接商用?
- 本站所有资源版权均属于原作者所有,这里所提供资源均只能用于参考学习用,请勿直接商用。若由于商用引起版权纠纷,一切责任均由使用者承担。更多说明请参考 VIP介绍。
- 提示下载完但解压或打开不了?
- 找不到素材资源介绍文章里的示例图片?
- 模板不会安装或需要功能定制以及二次开发?
发表评论
还没有评论,快来抢沙发吧!