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

LeetCode [中等]矩阵置零

73. 矩阵置零 - 力扣(LeetCode)

暴力解法

用两个标记数组分别记录每一行和每一列是否有零出现。

  • 遍历该数组一次,如果某个元素为 0,那么就将该元素所在的行和列所对应标记数组的位置置为 true。
  • 再次遍历该数组,用标记数组更新原数组即可。

时间复杂度:O(mn),其中 m 是矩阵的行数,n 是矩阵的列数。至多只需要遍历该矩阵两次。

空间复杂度:O(m+n),其中 m 是矩阵的行数,n 是矩阵的列数。需要分别记录每一行或每一列是否有零出现。

public class Solution {public void SetZeroes(int[][] matrix) {int m = matrix.Length, n = matrix[0].Length;bool[] row = new bool[m];bool[] col = new bool[n];for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if (matrix[i][j] == 0) {row[i] = col[j] = true;}}}for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if (row[i] || col[j]) {matrix[i][j] = 0;}}}}
}

使用两个标记变量

使用两个额外的变量记录原矩阵的第一行第一列是否包含0。之后便可以修改matrix[0][j]和 matrix[i][0]的数据。

用原矩阵的 第一行 matrix[0][j] 和第一列 matrix[i][0],来代替原来的两个标记数组,从而减少使用的空间。

