国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

358. Rearrange String k Distance Apart

Taonce / 3172人閱讀

摘要:題目鏈接的思想,這題要讓相同字母的距離至少為,那么首先要統計字母出現的次數,然后根據出現的次數來對字母排位置。出現次數最多的肯定要先往前面的位置排,這樣才能盡可能的滿足題目的要求。

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();
    }
}

文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。

轉載請注明本文地址:http://specialneedsforspecialkids.com/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 評論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 評論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...

    周國輝 評論0 收藏0

發表評論

0條評論

Taonce

|高級講師

TA的文章

閱讀更多
最新活動
閱讀需要支付1元查看
<