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^31−231 <= matrix[i][j] <= 231−12^31 - 1231−1
进阶:
一个直观的解决方案是使用 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开始的秋招刷题路,记录下所刷每道题的题解,帮助自己回顾总结 73. 矩阵置零 给定一个 m x n 的矩阵,如果一个元素为 0 ,则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。 示例 1: 输入:mat…...

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

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

2023年美国大学生数学建模A题:受干旱影响的植物群落建模详解+模型代码(一)
目录 前言 一、题目理解 背景 解析: 要求 二、建模 1.相关性分析 2.相关特征权重 只希望各位以后遇到建模比赛可以艾特认识一下我,我可以提供免费的思路和部分源码,以后的数模比赛只要我还有时间肯定会第一时间写出免费开源思路&…...

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

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

在 Python 中只接受数字作为用户输入
只接受数字作为用户输入: 使用 while True 循环进行循环,直到用户输入一个数字。使用 float() 类尝试将值转换为浮点数。如果用户输入了一个数字,请使用 break 语句跳出循环。 while True:try:# 👇️ 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问题产生原因:因机房意外掉电导致集群部分机器两次掉电导致Elasticsearch重启,Elasticsearch重启后看似正常但某些index无数据。经排查判断为Elasticsearch的部分ind…...

Spring入门案例三:注解进行引用类型的自动装配
本系列文章将会带领大家进行Spring的全面学习,持续关注我,不断更新中… 一.案例分级 简单解析:配置类替代以前的配置文件,实体类提供对象,业务类中有实体类的引用对象,在业务层中实现引用类的自动装配。 二.各层代码…...
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 使用方法部署文档…...

软件测试项目实战(附全套实战项目教程+视频+源码)
开通博客以来,我更新了很多实战项目,但一部分小伙伴在搭建环境时遇到了问题。 于是,我收集了一波高频问题,汇成本篇,供大家参考,避免重复踩坑。 如果你还遇到过其他坑和未解决的问题,可在评论区…...

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

数据库系统:1. 绪论
更好的阅读体验\huge{\color{red}{更好的阅读体验}}更好的阅读体验 文章目录1.1 数据库系统概述1.1.1 基本概念数据(data)数据库(DataBase, DB)数据库管理系统(DataBase Management System, DBMS)数据库系统…...

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…...

力扣-分数排名
大家好,我是空空star,本篇带你了解一道简单的力扣sql练习题。 文章目录前言一、题目: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模式,这里改成Non…...

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

计算机网络期末复习汇总(附某高校期末真题试卷)
文章目录一、选择题二、填空题三、名词解析四、简答题五、高校期末真题一、选择题 1、传输延迟时间最小的交换方法是( A ) A.电路交换 B.报文交换 C.分组交换 D.信元交换 2、在OSI七层结构模型中,处于数据链路层与运输层之间的是( B) A、物…...
浅谈 React Hooks
React Hooks 是 React 16.8 引入的一组 API,用于在函数组件中使用 state 和其他 React 特性(例如生命周期方法、context 等)。Hooks 通过简洁的函数接口,解决了状态与 UI 的高度解耦,通过函数式编程范式实现更灵活 Rea…...
OpenLayers 可视化之热力图
注:当前使用的是 ol 5.3.0 版本,天地图使用的key请到天地图官网申请,并替换为自己的key 热力图(Heatmap)又叫热点图,是一种通过特殊高亮显示事物密度分布、变化趋势的数据可视化技术。采用颜色的深浅来显示…...

地震勘探——干扰波识别、井中地震时距曲线特点
目录 干扰波识别反射波地震勘探的干扰波 井中地震时距曲线特点 干扰波识别 有效波:可以用来解决所提出的地质任务的波;干扰波:所有妨碍辨认、追踪有效波的其他波。 地震勘探中,有效波和干扰波是相对的。例如,在反射波…...

超短脉冲激光自聚焦效应
前言与目录 强激光引起自聚焦效应机理 超短脉冲激光在脆性材料内部加工时引起的自聚焦效应,这是一种非线性光学现象,主要涉及光学克尔效应和材料的非线性光学特性。 自聚焦效应可以产生局部的强光场,对材料产生非线性响应,可能…...
spring:实例工厂方法获取bean
spring处理使用静态工厂方法获取bean实例,也可以通过实例工厂方法获取bean实例。 实例工厂方法步骤如下: 定义实例工厂类(Java代码),定义实例工厂(xml),定义调用实例工厂ÿ…...

ServerTrust 并非唯一
NSURLAuthenticationMethodServerTrust 只是 authenticationMethod 的冰山一角 要理解 NSURLAuthenticationMethodServerTrust, 首先要明白它只是 authenticationMethod 的选项之一, 并非唯一 1 先厘清概念 点说明authenticationMethodURLAuthenticationChallenge.protectionS…...
vue3 定时器-定义全局方法 vue+ts
1.创建ts文件 路径:src/utils/timer.ts 完整代码: import { onUnmounted } from vuetype TimerCallback (...args: any[]) > voidexport function useGlobalTimer() {const timers: Map<number, NodeJS.Timeout> new Map()// 创建定时器con…...

现代密码学 | 椭圆曲线密码学—附py代码
Elliptic Curve Cryptography 椭圆曲线密码学(ECC)是一种基于有限域上椭圆曲线数学特性的公钥加密技术。其核心原理涉及椭圆曲线的代数性质、离散对数问题以及有限域上的运算。 椭圆曲线密码学是多种数字签名算法的基础,例如椭圆曲线数字签…...

在WSL2的Ubuntu镜像中安装Docker
Docker官网链接: https://docs.docker.com/engine/install/ubuntu/ 1、运行以下命令卸载所有冲突的软件包: for pkg in docker.io docker-doc docker-compose docker-compose-v2 podman-docker containerd runc; do sudo apt-get remove $pkg; done2、设置Docker…...

微软PowerBI考试 PL300-在 Power BI 中清理、转换和加载数据
微软PowerBI考试 PL300-在 Power BI 中清理、转换和加载数据 Power Query 具有大量专门帮助您清理和准备数据以供分析的功能。 您将了解如何简化复杂模型、更改数据类型、重命名对象和透视数据。 您还将了解如何分析列,以便知晓哪些列包含有价值的数据,…...