题目大意：
吃掉 N 个橘子的最少天数
厨房里总共有 n 个橘子，你决定每一天选择如下方式之一吃这些橘子：
- 吃掉一个橘子。
- 如果剩余橘子数
n能被 2 整除，那么你可以吃掉 n/2 个橘子。 - 如果剩余橘子数
n能被 3 整除，那么你可以吃掉 2*(n/3) 个橘子。
每天你只能从以上 3 种方案中选择一种方案。
请你返回吃掉所有 n 个橘子的最少天数。
示例 1：
输入：n = 10 输出：4 解释：你总共有 10 个橘子。 第 1 天：吃 1 个橘子，剩余橘子数 10 - 1 = 9。 第 2 天：吃 6 个橘子，剩余橘子数 9 - 2*(9/3) = 9 - 6 = 3。（9 可以被 3 整除） 第 3 天：吃 2 个橘子，剩余橘子数 3 - 2*(3/3) = 3 - 2 = 1。 第 4 天：吃掉最后 1 个橘子，剩余橘子数 1 - 1 = 0。 你需要至少 4 天吃掉 10 个橘子。
示例 2：
输入：n = 6 输出：3 解释：你总共有 6 个橘子。 第 1 天：吃 3 个橘子，剩余橘子数 6 - 6/2 = 6 - 3 = 3。（6 可以被 2 整除） 第 2 天：吃 2 个橘子，剩余橘子数 3 - 2*(3/3) = 3 - 2 = 1。（3 可以被 3 整除） 第 3 天：吃掉剩余 1 个橘子，剩余橘子数 1 - 1 = 0。 你至少需要 3 天吃掉 6 个橘子。
示例 3：
输入：n = 1 输出：1
示例 4：
输入：n = 56 输出：6
提示：
1 <= n <= 2*10^9
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1553
解题思路分析：
虽然本题是Hard级别，但实际上难度并不大。将题目简单翻译一下，其实我们求的是从n到0的最短距离。关于求解求解最短距离问题，我们之前文章多次讲过，使用bfs深度优先搜索的方式是最为简单有效的。本题也不例外。
解题时，我们首先建立一个bfs用的Queue，初始时，Queue中仅存在元素n。接下来即是标准的bfs逻辑，如果你对bfs的思路不熟悉，强烈建议你参考一下我之前总结过的关于bfs的文章：LEETCODE常见算法之广度优先搜索BFS超详细白话讲解。bfs中，每次取出一个元素之后，如果为0，返回当前bfs步数，如果为1，返回当前步数加一即可。此外，代表当前数字仍需要进一步bfs（继续吃橘子）。如果当前数字可以被3整除，那么将当前数字除以3加入到Queue。如果当前数字可以被2整除，则将当前数字除以2加入到Queue。最后再将当前数字减一加入Queue。
另外做bfs操作时别忘记使用访问数组，以免重复计算。这里我们可以使用是个HashSet记录下已经访问过的节点。
实现代码：
public int minDays(int n) {
Queue<Integer> q=new LinkedList<>(); // BFS用的Queue
q.offer(n); // 初始化，将n加入到queue
int day=0; // 返回结果
Set<Integer> visited = new HashSet<>(); // 访问数组（避免重复访问）
// 以下为标准bfs模板代码
while(q.size()>0){ // 当queue中元素个数大于0，持续循环
int size=q.size(); // 当前queue中元素个数
while(size>0){ // 循环size次结束后，相当于bfs走了一天（向外扩散了一步）
size--;
int num=q.poll(); // 取出一个元素
if(num==0) return day; // 如果为0，返回当前天数
if(num==1) return day+1; // 如果为1，返回当前天数加一
// 如果当前数字可以被3整除，并且num/3没有被访问过
if(num%3==0&&!visited.contains(num/3)){
q.offer(num/3); // 将num/3加入到Queue
visited.add(num/3); // 将num/3加入到已访问过列表
}
// 如果当前数字可以被2整除，并且num/2没有被访问过
if(num%2==0&&!visited.contains(num/2)){
q.offer(num/2);
visited.add(num/2);
}
// 如果num-1没有被访问过
if(!visited.contains(num-1)){
q.offer(num-1);
visited.add(num-1);
}
} // 当前bfs循环结束
day++; // 天数加一
}
return day;
}本题解法执行时间为22ms。
Runtime: 22 ms, faster than 71.43% of Java online submissions for Minimum Number of Days to Eat N Oranges.
Memory Usage: 38.9 MB, less than 71.43% of Java online submissions for Minimum Number of Days to Eat N Oranges.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-1553-minimum-number-of-days-to-eat-n-oranges-解题思路分析/