2024年5月12日每日一题--1553. 吃掉 N 个橘子的最少天数

https://leetcode.cn/problems/minimum-number-of-days-to-eat-n-oranges/description/

题目分析

方案一

递归求解

class Solution {
    public int minDays(int n) {
        if (n <= 2) return n;
        int[] orange = new int[n + 1];
        orange[1] = 1;
        orange[2] = 2;
        for (int i = 3; i <= n; i++) {
            if(i % 6 == 0) {
                orange[i] = Math.min(Math.min(orange[i / 2], orange[i / 3]), orange[i - 1]) + 1;
            } else if (i % 2 == 0) {
                orange[i] = Math.min(orange[i / 2], orange[i - 1]) + 1;
            } else if (i % 3 == 0) {
                orange[i] = Math.min(orange[i / 3], orange[i - 1]) + 1;
            } else {
                orange[i] = orange[i - 1] + 1;
            }
        }
        return orange[n];
    }
}

结果

超出内存限制

116 / 176 个通过的测试用例

最后执行的输入

n = 61455274

分析

时间复杂度：
O( n )

空间复杂度：
O( n )

方案二

根据题目提示做出的。
提示如下： In each step, choose between 2 options: minOranges = 1 + min( (n%2) + f(n/2), (n%3) + f(n/3) ) where f(n) is the minimum number of days to eat n oranges.

class Solution {
    public int minDays(int n) {
        if (n <= 2) return n;
        return 1 + Math.min((n % 2) + minDays(n / 2), (n % 3) + minDays(n / 3));
        
    }
}

结果

官方题解

https://leetcode.cn/problems/minimum-number-of-days-to-eat-n-oranges/solutions/384947/chi-diao-n-ge-ju-zi-de-zui-shao-tian-shu-by-leetco/