LeetCode算法题-Range Addition II(Java实现)

作者 : 开心源码 本文共1189个字,预计阅读时间需要3分钟 发布时间: 2022-05-12 共145人阅读

这是悦乐书的第271次升级,第285篇原创

01 看题和准备

今天详情的是LeetCode算法题中Easy级别的第138题(顺位题号是598)。给定一个m行n列的新二维数组M,其初始值为0。提供一个二维数组ops,每次对M做如下操作,每次从ops中取出一个数组temp,temp里面包含两个整数a和b,使得M[i][j]的元素都自增1,其中0 <= i < a, 0 <= j < b。在遍历完ops中的所有数组后,找出M中值最大的元素的个数。例如:

输入: m = 3, n = 3,ops = [[2,2],[3,3]]

输出: 4

说明: 初始化二维数组M = [[0, 0, 0],[0, 0, 0],[0, 0, 0]],而后取ops中的第一个数组[2,2],也就是0<=i<2,0<=j<2,所以M[0][0],M[0][1],M[1][0],M[1][1]都自加1,此时M=[[1, 1, 0],[1, 1, 0],[0, 0, 0]]。而后取ops中的第二个数组[3,3],表明0<=i<3,0<=j<3,分别对M中的元素加1,此次操作是对数组中所有元素都加1,由于M的下标最大到2,此时M = [[2, 2, 1],[2, 2, 1],[1, 1, 1]],其中2是最大值,出现了4次,所以返回4。

注意:

  • m和n的范围是[1,40000]。

  • a的范围是[1,m],b的范围是[1,n]。

  • ops的范围不超过10,000。

本次解题使用的开发工具是eclipse,jdk使用的版本是1.8,环境是win7 64位系统,使用Java语言编写和测试。

02 解题

通过观察上面的例子,我们可以知道,被加的次数最多的元素值最大,其次数就是坐标范围之积,就是题目要求的M中值最大的元素的个数。例题中,被加次数最多坐标范围是[2,2],这中间有4个数。我们只要要找到每次操作的坐标最小值,即可以锁定操作的最小范围,此范围内的值最大,由于每次都会把该范围内的数加1。题目已经告诉了M的行是m,列是n,而每次操作的坐标的ops中数组的前两位元素,取两者之间的最小行值、列值,最后相乘就是最大值的个数。特殊情况就是,给的ops为null或者者是个空数组,那么值最大的元素值为0,次数就是M的行列之积。

public int maxCount(int m, int n, int[][] ops) {    if (ops == null || ops.length == 0) {        return m*n;    }    for (int[] temp : ops) {        m = Math.min(m, temp[0]);        n = Math.min(n, temp[1]);    }    return m*n;}

03 小结

算法专题目前已日更超过四个月,算法题文章138+篇,公众号对话框回复【数据结构与算法】、【算法】、【数据结构】中的任一关键词,获取系列文章合集。

以上就是一律内容,假如大家有什么好的解法思路、建议或者者其余问题,可以下方留言交流,点赞、留言、转发就是对我最大的回报和支持!

说明
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是摆设,本站源码仅提供给会员学习使用!
7. 如遇到加密压缩包,请使用360解压,如遇到无法解压的请联系管理员
开心源码网 » LeetCode算法题-Range Addition II(Java实现)

发表回复