資訊專欄INFORMATION COLUMN
摘要：題目解答先記錄中的及它出現(xiàn)在次數(shù)，存在里，用來(lái)記錄這個(gè)最小出現(xiàn)的位置。
題目：
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及它出現(xiàn)在次數(shù)，存在count[]里，用valid[]來(lái)記錄這個(gè)char最小出現(xiàn)的位置。
//每一次把count值最大的數(shù)選出來(lái)，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];
//把每個(gè)出現(xiàn)了的char的個(gè)數(shù)記下來(lái)
for (char c : str.toCharArray()) {
count[c - "a"]++;
}
StringBuilder sb = new StringBuilder();
for (int i = 0; i < str.length(); i++) {
//選出剩下需要出現(xiàn)次數(shù)最多又滿足條件的字母，即是我們最應(yīng)該先放的數(shù)
int curt = selectedValue(count, valid, i);
//如果不符合條件，返回“”
if (curt == -1) return "";
//選擇好后，count要減少，valid要到下一個(gè)k distance之后
count[curt]--;
valid[curt] = i + k;
sb.append((char)("a" + curt));
}
return sb.toString();
}
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://m.specialneedsforspecialkids.com/yun/64874.html
摘要：題目鏈接的思想，這題要讓相同字母的距離至少為，那么首先要統(tǒng)計(jì)字母出現(xiàn)的次數(shù)，然后根據(jù)出現(xiàn)的次數(shù)來(lái)對(duì)字母排位置。出現(xiàn)次數(shù)最多的肯定要先往前面的位置排，這樣才能盡可能的滿足題目的要求。 358. Rearrange String k Distance Apart 題目鏈接：https://leetcode.com/problems... greedy的思想，這題要讓相同字母的charact...
摘要：比較長(zhǎng)度法復(fù)雜度時(shí)間空間思路雖然我們可以用的解法，看是否為，但中會(huì)超時(shí)。這里我們可以利用只有一個(gè)不同的特點(diǎn)在時(shí)間內(nèi)完成。 One Edit Distance Given two strings S and T, determine if they are both one edit distance apart. 比較長(zhǎng)度法 復(fù)雜度 時(shí)間 O(N) 空間 O(1) 思路 雖然我們可以用...
摘要：復(fù)雜度思路考慮如果兩個(gè)字符串的長(zhǎng)度，是肯定當(dāng)兩個(gè)字符串中有不同的字符出現(xiàn)的時(shí)候，說(shuō)明之后的字符串一定要相等。的長(zhǎng)度比較大的時(shí)候，說(shuō)明的時(shí)候，才能保證距離為。 LeetCode[161] One Edit Distance Given two strings S and T, determine if they are both one edit distance apart. Stri...
閱讀 3544·2021-09-10 10:51
閱讀 2518·2021-09-07 10:26
閱讀 2495·2021-09-03 10:41
閱讀 821·2019-08-30 15:56
閱讀 2909·2019-08-30 14:16
閱讀 3497·2019-08-30 13:53
閱讀 2113·2019-08-26 13:48
閱讀 1925·2019-08-26 13:37
