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

Leetcode力扣秋招刷题路-0073

从0开始的秋招刷题路,记录下所刷每道题的题解,帮助自己回顾总结

73. 矩阵置零

给定一个 m x n 的矩阵,如果一个元素为 0 ,则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。

示例 1:
在这里插入图片描述

输入:matrix = [[1,1,1],[1,0,1],[1,1,1]]
输出:[[1,0,1],[0,0,0],[1,0,1]]

示例 2:
在这里插入图片描述

输入:matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]]
输出:[[0,0,0,0],[0,4,5,0],[0,3,1,0]]

提示:
m == matrix.length
n == matrix[0].length
1 <= m, n <= 200
−231-2^31231 <= matrix[i][j] <= 231−12^31 - 12311

进阶:
一个直观的解决方案是使用 O(mn) 的额外空间,但这并不是一个好的解决方案。
一个简单的改进方案是使用 O(m + n) 的额外空间,但这仍然不是最好的解决方案。
你能想出一个仅使用常量空间的解决方案吗?

方法一
思路:用两个set分别记录需要置0的行和需要置0的列。第一次遍历矩阵时,若发现一个元素为0,则将其行和列值分别加入到两个set中。第二次遍历矩阵时,将行set中的行全部置0,将列set中的列全部置0。

public void setZeroes(int[][] matrix) {if(matrix == null || matrix.length == 0)return;int m = matrix.length, n = matrix[0].length;Set<Integer> row = new HashSet<Integer>();Set<Integer> col = new HashSet<Integer>();for(int i = 0; i < m; i++){for(int j = 0; j < n; j++){if(matrix[i][j] == 0){row.add(i);col.add(j);}}}for(int i : row){for(int j = 0; j < n; j++)matrix[i][j] = 0;}for(int j : col){for(int i = 0; i < m; i++)matrix[i][j] = 0;}
}

时间复杂度:O(m×n)
空间复杂度:O(m+n) 最坏情况是矩阵中全部元素为0的情况,这时两个set的大小分别为m和n。

方法二
思路:不用额外空间,让首行和首列记录某列和某行是否有0

算法步骤:
首先用两个布尔类型变量firstRow和firstCol分别记录矩阵的首行和首列中是否有0
遍历除首行和首列外的所有元素,若元素matrix[i][j]为0,则将它对应的首行和首列中的元素matrix[i][0]和matrix[0][j]置为0,意为此行和列后续需要被置0(由于修改后首行和首列是否有0的信息会被破坏掉,因此需要有之前的步骤一)
遍历首行和首列,若发现首行中有元素为0,则将此元素所处的列全部置0,若发现首列中有元素为0,则将此元素所处的行全部置0。
根据步骤一的布尔类型变量firstRow和firstCol来判断首行和首列是否需要被置0。

public void setZeroes(int[][] matrix) {if(matrix == null || matrix.length == 0)return;int m = matrix.length, n = matrix[0].length;boolean firstRow = false, firstCol = false;//步骤一for(int i = 0; i < m; i++){if(matrix[i][0] == 0)firstCol = true;}for(int j = 0; j < n; j++){if(matrix[0][j] == 0)firstRow = true;}//步骤二for(int i = 1; i < m; i++){for(int j = 1; j < n; j++){if(matrix[i][j] == 0){matrix[i][0] = 0;matrix[0][j] = 0;}}}//步骤三for(int i = 1; i < m; i++){if(matrix[i][0] == 0){for(int j = 0; j < n; j++)matrix[i][j] = 0;}}for(int j = 1; j < n; j++){if(matrix[0][j] == 0){for(int i = 0; i < m; i++)matrix[i][j] = 0;}}//步骤四if(firstRow){for(int j = 0; j < n; j++)matrix[0][j] = 0;}if(firstCol){for(int i = 0; i < m; i++)matrix[i][0] = 0;}
}

时间复杂度:O(m×n)
空间复杂度:O(1)

相关文章:

Leetcode力扣秋招刷题路-0073

