和为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
解题思路:
定义一个全局的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;
}
};