【算法挨揍日记】day16——525. 连续数组、1314. 矩阵区域和

 525. 连续数组

525. 连续数组

 题目描述:

给定一个二进制数组 nums , 找到含有相同数量的 0 和 1 的最长连续子数组,并返回该子数组的长度。

解题思路:

本题的元素只有0和1,根据题目意思,我们可以把题目看成找一段最长的子区间使得区间的0

和1的数量相同,我们可以对其优化将所有的0变成-1,这样这段区间的和就为0

也就是转化为在【0,i-1】这个区间内最长的和为0的子数组

我们依旧可以利用哈希表hash,我们还得处理一下默认前缀和为0的时候等于-1的时候 

长度的计算:

解题思路: 

class Solution {
public:int findMaxLength(vector<int>& nums) {unordered_map<int,int>hash;hash[0]=-1;int ret=0,sum=0;for(int i=0;i<nums.size();i++){sum+=nums[i]==0?-1:1;if(hash.count(sum))ret=max(ret,i-hash[sum]);else hash[sum]=i;}return ret;}
};

 1314. 矩阵区域和

1314. 矩阵区域和

题目描述:

给你一个 m x n 的矩阵 mat 和一个整数 k ,请你返回一个矩阵 answer ,其中每个 answer[i][j] 是所有满足下述条件的元素 mat[r][c] 的和: 

  • i - k <= r <= i + k,
  • j - k <= c <= j + k 且
  • (r, c) 在矩阵内。

 

解题思路: 

本题我们还是使用前缀和+哈希表,不过是二维前缀和

 因为本题的计算的下标的范围可能会越界,因此我们可以min和max函数就行解决,这里的+1是因为需要进行下标匹配,下标匹配下面会讲;

 有个细节需要注意就是:

我们的mat数组是从0开始的,而我们的前缀和数组dp是从1开始,而我们返回的数组ans是从0开始的

因为力扣进行结果判断的时候需要从0开始,不然本题更加简单

解题代码: 

class Solution {
public:vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int k) {int n=mat.size();int m=mat[0].size();vector<vector<int>> dp(n+1,vector<int>(m+1));for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)dp[i][j]=dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1]+mat[i-1][j-1];vector<vector<int>> ans(n,vector<int>(m));for(int i=0;i<n;i++){for(int j=0;j<m;j++){int x1=max(0,i-k)+1;int y1=max(0,j-k)+1;int x2=min(n-1,i+k)+1;int y2=min(m-1,j+k)+1;ans[i][j]=dp[x2][y2]-dp[x2][y1-1]-dp[x1-1][y2]+dp[x1-1][y1-1];}}return ans;}
};

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/161276.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

DirectX3D 正交投影学习记录

所谓正交投影变换&#xff0c;就是已知盒状可视空间内任意点坐标(x,y,z)&#xff0c;求解垂直投影到xy平面的对应点坐标。 按照这个定义&#xff0c;xyz坐标系本身就是正交坐标系&#xff0c;盒状可视空间内任意点的坐标(x,y,z)投影到(x,y)平面&#xff0c;只要简单地丢弃z坐标…

如何使用前端框架(React、Angular、Vue.js等)?该如何选择?

聚沙成塔每天进步一点点 ⭐ 专栏简介 前端入门之旅&#xff1a;探索Web开发的奇妙世界 欢迎来到前端入门之旅&#xff01;感兴趣的可以订阅本专栏哦&#xff01;这个专栏是为那些对Web开发感兴趣、刚刚踏入前端领域的朋友们量身打造的。无论你是完全的新手还是有一些基础的开发…

SLAM从入门到精通(dwa算法)

【 声明&#xff1a;版权所有&#xff0c;欢迎转载&#xff0c;请勿用于商业用途。 联系信箱&#xff1a;feixiaoxing 163.com】 要说搜路算法&#xff0c;这个大家都比较好理解。毕竟从一个地点走到另外一个地点&#xff0c;这个都是直觉上可以感受到的事情。但是这条道路上机…

基于SSM的视频播放系统的设计与实现

末尾获取源码 开发语言&#xff1a;Java Java开发工具&#xff1a;JDK1.8 后端框架&#xff1a;SSM 前端&#xff1a;Vue 数据库&#xff1a;MySQL5.7和Navicat管理工具结合 服务器&#xff1a;Tomcat8.5 开发软件&#xff1a;IDEA / Eclipse 是否Maven项目&#xff1a;是 目录…

NSS [GWCTF 2019]枯燥的抽奖

NSS [GWCTF 2019]枯燥的抽奖 开题让我猜字符串&#xff0c;这种题目肯定不是猜&#xff0c;应该是类似于php伪随机数。 dirsearch扫他一下。 访问/check.php得到源码。 分析一下代码。 通过PHP伪随机数从字符库$str_long1中选取20个字符组成字符串&#xff0c;返回给我们前十…

UE5 运行时生成距离场数据

1.背景 最近有在运行时加载模型的需求&#xff0c;使用DatasmithRuntimeActor可以实现&#xff0c;但是跟在编辑器里加载的模型对比起来&#xff0c;室内没有Lumen的光照效果。 图1 编辑器下加载模型的效果 图2 运行时下加载模型的效果 然后查看了距离场的数据&#xff0c;发现…

【扩散模型从原理到实战】Chapter2 Hugging Face简介

