侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 471 篇文章
  • 累计创建 108 个标签
  • 累计收到 9 条评论

目 录CONTENT

文章目录

【排序, 哈希表】K 距离间隔重排字符串

GabrielxD
2022-06-03 / 0 评论 / 0 点赞 / 40 阅读 / 892 字 / 正在检测是否收录...

题目

358. K 距离间隔重排字符串


给你一个非空的字符串 s 和一个整数 k ,你要将这个字符串 s 中的字母进行重新排列,使得重排后的字符串中相同字母的位置间隔距离 至少 为 k 。如果无法做到,请返回一个空字符串 ""

示例 1:

输入: s = "aabbcc", k = 3
输出: "abcabc" 
解释: 相同的字母在新的字符串中间隔至少 3 个单位距离。

示例 2:

输入: s = "aaabc", k = 3
输出: "" 
解释: 没有办法找到可能的重排结果。

示例 3:

输入: s = "aaadbbcc", k = 2
输出: "abacabcd"
解释: 相同的字母在新的字符串中间隔至少 2 个单位距离。

提示:

  • 1 <= s.length <= 3 * 10^5
  • s 仅由小写英文字母组成
  • 0 <= k <= s.length

解题

方法一:哈希表 优先队列

思路

首先创建一个哈希表(freqs)统计每个字符出现的次数,然后维护一个按重复次数降序排序的优先队列(priQueue)/大顶堆并把 freqs 中的键值对全部入队。

创建一个StringBuilder(ans)用来构造字符串,再维护一个普通队列(queue)用来记录已经加入 ans 中的字符。

遍历取出 priQueue 队头元素:

  • 当前元素表示的字符拼入 ans 中并把其计数减一。
  • 把当前元素放入 queue 中表示该字符已加入 ans 中。
  • 如果 queue 中元素个数为 k,说明 ans 中距离上一个「queue 的队头元素表示的字符」已经间隔了 k 个字符了,可以把「queue 的队头元素表示的字符」再拼入一次了,如果其计数还大于 1,就把 queue 的队头元素取出放入 priQueue 中等待下次拼入。
  • priQueue 中没有元素即退出循环。

如果 ans 长度和 s 相同,说明字符串已经重新排列完成,返回 ans.toString() 即可。

否则说明还有些字符在 queue 中没有装入 priQueue ,有些字符无法间隔 k 个距离,返回 ""

代码

class Solution {
    public String rearrangeString(String s, int k) {
        if (k <= 1) return s;
        int n = s.length();
        if (n < k) return "";
        Map<Character, Integer> freqs = new HashMap<>();
        for (char ch : s.toCharArray()) {
            freqs.put(ch, freqs.getOrDefault(ch, 0) + 1);
        }
        Queue<Map.Entry<Character, Integer>> priQueue =
            new PriorityQueue<>((a, b) ->b.getValue() - a.getValue());
        priQueue.addAll(freqs.entrySet());
        StringBuilder ans = new StringBuilder();
        Queue<Map.Entry<Character, Integer>> queue = new LinkedList<>();
        while (!priQueue.isEmpty()) {
            Map.Entry<Character, Integer> curr = priQueue.poll();
            ans.append(curr.getKey());
            curr.setValue(curr.getValue() - 1);
            queue.offer(curr);
            if (queue.size() == k) {
                Map.Entry<Character, Integer> next = queue.poll();
                if (next.getValue() > 0) priQueue.offer(next);
            }
        }
        return ans.length() == n ? ans.toString() : "";
    }
}

优化

因为字符串中只含有小写字母,所以哈希表可以用数组来待代替。

class Solution {
    public String rearrangeString(String s, int k) {
        if (k <= 1) return s;
        int n = s.length();
        if (n < k) return "";
        int[] counts = new int[26];
        for (char ch : s.toCharArray()) {
            counts[ch - 'a']++;
        }
        Queue<int[]> priQueue = new PriorityQueue<>((a, b) -> b[1] - a[1]);
        for (int i = 0; i < counts.length; i++) {
            if (counts[i] > 0) {
                priQueue.offer(new int[]{i, counts[i]});
            }
        }
        Queue<int[]> queue = new LinkedList<>();
        StringBuilder ans = new StringBuilder(n);
        while (!priQueue.isEmpty()) {
            int[] curr = priQueue.poll();
            ans.append((char) (curr[0] + 'a'));
            curr[1]--;
            queue.offer(curr);
            if (queue.size() == k) {
                int[] next = queue.poll();
                if (next[1] > 0) priQueue.offer(next);
            }
        }
        return ans.length() == n ? ans.toString() : "";
    }
}
0

评论区