英文:
LeetCode: Minimum Number of Days to Eat N Oranges
问题
我今天在Leetcode比赛中遇到了这个问题，我已经为这个问题编写了一段代码，但是它不起作用，有人能告诉我我漏掉了哪些条件吗？
问题链接：[吃掉 N 个橘子的最少天数][1]
**问题：**
厨房里有 n 个橘子，你决定按照以下方式每天吃一些橘子：
- 吃掉一个橘子。
- 如果剩余橘子数 (n) 能被 2 整除，那么你可以吃掉 n/2 个橘子。
- 如果剩余橘子数 (n) 能被 3 整除，那么你可以吃掉 2*(n/3) 个橘子。你每天只能选择其中一种行动。
返回吃完 n 个橘子的最少天数。
**我的解决方案：**
```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);
}
}
它无法通过输入为: 182 的测试用例
<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'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 <= 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 && 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
正如@WJS在他们现已删除的答案中指出的那样，您没有考虑到`n`同时被2和3整除的情况。值得赞扬的是，您似乎意识到贪婪算法不起作用——即使有两个以上的橙子可用，某些情况下在某一天只吃一个橙子是正确的选择。您可以通过对代码进行相对较小的调整来解决这个能被六整除的问题：
```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;
}
但要注意，尽管在算法上是正确的，这个公式在n增加时具有糟糕的性能特征，因为会一遍又一遍地重新计算相同的部分结果。为了使其适用于适度大的输入，您需要使用记忆化来避免这种情况。
例如，Norange()可以接受一个至少长度为n + 1的int数组作为额外的参数。顶层调用者应该实例化该数组（默认初始化为全零即可）。然后，每次Norange()调用都会将该数组的第n个元素设置为其最终结果，并且还将使用记录在那里的部分结果在可能的情况下避免递归。具体细节作为练习留给读者。
英文:
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 <= 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
得分: 1
以下是翻译好的内容：
更容易编写自底向上的动态规划解法，或者同样方式的递归解法。
但是对于较大的数字，这不起作用。
在这个问题中，n 可以达到 2x10^9。在动态规划中计算所有状态会导致超时。
因此，我们必须进行某种修剪。当数字很大时，一天吃一个橙子是没有意义的。我们总可以尝试将数字减少到最接近的可被 2 或 3 整除的数字；然后可以消耗 n/2 或 2*n/3 个橙子，并选择给出最少天数的路径。
以下是自底向上的动态规划代码：
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 <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);
// System.out.println(" 3 "+ 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<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 + minDays(n/2), n%3+ minDays(n/3));
map.put(n, ans);
return ans;
}
答案3
得分: -1
我认为这样会清晰得多！
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 && 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++;
}
}
}
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论