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

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

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

斐波那契数字定义为:

F1 = 1
F2 = 1
Fn = Fn-1 + Fn-2 , 其中 n > 2 。
数据保证对于给定的 k ,一定能找到可行解。

题目链接:1414. 和为 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

解题思路:

定义一个全局的vector,然后自己写一个函数用来求斐波那契数列一些数的值,然后将这些值放到vector里面,vector里面的最后一个值是在斐波那契数列里面大于k的最小值,即第一个大于k的值。

定义一个变量ans,用来记录需要几个斐波那契数字相加才能得到k

由于斐波那契数列中的数字是非递减序列,因此我们可以采用二分的方法来做.

每次通过二分找出最接近k(<=k)的那个值,然后再将我们的k减去这个值,更新k的值,然后再让ans++。

只要我们的k不等于0,我们就继续用二分去找最接近现在这个k的值,直到我们的k等于0为止。

代码:

class Solution {
    vector<int>f;
public:
        //自己写个求斐波那契数列的函数
        void creat_f(int k)
        {
            f.push_back(1);
            f.push_back(1);
            int a = 1;
            int b = 1;
            int c = 0;
            while(c<=k)
            {
                c = a+b;
                b = a;
                a = c;
                f.push_back(c);
            }
        }

    int findMinFibonacciNumbers(int k) {
        creat_f(k);
        int ans = 0;
        while(k!=0)
        {
            //通过二分查找到每次最接近k的值
            int left = 0,right = f.size()-1;
            while(left<right)
            {
                //这里要向上取整
                int mid = (left+right+1)>>1;
                //如果mid下标值大于k
                //证明我们要找的最接近k的值在[left,mid]这个区间里面,包括mid
                if(f[mid]<=k)
                {
                    left = mid;
                }
                //反之在[left,mid-1]这个区间里面
                else
                {
                    right = mid-1;
                }
            }
            //每次二分完更新k的值
            k-=f[right];
            ans++;
        }
        return ans;
    }
};
上一篇:有效的完全平方数


下一篇:Shell脚本一键部署——源码编译安装LAMP架构!