LeetCode中等题之和为 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)

解题思路

  这道题的做法不难,难点在理论上。我们先简单证明一下给定一个正整数k,可以在Fibonacci数列(除第一第二项外严格单调递增)中找到几个数字的和恰恰等于k。给定一个有限的Fibonacci数列a0…ai…an,在此数列中寻找几个数字的和恰好等于k,情况一:ai=k,那么直接返回1就可以;情况二:ai>k,数列里都是正数在ai的后边肯定找不到那几个数求和恰好等于k,那么还需要我们继续往前找直到找到一个数aj使得k刚刚好可以大于aj;情况三:k>ai,这里的情况还需要细分一下,先暂时讨论一下k刚刚好大于ai的情况,假设Fibonacci里的数字只使用一次,将ai作为加数之一,我们仍需要找到剩下的加数使得结果尽可能的成立,也就是在ai前边继续寻找k-ai的可行解,这样的话k-ai作为新的k又可以套这三种情况了。k在迭代的过程中一定是单调递减的且我们这里假定的都是k刚刚好大于ai,那么k-ai一定是小于ai的(反证法:假设k超出ai的部分大于a(i-1),那么按照以上规则则应该是先在ai的后边找符合条件的值)考虑最坏的情况k每次迭代都在当前的前一项找到符合条件的加数,即sum(a0…ai)=k,当k迭代到Fibonacci数列的第二项,如果k刚刚好大于第二项(1)那么第三项(2)就符合情况一了,如果k=1那么直接符合情况一。
  以上证明是在每个斐波那契数字只可以被使用一次的情况下,且由大到小来寻找加数,在这种情况下找到的加数个数肯定是最小的,因为每次我们都是挑选数列里最大的值作为加数。现在证明等效性,即如果在k的迭代中不按照刚刚好大于的规则进行。假设k在迭代中发现了k=2*aj,此时的k需要两个加数就可以直接返回结果,根据Fibonacci数列的特性有:2aj=a(j-1)+a(j-2)+a(j);为了凑我们假设的规则对这个等式进行调整因为a(j-1)+aj=a(j+1),所以原式:2aj=a(j+1)+a(j-2),如果按照我们刚刚好大于的原则,k在当前轮的迭代过程应该找到的加数是a(j+1),这样的话再迭代一轮就找到了a(j-2)同样是两个加数,即k=2aj=a(j-1)+a(j-2)+a(j)和k=a(j+1)+a(j-2)等效,同理三倍(3aj=2(a(j-1)+a(j-2))+aj;2a(j-1)和2a(j-2)同以上操作处理)四倍到N倍也是这样处理。

class Solution:
    def findMinFibonacciNumbers(self, k: int) -> int:
        fib=[1,1]
        while fib[-1]<k:  #记录刚刚好大于k之前的所有Fibonacci数
            fib.append(fib[-1]+fib[-2])
        if k==fib[-1]:  #如果符合情况一直接返回
            return 1
        i=-2
        count=0  #加数个数计数器
        while k>0:
            if k>=fib[i]:
                k-=fib[i]
                i-=1
                count+=1
            else:
                i-=1
        return count

LeetCode中等题之和为 K 的最少斐波那契数字数目

上一篇:MapReduce报错Exception in thread "main" java.lang.UnsatisfiedLinkError: org.apache.hadoop.io


下一篇:hafs简单Api调用