https://gist.github.com/gcrfelix/cd4f4e887e41882ca1f2
题目:输出任意permutation使得List中的相同element的间距要>=minDistance
例1:
输入:[B, E, A, C, D, F, F],2
输出:[B, F, A, C, D, E, F] (两个F之间的间距为4大于2)
例2:
输入:[A, B, B],1
输出:[A, B, B] (两个B之间的间距为1)
例3:
输入:[A, B, B],2
输出:[B, A, B] (两个B之间的间距为2)
解题思路:
和Rerrange String的思路比较像
先按频率排序,然后每次取出频率最高的d个不同的放到result,然后把剩下的再排序,再放。。。。
一开始A3 B3 C1 D1 E1 (A3代表3个A)
找最大的三个:ABC
之后A2 B2 D1 E1
最大的三个加入:ABCABD
之后A1 B1 E1
ABCABDABE
public class Solution {
public char[] getMinDistance(char[] chars, int minDistance) {
HashMap<Character, Integer> map = new HashMap<Character, Integer>();
for(int i=0; i<chars.length; i++) {
char c = chars[i];
if(map.containsKey(c)) {
map.put(c, map.get(c)+1);
} else {
map.put(c, 1);
}
}
PriorityQueue<Element> maxHeap = new PriorityQueue<Element>(1, new Comparator<Element>() {
public int compare(Element e1, Element e2) {
return e2.count - e1.count;
}
});
for(char c : map.keySet()) {
int count = map.get(c);
Element e = new Element(c, count);
maxHeap.offer(e);
}
int index = 0;
char[] result = new char[chars.length];
while(!maxHeap.isEmpty()) {
Queue<Element> queue = new LinkedList<Element>();
int i=0;
for(; i<minDistance && !maxHeap.isEmpty(); i++) {
queue.offer(maxHeap.poll());
}
if(i < minDistance && queue.peek().count > 1) { // 说明不可能有这样的char组合满足minDistance
return new char[0];
}
while(!queue.isEmpty()) {
Element e = queue.poll();
result[index++] = e.c;
e.count --;
if(e.count > 0) {
maxHeap.offer(e);
}
}
}
return result;
}
}
class Element {
char c;
int count;
public Element(char c, int count) {
this.c = c;
this.count = count;
}
}
Related: String Reorder Distance Apart | LeetCode
Rearrange a string so that all same characters become d distance away
题目:输出任意permutation使得List中的相同element的间距要>=minDistance
例1:
输入:[B, E, A, C, D, F, F],2
输出:[B, F, A, C, D, E, F] (两个F之间的间距为4大于2)
例2:
输入:[A, B, B],1
输出:[A, B, B] (两个B之间的间距为1)
例3:
输入:[A, B, B],2
输出:[B, A, B] (两个B之间的间距为2)
解题思路:
和Rerrange String的思路比较像
先按频率排序,然后每次取出频率最高的d个不同的放到result,然后把剩下的再排序,再放。。。。
一开始A3 B3 C1 D1 E1 (A3代表3个A)
找最大的三个:ABC
之后A2 B2 D1 E1
最大的三个加入:ABCABD
之后A1 B1 E1
ABCABDABE
public class Solution {
public char[] getMinDistance(char[] chars, int minDistance) {
HashMap<Character, Integer> map = new HashMap<Character, Integer>();
for(int i=0; i<chars.length; i++) {
char c = chars[i];
if(map.containsKey(c)) {
map.put(c, map.get(c)+1);
} else {
map.put(c, 1);
}
}
PriorityQueue<Element> maxHeap = new PriorityQueue<Element>(1, new Comparator<Element>() {
public int compare(Element e1, Element e2) {
return e2.count - e1.count;
}
});
for(char c : map.keySet()) {
int count = map.get(c);
Element e = new Element(c, count);
maxHeap.offer(e);
}
int index = 0;
char[] result = new char[chars.length];
while(!maxHeap.isEmpty()) {
Queue<Element> queue = new LinkedList<Element>();
int i=0;
for(; i<minDistance && !maxHeap.isEmpty(); i++) {
queue.offer(maxHeap.poll());
}
if(i < minDistance && queue.peek().count > 1) { // 说明不可能有这样的char组合满足minDistance
return new char[0];
}
while(!queue.isEmpty()) {
Element e = queue.poll();
result[index++] = e.c;
e.count --;
if(e.count > 0) {
maxHeap.offer(e);
}
}
}
return result;
}
}
class Element {
char c;
int count;
public Element(char c, int count) {
this.c = c;
this.count = count;
}
}
Related: String Reorder Distance Apart | LeetCode
Rearrange a string so that all same characters become d distance away