<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

 

  

全部评论

相关推荐

07-08 13:48
门头沟学院 C++
点赞 评论 收藏
分享
06-23 11:28
门头沟学院 Java
牛客91966197...:也有可能是点拒绝的时候自动弹的话术
点赞 评论 收藏
分享
湫湫湫不会java:先投着吧,大概率找不到实习,没实习的时候再加个项目,然后把个人评价和荣誉奖项删了,赶紧成为八股战神吧,没实习没学历,秋招机会估计不多,把握机会。或者说秋招时间去冲实习,春招冲offer,但是压力会比较大
点赞 评论 收藏
分享
练习生懒羊羊:开飞机把这个公司创飞吧
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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