题目描述
给你数字 k
,请你返回和为 k
的斐波那契数字的最少数目,其中,每个斐波那契数字都可以被使用多次。
斐波那契数字定义为:
- F1 = 1
- F2 = 1
- Fn = Fn-1 + Fn-2 , 其中 n > 2 。
数据保证对于给定的k
,一定能找到可行解。
样例
输入:k = 7
输出:2
解释:斐波那契数字为:1,1,2,3,5,8,13,……
对于 k = 7 ,我们可以得到 2 + 5 = 7 。
输入:k = 10
输出:2
解释:对于 k = 10 ,我们可以得到 2 + 8 = 10 。
输入:k = 19
输出:3
解释:对于 k = 19 ,我们可以得到 1 + 5 + 13 = 19 。
提示:
- 1 <= k <= 10^9
算法分析
贪心 + 二分
- 1、和为
K
的最少斐波那契数字数目,因此每个斐波那契数字尽可能大 - 2、算出
10^9
以内的所有斐波那契数字,测试过是取到44
, - 3、每次二分找到小于等于
k
的最大值f[l]
,k = k - f[l]
,res ++
时间复杂度$O(logn * 44)$
Java 代码
class Solution {
public int findMinFibonacciNumbers(int k) {
int[] f = new int[1000];
f[0] = 1;
f[1] = 1;
for(int i = 2;i <= 44;i ++)
{
f[i] = f[i - 1] + f[i - 2];
}
int res = 0;
while(k > 0)
{
int l = 0,r = 44;
while(l < r)
{
int mid = l + r + 1 >> 1;
if(f[mid] <= k) l = mid;
else r = mid - 1;
}
k -= f[l];
res ++;
}
return res;
}
}