文章目录 Hugging Face的核心功能介绍Hugging Face开源库Hugging Face开源库Gradio工具介绍参考资料 Hugging Face是机器学习从业者协作和交流的平台&#xff0c;成立于2016年&#xff0c;在纽约和巴黎设有办事处&#xff0c;团队成员来自世界各地&#xff0c;远程办公。 致力于…

封装一个Element-ui生成一个可行内编辑的表格(vue2项目)

这个封装的是一个供整个项目使用的表格,可多次复用.放在一个全局使用的公共组件文件下. 大致功能介绍,封装自定义指令,点击获得焦点,显示输入框,失去焦点显示文本内容,类型是字典决定类型,图片可以显示图片名还是上传图片 子组件 <script> export default {props: {//生…

SpringCloud ---day1

认识微服务 单体架构 微服务架构 方便进行打包上线,版本的更新上线,降低项目之间的耦合度,减少代码量巨大导致的编译/打包时间长的问题 SpringCloud简介 项目熟悉 业务流程 项目模块划分 服务拆分原则 什么时候拆: 对于一个初创的项目&#xff0c;首先要做的是验证项目的可…

el-table :span-method合并单元格

<el-table :data"tableData" :span-method"objectSpanMethod" border style"width: 100%" :height"300"><el-table-column type"index" label"序号" width"50"></el-table-column>&l…

ajax同步与异步,json-serve的安装与使用,node.js的下载

20.ajax json 轻量级的数据格式做配置文件网络传输 xml 重量级的数据格式 可扩展标记语言做配置文件网络传输 现在目前主流就是大量采用json做网络传输数据格式 1.ajax的概念: 与服务器进行’通信’的一种技术,能够实现异步的刷新页面 **同步:**按照顺序一步步的执行,容易造…

算法通过村第十四关-堆|黄金笔记|中位数

文章目录 前言数据流中的中位数的问题总结 前言 提示&#xff1a;我独自度过了太多的时光&#xff0c;沉默已成一种习惯。 帕瑞尔马卡姆《夜航西飞》 这个是一个比较难的题目&#xff0c;要不尝试一下看看。 数据流中的中位数的问题 参考题目地址&#xff1a;295. 数据流的中位…

MyBatisPlus-02

一 查询条件的三种 1.按条件查询 //方式一&#xff1a;按条件查询QueryWrapper qw new QueryWrapper();qw.lt("age",18);List<User> userList userDao.selectList(qw);System.out.println(userList); 2.lambda格式按条件查询 //方式二&#xff1a;lambda格…

基于EtherCAT的机器人多轴同步运动控制

随着工业自动化的发展&#xff0c;机器人在生产线上的应用越来越广泛。为了实现高效、精确的运动控制&#xff0c;机器人的多轴运动必须能够实现同步操作&#xff0c;它能够提高机器人的运动精度和稳定性&#xff0c;实现更高效的生产线操作。同时&#xff0c;它也为机器人的协…

WebGPU入门一

1 WebGPU学习开发环境配置 WebGPU的环境配置比较简单&#xff0c;不需要vite或webpack配置一个复杂的开发环境&#xff0c;直接使用.html文件即可。 1.1 支持WebGPU的浏览器 Chrome 113 beta测试版开始默认支持WebGPU。 1.2 index.html文件 创建index.html文件&#xff0c…

C++进阶篇1---继承

一、继承的概念和定义 1.1概念 继承机制是面向对象程序设计使代码可以复用的最重要的手段&#xff0c;它允许程序员在保持原有类特性的基础上进行扩展&#xff0c;增加功能&#xff0c;这样产生新的类&#xff0c;称为派生类。继承呈现了面向对象程序设计的层次结构&#xff…

ExoPlayer架构详解与源码分析(5)——MediaSource

系列文章目录 ExoPlayer架构详解与源码分析&#xff08;1&#xff09;——前言 ExoPlayer架构详解与源码分析&#xff08;2&#xff09;——Player ExoPlayer架构详解与源码分析&#xff08;3&#xff09;——Timeline ExoPlayer架构详解与源码分析&#xff08;4&#xff09;—…

掌握Python爬虫实现网站关键词扩展提升曝光率

目录 一、关键词优化的重要性 二、关键词优化的基本方法 1、选择与网站内容相关的关键词 2、控制关键词的密度和分布 3、关键词的层次布局 三、Python爬虫实现网站关键词扩展 1、确定目标网站 2、分析目标网站的HTML结构 3、编写Python爬虫代码 4、分析爬取到的关键词…

【算法练习Day22】 组合总和 III电话号码的字母组合

​&#x1f4dd;个人主页&#xff1a;Sherry的成长之路 &#x1f3e0;学习社区&#xff1a;Sherry的成长之路&#xff08;个人社区&#xff09; &#x1f4d6;专栏链接&#xff1a;练题 &#x1f3af;长路漫漫浩浩&#xff0c;万事皆有期待 文章目录 组合总和 III剪枝 电话号码…

深入理解React中的useEffect钩子函数

引言&#xff1a; React是一种流行的JavaScript库&#xff0c;它通过组件化和声明式编程的方式简化了前端开发。在React中&#xff0c;一个核心概念是组件的生命周期&#xff0c;其中包含了许多钩子函数&#xff0c;用于管理组件的不同阶段。其中之一就是useEffect钩子函数&…