LEETCODE 1231. Divide Chocolate 解题思路分析

题目大意:

你有一大块巧克力,它由一些甜度不完全相同的小块组成。我们用数组 sweetness 来表示每一小块的甜度。

你打算和 K 名朋友一起分享这块巧克力,所以你需要将切割 K 次才能得到 K+1 块,每一块都由一些 连续 的小块组成。

为了表现出你的慷慨,你将会吃掉 总甜度最小 的一块,并将其余几块分给你的朋友们。

请找出一个最佳的切割策略,使得你所分得的巧克力 总甜度最大,并返回这个 最大总甜度。

示例 1:

输入:sweetness = [1,2,3,4,5,6,7,8,9], K = 5
输出:6
解释:你可以把巧克力分成 [1,2,3], [4,5], [6], [7], [8], [9]。

示例 2:

输入:sweetness = [5,6,7,8,9,1,2,3,4], K = 8
输出:1
解释:只有一种办法可以把巧克力分成 9 块。

示例 3:

输入:sweetness = [1,2,2,1,2,2,1,2,2], K = 2
输出:5
解释:你可以把巧克力分成 [1,2,2], [1,2,2], [1,2,2]。

提示:

  • 0 <= K < sweetness.length <= 10^4
  • 1 <= sweetness[i] <= 10^5

如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=1231

解题思路分析:

这是一道Hard级别的题目,一开始想到使用DP或者递归加记忆数组的方式解题,结果TLE超时。超时的原因在于本题的数据规模比较大,不适于使用动态规划(如果数据量小一些,DP应该是可行的)。后来想到了二分查找。本题的思路其实有些类似于之前讲过的一道题目:LEETCODE 1201. Ugly Number III 解题思路分析

二分查找本身并不难,但难点在于如何二分。先看题目,我们要把一个巧克力分成N份(N等于K+1),然后将其中甜度最小的一份M分给自己。也就是说,这N份巧克力的甜度肯定都是大于等于M的。因此这道题可以转化为,我们能否找到一个最大的M,使得能够将巧克力分成N份,并且每一份的甜度都大于等于M。M的取值范围在0到总甜度和之间,利用二分查找能够最高效的找到最大的M值。

看下实现代码:

public int maximizeSweetness(int[] sweetness, int K) {
    // 定义二分查找使用的左右指针
    // 初始时左指针为sweetness中最小值,
    // 右指针为sweetness之和
    int right=0,left=Integer.MAX_VALUE;
    for(int sweet : sweetness){
        right+=sweet;
        left=Math.min(left, sweet);
    } 
    int res=0; // 返回结果
    while(left<right){ // 开始二分查找
        int mid=(left+right)/2; // 中间值
        int sum=0; // 当前份的甜度和
        int count=0; // 已分完的份数
        int min=Integer.MAX_VALUE; // 最小甜度
        // 从头开始循环每一块巧克力
        for(int i=0;i<sweetness.length;i++){
            // 累加当前份的甜度和
            sum+=sweetness[i];
            // 当甜度和大于等于mid时,代表可以分出一份
            if(sum>=mid){
                // 更新甜度最小的那一份
                min=Math.min(min, sum);
                // 如果已经分出了K+1份,说明当前mid这个甜度是可行的
                // (剩下没分的部分可以分给任何一份)
                if(++count==K+1){
                    // 更新最大的返回结果
                    res=Math.max(res, min);
                    break; // 退出
                }
                sum=0; // 重置sum,为了计算下一份的甜度和
            }
        }
        // 如果当前mid是可行的(K+1份的甜度都大于等于mid)
        // 说明可以适当加大mid,看看是否还可行
        if(count==K+1){
            left=mid+1;
        }else{ // 反之减小mid找合理解
            right=mid;
        }
    }
    return res;
}

本解法运行时间为10ms。

Runtime: 10 ms, faster than 30.39% of Java online submissions for Divide Chocolate.

Memory Usage: 40.1 MB, less than 100.00% of Java online submissions for Divide Chocolate.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: http://leetcode.jp/leetcode-1231-divide-chocolate-解题思路分析/
此条目发表在leetcode分类目录,贴了, , 标签。将固定链接加入收藏夹。

发表评论

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