<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

 

  

全部评论

相关推荐

nus2201602...:兄弟,你这个简历撕了丢了吧,就是一坨,去找几个项目,理解项目流程,看几遍就是你的了,看看八股就去干了,多看看牛客里别人发出来的简历,对着写,你这写的啥啊,纯一坨
点赞 评论 收藏
分享
07-01 13:37
门头沟学院 Java
steelhead:不是你的问题,这是社会的问题。
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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