Daily Archives: January 17, 2015

package weeklychallenge1;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Set;
import java.util.TreeMap;
import java.util.Map.Entry;

/*
* Given a string, sort its chars by their number of
* appearance in descending order. e.g. input: abcbaa, output: aaabbc.
*/
public class DescendPrint {

/*
* Step1, put all <char, count> in hashMap. This costs O(n) time, O(n) space
* Step2, put all <char, count> to hashTree, as <count, List<char>>. This costs O(nlogn), O(n) space
* Step3, print result from hashTree
* Total time, O(n + nlogn) = O(nlogn)
* Total space, O(n + n) = O(n)
*/
public static void descendPrint(String str){
if(str==null||str.length()==0){
return;
}
//put char count to hashMap
Map<Character, Integer> hm = new HashMap<Character, Integer>();
for(int i=0;i<str.length();i++){
if(!hm.containsKey(str.charAt(i))){
hm.put(str.charAt(i), 1);
continue;
}
int count = hm.get(str.charAt(i));
hm.put(str.charAt(i), ++count);
}
//dump <K,V> from hashmap to treeMap, as <V, Set(K)>
Map<Integer, ArrayList<Character>> tm = new TreeMap<Integer, ArrayList<Character>>(Collections.reverseOrder());
Iterator<Entry<Character, Integer>> itr = hm.entrySet().iterator();
while(itr.hasNext()){
Entry<Character, Integer> hmItem = itr.next();
char ch = hmItem.getKey();
int times = hmItem.getValue();
ArrayList<Character> tmItem = tm.get(times);
if(tmItem==null){    //a new character
tmItem = new ArrayList<Character>();
tmItem.add(ch);
tm.put(times, tmItem);
continue;
}
tmItem.add(ch);
}
//Print result
Set<Entry<Integer, ArrayList<Character>>> resultSets = tm.entrySet();
for(Entry<Integer, ArrayList<Character>> set:resultSets){
int times = set.getKey();
for(char ch:set.getValue()){
for(int i=0;i<times;i++){
System.out.print(ch);
}
}
}
}

public static void main(String[] args) {
String str = “abcccb”;
descendPrint(str);
}
}

package weeklychallenge1;

import java.util.HashMap;
import java.util.Map;

/*
* Given a string, find the char which repeats most.
*/
public class MostRepeatedChar {

/*
* Use a static 65535 to store the appeared times of each char.
* Iterate chs[] one time. Use extra int[65535] space for record char times.
* Time complexity O(n), space complexity O(1)
*/
public static char findMostRepeatedChar1(String str){
if(str==null||str.length()==0){
throw new RuntimeException(“invalid input”);
}
int[] rec = new int[65535];
int bigPos = 0;
for(int i=0;i<str.length();i++){
rec[str.charAt(i)]++;
bigPos = rec[str.charAt(i)]>rec[bigPos]?str.charAt(i):bigPos;
}
return (char)bigPos;
}

/*
* Use hashmap.
* Time complexity O(n), space complexity O(1)
*/
public static char findMostRepeatedChar2(String str){
if(str==null||str.length()==0){
throw new RuntimeException(“invalid input”);
}
Map<Character, Integer> hm = new HashMap<Character, Integer>();
char result = str.charAt(0);
for(int i=0;i<str.length();i++){
if(!hm.containsKey(str.charAt(i))){
hm.put(str.charAt(i), 1);
continue;
}
int currTimes = hm.get(str.charAt(i));
result = (++currTimes>hm.get(result))?str.charAt(i):result;
hm.put(str.charAt(i), ++currTimes);
}
return result;
}

/*
* If the most repeated char appears more than half times in char[]
* Iterate chs 1 time. Use 2 extra integers.
* Time complexity O(n), space complexity O(1)
*/
public static char findMostRepeatedChar3(String str){
if(str==null||str.length()==0){
throw new RuntimeException(“invalid input”);
}
char result = str.charAt(0);
int times = 1;
for(int i = 1; i<str.length(); i++){
if(str.charAt(i)==result){
times++;
continue;
}
times–;
if(times<0){
times = 1;
result = str.charAt(i);
}
}
return result;
}

public static void main(String[] args) {
String str = “12abaa11a”;
char result = findMostRepeatedChar3(str);
System.out.println(result);
}

}