[数据结构与算法]和为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;
    }
};