我正在尝试解决这个 leetcode 问题

Question

问题：

给定一个数k，return求和等于k的斐波那契数的最少个数，一个斐波数是否可以多次使用

斐波那契数列定义为：

F1 = 1
F2 = 1
Fn = Fn-1 + Fn-2 , for n > 2.

保证对于给定的约束，我们总能找到这样的斐波那契数和k。

Link 提问：

https://leetcode.com/problems/find-the-minimum-number-of-fibonacci-numbers-whose-sum-is-k/

示例：输入：k = 7 输出：2 解释：斐波那契数列是：1, 1, 2, 3, 5, 8, 13, ... 对于 k = 7 我们可以使用 2 + 5 = 7.


    class Solution {
        public int findMinFibonacciNumbers(int count) {
            PriorityQueue<Integer> num=new PriorityQueue<>(Collections.reverseOrder());
          
            int i1=1,i2=1;
            num.add(i1);
            num.add(i2);
            int k=count;
            int i3=0;
            k=k-2;
            int res=0;
            while(k>=1){
                i3=i2+i1;
                num.add(i3);
                int temp=i2;
                i2=i3;
                i1=temp;
                k--;
            }
            while(count!=0){
                int n=num.poll();
                if(n<=count)
                {      res++;
                       count-=n;
                }
            }
            return res;
            
        }
    }

它说 'input=3' 的输出错误。我生成了斐波那契数列并从最高数开始遍历以找到小于或等于总和的数。如果有人帮助我，那将非常有帮助。提前谢谢你。

Answer 1

你可以简单地使用递归来解决这个问题。

这将通过：

class Solution {
    public int findMinFibonacciNumbers(int k) {
        if (k < 2)
            return k;

        int first = 1;
        int second = 1;

        while (second <= k) {
            second += first;
            first = second - first;
        }

        return 1 + findMinFibonacciNumbers(k - first);
    }
}

参考资料

有关其他详细信息，您可以在其中查看 Discussion Board. There are plenty of accepted solutions with a variety of languages and explanations, efficient algorithms, as well as asymptotic time/space complexity analysis^{1, 2}。

如果您正在为 interviews 做准备：

我们想写成bug-free and clean codes based on standards and conventions (e.g., c^{1, 2}, c++^{1, 2}, java^{1, 2}, c#^{1, 2}, python¹, javascript¹, go¹, rust¹)。总的来说，我们希望避免任何可能引起采访争议的事情。
还有其他类似的 platforms，您可能需要熟悉它们，以防您面试使用这些平台的特定公司。

如果您正在练习 contests¹:

尽可能快地编写代码，几乎所有其他事情都是微不足道的。
为easy questions, brute force algorithms usually get accepted. For interviews, brute force is less desired, especially if the question would be an easy级。
对于 medium and hard questions, about 90% of the time, brute force algorithms fail mostly with Time Limit Exceeded (TLE) 和更少内存限制 (MLE) 错误。
参赛者根据 here 解释的算法排名。

我正在尝试解决这个 leetcode 问题

I am trying to solve this leetcode problem

java

fibonacci

参考资料

如果您正在为 interviews 做准备：

如果您正在练习 contests1:

如果您正在练习 contests¹: