1条回答 默认 最新
关注 【相关推荐】
- 这有个类似的问题, 你可以参考下: https://ask.csdn.net/questions/7578627
- 你也可以参考下这篇文章:Python 3爬虫 爬取煎蛋网图片 100%能用 字符串查找 不用正则表达式
- 除此之外, 这篇博客: 算法第四期——前缀和(Python)中的 方法2:二维前缀和(通过70%) 部分也许能够解决你的问题, 你可以仔细阅读以下内容或跳转源博客中阅读:
【思路】
“二维前缀和”,定义s[ ][ ]:
s[i][j]表示子矩阵[1,1] ~ [i,j]的和(1) 预计算出s[ ][ ],然后快速计算二维子区间和
(2)阴影子矩阵[i1,j1] ~ [i2, j2]区间和,等于:s[i2][j2] - s[i2][j1-1] - s[i1-1][j2]+s[i1-1][j1-1](结合上图来理解:绿-红1-红2+蓝)
其中:1、s[i1-1][ j1-1](上图蓝色区域)被减了2次,需要加回来1次。2、s[i2][j1-1]、s[i1-1][j2]和s[i1-1][j1-1]这里的-1是红色和蓝色区域不包括阴影部分。(不-1的话上式会减去阴影部分的一部分)
【复杂度】相比暴力法O(),这里预计算前缀和再求和的总复杂度为O()+O()≈O(),70%的数据,N,M≤100,,刚好可以通过70%。
如果你已经解决了该问题, 非常希望你能够分享一下解决方案, 写成博客, 将相关链接放在评论区, 以帮助更多的人 ^-^解决评论 打赏 举报无用 1
悬赏问题
- ¥15 这个如何解决详细步骤
- ¥15 在微信h5支付申请中,别人给钱就能用我的软件,这个的所属行业是啥?
- ¥30 靶向捕获探针设计软件包
- ¥15 别人给钱就能用我的软件,这个的经营场景是啥?
- ¥15 react-diff-viewer组件,如何解决数据量过大卡顿问题
- ¥20 遥感植被物候指数空间分布图制作
- ¥15 安装了xlrd库但是import不了…
- ¥20 Github上传代码没有contribution和activity记录
- ¥20 SNETCracker
- ¥15 数学建模大赛交通流量控制