当前位置: 首页 > news >正文

LeetCode 热题 100之矩阵

1.矩阵置0

在这里插入图片描述
思路分析:使用标记数组

  • 记录需要置为 0 的行和列:使用两个布尔数组 zeroRows 和 zeroCols 来记录需要置为 0 的行和列
  • 两次遍历
    • 第一遍遍历整个矩阵,找到所有为0的元素,并更新zeroRows和zeroCols;
    • 第二遍遍历,依照zeroRows和zeroCols的状态,将对应的行和列元素置为0
    • 时间复杂度为 O(m * n),空间复杂度为 O(m + n),其中 m 和 n 分别是矩阵的行数和列数。

具体实现代码(详解版):

class Solution {
public:void setZeroes(vector<vector<int>>& matrix) {if (matrix.empty()) return;int rows = matrix.size();int cols = matrix[0].size();vector<bool> zeroRows(rows,false);vector<bool> zeroCols(cols,false);//第一次遍历,记录哪些行和列需要置为0for(int i = 0 ; i < rows ; i ++){for(int j = 0 ; j < cols ;j ++){if(matrix[i][j] == 0 ){zeroRows[i] = true;//记录第i行需要置为0zeroCols[j] = true;//记录第j列需要置为0}}}//第二次遍历,根据记录的行和列将其置为0for(int i = 0 ; i < rows ; i ++){for(int j = 0 ; j < cols ;j ++){if(zeroRows[i] || zeroCols[j] ){matrix[i][j] = 0;}}}}
};

2.螺旋矩阵

在这里插入图片描述
思路分析:要以顺时针螺旋顺序返回一个矩阵中的所有元素,可以采用四个边界(上、下、左、右)来控制遍历的范围。具体步骤如下

