JAVA练习76-和为 K 的最少斐波那契数字数目
2022/2/3 22:13:24
本文主要是介绍JAVA练习76-和为 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
分析:
方法1:贪心+递归
其实这道题很容易看出 k 的组成数字都有离它最近的斐波那契数字,只要每次找到离它最近的斐波那契数字,然后 k 减去最近的斐波那契数字,再继续找新 k 的最近斐波那契数字,直到 k 为 0,那么找的次数就为最少数目,用一个递归可以轻松解决。但是这些思路都是建立在 k 的组成数字一定有离它最近的数 的基础上,接下来我们来证明这个条件是正确的:
令离 k 最近的数为 Fn,易证 k 的组成一定不含连续数字,因为连续数字加起来就是一个新的斐波那契数字,所以假设 k 的组成不含 Fn,那么 k 的最大值 max 满足:
- 令 max = F(n - 1) + F(n - 3) + ... + F1 (n 为 偶数)或 max = F(n - 1) + F(n - 3) + ... + F2(n 为 奇数)
- 因为 Fn = F(n - 1) + F(n - 2) = F(n - 1) + F(n - 3) + F(n - 4) = F(n - 1) + F(n - 3) + F(n - 5) + ... + F1 + F1(n 为 偶数)或 F(n - 1) + F(n - 3) + F(n - 5) + ... + F2 + F1(n 为 奇数)
- 所以Fn >= max
- 因为 k >= Fn
- 所以在 F(n - ?) 不重复的情况下,一定有 Fn。
下面考虑重复的情况:
- 令 max = F(n - 1) + F(n - 1)
- 因为 F(n - 1) = F(n - 2) + F(n - 3)
- 所以 max = F(n - 1) + F(n - 2) + F(n - 3) = Fn + F(n - 3)
- 所以在重复的情况下,重复的运算式也可以转换为含 Fn 运算式
因此,无论什么情况,k 的组成数字一定有离它最近的斐波那契数字。
时间复杂度:O(log n)
空间复杂度:O(log n)
class Solution { public int findMinFibonacciNumbers(int k) { //如果 k 为 0,返回 0 if(k == 0){ return 0; } //定义当前值,上一值,辅助变量 int cur = 1, pre = 1, temp = 2; //给数组赋值 while(cur <= k){ //计算新的值 temp = cur + pre; //上一值变为当前值 pre = cur; //当前值变为新的值 cur = temp; } //k 减去上一值,继续递归遍历 return findMinFibonacciNumbers(k - pre) + 1; } }
方法2:贪心+迭代
因为 方法1 每次递归都要重复创建斐波那契数列,比较浪费时间,为避免这种情况,我们可以用迭代的方式。因为找斐波那契数列的时候我们定义了记录上一值的变量,那么我们可以反编译斐波那契数列,如果 k 的值大于当前数字,就减去当前数字,继续遍历,直到 k 为 0,然后返回减去的次数即可。
时间复杂度:O(log n)
空间复杂度:O(log n)
class Solution { public int findMinFibonacciNumbers(int k) { //定义当前值,上一值,辅助变量 int cur = 1, pre = 1, temp = 2; //给数组赋值 while(cur <= k){ //计算新的值 temp = cur + pre; //上一值变为当前值 pre = cur; //当前值变为新的值 cur = temp; } //记录数目 int count = 0; //反编译斐波那契数列 while(k > 0){ //当前数字小于等于 k,k 减去当前数字 if(cur <= k){ k -= cur; count++; } //计算上上一值 temp = cur - pre; //当前值变为上一值 cur = pre; //上一值变为上上一值 pre = temp; } //返回计数结果 return count; } }
题目来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/find-the-minimum-number-of-fibonacci-numbers-whose-sum-is-k
这篇关于JAVA练习76-和为 K 的最少斐波那契数字数目的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-09-28微服务架构中API版本控制的实践
- 2024-09-28AI给的和自己写的Python代码,都无法改变输入框的内容,替换也不行
- 2024-09-27Sentinel配置限流资料:新手入门教程
- 2024-09-27Sentinel配置限流资料详解
- 2024-09-27Sentinel限流资料:新手入门教程
- 2024-09-26Sentinel限流资料入门详解
- 2024-09-26Springboot框架资料:初学者入门教程
- 2024-09-26Springboot框架资料详解:新手入门教程
- 2024-09-26Springboot企业级开发资料:新手入门指南
- 2024-09-26SpringBoot企业级开发资料新手指南