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 的大作中提到】
: 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 的大作中提到】
: 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 的大作中提到】
: 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 的大作中提到】
: 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 的大作中提到】
:
: 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 的大作中提到】
: 面试不可能写这么长吧
| 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 的大作中提到】
: 第一次见到这个题目。
: 首先，把字母按照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 的大作中提到】
: 这个应该很简单吧。
: 首先sort：cccaaaabbbbddddd
: 然后按长度排序：dddddaaaabbbbccc
: 从中间拆成两个array：dddddaaa abbbbccc
: 两个array merge：dadbdbdbdbdacacac
: 这里面有一个结论，就是如果最长的字母序列长度大于n/2+2，那么不可能有答案。很
: 简单，要间隔开n/2+2个字母，你需要n/2个其他字母。
|
|
