[数据结构与算法]贪心 -leetcode-1414. 和为 K 的最少斐波那契数字数目

1414. 和为 K 的最少斐波那契数字数目

题目描述

提示：

• $1<=k<=10^9$

贪心

思路：🤔

1. 先枚举出 [1, k] 内所有的斐波那契数；
2. 然后，找到“最接近 k的斐波那契数”（即，下标为 fabo.size() - 1对应的数，下标记作 index）；
3. 从 index开始，从后向前 贪心枚举每个数：
   • 如果当前斐波那契数 cnt > k，则需要将 index 向前移动，直至 cnt <= k;
   • 否则，需要增加一个步数 res++;（注意：此时 index暂时不变 -> 因为题目说了每个斐波那契数可以重复使用）

class Solution {
    public int findMinFibonacciNumbers(int k) {
    	// 1、枚举出 [1, k] 内所有的斐波那契数；
        List<Integer> fabo = getFabo(k);
        System.out.println(fabo);
        int res = 0;
        int index = -1;
        // for (int i = 0; i < fabo.size() && fabo.get(i) <= k; i++) index = i;
        index = fabo.size() - 1; // 2、最近接k的斐波那契数
        System.out.println("index = " + index);
        // 3、贪心：从大到小
        while (k > 0) {
        	// cnt > k，则需要将 index 向前移动
            while (index > 0 && k < fabo.get(index)) index--;
            // 此时 index暂时不变 -> 因为题目说了每个斐波那契数可以重复使用
            k -= fabo.get(index);
            res++; // 步数加一
        }
        return res;
    }

    public List<Integer> getFabo(int k) {
        // 获取斐波那契数列
        List<Integer> fabo = new ArrayList<>();
        fabo.add(1);
        fabo.add(1);
        int i = 2;
        while (0L + fabo.get(i - 1) + fabo.get(i - 2) <= k) {
            int cnt = fabo.get(i - 1) + fabo.get(i - 2);
            // System.out.println("cnt = " + cnt);
            fabo.add(cnt);
            i++;
        }
        return fabo;
    }
}