知识储备--基础算法篇-矩阵

2.矩阵

2.1第54题螺旋矩阵

第一题上来就跪了,看了官方答案感觉不是很好理解,找了一个比较容易理解的。

class Solution(object):def spiralOrder(self, matrix):""":type matrix: List[List[int]]:rtype: List[int]"""m = len(matrix)n = len(matrix[0])result = []left = 0right = n-1top = 0bottom = m-1nums = m*nwhile nums >= 1:i = leftwhile i <= right and nums >= 1:result.append(matrix[top][i])nums = nums - 1i = i + 1top = top + 1i = topwhile i <= bottom and nums >= 1:result.append(matrix[i][right])nums = nums - 1i = i + 1right = right - 1i = rightwhile i >= left and nums >= 1:result.append(matrix[bottom][i])nums = nums - 1i = i - 1bottom = bottom - 1i = bottomwhile i >= top and nums >= 1:result.append(matrix[i][left])nums = nums - 1i = i - 1left = left + 1return result

还有一个暴力方法,其中有几个知识点,

  • list的[]中有三个参数,用冒号分割
  • list[param1:param2:param3]
  • param1,相当于start_index,可以为空,默认是0
  • param2,相当于end_index,可以为空,默认是list.size
  • param3,步长,默认为1。步长为-1时,返回倒序原序列

技巧:使用zip(*matrix)

代码:这里*解包,zip压缩,zip后变成zip类型,zip会把原有矩阵从第一列开始,把每一列打包成一个元祖,把元祖强转为list达到矩阵转置的效果。

但是实现顺时针旋转效果还需要配合[::-1]使用,先把行调换,第一行与最后一行换,然后再矩阵转置,达到矩阵旋转的效果。

class Solution(object):def spiralOrder(self, matrix):""":type matrix: List[List[int]]:rtype: List[int]"""res = []while matrix:# 删除第一行并返回res += matrix.pop(0)# 矩阵转置matrix = list(zip(*matrix))# 行调换,如第一行与最后一行换matrix = matrix[::-1]return res

2.2第73题-矩阵置零

第二道题还是比较简单的,获得0元素的行列索引,将其存到字典中,如果有重复的就不管,最后遍历字典的key,将指定的行列都置0就行了。

class Solution(object):def setZeroes(self, matrix):""":type matrix: List[List[int]]:rtype: None Do not return anything, modify matrix in-place instead."""m = len(matrix)n = len(matrix[0])hang = {}lie = {}for i in range(m):for j in range(n):if matrix[i][j]==0:if i not in hang:hang[i] = 1if j not in lie:lie[j] = 1for i in hang:for j in range(n):matrix[i][j] = 0for i in lie:for j in range(m):matrix[j][i] = 0

2.3第48题-旋转图像

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

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

示例 1:

直接用刚学会的矩阵转置来做,飞快,就是内存用的多。

class Solution(object):def rotate(self, matrix):""":type matrix: List[List[int]]:rtype: None Do not return anything, modify matrix in-place instead."""# 直接用转置# 先颠倒,再转置matrix[:] = matrix[::-1]matrix[:] = list(zip(*matrix))

用常规方法,第i行的第x个元素(列)移动到第m-i-1列的第x个位置(行)

class Solution(object):def rotate(self, matrix):""":type matrix: List[List[int]]:rtype: None Do not return anything, modify matrix in-place instead."""matrix2 = copy.deepcopy(matrix)m = len(matrix)for i in range(m):for j in range(m):matrix[j][m-1-i] = matrix2[i][j]

2.4第240题搜索二维矩阵

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

  • 每行的元素从左到右升序排列。
  • 每列的元素从上到下升序排列。

示例 1:

class Solution(object):def searchMatrix(self, matrix, target):""":type matrix: List[List[int]]:type target: int:rtype: bool"""# 对角线上的元素是左上角块的最大值,只需要确定target的范围,# 找到比target小的对应行列就可以了# 比如target=14,先确定范围,>1,>5,>9,<17# 这时候就可以在元素17对应的左边和上边遍历寻找了# 如果m!=n,则先寻找对角线,再寻找剩下几列max_ = []m = len(matrix)n = len(matrix[0])a = min(m,n)flag = Falsefor i in range(a):max_.append(matrix[i][i])b = 0c = 0d = 0for i in range(a):if target < max_[i]:b = i-1breakelif target==max_[i]:return Truefor i in range(b+1,n):if target < matrix[b][i]:c = ibreakelif target == matrix[b][i]:return Truefor i in range(b+1,m):if target < matrix[i][b]:d = ibreakelif target == matrix[i][b]:return Truefor j in range(c,n):for i in range(b):if matrix[i][j] == target:return Truefor j in range(d,m):for i in range(b):if matrix[j][i] == target:return True

