LEETCODE 1553. Minimum Number of Days to Eat N Oranges 解题思路分析

题目大意:

吃掉 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-解题思路分析/
此条目发表在leetcode分类目录,贴了, , 标签。将固定链接加入收藏夹。

发表评论

您的电子邮箱地址不会被公开。