j******e
发帖数: 64 | 1 给一个字符串，重新排列成相邻字母不能相同
我的想法是看到两个相同，就把第二个替换成后面不同的 aaabb -> abaab -> ababa
aaabbb-> abaabb -> ababab
但是这样的话就没法处理 aabbb的情况 aabbb-> ababb | l*********g
发帖数: 107 | | i***h
发帖数: 12655 | | j******e
发帖数: 64 | 4 可以展开说说具体算法吗？比如现在有4个a, 2个b, 1个c.你的算法怎么做？
priorityqueue?
【在 i***h 的大作中提到】
: 从最多的字符开始
| o*******y
发帖数: 362 | 5 priorityqueue再加一个queue当小黑屋
【在 j******e 的大作中提到】
: 可以展开说说具体算法吗？比如现在有4个a, 2个b, 1个c.你的算法怎么做？
: priorityqueue?
| m******3
发帖数: 346 | 6 这个方法行么
记录每一个字符出现的次数，比如count['a']=4, count['b']=2, count['c']=1
每次找满足条件的count最大的字符
比如，一开始
取a, 然后 count['a']-1,变成3
下一轮，虽然count['a']是最大，但是不能取，因为上一次取的是'a, 所以，这次取b,
count['b]-1 变成1
然后再取a
b
a
c
a
最后结果是ababaca | i***h
发帖数: 12655 | 7 就是这样
不过没想好如果这个没結果的话能不能证明无解
b,
【在 m******3 的大作中提到】
: 这个方法行么
: 记录每一个字符出现的次数，比如count['a']=4, count['b']=2, count['c']=1
: 每次找满足条件的count最大的字符
: 比如，一开始
: 取a, 然后 count['a']-1,变成3
: 下一轮，虽然count['a']是最大，但是不能取，因为上一次取的是'a, 所以，这次取b,
: count['b]-1 变成1
: 然后再取a
: b
: a
| m******0
发帖数: 222 | 8 我认为你的办法没什么问题
我还有一个办法：
也是统计所有字母的freq，
let s = 目前已经拼成的半成品string
repeat {
对每个freq>0的letter，取出一个，组成新string t, update freq[]
s = (s+t) or (t+s), depending on which is valid
}
return s
b,
【在 m******3 的大作中提到】
: 这个方法行么
: 记录每一个字符出现的次数，比如count['a']=4, count['b']=2, count['c']=1
: 每次找满足条件的count最大的字符
: 比如，一开始
: 取a, 然后 count['a']-1,变成3
: 下一轮，虽然count['a']是最大，但是不能取，因为上一次取的是'a, 所以，这次取b,
: count['b]-1 变成1
: 然后再取a
: b
: a
| y******g
发帖数: 4 | 9 #include
#include
#include
#include
using namespace std;
struct Item {
int counter;
char c;
Item(): counter(0), c('\0') {};
Item(int counter_, char c_) : counter(counter_), c(c_) {};
Item(const Item &anotherItem): counter(anotherItem.counter), c(
anotherItem.c) {};
};
struct ItemCompare {
Item* prev;
ItemCompare(Item* prevItem): prev(prevItem) {};
bool operator() (const Item &item1, const Item &item2) {
if (!prev) {
return item1.counter < item2.counter;
} else {
if (prev->c == item1.c) {
return true;
} else if (prev->c == item2.c){
return false;
} else {
return item1.counter < item2.counter;
}
}
}
};
string shuffle(string str) {
if (str.empty()) return str;
unordered_map m;
for_each(str.begin(), str.end(), [&](char c) {
if (m.count(c)) {
++m[c].counter;
} else {
m[c] = Item(1, c);
}
});
vector- items;
for (auto kv: m) {
items.push_back(kv.second);
}
string result;
Item* prev = NULL;
while (!items.empty()) {
make_heap(items.begin(), items.end(), ItemCompare(prev));
result.push_back(items.front().c);
if (!--items.front().counter) {
pop_heap(items.begin(), items.end(), ItemCompare(prev));
items.pop_back();
prev = NULL;
} else {
prev = &(items.front());
}
}
return result;
};
int main() {
// your code goes here
cout << shuffle("aabb") << endl;
cout << shuffle("aaabb") << endl;
cout << shuffle("aabbb") << endl;
cout << shuffle("aabbbcc") << endl;
cout << shuffle("aabbc") << endl;
cout << shuffle("aabbcc") << endl;
cout << shuffle("aabbbbcc") << endl;
cout << shuffle("aabbbbc") << endl;
return 0;
} | L*********s
发帖数: 3063 | 10 如果最多的字符是A，字符A有N个，
你就挖N个坑，先在每个坑填一个A，
然后往坑里填其它字符，字符一种一种地填，
坑一个一个地往前填，填到最后一个坑再回到最前面第一个坑继续填。
填好后发现不是解就无解。 | l***i
发帖数: 1309 | 11 This is correct. You can prove that if an input has a solution, then there
exists a solution starts with max count char. If not, let the solution be
string s, and let the max count char be X, then we can partition s into
blocks starting with X. At least one of those blocks can be moved to the
beginning of S without causing a conflict with s[0], otherwise s[0] has a
larger count than X. Similarly we can show that there always exists a
solution with a prefix generated by this algorithm and an induction on
length of s will complete the proof.
b,
【在 m******3 的大作中提到】
: 这个方法行么
: 记录每一个字符出现的次数，比如count['a']=4, count['b']=2, count['c']=1
: 每次找满足条件的count最大的字符
: 比如，一开始
: 取a, 然后 count['a']-1,变成3
: 下一轮，虽然count['a']是最大，但是不能取，因为上一次取的是'a, 所以，这次取b,
: count['b]-1 变成1
: 然后再取a
: b
: a
|
|
