y***n 发帖数: 1594 | 1 Given a string of lowercase characters, reorder them such that the same
characters are at least distance d from each other.
Input: { a, b, b }, distance = 2
Output: { b, a, b } | w********s 发帖数: 1570 | 2 不一定有解,有可能有多个解
你要所有解,还是一个就够了? | w********s 发帖数: 1570 | 3 瞄了一眼,第一想法是sort,然后用唯一出现字符去插
【在 y***n 的大作中提到】![](/moin_static193/solenoid/img/up.png) : Given a string of lowercase characters, reorder them such that the same : characters are at least distance d from each other. : Input: { a, b, b }, distance = 2 : Output: { b, a, b }
| y***n 发帖数: 1594 | 4 一个就够了,leetCode 看到了,觉得还是有点绕,不是很常规的思维。 | l*********8 发帖数: 4642 | 5 第一次见到这个题目。
首先,把字母按照frequency降序排序.
S = {{2,b}, {1,a}}
然后,把字母依次放到以下位置:0, d, 2*d, ..., 1, 1+d, 1+2d, ....
【在 y***n 的大作中提到】![](/moin_static193/solenoid/img/up.png) : Given a string of lowercase characters, reorder them such that the same : characters are at least distance d from each other. : Input: { a, b, b }, distance = 2 : Output: { b, a, b }
| d*****y 发帖数: 1365 | 6 I think if you use a queue of length d, you can get an O(dn) algorithm. You
probably can improve it to O(nlogd) though.
【在 y***n 的大作中提到】![](/moin_static193/solenoid/img/up.png) : Given a string of lowercase characters, reorder them such that the same : characters are at least distance d from each other. : Input: { a, b, b }, distance = 2 : Output: { b, a, b }
| m*****n 发帖数: 204 | 7
The following is an O(nlgn) solution for string of size n.
It maintains a heap for eligible chars, preferring longer streams.
Ineligible chars are maintained in a candidate queue, and added back
to the working queue when their position constraint is removed.
public class MinDistance {
public String rearrange(String source, int distance) {
// TODO Check params.
// WorkingQueue of eligible streams. Longest stream at head,
// but BackupStream at tail.
PriorityQueue workingQueue = buildStreams(source.toLowerCase
());
// CandidateQueue of ineligible streams. Sorted by target position.
List candidateQueue = new LinkedList<>();
StringBuilder result = new StringBuilder();
while (result.length() < source.length()) {
int currPos = result.length();
// Resupply the working queue:
if (!candidateQueue.isEmpty()) {
CharStream candidate = candidateQueue.get(0);
if (candidate.getTargetPos() <= currPos) {
workingQueue.add(candidateQueue.remove(0));
}
}
if (workingQueue.isEmpty()) {
// No solution. Return null or throw
}
CharStream stream = workingQueue.poll();
result.append(stream.next());
if (stream.hasNext()) {
stream.setTargetPos(currPos + distance);
}
candidateQueue.add(stream);
}
return result.toString();
}
private PriorityQueue buildStreams(String source) {
Map map = new HashMap<>();
for (int pos = 0; pos < source.length(); pos++) {
Character c = source.charAt(pos);
AtomicInteger count = map.get(c);
if (count == null) {
count = new AtomicInteger();
map.put(c, count);
}
count.incrementAndGet();
}
PriorityQueue streams =
new PriorityQueue<>(source.length(), new LengthComparator());
List backupList = new ArrayList<>();
for (Map.Entry entry : map.entrySet()) {
if (entry.getValue().get() == 1) {
backupList.add(entry.getKey());
} else {
streams.add(
new SingleCharStream(entry.getKey(), entry.getValue().get()));
}
}
if (backupList.size() > 0) {
streams.add(new BackupStream(backupList.iterator()));
}
return streams;
}
// Comparator for the working queue. BackupStream is at the tail.
private static class LengthComparator implements Comparator {
@Override
public int compare(CharStream o1, CharStream o2) {
if (o1 instanceof BackupStream) {
return 1;
} else if (o2 instanceof BackupStream) {
return -1;
}
SingleCharStream sc1 = (SingleCharStream) o1;
SingleCharStream sc2 = (SingleCharStream) o2;
return -Integer.compare(sc1.remaining, sc2.remaining);
}
}
private static interface CharStream extends Iterator {
int getTargetPos();
void setTargetPos(int targetPos);
}
private static class BackupStream implements CharStream {
private final Iterator myIterator;
BackupStream(Iterator it) {
this.myIterator = it;
}
@Override
public boolean hasNext() {
return myIterator.hasNext();
}
@Override
public Character next() {
return myIterator.next();
}
@Override
public void remove() {
myIterator.remove();
}
@Override
public int getTargetPos() {
return 0;
}
@Override
public void setTargetPos(int targetPos) {
// Do nothing.
}
}
private static class SingleCharStream implements CharStream {
private final char character;
private int remaining;
private int targetPos;
SingleCharStream(char c, int count) {
this.character = c;
this.remaining = count;
}
@Override
public boolean hasNext() {
return remaining > 0;
}
@Override
public Character next() {
// check hasNext()
remaining--;
return character;
}
@Override
public void remove() {
throw new UnsupportedOperationException();
}
@Override
public int getTargetPos() {
return targetPos;
}
@Override
public void setTargetPos(int targetPos) {
this.targetPos = targetPos;
}
}
}
【在 y***n 的大作中提到】![](/moin_static193/solenoid/img/up.png) : Given a string of lowercase characters, reorder them such that the same : characters are at least distance d from each other. : Input: { a, b, b }, distance = 2 : Output: { b, a, b }
| l*********8 发帖数: 4642 | 8 面试不可能写这么长吧
【在 m*****n 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : The following is an O(nlgn) solution for string of size n. : It maintains a heap for eligible chars, preferring longer streams. : Ineligible chars are maintained in a candidate queue, and added back : to the working queue when their position constraint is removed. : public class MinDistance { : public String rearrange(String source, int distance) { : // TODO Check params. : : // WorkingQueue of eligible streams. Longest stream at head,
| m*****n 发帖数: 204 | 9 Start with pseudo code for helper methods and classes.
Fill in details if you have time.
【在 l*********8 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 面试不可能写这么长吧
| r****s 发帖数: 1025 | 10 这个应该很简单吧。
首先sort:cccaaaabbbbddddd
然后按长度排序:dddddaaaabbbbccc
从中间拆成两个array:dddddaaa abbbbccc
两个array merge:dadbdbdbdbdacacac
这里面有一个结论,就是如果最长的字母序列长度大于n/2+2,那么不可能有答案。很
简单,要间隔开n/2+2个字母,你需要n/2个其他字母。 | | | l********1 发帖数: 24 | | l*********8 发帖数: 4642 | | f******n 发帖数: 279 | | f*****e 发帖数: 2992 | 14 还真是;
Let N = total # of chars,
ceil(N / d) must >= max # of a specific char. 大于等于一定有解,小于一定无解。
比如bbccceeee, d = 2, N = 9, ceil(N/d)=5>4, 5 buckets with d slots.
%d == 0 : e e e e c
%d == 1 : c c b b
Final -> ececebebc
【在 l*********8 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 第一次见到这个题目。 : 首先,把字母按照frequency降序排序. : S = {{2,b}, {1,a}} : 然后,把字母依次放到以下位置:0, d, 2*d, ..., 1, 1+d, 1+2d, ....
| j**********3 发帖数: 3211 | | m*****k 发帖数: 731 | 16 Input: { a, a, b, b,c,c,d,d }, distance = 3
Output: { a,b,c,d,a,b,c,d}
你的解法貌似不会给出这个答案吧?
【在 r****s 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这个应该很简单吧。 : 首先sort:cccaaaabbbbddddd : 然后按长度排序:dddddaaaabbbbccc : 从中间拆成两个array:dddddaaa abbbbccc : 两个array merge:dadbdbdbdbdacacac : 这里面有一个结论,就是如果最长的字母序列长度大于n/2+2,那么不可能有答案。很 : 简单,要间隔开n/2+2个字母,你需要n/2个其他字母。
|
|