public class Solution {public void SetZeroes(int[][] matrix) {int m = matrix.Length, n = matrix[0].Length;bool flagCol0 = false, flagRow0 = false;//第一列for(int i = 0; i < m; i++){if(matrix[i][0] == 0){flagCol0 = true;break;}}//第一行for(int j = 0; j < n; j++){if(matrix[0][j] == 0){flagRow0 = true;break;}}//从第二行第二列开始遍历矩阵,将0结点的行列保存在第一行第一列中for(int i = 1; i < m; i++){for(int j = 1; j < n; j++){if(matrix[i][j] == 0)matrix[i][0] = matrix[0][j] = 0;}}//从第二行第二列开始遍历矩阵,根据第一行第一列中的的0修改for(int i = 1; i < m; i++){for(int j = 1; j < n; j++){if(matrix[i][0] == 0 || matrix[0][j] == 0)matrix[i][j] = 0;}}//修改第一列if(flagCol0){for(int i = 0; i < m; i++)matrix[i][0] = 0;}//修改第一行if(flagRow0){for(int j = 0; j < n; j++)matrix[0][j] = 0;}}
}

时间复杂度:O(mn),其中 m 是矩阵的行数,n 是矩阵的列数。我们至多只需要遍历该矩阵两次。

空间复杂度:O(1)。我们只需要常数空间存储若干变量。

相关文章:

LeetCode [中等]矩阵置零

73. 矩阵置零 - 力扣&#xff08;LeetCode&#xff09; 暴力解法 用两个标记数组分别记录每一行和每一列是否有零出现。 遍历该数组一次&#xff0c;如果某个元素为 0&#xff0c;那么就将该元素所在的行和列所对应标记数组的位置置为 true。再次遍历该数组&#xff0c;用标…...

十一、了解分布式计算

1、什么是&#xff08;数据&#xff09;计算&#xff1f; 2、分布式(数据)计算 &#xff08;1&#xff09;概念 顾名思义&#xff0c;分布式计算&#xff0c;即以分布式的形式完成数据的统计&#xff0c;得到需要的结果。 分布式数据计算&#xff0c;顾名思义&#xff0c;就是…...

数据结构和算法专题---2、算法思想

上文讲到算法的概念、复杂度&#xff0c;本文给大家介绍具体的算法思想&#xff0c;让大家对算法设计理念有个认识&#xff0c;后续再分别介绍各种算法。 算法思想 算法是解决问题的一种思想和方法&#xff0c;其基本思想是将一个复杂问题分解为多个简单的子问题&#xff0c;…...

在AWS Lambda上部署标准FFmpeg工具——自定义层的方案

大纲 1 确定Lambda运行时环境1.1 Lambda系统、镜像、内核版本1.2 运行时1.2.1 Python1.2.2 Java 2 打包FFmpeg3 创建Lambda的Layer4 测试4.1 创建Lambda函数4.2 附加FFmpeg层4.3 添加测试代码4.4 运行测试 参考文献 FFmpeg被广泛应用于音/视频流处理领域。对于简单的需求&#…...

prometheus服务发现之consul

文章目录 前言一、Consul 在这里的作用二、原理三、实现过程安装 consul节点信息&#xff08;exporter&#xff09;注册进去consul节点信息&#xff08;exporter&#xff09;从consul解除注册&#xff1a;prometheus配置consul地址 总结 前言 我们平时使用 prometheus 收集监控…...

基于SSM的鞍山职业技术学院图书借阅管理系统

文章目录 项目介绍主要功能截图:部分代码展示设计总结项目获取方式🍅 作者主页:超级无敌暴龙战士塔塔开 🍅 简介:Java领域优质创作者🏆、 简历模板、学习资料、面试题库【关注我,都给你】 🍅文末获取源码联系🍅 项目介绍 基于SSM的鞍山职业技术学院图书借阅管理…...

分布式数据库HBase

文章目录 前言 一、HBase概述 1.1.1 什么是HBase HBase是一个分布式的、面向列的开源数据库HBase是Google BigTable的开源实现HBase不同于一般的关系数据库, 适合非结构化数据存储HBase是一种分布式、可扩展、支持海量数据存储的 NoSQL数据库。HBase是依赖Hadoop的。为什么HBa…...

快捷切换raw页面到repo页面-Raw2Repo插件

Raw2Repo By Rick &#x1f4d6;快捷切换代码托管平台raw页面到repo页面 &#x1f517;github链接 https://github.com/rickhqh/Raw2Repo ✨Features 功能&#xff1a; ✅单击 Raw2Repo 插件按钮&#xff0c;即可跳转到相应的代码仓库页面。✅支持 GitHub、Gitee、GitCode …...

web:[GXYCTF2019]BabyUpload(文件上传、一句话木马、文件过滤)

题目 页面显示为文件上传 随便上传一个文件看看 上传一个文本文件显示 上传了一个图片显示 上传包含一句话木马的图片 上传了一个包含php一句话木马的文件&#xff0c;显示如上 换一个写法 上传成功 尝试上传.htaccess&#xff0c;上传失败&#xff0c;用抓包修改文件后缀 …...

C++ Div3、Sqrt 函数高性能实现(带汇编指令集)

均采用魔法数字&#xff08;Magic Number&#xff09;实现&#xff0c;一个是经典求平方根函数所使用的魔法数字&#xff1a;0x5f375a86、0x5f3759df。 float Sqrt(float x) noexcept { /* 0x5f3759df */float xhalf 0.5f * x;int32_t i *(int32_t*)&x;i 0x5f375a86 - …...

西南科技大学模拟电子技术实验四(集成运算放大器的线性应用)预习报告

一、计算/设计过程 说明:本实验是验证性实验,计算预测验证结果。是设计性实验一定要从系统指标计算出元件参数过程,越详细越好。用公式输入法完成相关公式内容,不得贴手写图片。(注意:从抽象公式直接得出结果,不得分,页数可根据内容调整) 反相比例运算电路(1)实验…...

【五分钟】学会利用cv2.resize()函数实现图像缩放

引言 在numpy知识库&#xff1a;深入理解numpy.resize函数和数组的resize方法中&#xff0c;小编较为详细地探讨了numpy的resize函数背后的机理。从结果来看&#xff0c;numpy.resize函数并不适合对图像进行缩放操作。而opencv中的resize函数虽然和numpy的resize函数同名&…...

vuepress-----18、图片缩放

图片引入两种方式 地址 # 图片缩放插件 # 实战 md文件引入图片 <img class"zoom-custom-imgs" :src"$withBase(/favicon.ico)" alt"favicon">安装配置插件 vuepress/medium-zoom: {selector: img.zoom-custom-imgs,},效果展示...

前端开发_移动Web+动画

平面转换 作用&#xff1a;为元素添加动态效果&#xff0c;一般与过渡配合使用 概念&#xff1a;改变盒子在平面内的形态&#xff08;位移、旋转、缩放、倾斜&#xff09; 平面转换又叫 2D 转换 平移 属性&#xff1a;transform: translate(X轴移动距离&#xff0c;Y轴移动…...

【Python】 生成二维码

创建了一个使用 python 创建二维码的程序。 下面是生成的程序的图像。 功能描述 输入网址&#xff08;URL&#xff09;。 输入二维码的名称。 当单击 QR 码生成按钮时&#xff0c;将使用 QRname 中输入的字符将 QR 码生成为图像。 程序代码 import qrcode import tkinterd…...

Qt与Sqlite3

操作流程&#xff1a; (1)与数据库连接 (2)进行增删改查操作 (3)关闭数据库 示例&#xff1a; 参考&#xff1a;Qt 操作SQLite数据库_qt sqlite数据库操作_houxian1103的博客-CSDN博客 再谈QSqlQuery::exec: database not open问题的解决_qt database not open-CSDN博客…...

在idea中使用maven创建dynamic web project

1、先创建一个empty project 2、添加一个module , 核心是选择maven archetype webapp, 这个是maven提供的创建web工程的模版。 3、添加完等自动安装好即可 4、目录可能不完整 右键src---->点击New---->点击Directory &#xff08;注意&#xff1a;这是笔者所缺失的结…...

【外观模式】SpringBoot集成mail发送邮件

前言 发送邮件功能&#xff0c;借鉴 刚果商城&#xff0c;根据文档及项目代码实现。整理总结便有了此文&#xff0c;文章有不对的点&#xff0c;请联系博主指出&#xff0c;请多多点赞收藏&#xff0c;您的支持是我最大的动力~ 发送邮件功能主要借助 mail、freemarker以及rocke…...

GUAVA 工具类

Guava是一个Google的开源Java库&#xff0c;常用的工具&#xff1a; 集合工具类&#xff0c;包括Lists&#xff08;创建&#xff1a;newArrayList、newLinkedList等&#xff09;、Sets&#xff08;创建&#xff1a;newHashSet、newLinkedHashSet等&#xff09;和Maps&#xff…...

高云GW1NSR-4C开发板上手使用

1.开发板 核心板&#xff0c;主芯片GW1NSR-LV4CQN48P&#xff0c;丝印文字“奥陶纪Octet&#xff0c;QQ群808770961”&#xff1a; 晶振&#xff1a;27MHz&#xff0c;22引脚 两个按键&#xff1a;靠近中间&#xff0c;23引脚&#xff0c;按下为低电平&#xff1b;靠近外侧&…...

网络编程(Modbus进阶)

思维导图 Modbus RTU&#xff08;先学一点理论&#xff09; 概念 Modbus RTU 是工业自动化领域 最广泛应用的串行通信协议&#xff0c;由 Modicon 公司&#xff08;现施耐德电气&#xff09;于 1979 年推出。它以 高效率、强健性、易实现的特点成为工业控制系统的通信标准。 包…...

React Native在HarmonyOS 5.0阅读类应用开发中的实践

一、技术选型背景 随着HarmonyOS 5.0对Web兼容层的增强&#xff0c;React Native作为跨平台框架可通过重新编译ArkTS组件实现85%以上的代码复用率。阅读类应用具有UI复杂度低、数据流清晰的特点。 二、核心实现方案 1. 环境配置 &#xff08;1&#xff09;使用React Native…...

五年级数学知识边界总结思考-下册

目录 一、背景二、过程1.观察物体小学五年级下册“观察物体”知识点详解&#xff1a;由来、作用与意义**一、知识点核心内容****二、知识点的由来&#xff1a;从生活实践到数学抽象****三、知识的作用&#xff1a;解决实际问题的工具****四、学习的意义&#xff1a;培养核心素养…...

React19源码系列之 事件插件系统

事件类别 事件类型 定义 文档 Event Event 接口表示在 EventTarget 上出现的事件。 Event - Web API | MDN UIEvent UIEvent 接口表示简单的用户界面事件。 UIEvent - Web API | MDN KeyboardEvent KeyboardEvent 对象描述了用户与键盘的交互。 KeyboardEvent - Web…...

push [特殊字符] present

push &#x1f19a; present 前言present和dismiss特点代码演示 push和pop特点代码演示 前言 在 iOS 开发中&#xff0c;push 和 present 是两种不同的视图控制器切换方式&#xff0c;它们有着显著的区别。 present和dismiss 特点 在当前控制器上方新建视图层级需要手动调用…...

关于uniapp展示PDF的解决方案

在 UniApp 的 H5 环境中使用 pdf-vue3 组件可以实现完整的 PDF 预览功能。以下是详细实现步骤和注意事项&#xff1a; 一、安装依赖 安装 pdf-vue3 和 PDF.js 核心库&#xff1a; npm install pdf-vue3 pdfjs-dist二、基本使用示例 <template><view class"con…...

WebRTC从入门到实践 - 零基础教程

WebRTC从入门到实践 - 零基础教程 目录 WebRTC简介 基础概念 工作原理 开发环境搭建 基础实践 三个实战案例 常见问题解答 1. WebRTC简介 1.1 什么是WebRTC&#xff1f; WebRTC&#xff08;Web Real-Time Communication&#xff09;是一个支持网页浏览器进行实时语音…...

根目录0xa0属性对应的Ntfs!_SCB中的FileObject是什么时候被建立的----NTFS源代码分析--重要

根目录0xa0属性对应的Ntfs!_SCB中的FileObject是什么时候被建立的 第一部分&#xff1a; 0: kd> g Breakpoint 9 hit Ntfs!ReadIndexBuffer: f7173886 55 push ebp 0: kd> kc # 00 Ntfs!ReadIndexBuffer 01 Ntfs!FindFirstIndexEntry 02 Ntfs!NtfsUpda…...

vue3 daterange正则踩坑

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

基于江科大stm32屏幕驱动,实现OLED多级菜单(动画效果),结构体链表实现(独创源码)

引言 在嵌入式系统中&#xff0c;用户界面的设计往往直接影响到用户体验。本文将以STM32微控制器和OLED显示屏为例&#xff0c;介绍如何实现一个多级菜单系统。该系统支持用户通过按键导航菜单&#xff0c;执行相应操作&#xff0c;并提供平滑的滚动动画效果。 本文设计了一个…...