kiehl's货还没到 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Fashion - 美丽时尚

kiehl's货还没到

kiehl's货还没到# Fashion - 美丽时尚

y*n2010-12-07 08:12

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 }

A*r2010-12-07 08:12

2 楼

请问MM们KIEHL'S一般都多久到货啊，我买了都两星期了，还没收到！！！
也TRACK不到邮寄到哪里，烦死了

w*s2010-12-07 08:12

3 楼

不一定有解，有可能有多个解
你要所有解，还是一个就够了？

h*c2010-12-07 08:12

4 楼

merry刚出来的时候订的一单大概8天左右到了，前两天定的就别提了。。。

w*s2010-12-07 08:12

5 楼

瞄了一眼，第一想法是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*n2010-12-07 08:12

6 楼

一个就够了，leetCode 看到了，觉得还是有点绕，不是很常规的思维。

l*82010-12-07 08:12

7 楼

第一次见到这个题目。
首先，把字母按照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*y2010-12-07 08:12

8 楼

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*n2010-12-07 08:12

9 楼

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*82010-12-07 08:12

10 楼

面试不可能写这么长吧

【在 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*n2010-12-07 08:12

11 楼

Start with pseudo code for helper methods and classes.
Fill in details if you have time.

【在 l*********8 的大作中提到】

: 面试不可能写这么长吧

r*s2010-12-07 08:12

12 楼

这个应该很简单吧。
首先sort：cccaaaabbbbddddd
然后按长度排序：dddddaaaabbbbccc
从中间拆成两个array：dddddaaa abbbbccc
两个array merge：dadbdbdbdbdacacac
这里面有一个结论，就是如果最长的字母序列长度大于n/2+2，那么不可能有答案。很
简单，要间隔开n/2+2个字母，你需要n/2个其他字母。

l*12010-12-07 08:12

13 楼

是不是这道题，感觉是leetcode原题吧
http://leetcode.com/2010/05/here-is-another-google-phone-interv

l*82010-12-07 08:12

14 楼

就是这个题

f*n2010-12-07 08:12

15 楼

mark

f*e2010-12-07 08:12

16 楼

还真是；
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*32010-12-07 08:12

17 楼

晚点上我的答案

m*k2010-12-07 08:12

18 楼

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个其他字母。