_1414.java

packagecom.fishercoder.solutions.secondthousand;

importjava.util.PriorityQueue;

publicclass_1414 {
publicstaticclassSolution1 {
/*
 * My completely original solution, heap is not really necessary, a regular array/list works out as well.
 */
publicintfindMinFibonacciNumbers(intk) {
PriorityQueue<Integer> maxHeap = newPriorityQueue<>((a, b) -> b - a);
intone = 1;
inttwo = 1;
maxHeap.offer(one);
maxHeap.offer(two);
intthree = one + two;
while (three <= k) {
maxHeap.offer(three);
inttmp = two;
two = three;
one = tmp;
three = one + two;
 }
intminNumbers = 0;
while (k > 0) {
if (maxHeap.contains(k)) {
minNumbers++;
returnminNumbers;
 } else {
while (maxHeap.peek() > k) {
maxHeap.poll();
 }
Integermax = maxHeap.poll();
k -= max;
minNumbers++;
 }
 }
returnminNumbers;
 }
 }
}