Leetcode Hot100之矩阵

1. 矩阵置零

  • 题目描述
    给定一个 m x n 的矩阵,如果一个元素为 0 ,则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。
    在这里插入图片描述
  • 解题思路
    题目要求进行原地更改,也就是不能使用额外的空间,因此我们可以使用第一行的元素来记录对应的每一列是不是该置零,用第一列的元素来记录对应的每一行是不是该置零。但是这样的话就会有一个问题,就是第一行和第一列的元素会被覆盖,因此我们在覆盖第一行和第一列的元素前,需要额外的两个变量row_0_flag和col_0_flag来记录第一行和第一列是不是该置零。
    时间复杂度:O(m*n) 空间复杂度:O(1)
  • 代码
    class Solution:def setZeroes(self, matrix: List[List[int]]) -> None:"""Do not return anything, modify matrix in-place instead."""m = len(matrix)if m == 0:return n = len(matrix[0])# 在使用第一行和第一列进行记录之前,先把第一行和第一列是否需要置零给求出来row_0_flag = Falsefor i in range(n):if matrix[0][i] == 0:row_0_flag = Truebreakcol_0_flag = Falsefor i in range(m):if matrix[i][0] == 0:col_0_flag = Truebreak# 使用第一行和第一列进行记录for i in range(1, m):for j in range(1, n):if matrix[i][j] == 0:matrix[i][0] = 0matrix[0][j] = 0for i in range(1, m):for j in range(1, n):if (matrix[i][0] == 0 or matrix[0][j] == 0) and matrix[i][j] != 0:matrix[i][j] = 0if row_0_flag:for i in range(n):matrix[0][i] = 0if col_0_flag:for i in range(m):matrix[i][0] = 0
    

2. 螺旋矩阵

  • 题目描述
    给你一个 m 行 n 列的矩阵 matrix ,请按照 顺时针螺旋顺序 ,返回矩阵中的所有元素。
    在这里插入图片描述
  • 解题思路
    1. 首先确认螺旋的圈数,圈数是(min(m, n) + 1) // 2,也就是最外层的循环数。
    2. 在每一圈中,我们需要分别从左到右,从上到下,从右到左,从下到上四个方向遍历,在解题时可以现在纸上把每个方向遍历的起始位置和终止位置写出来,这样就很容易写出代码。
    3. 注意在从右往左、从下到上遍历的时候,要判断是不是和从左往右、从上往下是不是一行,是一行的话就不用遍历了。
      时间复杂度:O(m*n) 空间复杂度:O(1)
  • 代码
    class Solution:def spiralOrder(self, matrix: List[List[int]]) -> List[int]:m = len(matrix)n = len(matrix[0])iters = (min(m, n) + 1) // 2res = []for i in range(iters):# 从左往右打印for j in range(i, n - i):res.append(matrix[i][j])# 从上往下打印for j in range(i + 1, m - i):res.append(matrix[j][n - 1 - i])# 从右往左打印,此时要判断是不是和从左往右打印的是一行,是一行的话很明显就不用打印了if m - i - 1 > i:for j in range(n - 2 - i, i - 1, -1):res.append(matrix[m - i - 1][j])# 从下往上打印,此时要判断是不是和从上往下打印是一列,是一列的话很明显就不用打印了if i < n - 1 - i:for j in range(m - i - 2, i, -1):res.append(matrix[j][i])return res

3. 旋转图像

  • 题目描述
    给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。

    你必须在 原地 旋转图像,这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。

  • 解题思路
    先转置,再左右镜像

  • 代码

    class Solution:def rotate(self, matrix: List[List[int]]) -> None:"""Do not return anything, modify matrix in-place instead."""n = len(matrix)# 转置for i in range(n):for j in range(i + 1, n):matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]# 左右镜像for i in range(n):l, r = 0, n - 1while l < r:matrix[i][l], matrix[i][r] = matrix[i][r], matrix[i][l]l += 1r -= 1
    

