[LeetCode] 358. Rearrange String k Distance Apart 按距离为k隔离重排字符串
Given a non-empty string s and an integer k, rearrange the string such that the same characters are at least distance k from each other.
All input strings are given in lowercase letters. If it is not possible to rearrange the string, return an empty string ""
.
Example 1:
Input: s = "aabbcc", k = 3
Output: "abcabc"
Explanation: The same letters are at least distance 3 from each other.
Example 2:
Input: s = "aaabc", k = 3
Output: ""
Explanation: It is not possible to rearrange the string.
Example 3:
Input: s = "aaadbbcc", k = 2
Output: "abacabcd"
Explanation: The same letters are at least distance 2 from each other.
Credits:
Special thanks to @elmirap for adding this problem and creating all test cases.
这道题给了我们一个字符串str,和一个整数k,让我们对字符串str重新排序,使得其中相同的字符之间的距离不小于k,这道题的难度标为Hard,看来不是省油的灯。的确,这道题的解法用到了哈希表,堆,和贪婪算法。这道题我最开始想的算法没有通过OJ的大集合超时了,下面的方法是参考网上大神的解法,发现十分的巧妙。我们需要一个哈希表来建立字符和其出现次数之间的映射,然后需要一个堆来保存这每一堆映射,按照出现次数来排序。然后如果堆不为空我们就开始循环,我们找出k和str长度之间的较小值,然后从0遍历到这个较小值,对于每个遍历到的值,如果此时堆为空了,说明此位置没法填入字符了,返回空字符串,否则我们从堆顶取出一对映射,然后把字母加入结果res中,此时映射的个数减1,如果减1后的个数仍大于0,则我们将此映射加入临时集合v中,同时str的个数len减1,遍历完一次,我们把临时集合中的映射对由加入堆中,参见代码如下:
class Solution { public: string rearrangeString(string str, int k) { if (k == 0) return str; string res; int len = (int)str.size(); unordered_map<char, int> m; priority_queue<pair<int, char>> q; for (auto a : str) ++m[a]; for (auto it = m.begin(); it != m.end(); ++it) { q.push({it->second, it->first}); } while (!q.empty()) { vector<pair<int, int>> v; int cnt = min(k, len); for (int i = 0; i < cnt; ++i) { if (q.empty()) return ""; auto t = q.top(); q.pop(); res.push_back(t.second); if (--t.first > 0) v.push_back(t); --len; } for (auto a : v) q.push(a); } return res; } };
类似题目:
参考资料:
https://leetcode.com/problems/rearrange-string-k-distance-apart/
https://leetcode.com/discuss/108174/c-unordered_map-priority_queue-solution-using-cache
相关文章
- [LeetCode] Remove Duplicates from Sorted List - 链表问题
- Java实现 LeetCode 808 分汤 (暴力模拟)
- Java实现 LeetCode 576 出界的路径数(DFS || DP)
- Java实现 LeetCode 124 二叉树中的最大路径和
- Java实现 LeetCode 72 编辑距离
- Java实现 LeetCode 24 两两交换链表中的节点
- LeetCode:151_Reverse Words in a String | 字符串中单词的逆反 | Medium
- [LeetCode] Insertion Sort List
- LeetCode(75):分类颜色
- Atitit 字符串转换数组main参数解析 args splitByWholeSeparator String string=" -host 101.1 8*124 -db 1
- TypeScript里string和String,真不是仅仅是大小写的区别
- C# string.Format 和 String.Format 的区别
- Leetcode 1385. 两个数组间的距离值
- Leetcode 796. 旋转字符串
- [LeetCode] 213. 打家劫舍II ☆☆☆(动态规划)
- leetcode 78. 子集 js 实现
- leetCode 57.Insert Interval (插入区间) 解题思路和方法