【Leetcode】【每日一题】【中等】1465. 切割后面积最大的蛋糕

这篇具有很好参考价值的文章主要介绍了【Leetcode】【每日一题】【中等】1465. 切割后面积最大的蛋糕。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。


力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台备战技术面试?力扣提供海量技术面试资源,帮助你高效提升编程技能,轻松拿下世界 IT 名企 Dream Offer。https://leetcode.cn/problems/maximum-area-of-a-piece-of-cake-after-horizontal-and-vertical-cuts/description/?envType=daily-question&envId=2023-10-27

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

  •  horizontalCuts[i] 是从矩形蛋糕顶部到第  i 个水平切口的距离
  • verticalCuts[j] 是从矩形蛋糕的左侧到第 j 个竖直切口的距离

请你按数组 horizontalCuts  verticalCuts 中提供的水平和竖直位置切割后,请你找出 面积最大 的那份蛋糕,并返回其 面积 。由于答案可能是一个很大的数字,因此需要将结果  109 + 7 取余 后返回。

【Leetcode】【每日一题】【中等】1465. 切割后面积最大的蛋糕,Leetcode,java,算法,数据结构

自己的思路 

贪心思想,找最大的长和宽,如下图所示,2*2=4即为所求。

【Leetcode】【每日一题】【中等】1465. 切割后面积最大的蛋糕,Leetcode,java,算法,数据结构

可是我感觉该算法有问题,不能同时保证最大的长对应最大的宽。我用下面有问题的代码,通过了Leetcode... 

class Solution {
    public int calMax(int t, int[] data) {
        int h_len = data.length;
        ArrayList arrayList = new ArrayList<>();
        arrayList.add(data[0] - 0);
        arrayList.add(t - data[h_len - 1]);

        for (int i = h_len - 1; i >= 1; i--) {
            arrayList.add(data[i] - data[i - 1]);
        }
        return (Integer)Collections.max(arrayList);
    }

    public int maxArea(int h, int w, int[] horizontalCuts, int[] verticalCuts) {
        Arrays.sort(horizontalCuts);
        Arrays.sort(verticalCuts);
        long x = calMax(h, horizontalCuts);
        long y = calMax(w, verticalCuts);

        return (int) ((x * y) % 1000000007);
    }
}

【Leetcode】【每日一题】【中等】1465. 切割后面积最大的蛋糕,Leetcode,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);
    }
}

结论

这种算法有没有问题,能保证长和宽同时为最大吗?欢迎到评论区讨论。文章来源地址https://www.toymoban.com/news/detail-734425.html

到了这里,关于【Leetcode】【每日一题】【中等】1465. 切割后面积最大的蛋糕的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【LeetCode每日一题】410. 分割数组的最大值

    2024-1-21 410. 分割数组的最大值 思路:二分查找+贪心 利用二分查找法和贪心算法来求解将数组分割为m个非空连续子数组,使得每个子数组的和的最大值最小 首先,我们需要确定二分查找的左右边界。左边界 left 初始化为数组中的最大值,右边界 right 初始化为数组所有元素的

    2024年01月23日
    浏览(38)
  • LeetCode每日一题——1691. 堆叠长方体的最大高度

    题目: 828. 统计子串中的唯一字符 难度: 困难 给你 n 个长方体 cuboids ,其中第 i 个长方体的长宽高表示为 cuboids[i] = [widthi, lengthi, heighti](下标从 0 开始)。请你从 cuboids 选出一个 子集 ,并将它们堆叠起来。 如果 widthi = widthj 且 lengthi = lengthj 且 heighti = heightj ,你就可以将

    2024年02月10日
    浏览(33)
  • ( 数组和矩阵) 485. 最大连续 1 的个数 ——【Leetcode每日一题】

    难度:简单 给定一个二进制数组 nums , 计算其中最大连续 1 的个数。 示例 1: 输入:nums = [1,1,0,1,1,1] 输出:3 解释:开头的两位和最后的三位都是连续 1 ,所以最大连续 1 的个数是 3. 示例 2: 输入:nums = [1,0,1,1,0,1] 输出:2 提示: 1 = n u m s . l e n g t h = 1 0 5 1 = nums.length = 10^5

    2024年02月08日
    浏览(44)
  • LeetCode每日一题——813. 最大平均值和的分组

    题目: 813. 最大平均值和的分组 难度: 普通 给定数组 nums 和一个整数 k 。我们将给定的数组 nums 分成 最多 k 个相邻的非空子数组 。 分数 由每个子数组内的平均值的总和构成。 注意我们必须使用 nums 数组中的每一个数进行分组,并且分数不一定需要是整数。 返回我们所能

    2024年02月13日
    浏览(35)
  • 每日一题——LeetCode1299.将每个元素替换为右侧最大元素

    方法一 个人方法:  题目意思就是求在i=1;i++的循环条件下,arr[i]-arr[arr.length-1]的最大值分别为多少,最后一项默认为-1 用slice方法可以每次把数组第一位去除,得到求最大值的目标数组 Math的max方法可以直接返回数组里的最大值 但是不能每次循环都求一遍目标数组的最大值,

    2024年01月23日
    浏览(54)
  • 2023-08-22 LeetCode每日一题(到最近的人的最大距离)

    点击跳转到题目位置 给你一个数组 seats 表示一排座位,其中 seats[i] = 1 代表有人坐在第 i 个座位上,seats[i] = 0 代表座位 i 上是空的( 下标从 0 开始 )。 至少有一个空座位,且至少有一人已经坐在座位上。 亚历克斯希望坐在一个能够使他与离他最近的人之间的距离达到最大

    2024年02月11日
    浏览(52)
  • LeetCode每日一题:1921. 消灭怪物的最大数量(2023.9.3 C++)

    目录 1921. 消灭怪物的最大数量 题目描述: 实现代码与解析: 贪心 原理思路:         你正在玩一款电子游戏,在游戏中你需要保护城市免受怪物侵袭。给你一个  下标从 0 开始  且长度为  n  的整数数组  dist  ,其中  dist[i]  是第  i  个怪物与城市的  初始距离 (

    2024年02月10日
    浏览(41)
  • (动态规划) 剑指 Offer 42. 连续子数组的最大和 ——【Leetcode每日一题】

    难度:简单 输入一个整型数组,数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。 要求时间复杂度为 O(n) 。 示例1: 输入: nums = [-2,1,-3,4,-1,2,1,-5,4] 输出: 6 解释: 连续子数组 [4,-1,2,1] 的和最大,为 6。 提示 : 1 = a r r . l e n g t h = 1 0 5 1 = arr.length = 10^

    2024年02月11日
    浏览(49)
  • 2023-05-15LeetCode每日一题(按列翻转得到最大值等行数)

    点击跳转到题目位置 给定 m x n 矩阵 matrix 。 你可以从中选出任意数量的列并翻转其上的 每个 单元格。(即翻转后,单元格的值从 0 变成 1,或者从 1 变为 0 。) 返回 经过一些翻转后,行与行之间所有值都相等的最大行数 (1) 首先思考一个问题,如果光给 一行元素 的话,那

    2024年02月05日
    浏览(37)
  • Leetcode每日一题:849. 到最近的人的最大距离(2023.8.22 C++)

    目录 849. 到最近的人的最大距离 题目描述: 实现代码与解析: 双指针 原理思路:         给你一个数组  seats  表示一排座位,其中  seats[i] = 1  代表有人坐在第  i  个座位上, seats[i] = 0  代表座位  i  上是空的( 下标从 0 开始 )。 至少有一个空座位,且至少有一

    2024年02月11日
    浏览(41)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包