当前位置: 首页 > 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、物…...

2月,还是不要跳槽

新年已经过去&#xff0c;马上就到金三银四跳槽季了&#xff0c;一些不满现状&#xff0c;被外界的“高薪”“好福利”吸引的人&#xff0c;一般就在这时候毅然决然地跳槽了。 在此展示一套学习笔记 / 面试手册&#xff0c;年后跳槽的朋友可以好好刷一刷&#xff0c;还是挺有必…...

科技爱好者周刊之爱好者记录

前言 平时浏览的内容杂七杂八&#xff0c;说好听一些叫做“内容丰富&#xff0c;涉猎甚广”&#xff0c;实际一些则是受到主流大环境的冲击加之自身的控制力尚且不足。 有过类似经历的人大多知道&#xff0c;碎片化的信息除了填充大脑的冗余空间&#xff0c;在短期时间内就会被…...

C++入门:函数重载

目录 一. 函数重载的概念和分类 1.1 什么是函数重载 1.2 函数重载的分类 1.3 关于函数重载的几点注意事项 二. C实现函数重载的底层逻辑&#xff08;为什么C可以实现函数重载而C语言不能&#xff09; 2.1 编译器编译程序的过程 2.2 为什么C可以实现函数重载而C语言不能 …...

每天10个前端小知识 【Day 16】

&#x1f469; 个人主页&#xff1a;不爱吃糖的程序媛 &#x1f64b;‍♂️ 作者简介&#xff1a;前端领域新星创作者、CSDN内容合伙人&#xff0c;专注于前端各领域技术&#xff0c;成长的路上共同学习共同进步&#xff0c;一起加油呀&#xff01; ✨系列专栏&#xff1a;前端…...

23美赛D题:确定联合国可持续发展目标的优先级(ICM)思路Python代码

问题D(交叉网络建模题):确定联合国可持续发展目标的优先级(ICM) 赛题目的:对联合国制定的17个可持续发展目标进行关系网络的构建同时评估其可能存在的影响赛题解读&解题思路链接:交叉网络回归路径分析,如何寻找到能代表可持续发展目标的数值是这道题的难点。背景 联…...

高校房产管理系统有哪些管理功能范围?

数图互通高校房产管理系统是基于公司自主研发的FMCenterV5.0平台&#xff0c;是针对中国高校房产的管理特点和管理要求&#xff0c;研发的一套标准产品&#xff1b;通过在中国100多所高校的成功实施和迭代&#xff0c;形成了一套成熟、完善、全生命周期的房屋资源管理解决方案。…...

ACM MM 相关内容的整理+汇总

目录一、网址二、重要时间点三、论文篇幅要求四、征稿主题五、论文格式相关要求六、论文模板修改成投稿模式上述参考七、模板使用相关八、关于图片方面的问题九、Review and Rebuttal十、ACM MM2022相关论文参考arxiv上 ACM MM2022 论文汇总一、网址 ACM MM2023 主页&#xff1…...

前段时间公司招人,面了一个要20K的,一问自动化只会点皮毛···

前段时间公司要招2个自动化测试&#xff0c;同事面了几十个候选人&#xff0c;发现了一个很奇怪的现象&#xff0c;面试的时候&#xff0c;如果问的是框架api、脚本编写这些问题&#xff0c;基本上个个都能对答如流&#xff0c;等问到实际项目的时候&#xff0c;类似“怎么从0开…...

链表:反转链表、快慢指针、删除链表【零神基础精讲】

来源0x3f&#xff1a;https://space.bilibili.com/206214 文章目录反转链表[206. 反转链表](https://leetcode.cn/problems/reverse-linked-list/)[92. 反转链表 II](https://leetcode.cn/problems/reverse-linked-list-ii/)[25. K 个一组翻转链表](https://leetcode.cn/proble…...

SQlServer 定时执行sql语句作业的制定

1、打开【SQL Server Management Studio】&#xff0c;在【对象资源管理器】列表中选择【SQL Server 代理】&#xff1b; 2、鼠标右击【SQL Server 代理】&#xff0c;选择【启动(S)】&#xff0c;如已启动&#xff0c;可以省略此步骤&#xff1b; 3、展开【SQL Server 代理】列…...

网站功能设计怎么写/网站推广排名

禁止灵格斯2.7弹出“新奇英语 互动锐词”广告窗口的解决方法 用记事本打开并清空C:\Documents and Settings\Administrator\Application Data\Lingoes\Translator\tip.xml里的内容&#xff0c;保存后改属性为只读。 win7 下的路径是C:\Users\用户名\AppData\Roaming\Lingoes\T…...

电销如何介绍网站建设/做销售有什么技巧和方法

全自动无人值守安装&#xff0c;采用万能GHOST技术&#xff0c;安装系统过程只需5-8分钟&#xff0c;适合新旧各种机型。集成DX9.0c最新版、双核补丁。集成常用VB/VC2005、2008、2010、2012、2013/运行库、万能驱动助理稳定版安装过程会自动删除各分区下可能存在的AUTORUN病毒T…...

芜湖网站制作/百度关键词搜索量排行

AngularJS是一个javascript框架&#xff0c;通过AngularJS这个类库可以实现目前比较流行的单页面应用&#xff0c;AngularJS还具有双向数据绑定的特点&#xff0c;更加适应页面动态内容。所谓单页面应用就是在同一个页面动态加载不同的内容&#xff0c;而这里的“跳转”可以理解…...

网站工作状态建设/百度云网盘资源分享网站

https://howtodoinjava.com/core-java/string-class/interview-stuff-about-string-class-in-java/ 转载于:https://blog.51cto.com/881206524/1968726...

wordpress 动态解析/怎么注册域名网址

编辑&#xff1a;陈凌煜本文出自微信公众号“August精彩编程”(ID&#xff1a;august-edu)2019年8月12日网站分静态网站和动态网站&#xff0c;相信小伙伴们对这两个词略有耳闻或者已经了解&#xff0c;那么小编还是啰嗦一下这两种网站有什么区别。网页上的内容是随着数据库读取…...

提供手机网站制作哪家好/襄阳seo

用单调栈维护斜率&#xff0c;使之斜率单调递增&#xff0c;左右各跑一遍&#xff0c;具体的可以看代码里的注释 #include<cstdio> #include<algorithm> #include<iostream> #include<cstring> #include<cmath> #include <iomanip> #defi…...