从0开始的秋招刷题路&#xff0c;记录下所刷每道题的题解&#xff0c;帮助自己回顾总结 73. 矩阵置零 给定一个 m x n 的矩阵&#xff0c;如果一个元素为 0 &#xff0c;则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。 示例 1&#xff1a; 输入&#xff1a;mat…...

遥感数字图像处理

遥感数字图像处理 来源&#xff1a;慕课北京师范大学朱文泉老师的课程 遥感应用&#xff1a;遥感制图、信息提取 短期内了解知识结构–>有选择的剖析经典算法原理–>系统化知识结构、并尝试实践应用 跳出算法&#xff08;尤其是数学公式&#xff09; 关注原理及解决问…...

深度学习常用的python函数(一)

由于我只简单的学过python和pytorch&#xff0c;其中有很多函数的操作都还是一知半解的&#xff0c;其中有些函数经常见到&#xff0c;所以就打算记录下来。 1.zip zip(*a):针对单个可迭代对象压缩成n个元组&#xff0c;元组数量n等于min(a中元素的最小长度) a [(1, 2), (3…...

2023年美国大学生数学建模A题:受干旱影响的植物群落建模详解+模型代码(一)

目录 前言 一、题目理解 背景 解析&#xff1a; 要求 二、建模 1.相关性分析 2.相关特征权重 只希望各位以后遇到建模比赛可以艾特认识一下我&#xff0c;我可以提供免费的思路和部分源码&#xff0c;以后的数模比赛只要我还有时间肯定会第一时间写出免费开源思路&…...

PPS文件如何转换成PPT?附两种方法

在工作中&#xff0c;PPS文件的使用还是很广泛的&#xff0c;因为作为幻灯片放映文件&#xff0c;点击后就能直接播放&#xff0c;十分方便。但如果想要修改PPS里的内容&#xff0c;PPS是无法编辑的&#xff0c;我们需要把文件转换成PPT&#xff0c;再进行修改。 那PPS文件如何…...

ParallelsDesktop安装【亲测可行】

我这边安装的是macos最新系统 (Ventura13.2) 本文参考这篇文章安装&#xff0c;但是你完全按照这篇文章会报错&#xff0c;具体可行操作记录如下 一、下载软件和补丁 1、点这里去下载补丁18.0.1 2、点这里去下载对应版本的ParallelsDesktop18.0.1&#xff0c;安装上到试用这里…...

在 Python 中只接受数字作为用户输入

只接受数字作为用户输入&#xff1a; 使用 while True 循环进行循环&#xff0c;直到用户输入一个数字。使用 float() 类尝试将值转换为浮点数。如果用户输入了一个数字&#xff0c;请使用 break 语句跳出循环。 while True:try:# &#x1f447;️ use int() instead of floa…...

【集合】JAVA基础篇(二)

目录一、java常用集合1、Java集合接口的作用2、Java集合常用实现类的作用二、Collection 常用的方法三、List 集合接口1、ArrayList类的常用方法2、LinkList类中的方法3、Vector4、ArrayList 类和 LinkedList 类的区别四、Set 集合1、HashSet 类2、TreeSet 类3、HashSet 和 Tre…...

机房意外掉电导致Elasticsearch的部分index无数据的修复过程

环境 :华为大数据集群FusionInsight V100R002C800SPC200、Elasticsearch 6.1.3、Kibana问题产生原因&#xff1a;因机房意外掉电导致集群部分机器两次掉电导致Elasticsearch重启&#xff0c;Elasticsearch重启后看似正常但某些index无数据。经排查判断为Elasticsearch的部分ind…...

Spring入门案例三:注解进行引用类型的自动装配

本系列文章将会带领大家进行Spring的全面学习&#xff0c;持续关注我&#xff0c;不断更新中… 一.案例分级 简单解析:配置类替代以前的配置文件&#xff0c;实体类提供对象&#xff0c;业务类中有实体类的引用对象&#xff0c;在业务层中实现引用类的自动装配。 二.各层代码…...

kubernet + kubevirt + ceph 汇总文档

