LeetCode：吃掉 N 个橙子的最少天数

go评论55阅读模式

LeetCode: Minimum Number of Days to Eat N Oranges

问题

``````我今天在Leetcode比赛中遇到了这个问题，我已经为这个问题编写了一段代码，但是它不起作用，有人能告诉我我漏掉了哪些条件吗？

**问题：**

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

**我的解决方案：**

```java
class Solution {
static int Norange(int n, int days){

//没有剩余橘子了
if(n <= 0)
return days;

//天数增加
++days;

//能被2整除
if(n % 2 == 0)
return Math.min(Norange(n - 1 , days), Norange(n/2, days));

//不能被2和3整除
else if( n % 2 != 0 && n % 3 != 0)
return Norange(n - 1, days);

//能被3整除
return Math.min(Norange(n - 1, days), Norange( n - 2*(n/3), days ));
}

public int minDays(int n) {

return Norange(n, 0);

}
}
``````

``````
<details>
<summary>英文:</summary>

I ran into this problem today at the Leetcode contest and I have written a code for that problem but it doesn&#39;t work, Can anyone tell me what conditions am I missing?

Link for the question:[Minimum Number of Days to Eat N Oranges][1]

**Question:-**

There are n oranges in the kitchen and you decided to eat some of these oranges every day as follows:

- Eat one orange.
- If the number of remaining oranges (n) is divisible by 2 then you can eat  n/2 oranges.
- If the number of remaining oranges (n) is divisible by 3 then you can eat  2*(n/3) oranges. You can only choose one of the actions per day.

Return the minimum number of days to eat n oranges.

**My solution:**

class Solution {
static int Norange(int n, int days){

//no more oranges left
if(n &lt;= 0)
return days;

//increment days
++days;

//divisible by 2
if(n % 2 == 0)
return Math.min(Norange(n - 1 , days), Norange(n/2, days));

//not divisible by 2 and 3
else if( n % 2 != 0 &amp;&amp; n % 3 != 0)
return Norange(n - 1, days);

//divisible by 3
return Math.min(Norange(n - 1, days), Norange( n - 2*(n/3), days ));
}

public int minDays(int n) {

return Norange(n, 0);

}
}

***It is not passing the test case for input: 182***

[1]: https://leetcode.com/contest/weekly-contest-202/problems/minimum-number-of-days-to-eat-n-oranges/

</details>

# 答案1
**得分**: 2

```java
static int Norange(int n, int days){

//没有剩余橙子
if(n <= 0)
return days;

//增加天数
++days;

int min = Norange(n - 1 , days);

//被2整除
if(n % 2 == 0)
min = Math.min(min, Norange(n/2, days));

//被3整除
if(n % 3 == 0)
min = Math.min(min, Norange( n - 2*(n/3), days ));

return min;
}
``````

As @WJS remarked in their now-deleted answer, you do not accommodate the case where `n` is divisible by both 2 and 3. To your credit, however, you seem to recognize that a greedy algorithm does not work -- eating just one orange on a given day is sometimes the right move even when there are more than two oranges available. You could accommodate the multiple-of-six issue with a relatively small adjustment to your code:

``````static int Norange(int n, int days){

//no more oranges left
if(n &lt;= 0)
return days;

//increment days
++days;

int min = Norange(n - 1 , days);

//divisible by 2
if(n % 2 == 0)
min = Math.min(min, Norange(n/2, days));

//divisible by 3
if(n % 3 == 0)
min = Math.min(min, Norange( n - 2*(n/3), days ));

return min;
}
``````

Do note, however, that although algorithmically correct, this formulation has terrible performance characteristics as `n` increases, arising from recomputing the same partial results over and over and over. To make it work for moderately large inputs, you will need to employ memoization to avoid that.

For example, `Norange()` could accept an `int` array of length (at least) `n + 1` as an additional argument. The top-level caller would be expected to instantiate that array (default initialization to all-zeroes is fine). Then each `Norange()` call would set element `n` of that array to its final result, and, moreover, would use the partial results recorded there to avoid recursing whenever possible. Details are left as an exercise.

答案2