看了答案,发现从右上角慢慢缩小范围就可以了,妈的,这没想到。

class Solution(object):def searchMatrix(self, matrix, target):""":type matrix: List[List[int]]:type target: int:rtype: bool"""m = len(matrix)n = len(matrix[0])x = 0y = n-1while x<m and y>=0:if matrix[x][y]==target:return Trueelif matrix[x][y] < target:x = x + 1else:y = y - 1

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

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

相关文章

【JMeter】 二次开发插件开发 Dubbo 接口测试插件浅析

概述 在一些企业中&#xff0c;各类业务系统非常丰富&#xff0c;相互之间或对外提供很多的服务或接口这些服务或接口中&#xff0c;有很多是需要强契约约束的&#xff0c;服务的提供方、服务的使用方必须遵守相同契约这类服务最典型的就是RPC&#xff0c;其中应用广泛的有Dub…

【Android Framework系列】第13章 SVG矢量图形自定义组件(绘制中国地图)

1 前言 本章节我们来了解下什么是SVG矢量图形&#xff0c;怎么通过SVG实现图形的绘制&#xff0c;通过SVG实现不规则的自定义控件&#xff0c;项目实现一个中国地图&#xff0c;实现每个省都能够点击&#xff0c;项目地址在文末请自取。 2 SVG概念 2.1 SVG矢量图形 SVG 指可…

uni-app 客服按钮可上下拖动动

项目需求&#xff1a; 因为悬浮客服有时候会遮挡住界面内容&#xff0c;故需要对悬浮的气泡弹窗做可拖动操作 movable-area&#xff1a;可拖动区域 movable-view&#xff1a;可移动的视图容器&#xff0c;在页面中可以拖拽滑动或双指缩放。 属性说明 属性名类型默认值说…

音视频技术开发周刊 | 309

每周一期&#xff0c;纵览音视频技术领域的干货。 新闻投稿&#xff1a;contributelivevideostack.com。 腾讯云音视频及边缘平台专场邀你一起见证“连接”的力量 9月7日&#xff0c;腾讯全球数字生态大会之腾讯云音视频及边缘平台专场即将开启&#xff01;本次专场将重点分享腾…

JVM类的加载相关的问题

JVM类的加载相关的介绍 学习类的加载的加载过程对深入理解JVM有十分重要的作用&#xff0c;下面就跟我一起学习JVM类的加载过程吧&#xff01; 文章目录 JVM类的加载相关的介绍一、类的加载过程二、双亲委派机制1、类加载器的种类2、为什么JVM要分成不同的类的加载器3、类的加…

目标检测框架MMDetection训练自定义数据集实验记录

在上一篇博文中&#xff0c;博主完成了MMDetection框架的环境部署与推理过程&#xff0c;下面进行该框架的训练过程&#xff0c;训练的入口文件为tools/train.py&#xff0c;我们需要配置的内容如下&#xff1a; parser.add_argument(--config,default"/home/ubuntu/prog…

朴素,word,任何参考文献导入endnote

朴素&#xff0c;word&#xff0c;任何参考文献导入endnote 注意&#xff1a;对于以下这几种不做阐述&#xff0c;看其他帖子都有讲述&#xff1a; 这里的参考文献指的是类似于&#xff1a; [1]. Li Y, Lu Y, Huo X, et al. Bandgap tuning strategy by cations and halide io…

github无法访问

1.查看ip ipaddress.com 2.地址如下&#xff1a; 3.修改本地host文件 &#xff08;1&#xff09;打开访达后&#xff0c;在键盘上按ShiftCommandG组合键&#xff0c;进入&#xff0c;在etc找到host文件&#xff0c;修改 &#xff08;2&#xff09;如果修改不成功&#xff0…

【深度学习实验】数据可视化

目录 一、实验介绍 二、实验环境 三、实验内容 0. 导入库 1. 归一化处理 归一化 实验内容 2. 绘制归一化数据折线图 报错 解决 3. 计算移动平均值SMA 移动平均值 实验内容 4. 绘制移动平均值折线图 5 .同时绘制两图 6. array转换为tensor张量 7. 打印张量 一、…