4. 搜索二维矩阵 II

  • 题目描述
    编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性:

    每行的元素从左到右升序排列。
    每列的元素从上到下升序排列。
    在这里插入图片描述

  • 解题思路
    二分查找:从左上角开始搜索,小于target的话向下查找,大于target的话向左查找

  • 代码

    class Solution:def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:m = len(matrix)n = len(matrix[0])i = 0j = n - 1while i < m and j >= 0:if matrix[i][j] == target:return Trueelif matrix[i][j] > target:j -= 1else:i += 1return False
    

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

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

相关文章

java对word文档预设参数填值并生成

目录 &#xff08;1&#xff09;定义word文档模板 &#xff08;2&#xff09;模板二次处理 处理模板图片&#xff0c;不涉及图片可以跳过 处理模板内容 &#xff08;3&#xff09;java对word模板填值 &#xff08;4&#xff09;Notepad的XML Tools插件安装 工作上要搞一个…

基于STM32的智能家庭安防系统

目录 引言环境准备智能家庭安防系统基础代码实现&#xff1a;实现智能家庭安防系统 4.1 数据采集模块4.2 数据处理与分析4.3 控制系统实现4.4 用户界面与数据可视化应用场景&#xff1a;家庭安防管理与优化问题解决方案与优化收尾与总结 1. 引言 智能家庭安防系统通过使用ST…

flask与vue实现通过websocket通信

在一些情况下&#xff0c;我们需要实现前后端之间的时刻监听&#xff0c;本文是一篇工具文档&#xff0c;用于解决前后端之间使用websocket交互。 一. Flask的相关配置 1. 下载相关依赖库 如果还没有配置flask的话&#xff0c;需要先安装flask,同时为解决跨域问题&#xff0…

大模型自然语言生成自动驾驶可编辑仿真场景(其一 共十篇)

第一篇&#xff1a;LLM greater scene summarize 第二篇&#xff1a;LLM simulation Test effect 第三篇&#xff1a;LLM simulation driving scenario flow work 第四篇&#xff1a;LLM Algorithm flow description 第五篇&#xff1a;Configure the environment and back…

探索ChatGPT在程序员日常工作的多种应用

引言 在现代科技迅猛发展的今天&#xff0c;人工智能的应用已经深入到我们生活和工作的各个方面。作为程序员&#xff0c;我们时常面临大量繁杂的任务&#xff0c;从代码编写、错误调试到项目管理和团队协作&#xff0c;每一项都需要花费大量的时间和精力。近年来&#xff0c;…

[AI开发配环境]VSCode远程连接ssh服务器

文章目录 总览&#xff1a;ssh连接远程服务器连接免密登录&#xff1a;Docker&#xff1a;ssh连接远程宿主机后&#xff0c;进一步连接并使用其中的docker容器reload window 配置解释器&#xff1a;CtrlP&#xff0c;在上面输入“>python”, 然后选selecet interpreter运行命…

Sharding-JDBC分库分表

参考&#xff1a; https://mp.weixin.qq.com/s/A6WS1CSjF7wvBE_gKLyp8w https://shardingsphere.apache.org/document/legacy/4.x/document/cn/quick-start/sharding-jdbc-quick-start/ 注意&#xff1a; 支持的sql项&#xff1a; 全面支持DML、DDL、DCL、TCL和部分DAL。支…

Altera不同系列的型号命名规则

Altera芯片型号&#xff1a;10AX07H4F34I3SG 20nm工艺 资源&#xff1a; 大数据 云计算 人工智能 图像处理 MSEL

C#+uni-app医院HIS预约挂号系统源码 看病挂号快人一步

​​​​​​​ 提到去大型医院机构就诊时&#xff0c;许多人都感到恐惧。有些人一旦走进医院的门诊大厅&#xff0c;就感到迷茫&#xff0c;既无法理解导医台医生的建议&#xff0c;也找不到应该去哪个科室进行检查。实际上&#xff0c;就医也是一门学问&#xff0c;如何优化…

物联网系统运维——数据库部署,Linux环境下MySQL安装,使用phpMyAdmin管理MySQL,实验CentOS 7安装MySQL

一.MySQL 1.概要 MySQL是一种关联数据库管理系统&#xff0c;关联数据:而不是将所有数据放在一个大仓库内&#xff0c;这样就增加了速度并提高了灵活性库将数据保存在不同的表中。性能高、成本低、可靠性好&#xff0c;已经成为最流行的开源数据库。 二.MySQL安装与配置 1. …

