文档章节

Range Addition II

叶枫啦啦
 叶枫啦啦
发布于 2017/06/26 18:27
字数 389
阅读 19
收藏 0
点赞 0
评论 0

问题:

Given an m * n matrix M initialized with all 0's and several update operations.

Operations are represented by a 2D array, and each operation is represented by an array with two positive integers a and b, which means M[i][j] should be added by one for all 0 <= i < a and 0 <= j < b.

You need to count and return the number of maximum integers in the matrix after performing all the operations.

Example 1:

Input: 
m = 3, n = 3
operations = [[2,2],[3,3]]
Output: 4
Explanation: 
Initially, M = 
[[0, 0, 0],
 [0, 0, 0],
 [0, 0, 0]]

After performing [2,2], M = 
[[1, 1, 0],
 [1, 1, 0],
 [0, 0, 0]]

After performing [3,3], M = 
[[2, 2, 1],
 [2, 2, 1],
 [1, 1, 1]]

So the maximum integer in M is 2, and there are four of it in M. So return 4.

Note:

  1. The range of m and n is [1,40000].
  2. The range of a is [1,m], and the range of b is [1,n].
  3. The range of operations size won't exceed 10,000.

解决:

①只要找到二维坐标的第一个坐标的最小值和第二个坐标的最小值相乘即可;

public class Solution { //6ms
    public int maxCount(int m, int n, int[][] ops) {
        if(ops == null || ops.length == 0) return m * n;
        int minRow = Integer.MAX_VALUE;
        int minCol = Integer.MAX_VALUE;
        for (int op[] : ops) {
            if (minRow > op[0]) minRow = op[0]; 
            if (minCol > op[1]) minCol = op[1];
        }
        return minRow * minCol;
    }
}

② 我首先想到的是这种方法,按照题意依次将对应位置加1,然后遍历数组,查找与arr[0][0]相同的值的个数即可。但是出现了内存不足(Memory Limit Exceeded)。

public class Solution {
    public int maxCount(int m, int n, int[][] ops) {
        int[][] arr = new int[m][n];
        for(int[] op : ops){
            for(int i = 0;i < op[0];i ++){
                for(int j = 0;j < op[1];j ++){
                    arr[i][j] += 1;
                }
            }
        }
        int count = 0;
        for(int i = 0;i < m;i ++){
            for(int j = 0;j < n;j ++){
                if(arr[i][j] == arr[0][0]) count ++;
            }
        }
        return count;
    }
}

© 著作权归作者所有

共有 人打赏支持
叶枫啦啦
粉丝 3
博文 540
码字总数 260604
作品 0
海淀
从「林」开始--C++ primer 读书笔记 -- Part II: Containers ...

从「林」开始--C++ primer 读书笔记 -- Part II: Containers and Algorithms ###################################################### // 声明 : 1 笔记基本都是从《C++ Primer第四版中英文......

ll124884135 ⋅ 2012/04/13 ⋅ 0

python特殊字符

for i in range(100,0,-1): n=0 for ii in range(100,0,-1): n+=1 if (i3+ii4+int('%s'%n)*0.5)==100: print str(i)+'x3+'+str(ii)+'x4+'+str(n)+'x0.5=100' ttt=time.clock() t=ttt-tt prin......

梁选 ⋅ 2013/06/22 ⋅ 2

验证码识别技术二——北京市

大约8个月前,曾经写过一篇关于验证码识别的文章,很久没再更新了,今天再来介绍一下北京市的验证码识别技术。 1、验证码样例 北京市验证码有两种类型,第一种类型是四个字母或数字混合类,如...

东方神剑 ⋅ 2016/11/27 ⋅ 0

debian图形界面启动问题

开始在电脑上装了debian7系统,可以进入桌面,什么都妥妥的。就是安装 xen 之后 如果进入xen 环境,开进准备进入到登陆界面的时候没有反应,只有在桌面左上角有一个光标在动,回车 CTRL +C ...

goh ⋅ 2014/07/03 ⋅ 0

Lintcode54 String to Integer II solution 题解

【题目描述】 Implement function atoi to convert a string to an integer.If no valid conversion could be performed, a zero value is returned.If the correct value is out of the ran......

Winnielyn ⋅ 2017/08/16 ⋅ 0

My Calendar III

问题: Implement a class to store your events. A new event can always be added. Your class will have one method, . Formally, this represents a booking on the half open interval ......

叶枫啦啦 ⋅ 01/18 ⋅ 0

Java int 与 byte的转换 && 0xFF

