LWC 68: 767. Reorganize String
LWC 68: 767. Reorganize String
用户1147447
发布于 2019-05-26 07:52:14
发布于 2019-05-26 07:52:14
版权声明：本文为博主原创文章，未经博主允许不得转载。 https://cloud.tencent.com/developer/article/1434489
LWC 68: 767. Reorganize String
Problem:
Given a string S, check if the letters can be rearranged so that two characters that are adjacent to each other are not the same. If possible, output any possible result. If not possible, return the empty string.
Example 1:
Input: S = “aab” Output: “aba”
Example 2:
Input: S = “aaab” Output: “”
Note:
- S will consist of lowercase letters and have length in range 1, 500.
思路：
这是一种选择策略，如果统计字符出现的次数发现，约束出现频次最高的字符在tuple<a, b>中的位置a时，可以保证后续tuple中，位置a上的字符永远不会和前一个tuple中，位置b上的字符出现重复。按照这种约束关系选择到最后，如果还剩下一个字符的频次大于1的情况，说明无法构成Reorganize String。
代码如下：
class P implements Comparable<P>{
int c;
int count;
P(int c, int count){
this.c = c;
this.count = count;
}
@Override
public int compareTo(P o) {
return o.count - this.count;
}
@Override
public String toString() {
return c + "," + count;
}
}
public String reorganizeString(String S) {
P[] ps = new P[32];
for (int i = 0; i < 32; ++i) ps[i] = new P(i, 0);
for (char c : S.toCharArray()) {
int key = c - 'a';
ps[key].count ++;
}
PriorityQueue<P> queue = new PriorityQueue<>();
for (int i = 0; i < 32; ++i) {
if (ps[i].count >= 1)
queue.offer(ps[i]);
}
StringBuilder sb = new StringBuilder();
while (!queue.isEmpty()) {
P fir = queue.poll(); // fir
if (queue.isEmpty()) {
if (fir.count >= 2) return "";
sb.append((char)(fir.c + 'a'));
}
else {
P sec = queue.poll(); // sec
sb.append((char)(fir.c + 'a'));
sb.append((char)(sec.c + 'a'));
fir.count --;
sec.count --;
if (fir.count >= 1) {
queue.offer(fir);
}
if (sec.count >= 1) {
queue.offer(sec);
}
}
}
return sb.toString();
}Python版本：
class Solution(object):
def reorganizeString(self, S):
"""
:type S: str
:rtype: str
"""
from collections import Counter
import heapq
res = ""
pq = []
c = Counter(S)
for key, value in c.items():
heapq.heappush(pq, (-value, key))
while pq:
val_1, key_1 = heapq.heappop(pq)
val_1 = -val_1
if len(pq) == 0:
if val_1 >= 2: return ""
res += key_1
else:
val_2, key_2 = heapq.heappop(pq)
val_2 = -val_2
res += key_1
res += key_2
val_1 -= 1
val_2 -= 1
if val_1 >= 1: heapq.heappush(pq, (-val_1, key_1))
if val_2 >= 1: heapq.heappush(pq, (-val_2, key_2))
return res本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2018年01月21日，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录