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

資訊專欄INFORMATION COLUMN

358. Rearrange String k Distance Apart

oogh / 2326人閱讀

摘要:題目解答先記錄中的及它出現在次數,存在里,用來記錄這個最小出現的位置。

題目:
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 strings are given in lowercase letters. If it is not possible to rearrange the string, return an empty string "".

Example 1:
str = " ", k = 3

Result: "abcabc"

The same letters are at least distance 3 from each other.
Example 2:
str = "aaabc", k = 3

Answer: ""

It is not possible to rearrange the string.
Example 3:
str = "aaadbbcc", k = 2

Answer: "abacabcd"

Another possible answer is: "abcabcda"

The same letters are at least distance 2 from each other.

解答:

//先記錄str中的char及它出現在次數,存在count[]里,用valid[]來記錄這個char最小出現的位置。
    //每一次把count值最大的數選出來,append到新的string后面
    public int selectedValue(int[] count, int[] valid, int i) {
        int select = Integer.MIN_VALUE;
        int val = -1;
        for (int j = 0; j < count.length; j++) {
            if (count[j] > 0 && i >= valid[j] && count[j] > select) {
                select = count[j];
                val = j;
            }
        }
        return val;
    }
    
    public String rearrangeString(String str, int k) {
        int[] count = new int[26];
        int[] valid = new int[26];
        //把每個出現了的char的個數記下來
        for (char c : str.toCharArray()) {
            count[c - "a"]++;
        }
        
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < str.length(); i++) {
            //選出剩下需要出現次數最多又滿足條件的字母,即是我們最應該先放的數
            int curt = selectedValue(count, valid, i);
            //如果不符合條件,返回“”
            if (curt == -1) return "";
            //選擇好后,count要減少,valid要到下一個k distance之后
            count[curt]--;
            valid[curt] = i + k;
            sb.append((char)("a" + curt));
        }
        
        return sb.toString();
    }

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

轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/64874.html

相關文章

  • 358. Rearrange String k Distance Apart

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

    Taonce 評論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條評論

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