  • 初始化边界:设定四个变量,top,bottom,left,right,分别表示当前未遍历部分的上下左右边界
  • 循环遍历
    • 从左到右遍历当前的top行,更新top边界;
    • 从上到下遍历当前的right列,更新right边界;
    • 检查是否仍有行可遍历,若有,从右到左遍历当前的bottom行,更新bottom边界;
    • 检查是否仍有列可遍历,若有,从下到上遍历当前的left列,更新left边界;
  • 重复以上步骤,直到所有元素被遍历

具体实现代码(详解版):

class Solution {
public:vector<int> spiralOrder(vector<vector<int>>& matrix) {vector<int> result;if(matrix.empty() || matrix[0].empty()) return result;int top = 0, bottom = matrix.size() - 1;int left = 0, right = matrix[0].size() - 1;while(top <= bottom && left <= right){//从左到右遍历上边界for(int j = left ; j <= right ; j ++){result.push_back(matrix[top][j]);}top ++;//下移//从上到下遍历右边界for(int i = top ; i <= bottom ; i ++){result.push_back(matrix[i][right]);}right --;//左移if(top <= bottom){//检查是否仍有行可遍历//从右到左遍历下边界for(int j = right ; j >= left ; j --){result.push_back(matrix[bottom][j]);}bottom --;//上移}if(left <= right){//从下到上遍历左边界for(int i = bottom ; i >= top ; i --){result.push_back(matrix[i][left]);}left ++;//右移}}return result;}
};

还有一种写法,供参考:

class Solution {
public:vector<int> spiralOrder(vector<vector<int>>& matrix) {vector <int> ans;if(matrix.empty()) return ans; //若数组为空,直接返回答案int u = 0; //赋值上下左右边界int d = matrix.size() - 1;int l = 0;int r = matrix[0].size() - 1;while(true){for(int i = l; i <= r; ++i) ans.push_back(matrix[u][i]); //向右移动直到最右if(++ u > d) break; //重新设定上边界,若上边界大于下边界,则遍历遍历完成,下同for(int i = u; i <= d; ++i) ans.push_back(matrix[i][r]); //向下if(-- r < l) break; //重新设定右边界for(int i = r; i >= l; --i) ans.push_back(matrix[d][i]); //向左if(-- d < u) break; //重新设定下边界for(int i = d; i >= u; --i) ans.push_back(matrix[i][l]); //向上if(++ l > r) break; //重新设定左边界}return ans;}
};

3.旋转图像

在这里插入图片描述
思路分析:要在原地顺时针旋转 n×n 的矩阵,可以分为两个步骤:先进行矩阵的转置,然后再对每一行进行反转

  • 转置:通过双重循环,将 matrix[i][j] 和 matrix[j][i] 进行交换,从而完成转置操作。注意这里只需遍历上三角矩阵,以避免重复交换
  • 反转每一行:std::reverse 函数反转每一行,完成最终的旋转。

具体实现代码(详解版):

void rotate(vector<vector<int>>& matrix) {int n = matrix.size();// 1. 转置矩阵for (int i = 0; i < n; ++i) {for (int j = i + 1; j < n; ++j) {swap(matrix[i][j], matrix[j][i]);}}// 2. 反转每一行for (int i = 0; i < n; ++i) {reverse(matrix[i].begin(), matrix[i].end());}
}

4.搜索二维矩阵II

在这里插入图片描述

思路分析:使用一种从矩阵的右上角开始的搜索方法,这种方法的时间复杂度为 O(m+n),其中 m 是矩阵的行数,n 是列数。

  • 从右上角开始,设置 row 为 0,col 为最后一列的索引。
  • 搜索逻辑
    • 如果当前元素等于目标值,则返回 true;
    • 如果当前元素等大于目标值,说明target在左侧,向左移动(减少列索引);
    • 如果当前元素等小于目标值,说明target在下侧,向下移动(增加行索引);

具体实现代码(详解版):

class Solution {
public:bool searchMatrix(vector<vector<int>>& matrix, int target) {// 检查矩阵是否为空if (matrix.empty() || matrix[0].empty()) return false;int m = matrix.size();      // 矩阵行数int n = matrix[0].size();   // 矩阵列数int row = 0;                // 从第一行开始int col = n - 1;            // 从最后一列开始while (row < m && col >= 0) {if (matrix[row][col] == target) {return true; // 找到目标值} else if (matrix[row][col] > target) {col--; // 当前值大于目标,向左移动} else {row++; // 当前值小于目标,向下移动}}return false; // 未找到目标值}
};

相关文章:

LeetCode 热题 100之矩阵

1.矩阵置0 思路分析&#xff1a;使用标记数组 记录需要置为 0 的行和列&#xff1a;使用两个布尔数组 zeroRows 和 zeroCols 来记录需要置为 0 的行和列两次遍历 第一遍遍历整个矩阵&#xff0c;找到所有为0的元素&#xff0c;并更新zeroRows和zeroCols&#xff1b;第二遍遍历…...

YOlO系列——yolo v3

文章目录 一、算法原理二、网络结构三、正负样本匹配规则四、损失函数五、边框预测六、性能特点七、应用场景 YOLO-v3&#xff08;You Only Look Once version 3&#xff09;是一种先进的目标检测算法&#xff0c;属于YOLO系列算法的第三代版本。以下是对YOLO-v3的详细介绍&…...

基于Datawhale开源量化投资学习指南(11):LightGBM在量化选股中的优化与实战

1. 概述 在前几篇文章中&#xff0c;我们初步探讨了如何通过LightGBM模型进行量化选股&#xff0c;并进行了一些简单的特征工程和模型训练。在这一篇文章中&#xff0c;我们将进一步深入&#xff0c;通过优化超参数和实现交叉验证来提高模型的效果&#xff0c;并最终通过回测分…...

Python4

4. 更多控制流工具 除了刚介绍的 while 语句&#xff0c;Python 还用了一些别的。我们将在本章中遇到它们。 4.1. if 语句 if elif else if x<0: x 0 print(Negative changed to zero) elif x0: print( zero) else: print(More) 4.2. for 语句 Pyth…...

springboot系列--web相关知识探索六

一、前言 web相关知识探索五中研究了请求中所带的参数是如何映射到接口参数中的&#xff0c;也即请求参数如何与接口参数绑定。主要有四种、分别是注解方式、Servlet API方式、复杂参数、以及自定义对象参数。web相关知识探索五中主要研究自定义对象参数数据绑定底层原理。本次…...

FreeSWITCH 简单图形化界面30 - 使用MYODBC时可能遇到的错误

FreeSWITCH 简单图形化界面30 - 使用MYODBC时可能遇到的错误 测试环境1、 MYODBC 3.51.18 or higher2、分析和解决2.1 解决1&#xff0c;降级MySQL ODBC2.2 解决2&#xff0c;修改FreeSWITCH代码 测试环境 http://myfs.f3322.net:8020/ 用户名&#xff1a;admin&#xff0c;密…...

阿里云物联网的通信方式

阿里云物联网通信的两种方式&#xff0c;一个是物模型&#xff08;分为服务&#xff0c;事件&#xff0c;属性&#xff09;&#xff0c;一个是自定义topic&#xff08;要另外设置数据流转&#xff09; 1.使用产品内的功能定义&#xff0c;&#xff08;其实也就是Topic中定义好的…...

自由职业者的一天:作为小游戏开发者的真实工作日记

大家好&#xff0c;我是小蜗牛。 在这个快节奏的数字时代&#xff0c;自由职业者的生活往往充满了挑战与机遇。作为一名微信小游戏开发者&#xff0c;我的日常工作并不像人们想象中的那样充满光鲜亮丽的画面&#xff0c;而是由无数的编码、调试和创意碰撞组成的。今天&#xf…...

【RL Latest Tech】分层强化学习:Option-Critic架构算法

&#x1f4e2;本篇文章是博主强化学习RL领域学习时&#xff0c;用于个人学习、研究或者欣赏使用&#xff0c;并基于博主对相关等领域的一些理解而记录的学习摘录和笔记&#xff0c;若有不当和侵权之处&#xff0c;指出后将会立即改正&#xff0c;还望谅解。文章分类在&#x1f…...

分布式数据库

前言 分布式数据库系统&#xff08;‌DDBS&#xff09;包含分布式数据库管理系统&#xff08;‌DDBMS&#xff09;和分布式数据库&#xff08;DDB&#xff09;。在分布式数据库系统中&#xff0c;一个应用程序可以对数据库进行透明操作&#xff0c;数据库中的数据分别在不同的…...

MySQL(2)【库的操作】

阅读导航 引言一、创建数据库1. 基本语法2. 创建数据库案例&#x1f4cc;创建名为db1的数据库&#x1f4cc;创建一个使用utf8字符集的db2数据库&#x1f4cc;创建一个使用utf8字符集&#xff0c;并带校对规则的db3数据库 二、字符集和校验规则1. 查看系统默认字符集以及校验规则…...

python pip更换(切换)国内镜像源

国内镜像源列表(个人推荐清华大学的源) ​ 清华大学&#xff1a; https://pypi.tuna.tsinghua.edu.cn/simple阿里云&#xff1a; http://mirrors.aliyun.com/pypi/simple豆瓣&#xff1a; http://pypi.douban.com/simple中国科技大学&#xff1a; https://pypi.mirrors.ustc.e…...

阿里云镜像源无法访问?使用 DaoCloud 镜像源加速 Docker 下载(Linux 和 Windows 配置指南)

&#x1f680; 作者主页&#xff1a; 有来技术 &#x1f525; 开源项目&#xff1a; youlai-mall &#x1f343; vue3-element-admin &#x1f343; youlai-boot &#x1f343; vue-uniapp-template &#x1f33a; 仓库主页&#xff1a; GitCode&#x1f4ab; Gitee &#x1f…...

使用 BERT 和逻辑回归进行文本分类及示例验证

使用 BERT 和逻辑回归进行文本分类及示例验证 一、引言 在自然语言处理领域中&#xff0c;文本分类是一项至关重要的任务。本文将详细介绍如何结合 BERT 模型与逻辑回归算法来实现文本分类&#xff0c;并通过实际示例进行验证。 二、环境准备 为了运行本文中的代码&#xf…...

【skywalking 】监控 Spring Cloud Gateway 数据

使用Spring Cloud 开发&#xff0c;用Skywalking 监控服务&#xff0c;但是Skywalking 默认是不支持 Spring Cloud Gateway 网关服务的&#xff0c;需要手动将 Gateway 的插件添加到 Skywalking 启动依赖 jar 中。 skywalking相关版本信息 jdk&#xff1a;17skywalking&#x…...

SpringWeb

SpringWeb SpringWeb 概述 SpringWeb 是 spring 框架中的一个模块&#xff0c;基于 Servlet API 构建的 web 框架. springWeb 是 Spring 为 web 层开发提供的一整套完备的解决方案。 在 web 层框架历经 Strust1&#xff0c;WebWork&#xff0c;Strust2 等诸多产品的历代更…...

嵌入式刷题(day21)

MySQL和sqlite的区别 MySQL和SQLite是两种常见的关系型数据库管理系统(RDBMS),但它们在特性、使用场景和架构方面有显著的区别: 1. 架构 MySQL:是一个基于服务器的数据库系统,遵循客户端-服务器架构。MySQL服务器运行在主机上,客户端通过网络连接并发送查询。它可以并…...

OpenAI 下一代旗舰模型现身?奥尔特曼亲自辟谣“猎户座“传闻

在人工智能领域最受瞩目的ChatGPT即将迎来两周岁之际&#xff0c;一场关于OpenAI新旗舰模型的传闻再次引发业界热议。然而&#xff0c;这场喧嚣很快就被OpenAI掌门人奥尔特曼亲自澄清。 事件源于科技媒体The Verge的一则报道。据多位知情人士透露&#xff0c;OpenAI可能会在11…...

【C++】STL初识

【C】STL初识 文章目录 【C】STL初识前言一、STL基本概念二、STL六大组件简介三、STL三大组件四、初识STL总结 前言 本篇文章将讲到STL基本概念&#xff0c;STL六大组件简介&#xff0c;STL三大组件&#xff0c;初识STL。 一、STL基本概念 STL(Standard Template Library,标准…...

框架篇补充(东西多 需要重新看网课)

什么是AOP 面向切面编程 降低耦合 提高代码的复用 Spring的bean的生命周期 实例化bean 赋值 初始化bean 使用bean 销毁bean SpringMVC的执行流程 Springboot自动装配原理 实际上就是为了从spring.factories文件中 获取到对应的需要 进行自动装配的类 并生成相应的Bean…...

合约门合同全生命周期管理系统:企业合同管理的数字化转型之道

合约门合同全生命周期管理系统&#xff1a;企业合同管理的数字化转型之道 1. 引言 在现代企业中&#xff0c;合同管理已经不再是简单的文件存储和审批流程&#xff0c;而是企业合规性、风险管理和业务流程的关键环节之一。随着企业规模的扩大和合同数量的增加&#xff0c;传统…...

等保测评与风险管理:识别、评估和缓解潜在的安全威胁

在信息化时代&#xff0c;数据已成为企业最宝贵的资产之一&#xff0c;而信息安全则成为守护这份资产免受侵害的重中之重。等保测评&#xff08;信息安全等级保护测评&#xff09;作为保障信息系统安全的重要手段&#xff0c;其核心在于通过科学、规范、专业的评估手段&#xf…...

Golang Agent 可观测性的全面升级与新特性介绍

作者&#xff1a;张海彬&#xff08;古琦&#xff09; 背景 自 2024 年 6 月 26 日&#xff0c;ARMS 发布了针对 Golang 应用的可观测性监控功能以来&#xff0c;阿里云 ARMS 团队与程序语言与编译器团队一直致力于不断优化和提升该系统的各项功能&#xff0c;旨在为开发者提…...

SpringBoot的开篇 特点 初始化 ioc 配置文件

文章目录 前言SpringBoot发展历程SpringBoot前置准备SpringBoot特点 SpringBoot项目初始化项目启动Springboot的核心概念IOC概念介绍Bean对象通过注解扫描包 例子配置文件 前言 SpringBoot发展历程 最初&#xff0c;Spring框架的使用需要大量的XML配置&#xff0c;这使得开发…...

docker 可用镜像服务地址(2024.10.25亲测可用)

1.错误 Error response from daemon: Get “https://registry-1.docker.io/v2/” 原因&#xff1a;镜像服务器地址不可用。 2.可用地址 编辑daemon.json&#xff1a; vi /etc/docker/daemon.json内容修改如下&#xff1a; {"registry-mirrors": ["https://…...

【SQL实验】表的更新和简单查询

完整代码在文章末尾 在上次实验创建的educ数据库基础上&#xff0c;用SQL语句为student表、course表和sc表中添加以下记录 【SQL实验】数据库、表、模式的SQL语句操作_创建一个名为educ数据库,要求如下: (下面三个表中属性的数据类型需要自己设计合适-CSDN博客在这篇博文中已经…...

【C++】 string的了解及使用

标准库中的string类 在使用string类时&#xff0c;必须包含#include头文件以及using namespace std; string类的常用接口说明 C中string为我们提供了丰富的接口来供我们使用 – string接口文档 这里我们只介绍一些常见的接口 string类对象的常见构造 #include <iostrea…...

【K8S】kubernetes-dashboard.yaml

https://raw.githubusercontent.com/kubernetes/dashboard/v3.0.0-alpha0/charts/kubernetes-dashboard.yaml 以下链接的内容&#xff1a; 由于国内访问不了&#xff0c;找到一些方法下载了这个文件内容&#xff0c; 部署是mages 对象的镜像 WEB docker.io/kubernetesui/dash…...

远程root用户访问服务器中的MySQL8

一、Ubuntu下的MySQL8安装 在Ubuntu系统中安装MySQL 8.0可以通过以下步骤进行1. 更新包管理工具的仓库列表&#xff1a; sudo apt update 2. 安装MySQL 8.0&#xff0c;root用户默认没有密码&#xff1a; sudo apt install mysql-server sudo apt install mysql-client 【…...

解释一下 Java 中的静态变量(Static Variable)和静态方法(Static Method)?

今天来和大家深入探讨一下 Java 中的静态变量和静态方法&#xff0c;并通过一些具体的例子来理解它们在实际开发中的应用。 静态变量&#xff08;Static Variable&#xff09; 静态变量&#xff0c;也称为类变量&#xff0c;是在类的层次上共享的变量。这意味着无论创建了多少…...

鞍山网站开发公司/优化师是做什么的

北京市控烟行动轰轰烈烈&#xff0c;然而很多老烟民在既往戒烟时遇到过这样一些问题&#xff1a;突然不抽烟&#xff0c;身体反而出现各种不适&#xff01;甚至社会上一直流传着这样一种说法“突然戒烟会打乱身体平衡&#xff0c;反而对身体不好”&#xff01;老烟民突然戒烟&a…...

那些网站做汽车可靠性/站长之家ping检测

通过log打印出来的信息很快就一闪而过了&#xff0c;着实很郁闷。这里通过更改logcat的缓存数解决的&#xff0c;eclipse默认是5000&#xff0c;我将其改成了50000。 转载于:https://www.cnblogs.com/xiaofeng6636/p/4931913.html...

网站左侧qq客服代码/苏州网站制作推广

首先说明一下&#xff0c;本人并没做过智能音箱类结构&#xff0c;至于为什么会写有关智能音箱相关的内容&#xff0c;主要原因是想通过自己总结下智能音箱类硬件结构的共性点以及注意点&#xff0c;以便日后能用得上&#xff0c;在写本篇之前&#xff0c;本人也拆解过自己的音…...

wordpress 添加百度统计/佛山seo关键词排名

建筑模型设计制作实践室带锯、圆盘锯安全操作规程一、开机前1、检查锯齿是否变钝&#xff0c;固定锯片的螺丝是否坚固&#xff0c;锯条是否绷紧适中。2、接通电源&#xff0c;检查转动方向是否正确。3、根据锯切需要&#xff0c;调整锯条、档板等至合适位置&#xff0c;做好锯切…...

自学做网站多久/商务网站如何推广

内存泄漏 memory leak 申请内存后&#xff0c;无法释放 内存溢出 out of memory 申请内存时&#xff0c;空间不够 关系 内存泄漏的堆积最终会导致内存溢出...

设计网站需要多少钱/雅虎搜索引擎入口

一、正向代理与反向代理 核心区别&#xff1a; 正向代理&#xff1a;代理对象【客户端】&#xff0c;隐藏客户端。 反向代理&#xff1a;代理对象【服务器 】&#xff0c;隐藏服务器。 正向代理 client想访问server网站&#xff0c;但是不知道在哪&#xff0c;proxy知道在…...