首页 > 编程语言 >【算法题】割后面积最大的蛋糕

【算法题】割后面积最大的蛋糕

时间:2023-10-30 12:34:45浏览次数:42  
标签:pre verticalCuts int res horizontalCuts 算法 蛋糕 割后


题目:

矩形蛋糕的高度为 h 且宽度为 w,给你两个整数数组 horizontalCuts 和 verticalCuts,其中:

horizontalCuts[i] 是从矩形蛋糕顶部到第 i 个水平切口的距离
verticalCuts[j] 是从矩形蛋糕的左侧到第 j 个竖直切口的距离
请你按数组 horizontalCuts 和 verticalCuts 中提供的水平和竖直位置切割后,请你找出 面积最大 的那份蛋糕,并返回其 面积 。由于答案可能是一个很大的数字,因此需要将结果 对 109 + 7 取余 后返回。

示例 1:

【算法题】割后面积最大的蛋糕_职场和发展

输入:h = 5, w = 4, horizontalCuts = [1,2,4], verticalCuts = [1,3]
输出:4
解释:上图所示的矩阵蛋糕中,红色线表示水平和竖直方向上的切口。切割蛋糕后,绿色的那份蛋糕面积最大。

示例 2:

【算法题】割后面积最大的蛋糕_Math_02


输入:h = 5, w = 4, horizontalCuts = [3,1], verticalCuts = [1]

输出:6

解释:上图所示的矩阵蛋糕中,红色线表示水平和竖直方向上的切口。切割蛋糕后,绿色和黄色的两份蛋糕面积最大。

示例 3:

输入:h = 5, w = 4, horizontalCuts = [3], verticalCuts = [3]
输出:9

提示:

2 <= h, w <= 10^9
1 <= horizontalCuts.length <= min(h - 1, 10^5)
1 <= verticalCuts.length <= min(w - 1, 10^5)
1 <= horizontalCuts[i] < h
1 <= verticalCuts[i] < w
题目数据保证 horizontalCuts 中的所有元素各不相同
题目数据保证 verticalCuts 中的所有元素各不相同

java代码:

class Solution {
    public int maxArea(int h, int w, int[] horizontalCuts, int[] verticalCuts) {
        Arrays.sort(horizontalCuts);
        Arrays.sort(verticalCuts);
        return (int) ((long) calMax(horizontalCuts, h) * calMax(verticalCuts, w) % 1000000007);
    }

    public int calMax(int[] arr, int boardr) {
        int res = 0, pre = 0;
        for (int i : arr) {
            res = Math.max(i - pre, res);
            pre = i;
        }
        return Math.max(res, boardr - pre);
    }
}


标签:pre,verticalCuts,int,res,horizontalCuts,算法,蛋糕,割后
From: https://blog.51cto.com/u_6813689/8087451

相关文章

  • 【算法题】2909. 元素和最小的山形三元组 II
    题目:给你一个下标从0开始的整数数组nums。如果下标三元组(i,j,k)满足下述全部条件,则认为它是一个山形三元组:i<j<knums[i]<nums[j]且nums[k]<nums[j]请你找出nums中元素和最小的山形三元组,并返回其元素和。如果不存在满足条件的三元组,返回-1。示例1:......
  • 【算法题】合法分组的最少组数
    题目:给你一个长度为n下标从0开始的整数数组nums。我们想将下标进行分组,使得[0,n-1]内所有下标i都恰好被分到其中一组。如果以下条件成立,我们说这个分组方案是合法的:对于每个组g,同一组内所有下标在nums中对应的数值都相等。对于任意两个组g1和g2,两个组中下......
  • 【算法题】1402. 做菜顺序
    题目:一个厨师收集了他n道菜的满意程度satisfaction,这个厨师做出每道菜的时间都是1单位时间。一道菜的「like-time系数」定义为烹饪这道菜结束的时间(包含之前每道菜所花费的时间)乘以这道菜的满意程度,也就是time[i]*satisfaction[i]。返回厨师在准备了一定数量的菜肴后可......
  • 【算法题】得到K个半回文串的最小修改次数
    题目:给你一个字符串s和一个整数k,请你将s分成k个子字符串,使得每个子字符串变成半回文串需要修改的字符数目最少。请你返回一个整数,表示需要修改的最少字符数目。注意:如果一个字符串从左往右和从右往左读是一样的,那么它是一个回文串。如果长度为len的字符串存在......
  • 【算法题】统计无向图中无法互相到达点对数
    题目:给你一个整数n,表示一张无向图中有n个节点,编号为0到n-1。同时给你一个二维整数数组edges,其中edges[i]=[ai,bi]表示节点ai和bi之间有一条无向边。请你返回无法互相到达的不同点对数目。示例1:输入:n=3,edges=[[0,1],[0,2],[1,2]]输出:0解释:所......
  • 基于多尺度分形残差注意力网络的超分辨率重建算法
    1.引言深度神经网络可以显著提高超分辨率的质量,但现有方法难以充分利用低分辨率尺度特征和通道信息,从而阻碍了卷积神经网络的表达能力。针对此类问题,本章提出了一种多尺度分形残差注意力网络(Multi-scaleFractalResidualAttentionNetwork,MFRAN)。具体而言,MFRAN由分形残差块(Fra......
  • 算法:实现中序遍历(3种方法图例详解,小白也能看懂)
     中序遍历:左->中 ->右练习地址:力扣(LeetCode)官网-全球极客挚爱的技术成长平台1、递归法 #Definitionforabinarytreenode.classTreeNode(object):def__init__(self,val=0,left=None,right=None):self.val=valself.left=left......
  • 【智能优化算法】开普勒优化算法KOA附matlab代码
    ✅作者简介:热爱科研的Matlab仿真开发者,修心和技术同步精进,代码获取、论文复现及科研仿真合作可私信。......
  • 去雨去雪去雾算法运行问题汇总记录
    问题一在进行去雨去雪去雾算法过程中,遇到了一个问题,这在先前的电脑运行是都没有出现过,但在博主新买的电脑上却出现了,讲道理是有点小抑郁的。RuntimeWarning:invalidvalueencounteredinscalardivideret=ret.dtype.type(ret/rcount)NaNorInffoundininputtensor.......
  • 国密sm4算法
    一、概述国密算法定义:即国家密码局认定的国产密码算法。通过定义我们可以知道,国密算法有两个要素:1、国家密码局认定在国家密码局官网上,可以看到由其发布的标准规范。2、密码算法首先知道什么是密码,密码就是将正常的信息加密后变为无法正常识别的编码,可以认为是一种混淆......