5490. 吃掉 N 个橘子的最少天数

太过爱你忘了你带给我的痛 2022-11-27 15:56 11阅读 0赞

## 问题描述： ##

厨房里总共有 n 个橘子，你决定每一天选择如下方式之一吃这些橘子：

吃掉一个橘子。  
如果剩余橘子数 n 能被 2 整除，那么你可以吃掉 n/2 个橘子。  
如果剩余橘子数 n 能被 3 整除，那么你可以吃掉 2\*(n/3) 个橘子。  
每天你只能从以上 3 种方案中选择一种方案。

请你返回吃掉所有 n 个橘子的最少天数。

来源：力扣（LeetCode）  
链接：[https://leetcode-cn.com/problems/minimum-number-of-days-to-eat-n-oranges][https_leetcode-cn.com_problems_minimum-number-of-days-to-eat-n-oranges]

**提示：**

*  `1 <= n <= 2*10^9`

## 解题思路： ##

动态规划

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

但是这里时间和空间都会超出内存

## 记忆化搜索 ##

class Solution {
        Map<Integer,Integer> dp = new HashMap<>();
        public int minDays(int n) {
            dp.put(0,0);
            dp.put(1,1);
            dp.put(2,2);
            if(dp.containsKey(n)) return dp.get(n);
            int res = Math.min(minDays(n/2)+n%2+1,minDays(n/3)+n%3+1);
            dp.put(n,res);
            return dp.get(n);
        }
    }

[https_leetcode-cn.com_problems_minimum-number-of-days-to-eat-n-oranges]: https://leetcode-cn.com/problems/minimum-number-of-days-to-eat-n-oranges

发表评论取消回复

表情：

评论列表（有 0 条评论，11人围观）

还没有评论，来说两句吧...

相关阅读

相关 springboot事务失效：try catch‘吃掉’异常场景

> 我们在写业务逻辑时，对于有些方法逻辑中，可能会抛异常，比如增删改查的dao层接口throws异常，那在service层中调用后我们需要进行try catch捕获异常，不捕获

我会带着你远行/ 2024年04月06日 13:09/ 0 赞/ 40 阅读

相关计算两个日期之间的天数

package hh; import java.util.Calendar; import java.util.Date;

女爷i/ 2024年03月27日 15:20/ 0 赞/ 43 阅读

相关计算两个日期相差天数

计算两个日期相差的天数，看似简单实则可能存在坑方法一（最常用）计算两个日期相差天数，按照自然日算，以00点为分界点 / 计算两个日期

系统管理员/ 2024年03月26日 14:54/ 0 赞/ 39 阅读

相关 leetcond994. 腐烂的橘子

> [牛客华为机试题库【题号 HJ开头】（重点看）][HJ] > [牛客在线编程算法篇【题号NC开头】][NC] > [剑指offer【题号 JZ开头】][offer_

秒速五厘米/ 2024年03月26日 07:13/ 0 赞/ 24 阅读

相关 java计算两个日期之间的天数(java计算两个日期之间的天数算法)

两个日期之间的天数要怎么计算？两个日期之间的天数的计算=日期相减+1。比如:六月一号到六月三号，这之间是3天，分别是:一号、二号、三号，算式:3-1+1=3(天)。同理

落日映苍穹つ/ 2023年09月25日 08:14/ 0 赞/ 40 阅读

相关 leetcode 994腐烂的橘子

在给定的网格中，每个单元格可以有以下三个值之一：值 0 代表空单元格；值 1 代表新鲜橘子；值 2 代表腐烂的橘子。每分钟，任何与腐烂的橘子（在 4 个正

男娘i/ 2023年06月12日 04:18/ 0 赞/ 5 阅读

相关 5490. 吃掉 N 个橘子的最少天数

问题描述：厨房里总共有 n 个橘子，你决定每一天选择如下方式之一吃这些橘子：吃掉一个橘子。如果剩余橘子数 n 能被 2 整除，那么你可以吃掉 n/2 个橘子。

太过爱你忘了你带给我的痛/ 2022年11月27日 15:56/ 0 赞/ 12 阅读

相关被吃掉的Linux内存

在Windows下资源管理器查看内存使用的情况，如果使用率达到80%以上，再运行大程序就能感觉到系统不流畅了，因为在内存紧缺的情况下使用交换分区，频繁地从磁盘上换入换出页会极大

迈不过友情╰/ 2022年06月04日 08:40/ 0 赞/ 134 阅读

相关计算两个日期之间的天数

SimpleDateFormat sdf = new SimpleDateFormat("yyyy-MM-dd");//转换日期格式 Date d1 = sdf.parse(

梦里梦外;/ 2022年05月17日 10:52/ 0 赞/ 677 阅读

相关计算两个日期的天数差

两个日期的天数差，解决这类问题的统一思想是：把原区间问题统一到确定区间上去，如本问题中将特定问题统一到与一个原点时间（0000年01月01日）的天数差，将两个日期与原点的日期天

冷不防/ 2021年12月04日 06:11/ 0 赞/ 551 阅读