Java Coding Implementations

Question 1

(Medium) Priority Queues

Rank Team by Votes: https://leetcode.com/problems/rank-teams-by-votes/

In a special ranking system, each voter gives a rank from highest to lowest to all teams participated in the competition.

Given an array of strings votes which is the votes of all voters in the ranking systems. Sort all teams according to the ranking system described above.

Example 1:

Input: votes = [“ABC”,”ACB”,”ABC”,”ACB”,”ACB”]

Output: “ACB”

Answer 1

Solution:

1. Form the [26][26] array of all the 26 characters & at the count of votes they got at each possible position.
2. Iterate for each character and add it to a priority Queue with a custom comparator.
3. Poll the top entry and append the char to the result string.

class Solution {
 class RanksComparator implements Comparator<ranks>{ <br> public int compare(Ranks r1, Ranks r2) { <br> for (int i = 1; i &lt; =26; i++){<br> if (r1.value[i] != r2.value[i]){<br> return r2.value[i] - r1.value[i];<br> }<br> }<br> return (r2.ch - r1.ch)*-1;<br> } <br> } <br> <br>class Ranks { <br> public int[] value; <br> public int ch; <br> public Ranks(int[] value, int ch) { <br> this.value = value; <br> this.ch = ch; <br> } <br>} <br> <br> public String rankTeams(String[] votes) {<br> PriorityQueue<ranks> pQueue = new PriorityQueue<ranks>(new RanksComparator()); <br> int[][] ranks= new int[27][27];<br> String cmp =votes[0];<br> <br> for(String vote: votes){<br> for(int i=0; i&lt; vote.length();i++){<br> Character c = vote.charAt(i);<br> ranks[(c-'A')+1][i+1]++;<br> }<br> }</ranks></ranks></ranks>

// 26 \* O(logn)
 for(int r=1; r\< =26;r++){
 if(cmp.indexOf((char)(r+64))!=-1)
 pQueue.add(new Ranks(ranks[r],r));
 }
 // 26 \* O(logn)
 String resStr="";
 while (!pQueue.isEmpty()) {
 Ranks r = pQueue.poll();
 resStr+=(char)(r.ch+64); 
 }
 return resStr;
 }
}

Question 2

Custom comparator can only be used on objects.

https://stackoverflow.com/questions/3699141/how-to-sort-an-array-of-ints-using-a-custom-comparator

Answer 2

final int[] data = new int[] { 5, 4, 2, 1, 3 };

final Integer[] sorted = ArrayUtils.toObject(data);

Arrays.sort(sorted, new Comparator<integer>() {</integer>

public int compare(Integer o1, Integer o2) {

// Intentional: Reverse order for this demo return o2.compareTo(o1);

} });

System.arraycopy(ArrayUtils.toPrimitive(sorted), 0, data, 0, sorted.length);