Q:
Given a string, sort it in decreasing order based on the frequency of characters.
Example 1:
Input:
"tree"
Output:
"eert"
Explanation:
'e' appears twice while 'r' and 't' both appear once.
So 'e' must appear before both 'r' and 't'. Therefore "eetr" is also a valid answer.
Example 2:
Input:
"cccaaa"
Output:
"cccaaa"
Explanation:
Both 'c' and 'a' appear three times, so "aaaccc" is also a valid answer.
Note that "cacaca" is incorrect, as the same characters must be together.
Example 3:
Input:
"Aabb"
Output:
"bbAa"
Explanation:
"bbaA" is also a valid answer, but "Aabb" is incorrect.
Note that 'A' and 'a' are treated as two different characters.
A:
就是放到PriorityQueue里再取出来。
public class Solution {
public String frequencySort(String s) {
if(s==null || s.length()==0)
return "";
// put to HashMap
Map<Character,Integer> map = new HashMap();
for(char ch : s.toCharArray()){
map.put(ch, (map.containsKey(ch))? map.get(ch)+1: 1);
}
PriorityQueue<Obj> maxQueue = new PriorityQueue<>(map.size(), (A,B)->B.count - A.count);
//from HashMap, put to priorityQueue
for(char ch : map.keySet()){
Obj obj = new Obj(ch, map.get(ch));
maxQueue.add(obj);
}
//build result from PriorityQueue
StringBuffer buf = new StringBuffer();
while( ! maxQueue.isEmpty()) {
Obj node = maxQueue.poll();
for(int i =0;i<node.count;i++)
buf.append(node.ch);
}
return buf.toString();
}
class Obj{
char ch ='a';
int count = 0;
public Obj(char c, int cc){
ch = c;
count = cc;
}
}
}
Errors:
由于PriorityQueue需要的初始capaity 不能小于1。
Given a string, sort it in decreasing order based on the frequency of characters.
Example 1:
Input: "tree" Output: "eert" Explanation: 'e' appears twice while 'r' and 't' both appear once. So 'e' must appear before both 'r' and 't'. Therefore "eetr" is also a valid answer.
Example 2:
Input: "cccaaa" Output: "cccaaa" Explanation: Both 'c' and 'a' appear three times, so "aaaccc" is also a valid answer. Note that "cacaca" is incorrect, as the same characters must be together.
Example 3:
Input: "Aabb" Output: "bbAa" Explanation: "bbaA" is also a valid answer, but "Aabb" is incorrect. Note that 'A' and 'a' are treated as two different characters.
public class Solution { public String frequencySort(String s) { if(s==null || s.length()==0) return ""; // put to HashMap Map<Character,Integer> map = new HashMap(); for(char ch : s.toCharArray()){ map.put(ch, (map.containsKey(ch))? map.get(ch)+1: 1); } PriorityQueue<Obj> maxQueue = new PriorityQueue<>(map.size(), (A,B)->B.count - A.count); //from HashMap, put to priorityQueue for(char ch : map.keySet()){ Obj obj = new Obj(ch, map.get(ch)); maxQueue.add(obj); } //build result from PriorityQueue StringBuffer buf = new StringBuffer(); while( ! maxQueue.isEmpty()) { Obj node = maxQueue.poll(); for(int i =0;i<node.count;i++) buf.append(node.ch); } return buf.toString(); } class Obj{ char ch ='a'; int count = 0; public Obj(char c, int cc){ ch = c; count = cc; } } }
因此,我们需要开始检查s是否为0.
No comments:
Post a Comment