目的 1 创建 kubenetes 集群 2 kubenetes 集群上部署 kubevirt 3 kubernetes 支持 ceph 存储 4 VMI 可以存储在 ceph rbd 存储中并正常使用 参考部署文档 名称连接备注centos8 + kubernetes 1.24 master/node 节点部署文档kubernetes 集群部署kubectl top node 使用方法部署文档…...

软件测试项目实战(附全套实战项目教程+视频+源码)

开通博客以来&#xff0c;我更新了很多实战项目&#xff0c;但一部分小伙伴在搭建环境时遇到了问题。 于是&#xff0c;我收集了一波高频问题&#xff0c;汇成本篇&#xff0c;供大家参考&#xff0c;避免重复踩坑。 如果你还遇到过其他坑和未解决的问题&#xff0c;可在评论区…...

Python seek()和tell()函数详解

在讲解 seek() 函数和 tell() 函数之前&#xff0c;首先来了解一下什么是文件指针。我们知道&#xff0c;使用 open() 函数打开文件并读取文件中的内容时&#xff0c;总是会从文件的第一个字符&#xff08;字节&#xff09;开始读起。那么&#xff0c;有没有办法可以自定指定读…...

数据库系统:1. 绪论

更好的阅读体验\huge{\color{red}{更好的阅读体验}}更好的阅读体验 文章目录1.1 数据库系统概述1.1.1 基本概念数据&#xff08;data&#xff09;数据库&#xff08;DataBase, DB&#xff09;数据库管理系统&#xff08;DataBase Management System, DBMS&#xff09;数据库系统…...

Android App开发基础

文章目录一 App的开发特点1.1 App的运行环境1.2 App开发语言1.3 java语言开发1.4 Kotlin语言开发1.5 XML1.6 App连接的数据库二 App的工程结构2.1 App工程目录结构2.2 构建工具Grade2.3 编译配置文件build.gradle2.4 运行配置文件AndroidManifest.xml2.4.1 application2.4.2 ac…...

力扣-分数排名

大家好&#xff0c;我是空空star&#xff0c;本篇带你了解一道简单的力扣sql练习题。 文章目录前言一、题目&#xff1a;178. 分数排名二、解题1.错误示范①提交SQL运行结果2.错误示范②提交SQL运行结果3.正确示范①提交SQL运行结果4.正确示范②提交SQL运行结果5.正确示范③提交…...

图文详解Ansible中的变量及加密

文章目录一、变量命名二、变量级别三、.变量设定和使用方式1.在playbook中直接定义变量2.在文件中定义变量3.使用变量4.设定主机变量和清单变量5.目录设定变量6.用命令覆盖变量7.使用数组设定变量8.注册变量9.事实变量10.魔法变量四、JINJA2模板五、 Ansible的加密控制练习1.用…...

silicon labs平台通过串口升级固件方案

开发环境 windowssimplicity studio 5geck sdk 4.1 一 bootloader 新建BGAPI UART DFU工程 工程新建完成以后看一下linkerfile.ld文件的flash和ram的配置跟自己的application工程是否对应得上 配置串口波特率和引脚 默认使用PB0进入bootloader模式&#xff0c;这里改成Non…...

MySQL 派生表产生关联索引auto_key0导致SQL非常的慢

相同的SQL在maridb运行0.5秒&#xff0c;在MySQL8.0.26中运行要19秒 官方MySQL在处理子查时&#xff0c;优化器有个优化参数derived_merge&#xff0c;MySQL7开启添加&#xff0c;默认on.很多情况可以自动优化派生表&#xff0c;避免创建临时索引auto_key0和生成临时表数据做…...

计算机网络期末复习汇总(附某高校期末真题试卷)

文章目录一、选择题二、填空题三、名词解析四、简答题五、高校期末真题一、选择题 1、传输延迟时间最小的交换方法是( A ) A.电路交换 B.报文交换 C.分组交换 D.信元交换 2、在OSI七层结构模型中&#xff0c;处于数据链路层与运输层之间的是&#xff08; B&#xff09; A、物…...

浅谈 React Hooks

