X

LEETCODE 1414. Find the Minimum Number of Fibonacci Numbers Whose Sum Is K 解题思路分析

题目大意:

和为 K 的最少斐波那契数字数目

给你数字 k ,请你返回和为 k 的斐波那契数字的最少数目,其中,每个斐波那契数字都可以被使用多次。

斐波那契数字定义为:

  • F1 = 1
  • F2 = 1
  • Fn = Fn-1 + Fn-2 , 其中 n > 2 。

数据保证对于给定的 k ,一定能找到可行解。

示例 1:

输入:k = 7
输出:2 
解释:斐波那契数字为:1,1,2,3,5,8,13,……
对于 k = 7 ,我们可以得到 2 + 5 = 7 。

示例 2:

输入:k = 10
输出:2 
解释:对于 k = 10 ,我们可以得到 2 + 8 = 10 。

示例 3:

输入:k = 19
输出:3 
解释:对于 k = 19 ,我们可以得到 1 + 5 + 13 = 19 。

提示:

  • 1 <= k <= 10^9

如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=1414

解题思路分析:

  1. 先求出小于k的所有斐波那契数字,存放至List中。
  2. 用k减去List中小于等于k的最大数字。
  3. 重复第二步,直到k等于0为止,重复的次数即是返回结果。

这道题实际上使用到了贪心算法,即尽量使用大的数字去组合成k,这样才能保证使用的数字个数最少。使用贪心的基础是需要证明该贪心算法的正确性。我在网上看到了一个很好地证明,在这里引用过来仅供参考。


  • 方案中不会包含相邻的数,因为相邻的两个数可以由它们的和代替,从而构造出数目更少的方案。
  • 也不必要包含相同的数,因为f(n)+f(n)=f(n+1)+f(n-2) (n>=2)当n<2时,有f(2)=2f(1)=2f(0);如此可以将方案中所有相同的数都替换掉。
  • 选取小于f(n)的不相邻且不重复的数,其最大和为f(n-1)+f(n-3)+f(n-5)…+1<=f(n)。(n为奇数时直接可以f(0)+f(2)=f(3), f(3)+f(4)=f(5), … ,f(n-2)+f(n-1)=f(n); n为偶数时两边同时加上f(0)开始合并)。因此和为k的最小子数组中一定可以包含刚好不大于k的斐波那契数。例:4=1+3=2+2

实现代码:

public int findMinFibonacciNumbers(int k) {
    List<Integer> nums=new ArrayList<>();
    nums.add(1);
    int n1=1, n2=1;
    while(n1+n2<=k){
        int sum=n1+n2;
        n1=n2;
        n2=sum;
        nums.add(sum);
    }
    int res=0;
    while(k>0){
        for(int i=nums.size()-1;i>=0;i--){
            if(nums.get(i)<=k){
                k-=nums.get(i);
                res++;
                break;
            }
        }
    }
    return res;
}

本题解法执行时间为2ms。

Runtime: 2 ms, faster than 84.70% of Java online submissions for Find the Minimum Number of Fibonacci Numbers Whose Sum Is K.

Memory Usage: 37.1 MB, less than 100.00% of Java online submissions for Find the Minimum Number of Fibonacci Numbers Whose Sum Is K.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: https://leetcode.jp/leetcode-1414-find-the-minimum-number-of-fibonacci-numbers-whose-sum-is-k-解题思路分析/
Categories: leetcode
kwantong: