当前位置: 首页 > news >正文

304. 前缀和技巧中的边界值处理

文章目录

  • 题目
  • 问题
  • 反思

题目

题目如下,其实并不难,属于小而美的前缀和技巧中的体型。因为我之前做过这道题,所以重刷也马上就能写。但是对比我写的和之前看别人写的,明显我的代码不够简洁,一个核心的差异在于对DP数组的定义上。

在这里插入图片描述

问题

先看下我的代码,我对DP数组的定义是:存储以(0,0)为起点,到(i, j)的数组之和。提交代码显示超出时间限制。

两个问题:

  1. 边界条件处理贼麻烦,我自己写的时候也注意到了;(但这不是导致超时的原因)
  2. 处理超时,因为我每次要算一遍DP。
class NumMatrix:def __init__(self, matrix: List[List[int]]):self.matrix = matrixdef sumFromLeftCorner(self):R, C = len(self.matrix), len(self.matrix[0])dp = [[0 for j in range(C)] for i in range(R)]for i in range(R):for j in range(C):if i == 0 and j == 0:dp[i][j] = self.matrix[i][j]elif i == 0:dp[i][j] = dp[i][j-1] + self.matrix[i][j]elif j == 0:dp[i][j] = dp[i-1][j] + self.matrix[i][j]else:dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + self.matrix[i][j]return dpdef sumRegion(self, row1: int, col1: int, row2: int, col2: int) -> int:dp = self.sumFromLeftCorner()if row1 == 0 and col1 == 0:return dp[row2][col2]elif row1 == 0:return dp[row2][col2] - dp[row2][col1 - 1]elif col1 == 0:return dp[row2][col2] - dp[row1 - 1][col2]else:return dp[row2][col2] - dp[row1-1][col2] - dp[row2][col1-1] + dp[row1-1][col1-1]

反思

对于第一个问题:

  1. 边界条件处理贼麻烦,我自己写的时候也注意到了;(但这不是导致超时的原因)

只要改一下DP数组的定义即可:存储以(0,0)为起点,到(i-1, j-1)的数组之和。因此DP数组的长宽都要加1;

对于第二个问题:

  1. 处理超时,因为我每次要算一遍DP。

将DP数组计算的过程放在__init__下面,总是只计算一次,然后重复调用其结果即可/

修改以后的代码如下,明显简洁很多!

class NumMatrix:def __init__(self, matrix: List[List[int]]):self.matrix = matrixself.dp = self.sumFromLeftCorner()def sumFromLeftCorner(self):R, C = len(self.matrix), len(self.matrix[0])dp = [[0 for j in range(C+1)] for i in range(R+1)]for i in range(1, R+1):for j in range(1, C+1):dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + self.matrix[i-1][j-1]return dpdef sumRegion(self, row1: int, col1: int, row2: int, col2: int) -> int:return self.dp[row2+1][col2+1] - self.dp[row1][col2+1] - self.dp[row2+1][col1] + self.dp[row1][col1]

相关文章:

304. 前缀和技巧中的边界值处理

文章目录 题目问题反思 题目 题目如下,其实并不难,属于小而美的前缀和技巧中的体型。因为我之前做过这道题,所以重刷也马上就能写。但是对比我写的和之前看别人写的,明显我的代码不够简洁,一个核心的差异在于对DP数组…...

ios swift5 “Sign in with Apple“(使用苹果登录)怎样接入(第三方登录)集成AppleID登录

文章目录 截图1.在开发者网站的app id中添加Sign in with Apple功能2.在Xcode中添加Sign in with Apple功能3.代码:只有第一次登录的时候可以获取到用户名参考博客chatGPT答案 截图 1.在开发者网站的app id中添加Sign in with Apple功能 1.1 如果你新建app id,记得在…...

时间系列预测总结

转载自:https://mp.weixin.qq.com/s/B1eh4IcHTnEdv2y0l4MCog 拥有一种可靠的方法来预测和预测未来事件一直是人类的愿望。在数字时代,我们拥有丰富的信息,尤其是时间序列数据。 时间序列是指基于时间刻度维度(天、月、年等&…...

NineData创始人CEO叶正盛受邀参加『数据技术嘉年华』的技术大会

4月13日,NineData 创始人&CEO叶正盛受邀参加第13届『数据技术嘉年华』的技术大会。将和数据领域的技术爱好者一起相聚,并分享《NineData在10000公里跨云数据库间实时数据复制技术原理与实践》主题内容。 分享嘉宾 叶正盛,NineData CEO …...

nginx访问路径映射资源目录

Nginx映射资源目录是指在Nginx配置文件中设定规则,使得当客户端向Nginx服务器发送请求访问某个URL时,Nginx能够将该URL映射到服务器本地的实际文件目录,从而正确地提供该目录下的静态资源(如HTML、CSS、JavaScript、图片、视频等文…...

数据挖掘|序列模式挖掘及其算法的python实现

数据挖掘|序列模式挖掘及其算法的python实现 1. 序列模式挖掘2. 基本概念3. 序列模式挖掘实例4. 类Apriori算法(GSP算法)4.1 算法思想4.2 算法步骤4.3 基于Python的算法实现 1. 序列模式挖掘 序列(sequence)模式挖掘也称为序列分析。 序列模式发现&…...

3. Django 初探路由

3. 初探路由 一个完整的路由包含: 路由地址, 视图函数(或者视图类), 可选变量和路由命名. 本章讲述Django的路由编写规则与使用方法, 内容分为: 路由定义规则, 命名空间与路由命名, 路由的使用方式.3.1 路由定义规则 路由称为URL (Uniform Resource Locator, 统一资源定位符)…...

论文笔记:Large Language Models as Analogical Reasoners

iclr 2024 reviewer打分5558 1 intro 基于CoT prompt的大模型能够更好地解决复杂推理问题 然而传统CoT需要提供相关的例子作为指导,这就增加了人工标注的成本——>Zero-shot CoT避免了人工标注来引导推理 但是对于一些复杂的任务难以完成推理,例如c…...

第3章 数据定义语言DDL

文章目录 第3章 DDL语言:数据定义语言3.1 MySQL的数据类型3.2 表的创建:create3.3 表的删除:drop3.4 快速创建表3.5 快速删除表中的数据:truncate3.6 修改表结构:alter 第5章 约束5.1 非空约束:not null5.2…...

C#操作MySQL从入门到精通(7)——对查询数据进行简单过滤

前言 我们在查询数据库中数据的时候,有时候需要剔除一些我们不想要的数据,这时候就需要对数据进行过滤,比如学生信息中,我只需要年龄等于18的,类似这种操作,本文就是详细介绍如何对查询的数据进行初步的过滤。 1、等于操作符 本次查询student_age 等于20的数据,使用我…...

【CVE复现计划】CVE-2024-0195

CVE-2024-0195 简介: SpiderFlow是新一代开源爬虫平台,以图形化方式定义爬虫流程,不写代码即可完成爬虫。基于springbootlayui开发的前后端不分离,也可以进行二次开发。该系统/function/save接口存在RCE漏洞,攻击者可以构造恶意命…...

k8s的ca以及相关证书签发流程

k8s的ca以及相关证书签发流程 1. kube-apiserver相关证书说明2. 生成CA凭证1.1. 生成CA私钥1.2. 生成CA证书 2. 生成kube-apiserver凭证2.1. 生成kube-apiserver私钥2.2. 生成kube-apiserver证书请求2.3. 生成kube-apiserver证书 3. 疑问和思考4. 参考文档 对于网站类的应用&am…...

思迈特软件与上海德拓签署战略合作协议,携手赋能企业数字化转型

3月27日,广州思迈特软件有限公司(简称“思迈特软件”)与上海德拓信息技术有限公司(简称“德拓信息”)正式签约建立战略合作伙伴关系。双方将在数字化转型、数据服务、数据应用以及市场资源等多个领域展开深度合作&…...

【快捷部署】015_Minio(latest)

📣【快捷部署系列】015期信息 编号选型版本操作系统部署形式部署模式复检时间015MiniolatestCentOS 7.XDocker单机2024-04-09 一、快捷部署 #!/bin/bash ################################################################################# # 作者:c…...

<网络安全>《72 微课堂<什么是靶场?>》

1 简介 网络安全靶场是一种模拟真实网络环境的技术或平台。 网络安全靶场基于虚拟化技术,能够模拟网络架构、系统设备、业务流程的运行状态及运行环境,用于支持网络安全相关的学习、研究、检验、竞赛和演习等活动,旨在提高人员及机构的网络…...

Golang | Leetcode Golang题解之第18题四数之和

题目&#xff1a; 题解&#xff1a; func fourSum(nums []int, target int) (quadruplets [][]int) {sort.Ints(nums)n : len(nums)for i : 0; i < n-3 && nums[i]nums[i1]nums[i2]nums[i3] < target; i {if i > 0 && nums[i] nums[i-1] || nums[i]…...

自动驾驶中的传感器融合算法:卡尔曼滤波器和扩展卡尔曼滤波器

自动驾驶中的传感器融合算法&#xff1a;卡尔曼滤波器和扩展卡尔曼滤波器 附赠自动驾驶学习资料和量产经验&#xff1a;链接 介绍&#xff1a; 追踪静止和移动的目标是自动驾驶技术领域最为需要的核心技术之一。来源于多种传感器的信号&#xff0c;包括摄像头&#xff0c;雷达…...

基于ssm的星空游戏购买下载平台的设计与实现论文

摘 要 随着科学技术的飞速发展&#xff0c;各行各业都在努力与现代先进技术接轨&#xff0c;通过科技手段提高自身的优势&#xff0c;商品交易当然也不能排除在外&#xff0c;随着商品交易管理的不断成熟&#xff0c;它彻底改变了过去传统的经营管理方式&#xff0c;不仅使商品…...

DSOX6004A是德科技DSOX6004A示波器

181/2461/8938产品概述&#xff1a; 特点: 是德科技DSOX6004A具有7合1集成功能&#xff0c;结合了数字通道、串行协议分析、内置双通道波形发生器、频率响应分析、内置数字万用表和带累加器的内置10位计数器。1千兆赫至6千兆赫4个模拟通道在12.1英寸电容式多点触摸屏上轻松查…...

golang 使用 cipher、aes 实现 oauth2 验证

在Go语言中&#xff0c;crypto/cipher包提供了加密和解密消息的功能。这个包实现了各种加密算法&#xff0c;如AES、DES、3DES、RC4等&#xff0c;以及相应的模式&#xff0c;如ECB、CBC、CFB、OFB、CTR等。以下是如何使用crypto/cipher包进行加密和解密操作的基本步骤&#xf…...

AI-调查研究-01-正念冥想有用吗?对健康的影响及科学指南

点一下关注吧&#xff01;&#xff01;&#xff01;非常感谢&#xff01;&#xff01;持续更新&#xff01;&#xff01;&#xff01; &#x1f680; AI篇持续更新中&#xff01;&#xff08;长期更新&#xff09; 目前2025年06月05日更新到&#xff1a; AI炼丹日志-28 - Aud…...

【Linux】shell脚本忽略错误继续执行

在 shell 脚本中&#xff0c;可以使用 set -e 命令来设置脚本在遇到错误时退出执行。如果你希望脚本忽略错误并继续执行&#xff0c;可以在脚本开头添加 set e 命令来取消该设置。 举例1 #!/bin/bash# 取消 set -e 的设置 set e# 执行命令&#xff0c;并忽略错误 rm somefile…...

什么是库存周转?如何用进销存系统提高库存周转率?

你可能听说过这样一句话&#xff1a; “利润不是赚出来的&#xff0c;是管出来的。” 尤其是在制造业、批发零售、电商这类“货堆成山”的行业&#xff0c;很多企业看着销售不错&#xff0c;账上却没钱、利润也不见了&#xff0c;一翻库存才发现&#xff1a; 一堆卖不动的旧货…...

python如何将word的doc另存为docx

将 DOCX 文件另存为 DOCX 格式&#xff08;Python 实现&#xff09; 在 Python 中&#xff0c;你可以使用 python-docx 库来操作 Word 文档。不过需要注意的是&#xff0c;.doc 是旧的 Word 格式&#xff0c;而 .docx 是新的基于 XML 的格式。python-docx 只能处理 .docx 格式…...

什么是EULA和DPA

文章目录 EULA&#xff08;End User License Agreement&#xff09;DPA&#xff08;Data Protection Agreement&#xff09;一、定义与背景二、核心内容三、法律效力与责任四、实际应用与意义 EULA&#xff08;End User License Agreement&#xff09; 定义&#xff1a; EULA即…...

Hive 存储格式深度解析:从 TextFile 到 ORC,如何选对数据存储方案?

在大数据处理领域&#xff0c;Hive 作为 Hadoop 生态中重要的数据仓库工具&#xff0c;其存储格式的选择直接影响数据存储成本、查询效率和计算资源消耗。面对 TextFile、SequenceFile、Parquet、RCFile、ORC 等多种存储格式&#xff0c;很多开发者常常陷入选择困境。本文将从底…...

Mysql中select查询语句的执行过程

目录 1、介绍 1.1、组件介绍 1.2、Sql执行顺序 2、执行流程 2.1. 连接与认证 2.2. 查询缓存 2.3. 语法解析&#xff08;Parser&#xff09; 2.4、执行sql 1. 预处理&#xff08;Preprocessor&#xff09; 2. 查询优化器&#xff08;Optimizer&#xff09; 3. 执行器…...

mac:大模型系列测试

0 MAC 前几天经过学生优惠以及国补17K入手了mac studio,然后这两天亲自测试其模型行运用能力如何&#xff0c;是否支持微调、推理速度等能力。下面进入正文。 1 mac 与 unsloth 按照下面的进行安装以及测试&#xff0c;是可以跑通文章里面的代码。训练速度也是很快的。 注意…...

vue3 daterange正则踩坑

<el-form-item label"空置时间" prop"vacantTime"> <el-date-picker v-model"form.vacantTime" type"daterange" start-placeholder"开始日期" end-placeholder"结束日期" clearable :editable"fal…...

pgsql:还原数据库后出现重复序列导致“more than one owned sequence found“报错问题的解决

问题&#xff1a; pgsql数据库通过备份数据库文件进行还原时&#xff0c;如果表中有自增序列&#xff0c;还原后可能会出现重复的序列&#xff0c;此时若向表中插入新行时会出现“more than one owned sequence found”的报错提示。 点击菜单“其它”-》“序列”&#xff0c;…...