358. Rearrange String k Distance Apart

Taonce 发布于2019-08-14 17:35 / 3093人阅读

摘要：题目链接的思想，这题要让相同字母的距离至少为，那么首先要统计字母出现的次数，然后根据出现的次数来对字母排位置。出现次数最多的肯定要先往前面的位置排，这样才能尽可能的满足题目的要求。

358. Rearrange String k Distance Apart

题目链接：https://leetcode.com/problems...

greedy的思想，这题要让相同字母的character距离至少为k，那么首先要统计字母出现的次数，然后根据出现的次数来对字母排位置。出现次数最多的肯定要先往前面的位置排，这样才能尽可能的满足题目的要求。建一个heap，存char和剩余次数，每次从heap里面取k个不同的字母出来排，把字母放入一个大小为k的q里面等待，直到距离到k的时候再释放。
参考：
https://discuss.leetcode.com/...

public class Solution {
    public String rearrangeString(String s, int k) {
        int n = s.length();
        // count the characters
        int[] map = new int[26];
        for(int i = 0; i < n; i++) map[s.charAt(i) - "a"]++;
        // [0]: char, [1]: frequency
        PriorityQueue heap = new PriorityQueue<>((a, b) -> b[1] - a[1]);
        // wait queue
        Queue wait = new LinkedList();
        // add all characters
        for(int i = 0; i < map.length; i++) {
            if(map[i] != 0) heap.offer(new int[] {i, map[i]});
        }
        
        StringBuilder res = new StringBuilder();
        // loop invariant: all char in heap is k away from last time
        while(!heap.isEmpty()) {
            int[] cur = heap.poll();
            res.append((char) ("a" + cur[0]));
            cur[1] = cur[1] - 1;
            // add to wait queue
            wait.add(cur);
            // if already k away from wait queue, add to heap
            if(wait.size() >= k) {
                int[] release = wait.poll();
                if(release[1] > 0) heap.offer(release);
            }
        }
        // invalid
        if(res.length() != n) return "";
        return res.toString();
    }
}

GPU云服务器云服务器 Apart Rearrange Distance String

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/66677.html

358. Rearrange String k Distance Apart

摘要：题目解答先记录中的及它出现在次数，存在里，用来记录这个最小出现的位置。题目：Given a non-empty string str and an integer k, rearrange the string such that the same characters are at least distance k from each other. All input string...

oogh 2019-08-14 14:12 评论0 收藏0
[Leetcode] One Edit Distance 编辑距离为一

摘要：比较长度法复杂度时间空间思路虽然我们可以用的解法，看是否为，但中会超时。这里我们可以利用只有一个不同的特点在时间内完成。 One Edit Distance Given two strings S and T, determine if they are both one edit distance apart. 比较长度法复杂度时间 O(N) 空间 O(1) 思路虽然我们可以用...

lewinlee 2019-08-14 12:48 评论0 收藏0
Leetcode[161] One Edit Distance

摘要：复杂度思路考虑如果两个字符串的长度，是肯定当两个字符串中有不同的字符出现的时候，说明之后的字符串一定要相等。的长度比较大的时候，说明的时候，才能保证距离为。 LeetCode[161] One Edit Distance Given two strings S and T, determine if they are both one edit distance apart. Stri...

周国辉 2019-08-14 15:58 评论0 收藏0