``````public int minDaysBottomUp(int n) {
if(n < 2) return 1;
int[] dp = new int[n+1];
dp[1] = 1;
dp[2] = 2;

for(int i = 3; i <= n; i++) {
dp[i] = Integer.MAX_VALUE;
}
for(int i = 3; i <= n; i++) {
if(i % 3 == 0 && i % 2 == 0) {
int a = i - 2 * (i / 3);
int b = i - (i / 2);
dp[i] = 1 + Math.min(dp[i-1], Math.min(dp[a], dp[b]));
} else if(i % 3 == 0) {
int a = i - 2 * (i / 3);
dp[i] = 1 + Math.min(dp[i-1], dp[a]);
} else if(i % 2 == 0) {
int b = i - (i / 2);
dp[i] = 1 + Math.min(dp[i-1], dp[b]);
}
dp[i] = Math.min(dp[i], 1 + dp[i-1]);
}
return dp[n];
}
``````

``````Map<Integer, Integer> map = new HashMap<>();
public int minDaysOptimized(int n) {
if(n <= 1) return n;
if(map.containsKey(n)) return map.get(n);

int ans = 1 + Math.min(n % 2 + minDaysOptimized(n / 2), n % 3 + minDaysOptimized(n / 3));
map.put(n, ans);
return ans;
}
``````

It is easier to write bottom up dp solution or same way recursive solution.
But it won't work for larger number.
in that question n could be up to 2x10^9. calculating all the sates in dp would give you TLE.
so, we have to do some kind of pruning. when number is large, it doesn't make sense to eat one orange a day. we can always try to reduce the number to nearest number divisible by 2 or 3; then can consume n/2 or 2*n/3 oranges and take the path which gives minimum number of days.

Here is code for dp bottom up

`````` public int minDaysBottomUp(int n) {
if(n &lt;2)return 1;
int[] dp = new int[n+1];
dp[1] =1;
dp[2] = 2;

for(int i =3; i &lt;=n; i++){
dp[i] =Integer.MAX_VALUE;
}
for(int i=3; i &lt;=n; i++){

if(i%3 ==0 &amp;&amp; i%2 ==0 ){
int a = i-2*(i/3);
int b = i-(i/2);
dp[i] =1+ Math.min(dp[i-1], Math.min(dp[a], dp[b]));
}
else if(i%3==0){
int a = i-2*(i/3);
//   System.out.println(&quot; 3 &quot;+ rem);
dp[i] = 1+ Math.min(dp[i-1], dp[a]);

}else if ( i %2==0){
int b = i-(i/2);

dp[i]= 1+Math.min(dp[i-1], dp[b]);
}
dp[i] = Math.min(dp[i], 1+dp[i-1]);

}
return dp[n];

}
``````

Here is recursive dp with memoization which works for all:

``````  Map&lt;Integer, Integer&gt; map = new HashMap&lt;&gt;();
public int minDaysOptimized(int n){
if(n &lt;=1) return n;
if(map.containsKey(n))return map.get(n);

int ans = 1 + Math.min(n%2 + minDays(n/2), n%3+ minDays(n/3));
map.put(n, ans);
return ans;

}
``````

答案3

``````我认为这样会清晰得多！

public class OrangeInDays {

static int days;

public static void main(String[] args) {

System.out.println(minDays());

}

private static int minDays() {
countDays(293);
return days;
}

public static void countDays(int orng) {

if(orng != 0 ) {
if(orng % 3 == 0) {

orng -= 2 * (orng / 3);

}
else if(orng % 2 == 0 && orng % 3 != 1) {

orng -= orng / 2;
} else if(orng % 2 == 0 && ((orng - 1) / 3) % 2 != 0 && ((orng - 1) / 3) % 3 != 0) {
orng -= orng / 2;
}
else {
orng--;
}

countDays(orng);
days++;
}

}

}
``````

I think this will be much cleaner!

``````public class OrangeInDays {

static int days;

public static void main(String[] args) {

System.out.println(minDays());

}

private static int minDays() {
countDays(293);
return days;
}

public static void countDays(int orng) {

if(orng !=0 ) {
if(orng%3 == 0) {

orng -= 2*(orng/3);

}
else if(orng%2 ==0 &amp;&amp; orng%3 != 1) {

orng -= orng/2;
}else if(orng%2 ==0 &amp;&amp; ((orng-1)/3)%2!=0 &amp;&amp; ((orng-1)/3)%3!=0) {
orng -= orng/2;
}
else {
orng--;
}

countDays(orng);
days++;
}

}

}
``````

• 本文由 发表于 2020年8月16日 21:07:09
• 转载请务必保留本文链接：https://go.coder-hub.com/63437267.html
• java
• recursion

go 56

go 62

go 87

go 51