python 区域和检索_304. 二维区域和检索（Python）
题目
难度：★★★☆☆
类型：二维数组
方法：动态规划
给定一个二维矩阵，计算其子矩形范围内元素的总和，该子矩阵的左上角为 (row1, col1) ，右下角为 (row2, col2)。
示例:
给定 matrix = [
[3, 0, 1, 4, 2],
[5, 6, 3, 2, 1],
[1, 2, 0, 1, 5],
[4, 1, 0, 1, 7],
[1, 0, 3, 0, 5]
]
sumRegion(2, 1, 4, 3) -> 8
sumRegion(1, 1, 2, 2) -> 11
sumRegion(1, 2, 2, 4) -> 12
说明:
你可以假设矩阵不可变。
会多次调用 sumRegion 方法。
你可以假设 row1 ≤ row2 且 col1 ≤ col2。
解答
题目中的要求，实际上用numpy可以轻松实现：
import numpy as np
class NumMatrix:
def __init__(self, matrix):
self.matrix = np.array(matrix)
def sumRegion(self, row1: int, col1: int, row2: int, col2: int) -> int:
return self.matrix[row1:row2+1, col1:col2+1].sum()
但是，这样做是不文明的。因此我们采用一种动态规划的方法。
定义矩阵dp，维度与matrix一致，dp[r][c]表示从点(0,0)到点(r,c)的区域和。
递推关系式：我们需要一行一行遍历，在遍历的过程中，需要及时获得该行当前点及其左侧所有点的和cur_sum，用于计算递推关系：
对于第一行，直接填充当前点的和cur_sum即可。
其他情况，递推关系为：dp[r][c] = dp[r-1][c] + cur_sum
需要考虑特殊情况：
输入为[[]]：直接返回。
输入只有一行或者只有一列。这种情况都会干扰程序的运行，为此提前在matrix左上角增加一行和一列，全部填充为零。
(0,0)
+----------+--------------+
| A | B |
| | |
+----------+--------------+
| C | D |
+----------+----- -------+(row2, col2)
我们要获得的是D区域的面积，需要通过以下计算得到：
D = (A+B+C+D)-((A+B) + (A+C) - A)
也就是说
dp[row2][col2] - (dp[row2][col1] + dp[row1][col2] - [row1][col1])
这里需要注意一下下标索引可能需要进行+1或者-1的移位，才能获得正确结果。
class NumMatrix:
def __init__(self, matrix):
if not matrix:
self.dp = []
return
matrix = [[0 for _ in range(len(matrix[0])+1)]] + [[0] + row for row in matrix]
dp = [[0 for _ in range(len(matrix[0]))] for _ in range(len(matrix))]
for r in range(len(matrix)):
cur_sum = 0
for c in range(len(matrix[0])):
cur_sum += matrix[r][c]
if r == 0:
dp[r][c] = cur_sum
else:
dp[r][c] = dp[r-1][c] + cur_sum
self.dp = dp
def sumRegion(self, row1: int, col1: int, row2: int, col2: int) -> int:
# row1, col1 = row1-1, col1-1
row2, col2 = row2+1, col2+1
return self.dp[row2][col2] - (self.dp[row2][col1] + self.dp[row1][col2] - self.dp[row1][col1])
如有疑问或建议，欢迎评论区留言~
相关文章：
观察者模式(Observer Pattern)（二）：HeadFirst中的气象站的实现
1 观察者模式的原理，首先由一个主题，当主题发送变化的时候，通知该主题的订阅者 按照上面的分析我们来进行设计 1.抽象主题Subject public interface Subject {public void registerObserver(Observer o);public void removeObserver(Observer…
专访图灵奖得主John Hopcroft：中国必须提升本科教育水平，才能在AI领域赶上美国
AI技术年度盛会即将开启！11月8-9日，来自Google、Amazon、微软、Facebook、LinkedIn、阿里巴巴、百度、腾讯、美团、京东、小米、字节跳动、滴滴、商汤、旷视、思必驰、第四范式、云知声等企业的技术大咖将带来工业界AI应用的最新思维。 如果你是某个AI技…
完整复现何恺明ICCV获奖论文结果并开源 !（附论文开源代码）
ICCV 作为计算机视觉的顶级会议，2017年共收到2143篇论文投稿，比上一届ICCV2015的1698篇增加了26.2%。共621篇被选为大会论文，录用比例28.9%；poster、spotlight、oral 比例分别为24.61%、2.61%和2.09%。组委会根据作者署名统计了不…
电子合同的履行_什么是电子合同履行？怎么履行电子合同？
随着互联网产业的发展，许多传统产业都与互联网接轨，人们的传统生活方式也在转变。现在许多人的各种消费都喜欢在方便、快捷的互联网上进行，就连严肃的合同签订也是如此。不过还有很多人不知道什么是电子合同履行，下面律图小编就为…
10月机器学习开源项目Top10
作者 | Mybridge 译者 | 林春眄 整理 | Jane 出品 | AI科技大本营 【导读】过去一个月里，我们对近 250 个机器学习开源项目进行了排名，并挑选出热度前 10 的项目。这份清单的平均 github star 数量高达 1345，涵盖了包括深度学习, Tensorfl…
用SDM架构Cisco IOS ***图文详解全攻略（一）——easy ***
在测试***的过程中发现网上资料少少，于是自己花点力气写几篇普及教程，希望转贴的朋友给与支持，不要忘记署上原创是水煮豆豆的大名，嘿嘿～Cisco给我们提供了管理路由器的很好的安全工具SDM，同时也给我们提供了…
HP 服务器使用 SmartStart CD 引导安装 windows 2008 操作系统
1. 使用SmartStart CD引导安装之前的准备工作：首先，先根据自己的需要配置好RAID，可以使用开机自检检测到阵列卡时按F8进入ORCA的方法配置，也可以使用SmartStart CD中附带的ACU工具配置。其次，需要确认BIOS中启动顺…
parameter缩略语_缩略语
缩略语AccAccelerate(加速)BFBreakerfailure(断路器失灵)BRCBBuferReportControlBloc(有缓存报告控制块)CIDConfiguredIEDDescription(IED实例配置文件)CTCurrenttransformer(电流互感器)DevDevice(设备)ErrError(错误)FstFirst(第一个)GOOSE,GoGenericobjectorientedsubstatio…
[译]怎样用VisualStudio查看非托管代码
(译者:这篇文章作者是一位美国的MVP,这是他的系列文章"Under the cover"的第一篇,文章的本意从最底层的角度来优化代码的性能,并作为阅读作者其他文章的技术基础,这种通过这样的做法虽然初看起来有些过分,但是对读者了解.Net许多底层运作是十分有益的) 我们从使用vi…
盘点互联网大厂AI战略变迁，开发者将怎样pick前进路线？
随着各大企业相继试水“全面 AI”，人工智能在技术落地层面也开始持续深入，泛人工智能时代正在逼近。越来越多的发展趋势表明，未来的人工智能将逐步迈入广泛普及阶段，继而深入影响人类日常的生产生活方式，重塑传统生产结…
druid拦截器_CMS基于SpringBoot+Shiro+Mybatis+Druid+layui后台管理系统
contentManagerSystem后台管理系统简介contentManagerSystem,后台管理系统,采用SpringBoot构建整个项目框架,apacheShiro权限验证，mybatisdruid数据持久化动作,前端采用layui(http://www.layui.com/)展示，整个项目全部通过注解方式进行配置,具体大家可以…
Boost::asio io_service 实现分析
io_service的作用 io_servie 实现了一个任务队列，这里的任务就是void(void)的函数。Io_servie最常用的两个接口是post和run，post向任务队列中投递任务，run是执行队列中的任务，直到全部执行完毕，并且run可以被N个线程调…
叮！你有一份2018英特尔人工智能大会的邀请函，请查收！
AI赋能的数字化应用，作为时代发展的核心驱动力，已经成为改变各行各业的神奇力量。想要准确把握智能时代的发展航向，领航舵手英特尔已向你发出邀请：2018英特尔人工智能大会，欢迎你的到来！11月14日-15日&…
赢得高薪的锦囊三秘诀
作者：jingch 来源：南京竞成 时间：2007-6-27 10:58:40 秘诀一 获得高薪的必备素质通过对一些高收入的外企白领阶层的调查发现，高学历并不与高收入划等号，高薪收入者的基本素质上的优势才是他们获得高薪的关键。概括起…
可疑文件_【国家标准】印刷文件鉴定技术规范点阵式打印文件的同机鉴定
印刷文件鉴定技术规范(GB/T 37232-2018)总则印刷文件同机(同版)鉴定的受理程序、送检材料的标识、检验鉴定程序、送检材料的流转程序及结果报告程序应按GB/T 37234-2018第4章~第8章中相应的要求。印刷文件同机鉴定分为传统制版文件同机鉴定和办公设备机制文件同机鉴定。其中,办…
前端开发神器之ngrok
ngrok能做什么，为什么是前端开发神器？ 内网穿透，映射本地开发环境到公网，模拟多终端线上环境。 结合一个很简单的PWA demo，举个简单的例子 1.克隆demo到本地 git clone https://github.com/minimal-xyz/minimal-pwa.gi…
YC陆奇发起知乎第一问：怎样的环境才能让更多AI创业公司成功？
“在人工智能时代，怎样的创新环境和措施能让更多科技驱动的创业公司成功，使其不再是大型科技公司的专利？” 一周前，知乎发起了“2018 互联网洞见者”提问，先后邀请到鹅厂厂长马化腾、“风投女王”徐新、香港科技大学杨…
Linq to SQL 资源
Scott Guthrie 的 Linq to SQL 系列：1)介绍http://weblogs.asp.net/scottgu/archive/2007/05/19/using-linq-to-sql-part-1.aspx 2)定义数据模型http://weblogs.asp.net/scottgu/archive/2007/05/29/linq-to-sql-part-2-defining-our-data-model-classes.aspx 3)查询…
首发|机器学习未来十年：你需要把握的趋势和热点
CSDN 出品的《2018-2019 中国人工智能产业路线图》V2.0 版即将重磅面世！ V1.0 版发布以来，我们有幸得到了诸多读者朋友及行业专家的鼎力支持，在此表示由衷感谢。此次 V2.0 版路线图将进行新一轮大升级，力求为读者呈现更全面的中国…
web前端知识点太多_初学web前端，学习方法容易走偏，这是为什么？
一、了解web前端所谓“知己知彼，百战不殆”，在学习web前端之前，还是让我们先了解一下什么是web前端吧！所有用户终端产品与视觉和交互有关的部分，都属于前端开发的领域。从狭义上讲，Web前端就是用HTML、CSS、…
2017-2018 ACM-ICPC, NEERC, Southern Subregional Contest
A. Automatic Door 对于规律的点可以推公式计算，对于噪点则暴力计算，时间复杂度$O(m\log m)$。 #include<stdio.h> #include<iostream> #include<string.h> #include<string> #include<ctype.h> #include<math.h> #…
正则过滤非法字符
小写英文：大写英文：任意数字：限2位小数： 如: 123.12日 期： 如: 2002-9-29任意中文：部分英文： 范围: a,b,c,d,e部分中文： 范围: 一二三四五六七八九十有关正则表达式 ?.只能输入数…
emoji 乱码_这个自制emoji的网站，让你成为永远不输的斗图王者
作为表情界的元老级人物，不管是苹果官网输入法、微信官方表情还是各个主流输入法里，我们都可以从里面找到大量 emoji 表情。然鹅……就算这么多表情，小帮每次发 emoji 时还有有些选择困难。因为翻遍所有表情，都没法找到合适的啊&a…
[vijos1234]口袋的天空最小生成树
题目链接：https://vijos.org/p/1234 白天刚刚写完prim的算法，晚上就心血来潮的打了一道最小生成树的题 虽然有题解说可以用prim做，但是这道题明显是加最小的边，感觉kruskal方便多了 但是愉快的是我竟然不是一次过，最后…
南开大学提出最新边缘检测与图像分割算法，精度刷新记录（附开源地址）
作者 | 刘云、程明明、胡晓伟、边佳旺等 译者 | 刘畅 整理 | Jane 出品 | AI科技大本营 近日，南开大学媒体计算实验室提出的最新边缘检测和图像过分割（可用于生成超像素）被 IEEE PAMI 录用。研究的第一作者也发微博称：“这是第…
修改Vista系统目录权限
例如C:\Windows\System32\DriverStore\FileRepository1. 修改目录所有者右键菜单->Properties->Security->Advanced->Owner->Edit->Other users or groups...输入用户名并确定，勾选Replace owner on subcontainers and objects，一路确…
gitlab安装各种坑
架构：源码安装, 数据库用mysql,网站用nginx 坑一.nginx报错 122016/07/19 09:26:11 [crit] 3881#0: *10 connect() to unix:/home/git/gitlab/tmp/sockets/gitlab-workhorse.socket failed (13: Permission denied) while connecting to upstream, client: 192.168.…
当代的设计潮流是什么_解码“潮流合伙人”IP生意经
每经记者：杜蔚 每经编辑：董兴生11月18日，备受期待的《潮流合伙人2》在成都举办了FOURTRY FAMILY PARTY新品发布日活动，节目的品牌主理人陈伟霆，合伙人欧阳娜娜、范丞丞等纷纷亮相现场，吸引众多人前来围观。…
Loonframwork到SWT的移植测试（JAVA GAME TEST SOURCE）
愚以为，用SWT作界面，是一种在用Java写VB的体验。本周心情极度恶劣，一直不想说话，也不想写新代码，郁闷中尝试了一下将Loonframework的代码移植到SWT。（其实我觉得AWT,SWT,Swing用那个真的要根据需求决定&…
百度大脑发挥AI“头雁效应” 王海峰：在AI时代共同推动社会智能化升级
11月1日，百度大脑作为2018百度世界大会的第一弹登场。 近期国家层面也高度重视人工智能的发展现状和趋势，认为加快发展新一代人工智能是事关我国能否抓住新一轮科技革命和产业变革机遇的战略问题。人工智能技术具有溢出带动性很强的“头雁”效应。百度高…