IPFoxy Tips:匿名海外代理IP的使用方法及注意事项

在互联网上&#xff0c;隐私和安全问题一直备受关注。为了保护个人隐私和数据安全&#xff0c;使用匿名代理IP是一种常用的方法。匿名代理IP可以隐藏用户的真实IP地址&#xff0c;使用户在访问网站时更加隐秘和安全。 本文将介绍匿名代理IP的基本原理和核心功能。 基本原则 匿…

算法与数据结构——时间复杂度详解与示例(C#,C++)

文章目录 1. 算法与数据结构概述2. 时间复杂度基本概念3. 时间复杂度分析方法4. 不同数据结构的时间复杂度示例5. 如何通过算法优化来提高时间复杂度6. C#中的时间复杂度示例7. 总结 算法与数据结构是计算机科学的核心&#xff0c;它们共同决定了程序的性能和效率。在实际开发中…

Redis-集群-环境搭建

文章目录 1、清空主从复制和哨兵模式留下的一些文件1.1、删除以rdb后缀名的文件1.2、删除主从复制的配置文件1.3、删除哨兵模式的配置文件 2、appendonly修改回no3、开启daemonize yes4、protect-mode no5、注释掉bind6、制作六个实例的配置文件6.1、制作配置文件redis6379.con…

数据结构——带头双向循环链表(c语言实现)

目录 1.单链表和双向链表对比 2.双向链表实现 2.1 创建新节点 2.2 链表初始化 2.3 尾插 2.4 头插 2.5 尾删 2.6 头删 2.7 查找 2.8 指定位置后插入数据 2.9 删除指定节点 2.10 销毁链表 2.11 打印链表 前言&#xff1a; 我们在前几期详细地讲解了不带头单…

数据分析python基础实战分析

数据分析python基础实战分析 安装python&#xff0c;建议安装Anaconda 【Anaconda下载链接】https://repo.anaconda.com/archive/ 记得勾选上这个框框 安装完后&#xff0c;然后把这两个框框给取消掉再点完成 在电脑搜索框输入"Jupyter"&#xff0c;牛马启动&am…

网易严选礼品卡有什么用?

网易严选的礼品卡可以在网易商城里买东西 但是现在好多人买东西基本上都用的是淘宝京东之类的 很少会有人用网易吧 但是最近我朋友送了我几张网易的卡&#xff0c;我自己也用积分兑换一张&#xff0c;一直不知道怎么用 最后还是在收卡云上转让出去了&#xff0c;价格高不说…

2024年JCR分区,将发生重大变化

科睿唯安官方微信发布消息&#xff0c;指出今年的期刊排名及相应JCR分区将发生重大变化。 原文比较长&#xff0c;不熟悉相关规则的朋友也不太容易读懂。因此&#xff0c;我们今天做一个详细的解读。 首先明确几个基本概念&#xff1a; &#xff08;1&#xff09;2024年发布2…

File类和IO流

File类和IO流 文章目录 File类和IO流[TOC](文章目录)前言一、java.io.File类&IO流原理及流的分类1.1 File类及其API1.2 IO流原理及分类 二、节点流的介绍&#xff08;字符/字节&#xff09;2.1 Reader\Writer--字符IO抽象基类2.2 FileReader\FileWriter--字符IO节点流2.3 I…

Android 多媒体开发——Media3与MediaSession最全使用指南

一、Media3库简介 1.1 Media3是什么&#xff1f; 官方释义&#xff1a; Jetpack Media3 is the new home for media libraries that enables Android apps to display rich audio and visual experiences. Media3 offers a simple architecture with powerful customization,…

Git 和 TortoiseGit 安装和配置(图文详解)

使用git&#xff0c;需要在Windows上需要安装两个软件&#xff1a;1&#xff09;Git 2&#xff09;TortoiseGit 若需要&#xff0c;可以下载TortoiseGit汉化语言包。 注意&#xff1a;tortoiseGit是在安装了Git的基础上运行的&#xff0c;所以需要先安装Git&#xff0c;后安装…