当前位置:网站首页>模拟卷Leetcode【普通】1414. 和为 K 的最少斐波那契数字数目
模拟卷Leetcode【普通】1414. 和为 K 的最少斐波那契数字数目
2022-07-06 06:15:00 【邂逅模拟卷】
汇总:模拟卷Leetcode 题解汇总
1414. 和为 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
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/find-the-minimum-number-of-fibonacci-numbers-whose-sum-is-k
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
代码:
from leetcode_python.utils import *
class Solution:
def findMinFibonacciNumbers(self, k: int) -> int:
f = [1,1]
while f[-1]<k:f.append(f[-1]+f[-2])
res,i = 0,len(f)-1
while k:
if k>=f[i]:
k-=f[i]
res+=1
i-=1
return res
def test(data_test):
s = Solution()
data = data_test # normal
# data = [list2node(data_test[0])] # list转node
return s.getResult(*data)
def test_obj(data_test):
result = [None]
obj = Solution(*data_test[1][0])
for fun, data in zip(data_test[0][1::], data_test[1][1::]):
if data:
res = obj.__getattribute__(fun)(*data)
else:
res = obj.__getattribute__(fun)()
result.append(res)
return result
if __name__ == '__main__':
datas = [
[],
]
for data_test in datas:
t0 = time.time()
print('-' * 50)
print('input:', data_test)
print('output:', test(data_test))
print(f'use time:{
time.time() - t0}s')
备注:
GitHub:https://github.com/monijuan/leetcode_python
CSDN汇总:模拟卷Leetcode 题解汇总
可以加QQ群交流:1092754609
leetcode_python.utils详见汇总页说明
先刷的题,之后用脚本生成的blog,如果有错请留言,我看到了会修改的!谢谢!
边栏推荐
- Win10 cannot operate (delete, cut) files
- selenium源码通读·9 |DesiredCapabilities类分析
- IDEA 新UI使用
- Coordinatorlayout+nestedscrollview+recyclerview pull up the bottom display is incomplete
- Summary of anomaly detection methods
- 二维码的前世今生 与 六大测试点梳理
- 使用Nacos管理配置
- D - How Many Answers Are Wrong
- 10M25DCF484C8G(FPGA) AMY-6M-0002 BGA GPS模块
- Construction and integration of Zipkin and sleuth for call chain monitoring
猜你喜欢
Properties file
[API interface tool] Introduction to postman interface
VINS-Mono: A Robust and Versatile Monocular Visual-Inertial State Estimator
IPv6 comprehensive experiment
Basic knowledge of error
Database - current read and snapshot read
Postman核心功能解析-参数化和测试报告
Pat (Grade B) 2022 summer exam
Application du Groupe Li dans gtsam
Expose the serial fraudster Liu Qing in the currency circle, and default hundreds of millions of Cheng Laolai
随机推荐
LeetCode 731. 我的日程安排表 II
数学三大核心领域概述:代数
Function of contenttype
数字三角形模型 AcWing 1015. 摘花生
Nodejs realizes the third-party login of Weibo
properties文件
Online and offline problems
Testing and debugging of multithreaded applications
對數據安全的思考(轉載)
win10无法操作(删除、剪切)文件
Commodity price visualization
[leetcode] day96 - the first unique character & ransom letter & letter ectopic word
使用Nacos管理配置
全程实现单点登录功能和请求被取消报错“cancelToken“ of undefined的解决方法
把el-tree选中的数组转换为数组对象
黑猫带你学UFS协议第8篇:UFS初始化详解(Boot Operation)
通过修改style设置打印页样式
10m25dcf484c8g (FPGA) amy-6m-0002 BGA GPS module
Detailed explanation of P problem, NP problem, NPC problem and NP hard problem
isam2运行流程