Topic:
Given a string s, please reconstruct the string according to the following algorithm:
- Select the smallest character from s and appending it to the end of the result string.
- Select the smallest remaining character from s that is larger than the last added character and append it to the result string.
- Repeat step 2 until you cannot select a character from s.
- Select the largest character from s and appending it to the end of the result string.
- Selects the largest character from the remaining s character, which is smaller than the last added character, and appending it to the result string.
- Repeat step 5 until you cannot select a character from s.
- Repeat steps 1 through 6 until all characters in S have been selected.
In any step, if there is more than one minimum or maximum character, you can select either and add it to the resulting string.
Return the result string after reordering the characters in S.
Example:
- Example 1:
Enter: s ="aaaabbbbcccc"
Output:"abccbaabccba"
Explanation: After steps 1, 2, and 3 of the first round, the result string is result ="abc"
After steps 4, 5, and 6 in the first round, the result string is result ="abccba"
The first round is over, and now s is equal to"aabbcc", let's go back to step 1
After steps 1, 2, and 3 in the second round, the result string is result ="abccbaabc"
After steps 4, 5, and 6 in the second round, the result string is result ="abccbaabccba"
Copy the code- Example 2:
In: s ="rat"
Output:"art"
Explanation: Words"rat"After the above algorithm reorder becomes"art"
Copy the code- Example 3:
Enter: s ="leetcode"
Output:"cdelotee"
Copy the code- Example 4:
Enter: s ="ggggggg"
Output:"ggggggg"
Copy the code- Example 5:
Enter: s ="spo"
Output:"ops"
Copy the codeTip:
- 1 <= s.length <= 500
- The s contains only lowercase letters.
The topic
What is the meaning of this passage?
- First concatenate elements from small to large (each element is taken only once)
- Concatenate the elements again from large to small
- Until everything is reassembled
Use hash to record the number of occurrences of characters in s, use array sort to complete the above from large to small & from small to large:
- After reordering S, the whole assembly is directly spliced
- The number of occurrences of all characters in a whole concatenation is reduced by 1, and if the number of occurrences returns to 0, it is cleared from the sorting list
- Flip the array (from large to small – from small to large) for the next concatenation
/ * *
* @param {string} s
* @return {string}
* /
var sortString = function(s) {
let map = new Map(),
list = [],
result = [],
len = s.length,
max = 1
// Initialize hash computations and list arrays without repeating elements
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])
}
}
// Sort characters
list.sort()
// Maximum number of splices
while (max) {
// Complete a concatenation, hash -1
result = [...result, ...list]
for (let [key, value] of map.entries()) {
const num = value - 1
if (num) {
map.set(key, num)
} else {
// If the calculation returns to 0, delete the character
map.delete(key)
list.splice(list.indexOf(key), 1)
}
}
// Reverse the array conversion sort
list.reverse()
max--
}
return result.join(' ')
}
Copy the codeBarrels of count
- Use the utF-16 code of the character to place the space in the array, record the array of elements (complete the sorting and calculation of two logic)
- Loop through the concatenation multiple times until all characters are concatenated
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) {
// From small to big
for (let i = 0; i < 26; i++) {
if (list[i]) {
result += String.fromCharCode(i + 97)
list[i]--
len--
}
}
// From large to small
for (let i = 25; i >= 0; i--) {
if (list[i]) {
result += String.fromCharCode(i + 97)
list[i]--
len--
}
}
}
return result
}
Copy the codeBlog: Front end little bookboy
Every day a daily problem, write the solution of the problem will be updated to the public account one day a big Lee column welcome to pay attention to the message
Public number: front end little bookboy