LeetCode 767.重构字符串
程序员文章站
2024-03-16 16:52:58
...
给定一个字符串S
,检查是否能重新排布其中的字母,使得两相邻的字符不同。
若可行,输出任意可行的结果。若不可行,返回空字符串。
示例 1:
输入: S = "aab"
输出: "aba"
示例 2:
输入: S = "aaab"
输出: ""
注意:
S 只包含小写字母并且长度在[1, 500]区间内。
通过次数13,259
提交次数30,089
思路:基于计数的贪心算法:按照每个字符出现的频率进行排序,因此当字符相同时会连续出现,每隔一个位置插入一个字符,并且保证出现次数最多的字母排在最后并从小到大排序即可。
class Solution {
public String reorganizeString(String S) {
int len=S.length();
int[] nums=new int[26];
for(char c : S.toCharArray())
nums[c-'a']+=100;
for(int i=0;i<26;i++)
nums[i]+=i;
Arrays.parallelSort(nums);
int t=1;
char[] ans=new char[len];
for(int num : nums) {
int ct=num/100;
char ch=(char)('a'+(num%100));
if(ct>(len+1)/2) return "";
for(int i=0;i<ct;i++) {
if(t>=len) t=0;
ans[t]=ch;
t+=2;
}
}
return new String(ans);
}
}
推荐阅读
-
LeetCode 767.重构字符串
-
[leetCode]767. 重构字符串
-
leetcode 767. 重构字符串
-
leetcode——767.重构字符串
-
leetcode 767.重构字符串
-
每天一道LeetCode-----给定字符串s和字符数组words,在s中找到words出现的位置,words内部字符串顺序无要求
-
LeetCode 151. 翻转字符串里的单词
-
LeetCode[字符串] - #3 Longest Substring Without Repeating Characters 博客分类: LeetCode LeetCodeJavaAlgorithm题解String
-
Leetcode 443: 压缩字符串
-
LeetCode 443. 压缩字符串