Add all cards to PQ, poll a card as the start, check if there is number can make a straight. Remove from PQ. If no such card, return false.
T: O(n*logn) . S: O(n)
public boolean isNStraightHand(int[] hand, int W) {
if (hand == null || hand.length == 0) {
return false;
}
PriorityQueue<Integer> pq = new PriorityQueue<>();
for (int n : hand) {
pq.add(n);
}
while (!pq.isEmpty()) {
int start = pq.poll();
for (int i = 1; i < W; i++) {
if (!pq.remove(start + i)) {
return false;
}
}
}
return true;
}
373. Find K Pairs with Smallest Sums
public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
if (nums1 == null || nums2 == null || nums1.length == 0 || nums2.length == 0) {
return new ArrayList<>();
}
PriorityQueue<int[]> pq = new PriorityQueue<int[]>(new Comparator<int[]>() {
@Override
public int compare(int[] num1, int[] num2) {
int sum1 = num1[0] + num1[1];
int sum2 = num2[0] + num2[1];
return Integer.compare(sum1, sum2);
}
});
for (int i = 0; i < nums1.length; i++) {
pq.offer(new int[]{nums1[i], nums2[0], 0});
}
List<List<Integer>> list = new ArrayList<>();
while (!pq.isEmpty() && k-- > 0) {
int[] curt = pq.poll();
List<Integer> temp = new ArrayList<>();
temp.add(curt[0]);
temp.add(curt[1]);
list.add(temp);
int j = curt[2];
if (j + 1 < nums2.length) {
pq.offer(new int[]{curt[0], nums2[j + 1], j + 1});
}
}
return list;
}
Loop over the numbers, save existing consecutive arrays as range into PQ. Poll pq until find the range can connects to the current number. Start a new range if PQ is empty or pq.peek().end == n (eg.[1,2,3],[3,4,5]). Otherwise connect the range into a longer range.
public boolean isPossible(int[] nums) {
PriorityQueue<Range> pq = new PriorityQueue<>((o1,o2) -> {
if (o1.end == o2.end) {
return o1.range - o2.range;
}
return o1.end - o2.end;
});
for (int n : nums) {
while (!pq.isEmpty() && pq.peek().end + 1 < n) {
if (pq.poll().range < 3) return false;
}
if (pq.isEmpty() || pq.peek().end == n) {
pq.offer(new Range(n, n));
} else {
pq.offer(new Range(pq.poll().start, n));
}
}
while (!pq.isEmpty()) {
if (pq.poll().range < 3) return false;
}
return true;
}
class Range {
int start, end, range;
Range(int s, int e) {
this.start = s;
this.end = e;
this.range = e - s + 1;
}
}
Add all character counts to a maxHeap. Use a separate queue to keep k distance. As pq pops curt, append the char to sb, reduce the count, and add to queue. When queue.size() >= k, it means that the characters keep at least k distance. Put back the values back in maxHeap one by one, like sliding window.
public String rearrangeString(String s, int k) {
int[] counts = new int[26];
for (char c : s.toCharArray()) {
counts[c - 'a']++;
}
PriorityQueue<Pair> pq = new PriorityQueue<>((o1,o2)->(o2.count - o1.count));
for (char c = 'a'; c <= 'z'; c++) {
if (counts[c - 'a'] != 0) pq.offer(new Pair(c, counts[c - 'a']));
}
Queue<Pair> q = new LinkedList<>();
StringBuilder sb = new StringBuilder();
while (!pq.isEmpty()) {
Pair curt = pq.poll();
sb.append(curt.c);
curt.count--;
q.offer(curt);
if (q.size() >= k) {
Pair poll = q.poll();
if (poll.count != 0) pq.offer(poll);
}
}
return sb.length() == s.length() ? sb.toString() : "";
}
class Pair {
char c;
int count;
Pair(char c, int count) {
this.c = c;
this.count = count;
}
}
public String frequencySort(String s) {
Map<Character, Integer> map = new HashMap<>();
for (char c : s.toCharArray()) {
map.put(c, map.getOrDefault(c, 0) + 1);
}
PriorityQueue<Map.Entry<Character,Integer>> pq
= new PriorityQueue<>((o1,o2) -> (o2.getValue() - o1.getValue()));
for (Map.Entry<Character,Integer> e : map.entrySet()) {
pq.add(e);
}
StringBuilder sb = new StringBuilder();
while (!pq.isEmpty()) {
Map.Entry<Character,Integer> curt = pq.poll();
while (curt.getValue() > 0) {
sb.append(curt.getKey());
curt.setValue(curt.getValue() - 1);
}
}
return sb.toString();
}
Use minHeap and maxHeap to store numbers.
addNum: if size of two heap equal, add to minHeap, pop one from minHeap and add to maxHeap. Otherwise, add to maxHeap, pop one to minHeap.
findMedian: If sizes of two heaps equal, return an average from peek of both heaps. Otherwise return from the larger heap.
PriorityQueue<Integer> minHeap;
PriorityQueue<Integer> maxHeap;
public MedianFinder() {
this.minHeap = new PriorityQueue<>();
this.maxHeap = new PriorityQueue<>(new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return o2 - o1;
}
});
}
public void addNum(int num) {
if (minHeap.size() == maxHeap.size()){
minHeap.add(num);
maxHeap.offer(minHeap.poll());
} else {
maxHeap.add(num);
minHeap.offer(maxHeap.poll());
}
}
public double findMedian() {
if (minHeap.size() > maxHeap.size()) return (double) minHeap.peek();
else if (minHeap.size() < maxHeap.size()) return (double) maxHeap.peek();
return ((double) minHeap.peek() + (double) maxHeap.peek()) / 2.0;
}
public List<List<Integer>> getSkyline(int[][] buildings) {
List<List<Integer>> res = new ArrayList<>();
List<int[]> height = new ArrayList<>(); // height list to store all buildings' heights
for (int[] b : buildings) {
height.add(new int[]{b[0], - b[2]}); // start of a building, height stored as negtive
height.add(new int[]{b[1], b[2]}); // end of a building, height stored as positive
}
Collections.sort(height, (a, b) -> (a[0] == b[0] ? a[1] - b[1] : a[0] - b[0])); // sort the height list
// a pq that stores all the encountered buildings' heights in descending order
PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> (b - a));
pq.offer(0);
int preMax = 0;
for (int[] h : height) {
if (h[1] < 0) { // h[1] < 0, that means it meets a new building, so add it to pq
pq.offer(-h[1]);
} else { // h[1] >=0, that means it has reached the end of the building, so remove it from pq
pq.remove(h[1]);
}
// the current max height in all encountered buildings
int curMax = pq.peek();
// if the max height is different from the previous one, that means a critical point is met, add to result list
if (curMax != preMax) {
res.add(Arrays.asList(h[0], curMax));
preMax = curMax;
}
}
return res;
}
Every worker in the paid group should be paid in the ratio of their quality compared to other workers in the paid group.
cost[i] / cost[j] = quality[i] / quality[j]
cost[i] / total cost = quality[i] / total quality
Which means a group of workers share the same "cost[i] / quality[i]", let's call it PAID_RATIO:
PAID_RATIO = total cost / total quality
Sort the workers by paid ratio so that you have the most "efficient worker" (perform best quality and least pay), use maxHeap to and poll the most "inefficient worker" when the total number workers in the group is larger than K. Update the min cost with the updated PAID_RATIO.
public double mincostToHireWorkers(int[] quality, int[] wage, int K) {
Worker[] workers = new Worker[quality.length];
for (int i = 0; i < quality.length; i++) {
workers[i] = new Worker(quality[i], wage[i]);
}
Arrays.sort(workers, new Comparator<Worker>(){
public int compare(Worker w1, Worker w2) {
return Double.compare(w1.ratio, w2.ratio);
}
});
PriorityQueue<Worker> pq = new PriorityQueue<>(new Comparator<Worker>(){
public int compare(Worker w1, Worker w2) {
return w2.quality - w1.quality;
}
});
int totalQuality = 0;
double min = Integer.MAX_VALUE;
for (Worker w : workers) {
if (pq.size() >= K) {
Worker poll = pq.poll();
totalQuality -= poll.quality;
}
pq.offer(w);
totalQuality += w.quality;
if (pq.size() == K) {
min = Math.min(min, totalQuality * w.ratio);
}
}
return min;
}
class Worker {
int quality;
int wage;
double ratio;
Worker(int q, int w) {
this.quality = q;
this.wage = w;
ratio = (double) w / q;
}
}