如何移除 ONLYOFFICE 中的插件

如果您需要移除 ONLYOFFICE 编辑器中的某个甚至所有的插件&#xff0c;本文会向您介绍如何操作。如要详细了解&#xff0c;请阅读本文。 为什么会想移除插件 ONLYOFFICE 用户想知道如何删除插件&#xff0c;隐私问题是主要原因之一。有些插件&#xff08;如照片编辑器&#xf…

thinkphp6 入门(5)-- 模型是什么 怎么用

一、模型 MVC架构 之前开发一个功能&#xff0c;后端为在控制器&#xff08;C&#xff09;中写 php SQL&#xff0c;前端为在页面&#xff08;V&#xff09;中写html css js&#xff0c;这就形成了 VC 架构。 但是发现&#xff0c;相同的数据逻辑&#xff08;SQL&#xf…

建筑安全运行监测,预防建筑潜在风险

建筑物是人们生活和工作的场所&#xff0c;其安全性直接关系到人们的生命财产安全。建筑安全运行监测旨在及时发现和识别潜在的安全隐患&#xff0c;以确保建筑物的稳定运行&#xff0c;其重要性不可低估。 建筑安全运行监测可以帮助及早发现结构问题。随着时间的推移&#xff…

优化Docker权限管理:配置Docker用户组

Docker 利用 Linux 的用户和组权限来管理对 Docker 守护进程的访问权限。一般情况下&#xff0c;只有 root 用户和属于 docker 用户组的用户才被允许访问 Docker 守护进程。在 Linux 系统上使用 Docker 时&#xff0c;如果您尚未配置 docker 用户组&#xff0c;那么作为非 root…

企业级智能PDF及文档处理SDK GdPicture.NET 14.2 Crack

企业级智能PDF及文档处理SDK GdPicture.NET 提供了一组非常先进的 API&#xff0c;这些 API 利用了人工智能、机器学习和模糊逻辑算法等尖端技术。经过超过 15 年的持续研究和对创新的专注&#xff0c;我们的 SDK 已成为市场上针对PDF、OCR、条形码、文档成像和各种格式最全面的…

大数据成为市场营销利器 ,促进金融贷款企业获客精准化

随着大数据技术的不断普及&#xff0c;中国对尖端技术和云计算技术的投资大幅增加。大数据、云计算技术、物联网等一系列新一代信息技术也加速完善。 目前&#xff0c;大数据技术也非常成熟&#xff0c;大数据的应用领域也多种多样。大数据的重要方面“运营商大数据”已经被政…

R语言应用interactionR包进行亚组相加交互作用分析

在统计分析中交互作用是指某因素的作用随其他因素水平变化而变化&#xff0c;两因素共同作用不等于两因素单独作用之和(相加交互作用)或之积(相乘交互作用)。相互作用的评估是尺度相关的&#xff1a;乘法或加法。乘法尺度上的相互作用意味着两次暴露的综合效应大于&#xff08;…

java八股文面试[JVM]——JVM性能优化

JVM性能优化指南 JVM常用命令 jps 查看java进程 The jps command lists the instrumented Java HotSpot VMs on the target system. The command is limited to reporting information on JVMs for which it has the access permissions. jinfo &#xff08;1&#xff09;实时…

UniTask保姆级教程

目录 一、UniTask的简介和安装 https://github.com/Cysharp/UniTask.gitpathsrc/UniTask/Assets/Plugins/UniTask 空载性能测试 二、基础用法详解 三、基础用法扩展 四、进阶 五、VContainer简介 六、VContainer基础实例 方便快速查找 一、UniTask的简介和安装 项目地…

Medium: Where to Define Qualified users in A/B testing?

1. Common AB Testing Setup Issue (Framework) 局限性: unqualified users will also be considered and mess up experimentation results.

【力扣周赛】第 112 场双周赛

文章目录 竞赛链接Q1&#xff1a;7021. 判断通过操作能否让字符串相等 IQ2&#xff1a;7005. 判断通过操作能否让字符串相等 II&#xff08;贪心&#xff09;Q3&#xff1a;2841. 几乎唯一子数组的最大和竞赛时代码——滑动窗口 Q4&#xff1a;8050. 统计一个字符串的 k 子序列…