<span>leetcode-1414 Find the Minimum Number of Fibonacci Numbers Whose Sum Is K</span>

Given an integer k, return the minimum number of Fibonacci numbers whose sum is equal to k. The same Fibonacci number can be used multiple times.

The Fibonacci numbers are defined as:

F1 = 1
F2 = 1
Fn = Fn-1 + Fn-2 for n > 2.
It is guaranteed that for the given constraints we can always find such Fibonacci numbers that sum up to k.

输入输出实例:

Input: k = 7
Output: 2 
Explanation: The Fibonacci numbers are: 1, 1, 2, 3, 5, 8, 13, ... 
For k = 7 we can use 2 + 5 = 7.

代码:

 1 class Solution:
 2     def findMinFibonacciNumbers(self, k: int) -> int:
 3         F1, F2 = 1, 1
 4         while F2 <= k:
 5             F2, F1 = F2 + F1, F2
 6         num = 0
 7         while F1 > 0:
 8             if k > F2:
 9                 num += 1
10                 k -= F2
11             F2, F1 = F1, F2 - F1
12         return num

 

  

全部评论

相关推荐

每晚夜里独自颤抖:你cet6就cet6,cet4就cet4,你写个cet证书等是什么意思。专业技能快赶上项目行数,你做的这2个项目哪里能提现你有这么多技能呢
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务