AntonLagankin
BAN USERpublic class RangesRank {
private static TreeSet<RangeHolder> sortedRanges;
private static List<RangeHolder> buffer;
public static void main(String[] args) {
sortedRanges = new TreeSet<RangeHolder>();
sortedRanges.add(new RangeHolder(1.0, 5.0));
sortedRanges.add(new RangeHolder(2.0, 3.0));
sortedRanges.add(new RangeHolder(3.5, 4.0));
sortedRanges.add(new RangeHolder(2.5, 3.75));
buffer = new LinkedList<RangeHolder>();
for (RangeHolder range : sortedRanges) {
checkStack(range);
}
RangeHolder range = Collections.max(sortedRanges, new Comparator<RangeHolder>() {
@Override
public int compare(RangeHolder rangeHolder, RangeHolder rangeHolder2) {
return rangeHolder.getRank() - rangeHolder2.getRank();
}
});
System.out.println(range);
}
private static void checkStack(RangeHolder holder) {
Iterator<RangeHolder> iter = buffer.iterator();
while (iter.hasNext()) {
RangeHolder range = iter.next();
if (range.getSecond() < holder.getFirst()) {
iter.remove();
}
else {
range.increaseRank();
}
}
buffer.add(holder);
}
private static class RangeHolder implements Comparable<RangeHolder> {
private double first;
private double second;
private int rank;
public RangeHolder(double first, double second) {
this.first = first;
this.second = second;
this.rank = 0;
}
public double getFirst() {
return first;
}
public double getSecond() {
return second;
}
public void increaseRank() {
this.rank++;
}
public int getRank() {
return this.rank;
}
@Override
public int compareTo(RangeHolder rangeHolder) {
if (this.first == rangeHolder.first) {
if (this.second > rangeHolder.second) {
return 1;
}
else if (this.second < rangeHolder.second) {
return -1;
}
return 0;
}
return this.first > rangeHolder.first ? 1 : -1;
}
@Override
public String toString() {
return "RangeHolder{" +
"first=" + first +
", second=" + second +
", rank=" + rank +
'}';
}
}
}
It is assumed that all letters from the first word are in the second one.
public class Main {
public static void main(String[] args) {
String firstWord = "ThisWord";
String secondWord = "drowSiht";
Map<Character, Integer> orderMap = buildOrderMap(firstWord);
Set<CharWrapper> sortedWord = buildSortedWord(secondWord, orderMap);
System.out.println(sortedWord);
}
private static Map<Character, Integer> buildOrderMap(String word) {
Map<Character, Integer> resultMap = new HashMap<Character, Integer>();
int order = 0;
for (char c : word.toLowerCase().toCharArray()) {
resultMap.put(c, order++);
}
return resultMap;
}
private static Set<CharWrapper> buildSortedWord(String word, Map<Character, Integer> orderMap) {
Set<CharWrapper> result = new TreeSet<CharWrapper>();
for (char c : word.toLowerCase().toCharArray()) {
result.add(new CharWrapper(c, orderMap.get(c)));
}
return result;
}
private static class CharWrapper implements Comparable<CharWrapper> {
private char letter;
private int orderNum;
public CharWrapper(char letter, int orderNum) {
this.letter = letter;
this.orderNum = orderNum;
}
public char getLetter() {
return letter;
}
public int getOrderNum() {
return orderNum;
}
@Override
public int compareTo(CharWrapper charWrapper) {
return this.getOrderNum() - charWrapper.getOrderNum();
}
@Override
public String toString() {
return getLetter() + "";
}
}
}
Why not a some kind of set? For instance HashSet. From my point countries can't duplicate. And in this case HashSet should be fine because the first query can be addressed in O(n) in worst case but in average it should be faster than in LinkedList. The same is for states and cities.
- AntonLagankin July 25, 2013