用对角线去遍历矩阵
声明
该系列文章仅仅展示个人的解题思路和分析过程,并非一定是优质题解,重要的是通过分析和解决问题能让我们逐渐熟练和成长,从新手到大佬离不开一个磨练的过程,加油!
原题链接
用对角线遍历矩阵
https://leetcode.cn/leetbook/read/array-and-string/cuxq3/
算法分析
由上述四个图可以总结得出以下八个结论:
结论1:k属于[0,a(max)+b(max)]。
结论2:每一层遍历行最多存在min(m,n)个矩阵索引对,min(m,n)表示m和n二者中小的那一个值。
结论3:a属于[0,m-1],b属于[0,n-1]。
结论4:若k为偶数则以a为比较对象,此时若k<=a(max)则当前遍历行的起始索引对为(k,0),反之则起始索引对为(a(max),k-a(max))。
结论5:若k为奇数则以b为比较对象,此时若k<=b(max)则当前遍历行的起始索引对位(0,k),反之则起始索引对为(k-b(max),b(max))。
结论6:从当前遍历行的起始索引对开始,若k为偶数,则下一个索引对为(a-1,b+1),反之下一个索引对为(a+1,b-1)。
结论7:遍历行的结束条件由该矩阵的遍历行最大索引对个数和a(min)、b(min)共同决定,首先应判断当前遍历行访问的矩阵索引对个数是否达到了该矩阵的遍历行最大索引对个数,若达到了则完成该遍历行的遍历,否则判断下一个索引对(a,b),若a或b越界则表明完成该遍历行的遍历。
结论8:整个矩阵遍历结束的条件是当前遍历的矩阵索引对的个数是m×n个。
代码示例(C#)
public int[] FindDiagonalOrder(int[][] mat)
{int m = mat.Length;//矩阵的行数int n = mat[0].Length;//矩阵的列数int[] result = new int[m * n];//结果数组//a:索引对的a,b:索引对的b,k:a+b,count:当前已遍历的矩阵索引对个数,minA:a的最小值//minB:b的最小值,index:结果数组中的索引指针int a, b, k = 0, count = 0, minA = 0, minB = 0, index = 0;int maxA = m - 1;//a的最大值int maxB = n - 1;//b的最大值int maxIndexsCount = m <= n ? m : n;//该矩阵中遍历行的矩阵索引对个数的最大值int lineIndexsCount;//遍历行当前已遍历的矩阵索引对个数while (count < m * n){lineIndexsCount = 0;//若k%2为0则表示k为偶数,反之则为奇数if (k % 2 == 0){if (k <= maxA){a = k;b = 0;}else{a = maxA;b = k - maxA;}}else{if (k <= maxB){a = 0;b = k;}else{a = k - maxB;b = maxB;}}while (lineIndexsCount < maxIndexsCount){//a或b越界则完成此次遍历行的遍历if ((a < minA || a > maxA) || (b < minB || b > maxB)) break;//记录结果result[index++] = mat[a][b];count++;if (k % 2 == 0){a--;b++;}else{a++;b--;}}k++;}return result;
}
算法解说
按照原题的思路我们列举出了四种矩阵,严格来说只有三种,分别是矩阵行数大于列数、行数等于列数、行数小于列数,而为了保证后续结论的真实性,我们列举了两个行数等于列数的矩阵。
图中我们完成了四个矩阵的制定,然后按照题目要求去遍历了四个矩阵并且将遍历的结果记录下来,从行列定义上我们可以将矩阵构建在二维平面中,从而为每一个元素设立一个唯一的坐标值,在本题中我们把这个坐标值称为索引对。有了索引对我们可以进一步按照索引对两个数值之和对遍历结果进行分组,在本题中我们把索引对两个数值之和相同的一组索引对称为遍历行,为了简便后续将索引对两个数值之和称为索引对结果值。
将遍历行按照索引对结果值从小到大的顺序进行排列,为了能够发现更多有用的结论,我们把每一层遍历行的索引对结果值、结果值的奇偶性、索引对与k值的关系列举出来,除此之外还需要列举出矩阵行列数以及索引对两个数值的取值范围,至于为什么要去列举这些东西,实际上还是通过尝试和思考,就像上学时做数学题,浏览题目之后列举出题目中给定的条件,然后根据条件去解题。
这一步我们可以理解为进一步细化和剖析已知条件,我们的目的是从已知条件中获取可靠的结论,从而根据结论解决问题,因此我们总结出了上文的八个结论。
那么已知结论后如何去编写代码呢?本人是按照以下几个问题去解决的。
1.我们需要明白输入和输出是什么?
2.我们需要定义哪些变量?
3.函数主体是什么?
4.某些过程的结束条件是什么?
实际上,就是将我们的八个结论构建为代码,简单划分就是定义变量和逻辑主体,定义变量就看结论中需要记录数据的描述,逻辑主体就看结论中对于逻辑处理、结束条件的描述。
当然这样转换出来的代码比较粗糙,所以后续还可以结合自己的编程知识再去优化自己的代码,让它变得更加简洁精致。
相关文章:
用对角线去遍历矩阵
声明 该系列文章仅仅展示个人的解题思路和分析过程,并非一定是优质题解,重要的是通过分析和解决问题能让我们逐渐熟练和成长,从新手到大佬离不开一个磨练的过程,加油! 原题链接 用对角线遍历矩阵https://leetcode.c…...
【vue】点击按钮弹出卡片,点击卡片中的取消按钮取消弹出的卡片(附代码)
实现思路: 在按钮上绑定一个点击事件,默认是true;在export default { }中注册变量给卡片标签用v-if判断是否要显示卡片,ture则显示;在卡片里面写好你想要展示的数据;给卡片添加一个取消按钮,绑…...
【K8S】pod 基础概念讲解
目录 Pod基础概念:在Kubrenetes集群中Pod有如下两种使用方式:pause容器使得Pod中的所有容器可以共享两种资源:网络和存储。总结:kubernetes中的pause容器主要为每个容器提供以下功能:Kubernetes设计这样的Pod概念和特殊…...
ASP.NET Core中间件记录管道图和内置中间件
管道记录 下图显示了 ASP.NET Core MVC 和 Razor Pages 应用程序的完整请求处理管道 中间件组件在文件中添加的顺序Program.cs定义了请求时调用中间件组件的顺序以及响应的相反顺序。该顺序对于安全性、性能和功能至关重要。 内置中间件记录 内置中间件原文翻译MiddlewareDe…...
[系统安全] 五十二.DataCon竞赛 (1)2020年Coremail钓鱼邮件识别及分类详解
您可能之前看到过我写的类似文章,为什么还要重复撰写呢?只是想更好地帮助初学者了解病毒逆向分析和系统安全,更加成体系且不破坏之前的系列。因此,我重新开设了这个专栏,准备系统整理和深入学习系统安全、逆向分析和恶意代码检测,“系统安全”系列文章会更加聚焦,更加系…...
Android学习之路(3) 布局
线性布局LinearLayout 前几个小节的例程中,XML文件用到了LinearLayout布局,它的学名为线性布局。顾名思义,线性布局 像是用一根线把它的内部视图串起来,故而内部视图之间的排列顺序是固定的,要么从左到右排列…...
Python实现GA遗传算法优化XGBoost回归模型(XGBRegressor算法)项目实战
说明:这是一个机器学习实战项目(附带数据代码文档视频讲解),如需数据代码文档视频讲解可以直接到文章最后获取。 1.项目背景 遗传算法(Genetic Algorithm,GA)最早是由美国的 John holland于20世…...
C#软件外包开发流程
C# 是一种由微软开发的多范式编程语言,常用于开发各种类型的应用程序,从桌面应用程序到移动应用程序和Web应用程序。下面和大家分享 C# 编程学习流程,希望对大家有所帮助。北京木奇移动技术有限公司,专业的软件外包开发公司&#…...
队列的实现
1.队列的概念 队列:只允许在一端进行插入数据操作,在另一端进行删除数据操作的特殊线性表,队列具有先进先出FIFO(First In First Out)。 入队列:进行插入操作的一端称为队尾 出队列:进行删除操作的一端称为队头 2.队列…...
Node + Express 后台开发 —— 起步
Node Express 后台开发 —— 起步 前面陆续学习了一下 node、npm、模块,也稍尝试 Express,感觉得换一个思路加快进行。 比如笔者对前端的开发已较熟悉,如果领导给一个内部小网站的需求,难道说你得给我配置一个后端?…...
Python学习笔记第五十七天(Pandas 数据清洗)
Python学习笔记第五十七天 Pandas 数据清洗Pandas 清洗空值isnull() Pandas替换单元格mean()median()mode() Pandas 清洗格式错误数据Pandas 清洗错误数据Pandas 清洗重复数据duplicated()drop_duplicates() 后记 Pandas 数据清洗 数据清洗是对一些没有用的数据进行处理的过程…...
Elasticsearch的一些基本概念
文章目录 基本概念:文档和索引JSON文档元数据索引REST API 节点和集群节点Master eligible节点和Master节点Data Node 和 Coordinating Node其它节点 分片(Primary Shard & Replica Shard)分片的设定操作命令 基本概念:文档和索引 Elasticsearch是面…...
Guitar Pro8专业版吉他学习、绘谱、创作软件
Guitar Pro 8 专业版更强大!更优雅!更完美!Guitar Pro 8.0 五年磨一剑!多达30项功能优化!Guitar Pro8 版本一共更新近30项功能,令吉他打谱更出色!Guitar Pro8 是自2017年4月发布7.0之后发布的最…...
SpringBoot复习(39)Servlet容器的自动配置原理
Servlet容器自动配置类为ServletWebServerFactoryAutoConfiguration 可以看到通过Import注解导入了三个配置类: 通过这个这三个配置类可以看出,它们都使用了ConditionalOnClass注解,当类路径存在tomcat相关的类时,会配置一个T…...
【前端 | CSS】盒模型clientWidth、clientHeight、offsetWidht、offsetHeight
图 先看一个例子 html <div class"container"><div class"item">内容内容内容内容内容内容内容内容内容内容内容内容内容内容内容内容内容内容内容内容内容内容内容内容内容内容内容内容内容内容内容内容内容内容内容内容</div> </…...
Django 高级指南:深入理解和使用类视图和中间件
Django 是一款强大的 Python Web 框架,它提供了一套完整的解决方案,让我们能够用 Python 语言快速开发和部署复杂的 Web 应用。在本文中,我们将会深入研究 Django 中的两个高级特性:类视图(Class-Based Viewsÿ…...
《C语言深度解剖》.pdf
🐇 🔥博客主页: 云曦 📋系列专栏:深入理解C语言 💨吾生也有涯,而知也无涯 💛 感谢大家👍点赞 😋关注📝评论 C语言深度解剖.pdf 提取码:yunx...
【小梦C嘎嘎——启航篇】string介绍以及日常使用的接口演示
【小梦C嘎嘎——启航篇】string 使用😎 前言🙌C语言中的字符串标准库中的string类string 比较常使用的接口对上述函数和其他函数的测试代码演示: 总结撒花💞 😎博客昵称:博客小梦 😊最喜欢的座右…...
多个 Github 账户访问 Github
文章目录 多个 Github 账户访问 Github背景步骤 参考 多个 Github 账户访问 Github 背景 如果我想在这台电脑上同时使用两个 Github 账号怎么办呢? 你主机上的 SSH 公钥只能标识出一个账号。如果需要使用另外一个git账号,访问仓库,你需要创…...
c#实现命令模式
下面是一个使用C#实现命令模式的示例代码: using System; using System.Collections.Generic;// 命令接口 public interface ICommand {void Execute();void Undo(); }// 具体命令:打开文件 public class OpenFileCommand : ICommand {private FileMana…...
Spark 之 入门讲解详细版(1)
1、简介 1.1 Spark简介 Spark是加州大学伯克利分校AMP实验室(Algorithms, Machines, and People Lab)开发通用内存并行计算框架。Spark在2013年6月进入Apache成为孵化项目,8个月后成为Apache顶级项目,速度之快足见过人之处&…...
智慧工地云平台源码,基于微服务架构+Java+Spring Cloud +UniApp +MySql
智慧工地管理云平台系统,智慧工地全套源码,java版智慧工地源码,支持PC端、大屏端、移动端。 智慧工地聚焦建筑行业的市场需求,提供“平台网络终端”的整体解决方案,提供劳务管理、视频管理、智能监测、绿色施工、安全管…...
STM32标准库-DMA直接存储器存取
文章目录 一、DMA1.1简介1.2存储器映像1.3DMA框图1.4DMA基本结构1.5DMA请求1.6数据宽度与对齐1.7数据转运DMA1.8ADC扫描模式DMA 二、数据转运DMA2.1接线图2.2代码2.3相关API 一、DMA 1.1简介 DMA(Direct Memory Access)直接存储器存取 DMA可以提供外设…...
稳定币的深度剖析与展望
一、引言 在当今数字化浪潮席卷全球的时代,加密货币作为一种新兴的金融现象,正以前所未有的速度改变着我们对传统货币和金融体系的认知。然而,加密货币市场的高度波动性却成为了其广泛应用和普及的一大障碍。在这样的背景下,稳定…...
关于uniapp展示PDF的解决方案
在 UniApp 的 H5 环境中使用 pdf-vue3 组件可以实现完整的 PDF 预览功能。以下是详细实现步骤和注意事项: 一、安装依赖 安装 pdf-vue3 和 PDF.js 核心库: npm install pdf-vue3 pdfjs-dist二、基本使用示例 <template><view class"con…...
【从零开始学习JVM | 第四篇】类加载器和双亲委派机制(高频面试题)
前言: 双亲委派机制对于面试这块来说非常重要,在实际开发中也是经常遇见需要打破双亲委派的需求,今天我们一起来探索一下什么是双亲委派机制,在此之前我们先介绍一下类的加载器。 目录 编辑 前言: 类加载器 1. …...
leetcode73-矩阵置零
leetcode 73 思路 记录 0 元素的位置:遍历整个矩阵,找出所有值为 0 的元素,并将它们的坐标记录在数组zeroPosition中置零操作:遍历记录的所有 0 元素位置,将每个位置对应的行和列的所有元素置为 0 具体步骤 初始化…...
Linux 内存管理调试分析:ftrace、perf、crash 的系统化使用
Linux 内存管理调试分析:ftrace、perf、crash 的系统化使用 Linux 内核内存管理是构成整个内核性能和系统稳定性的基础,但这一子系统结构复杂,常常有设置失败、性能展示不良、OOM 杀进程等问题。要分析这些问题,需要一套工具化、…...
深入浅出JavaScript中的ArrayBuffer:二进制数据的“瑞士军刀”
深入浅出JavaScript中的ArrayBuffer:二进制数据的“瑞士军刀” 在JavaScript中,我们经常需要处理文本、数组、对象等数据类型。但当我们需要处理文件上传、图像处理、网络通信等场景时,单纯依赖字符串或数组就显得力不从心了。这时ÿ…...
Gitlab + Jenkins 实现 CICD
CICD 是持续集成(Continuous Integration, CI)和持续交付/部署(Continuous Delivery/Deployment, CD)的缩写,是现代软件开发中的一种自动化流程实践。下面介绍 Web 项目如何在代码提交到 Gitlab 后,自动发布…...