Java int 与 byte的转换 && 0xFF int -> byte 采用强制类型转换byte 类型的取值范围是 -128~127。当把int转换成byte时,超出这个范围,值就不会相等。 通过InputStream的read()方法获取的int...

秋风醉了 ⋅ 2016/09/29 ⋅ 0

python练习题

表内容有以下列: id,name,age,phone,dept,enrolldate //db1 数据库名 //emp表名 数据库表名和对应文件要关联上。 通过PYTHON脚本模拟实现以下SQL语句: 增删改查 sql>select sql>select fr...

chengpeng21186 ⋅ 2017/05/19 ⋅ 0

继承threading.local引发的内存泄露

python的bug,直到3.2还有: threading.local不释放成员属性,所以如果threading.local实例里引用了threading.local的实例,就不在释放了。 http://bugs.python.org/issue3757 threading.loc...

地中海蒲公英 ⋅ 2014/02/20 ⋅ 0

【转】杰奇 jieqi 多线程自动采集同步源站 python源码

该工具为python代码,对目标源站进行循环采集,同步更新。 采用多线程采集,保证采集速度。采集线程数可根据自己服务器压力自由调整。 采用小说字数比对,仅当当前字数大于已采集字数时才认为...

mayahs ⋅ 2016/08/27 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

AppDelegate 设置Root相关

self.window = UIWindow.init(frame: UIScreen.main.bounds) self.window?.backgroundColor = UIColor.white self.window?.makeKeyAndVisible() self.window?.rootViewController = RootTabB......

west_zll ⋅ 30分钟前 ⋅ 0

Java并发系列5--倒计时器CountDownLatch

今天讲一个倒计时器工具,叫CountDownLatch。需要这个工具的场景大概有:当所有的小任务都完成之后,再启动大任务。 先看代码: public class CountDownLatchDemo {static final CountDow...

大大枣 ⋅ 32分钟前 ⋅ 0

SpreadJS使用进阶指南 - 使用 NPM 管理你的项目

前言 SpreadJS作为一款性能出众的纯前端电子表格控件,自2015年发布以来,已经被广泛应用于各领域“在线Excel”数据管理项目中。NPM,作为管理Node.js库最有力的手段,解决了很多NodeJS代码部...

葡萄城控件技术团队 ⋅ 32分钟前 ⋅ 0

Mac下IntelliJ IDEA快捷键大全

https://blog.csdn.net/lisongjia123/article/details/54949364

细节探索者 ⋅ 35分钟前 ⋅ 0

建造者模式

1、工厂模式中创建的对象大都是简单的对象 复杂的产品类并且拥有不同的属性特点的管理就需要用到建造者模式 2、建造者模式: 将一个复杂的对象的构建与它的表示分离,使得同样的构建过程可以...

职业搬砖20年 ⋅ 37分钟前 ⋅ 0

Mysql数据库开发 怎么优化SQL语句?

 1) 现场抓出慢查询语句 show full processlist;   2) 配置参数:   slow_query_log_file = ON 慢查询开启开关   long_query_time =2 记录大于2秒的sql语句   log_queries_not_usi...

老男孩Linux培训 ⋅ 37分钟前 ⋅ 0

Laravel 安装执行php artisan migrate 出现字段过长错误

最近在自己研究Laravel Laravel版本:5.6 PHP版本:7.1.9 Mysql版本:5.7.19 Apache版本:2.4.27 系统版本:windows10 首先要保证电脑安装了composer,和node.js 执行命令 composer global ...

Marhal ⋅ 42分钟前 ⋅ 0

ELK6.0日志从收集到处理完整版教程(二)

ELK简介 Elasticsearch 开源分布式搜索引擎,它的特点有:分布式,零配置,自动发现,索引自动分片,索引副本机制,restful风格接口,多数据源,自动搜索负载等。也可以认为ElasticSearch是一...

bz_z ⋅ 45分钟前 ⋅ 0

Spark项目之电商用户行为分析大数据平台之(七)数据调研--基本数据结构介绍

目录 一、user_visit_action(Hive表) 1.1 表的结构 1.2 表的说明 二、user_info(Hive表) 2.1 表的结构 2.2 表的说明 三、task(MySQL表) 3.1 表的结构 3.2 表的说明 四、工作流程...

xiaomin0322 ⋅ 50分钟前 ⋅ 0

评分卡模型剖析之一(woe、IV、ROC、信息熵)

信用评分卡模型在国外是一种成熟的预测方法,尤其在信用风险评估以及金融风险控制领域更是得到了比较广泛的使用,其原理是将模型变量WOE编码方式离散化之后运用logistic回归模型进行的一种二...

火力全開 ⋅ 51分钟前 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部