React Hooks 是 React 16.8 引入的一组 API&#xff0c;用于在函数组件中使用 state 和其他 React 特性&#xff08;例如生命周期方法、context 等&#xff09;。Hooks 通过简洁的函数接口&#xff0c;解决了状态与 UI 的高度解耦&#xff0c;通过函数式编程范式实现更灵活 Rea…...

Java 语言特性(面试系列2)

一、SQL 基础 1. 复杂查询 &#xff08;1&#xff09;连接查询&#xff08;JOIN&#xff09; 内连接&#xff08;INNER JOIN&#xff09;&#xff1a;返回两表匹配的记录。 SELECT e.name, d.dept_name FROM employees e INNER JOIN departments d ON e.dept_id d.dept_id; 左…...

利用ngx_stream_return_module构建简易 TCP/UDP 响应网关

一、模块概述 ngx_stream_return_module 提供了一个极简的指令&#xff1a; return <value>;在收到客户端连接后&#xff0c;立即将 <value> 写回并关闭连接。<value> 支持内嵌文本和内置变量&#xff08;如 $time_iso8601、$remote_addr 等&#xff09;&a…...

剑指offer20_链表中环的入口节点

链表中环的入口节点 给定一个链表&#xff0c;若其中包含环&#xff0c;则输出环的入口节点。 若其中不包含环&#xff0c;则输出null。 数据范围 节点 val 值取值范围 [ 1 , 1000 ] [1,1000] [1,1000]。 节点 val 值各不相同。 链表长度 [ 0 , 500 ] [0,500] [0,500]。 …...

使用van-uploader 的UI组件,结合vue2如何实现图片上传组件的封装

以下是基于 vant-ui&#xff08;适配 Vue2 版本 &#xff09;实现截图中照片上传预览、删除功能&#xff0c;并封装成可复用组件的完整代码&#xff0c;包含样式和逻辑实现&#xff0c;可直接在 Vue2 项目中使用&#xff1a; 1. 封装的图片上传组件 ImageUploader.vue <te…...

ardupilot 开发环境eclipse 中import 缺少C++

目录 文章目录 目录摘要1.修复过程摘要 本节主要解决ardupilot 开发环境eclipse 中import 缺少C++,无法导入ardupilot代码,会引起查看不方便的问题。如下图所示 1.修复过程 0.安装ubuntu 软件中自带的eclipse 1.打开eclipse—Help—install new software 2.在 Work with中…...

Redis数据倾斜问题解决

Redis 数据倾斜问题解析与解决方案 什么是 Redis 数据倾斜 Redis 数据倾斜指的是在 Redis 集群中&#xff0c;部分节点存储的数据量或访问量远高于其他节点&#xff0c;导致这些节点负载过高&#xff0c;影响整体性能。 数据倾斜的主要表现 部分节点内存使用率远高于其他节…...

管理学院权限管理系统开发总结

文章目录 &#x1f393; 管理学院权限管理系统开发总结 - 现代化Web应用实践之路&#x1f4dd; 项目概述&#x1f3d7;️ 技术架构设计后端技术栈前端技术栈 &#x1f4a1; 核心功能特性1. 用户管理模块2. 权限管理系统3. 统计报表功能4. 用户体验优化 &#x1f5c4;️ 数据库设…...

网站指纹识别

网站指纹识别 网站的最基本组成&#xff1a;服务器&#xff08;操作系统&#xff09;、中间件&#xff08;web容器&#xff09;、脚本语言、数据厍 为什么要了解这些&#xff1f;举个例子&#xff1a;发现了一个文件读取漏洞&#xff0c;我们需要读/etc/passwd&#xff0c;如…...

MySQL 知识小结(一)

一、my.cnf配置详解 我们知道安装MySQL有两种方式来安装咱们的MySQL数据库&#xff0c;分别是二进制安装编译数据库或者使用三方yum来进行安装,第三方yum的安装相对于二进制压缩包的安装更快捷&#xff0c;但是文件存放起来数据比较冗余&#xff0c;用二进制能够更好管理咱们M…...