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

leetcode LCR121.寻找目标值-二维数组

目录

  • 问题描述
  • 示例
  • 具体思路
    • 思路一
    • 思路二
  • 代码实现

问题描述

m*n 的二维数组 plants 记录了园林景观的植物排布情况,具有以下特性:

  • 每行中,每棵植物的右侧相邻植物不矮于该植物;
    每列中,每棵植物的下侧相邻植物不矮于该植物。

题目链接:https://leetcode.cn/problems/er-wei-shu-zu-zhong-de-cha-zhao-lcof/description/

示例

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
相似题目链接(与leetcode 240题相同): https://leetcode-cn.com/problems/search-a-2d-matrix-ii/

具体思路

  这个题目和杨氏矩阵是一样的。
  杨氏矩阵:有一个二维数组,数组的每行从左到右都是递增的,每列从上到下都是递增的,在这样的数组中查找一个数字是否存在。
例如有一个矩阵为:
1 2 3
4 5 6
7 8 9

思路一

  直接对该二维数组进行遍历,但该种方法的时间复杂度为 O ( N 2 ) O(N^2) O(N2),在此不考虑。

思路二

  我们可以找到行列的交界处,比如[0][2],即数字3这个位置,通过观察,我们可以发现,该数字是所在行中的最大数字,所在列中的最小数字,可以用目标数target和该交界处数字进行比较,如果target大于该数,则表示比这行最大的数还要大,所以一定不在这一行,舍弃该行,向下行进行查找。 如果target小于该数,则表示target比这列最小的数还要小,所以一定不在这一列,舍弃该列,向左边行进行查找。依次类推,找到返回true,找不到返回false
在这里插入图片描述

如果用[2][0]也是可以的,思路则反过来。
在这里插入图片描述

代码实现

class Solution {
public:bool findTargetIn2DPlants(vector<vector<int>>& plants, int target) {//需要考虑输入为空数组时的判断,如果是空数组的话无法对其进行访问if (plants.size() == 0 || plants[0].size() == 0) //plants.size()表示是有几个vector<int>(行),plants[0].size()表示第0个vector里面有多少个元素(列){return false;}int i = 0;   //二维数组的第0行int j = plants[0].size() - 1;  //二维数组第0行的最后一个元素下标while (i < plants.size() && j >= 0){if (target < plants[i][j])  //目标值比第0行最后一个元素小就往左边进行查找{j--;}else if (target > plants[i][j]) //目标值比第0行最后一个元素大就往下查找{i++;}else{return true;}}return false;}
};
class Solution {
public:bool findTargetIn2DPlants(vector<vector<int>>& plants, int target) {int i = plants.size() - 1, j = 0;   //最后一行的第1个元素while (i >= 0 && j < plants[0].size()){if (plants[i][j] > target) i--;else if (plants[i][j] < target) j++;else return true;}return false;}
};

相关文章:

leetcode LCR121.寻找目标值-二维数组

目录 问题描述示例具体思路思路一思路二 代码实现 问题描述 m*n 的二维数组 plants 记录了园林景观的植物排布情况&#xff0c;具有以下特性&#xff1a; 每行中&#xff0c;每棵植物的右侧相邻植物不矮于该植物&#xff1b; 每列中&#xff0c;每棵植物的下侧相邻植物不矮于该…...

成都百洲文化传媒有限公司引领电商服务新潮流

在当今数字化时代&#xff0c;电商行业日新月异&#xff0c;竞争激烈。然而&#xff0c;在这个浪潮中&#xff0c;成都百洲文化传媒有限公司凭借其专业的电商服务&#xff0c;脱颖而出&#xff0c;成为了行业中的新领军者。今天&#xff0c;我们就来探讨一下这家公司如何在这个…...

【C++从练气到飞升】05---运算符重载

&#x1f388;个人主页&#xff1a;库库的里昂 ✨收录专栏&#xff1a;C从练气到飞升 &#x1f389;鸟欲高飞先振翅&#xff0c;人求上进先读书。 目录 ⛳️推荐 一、运算符重载的引用 二、运算符重载 三、赋值运算符重载 1 .赋值运算符重载格式: 2 .赋值运算符只能重载成…...

[leetcode] 994. 腐烂的橘子

在给定的 m x n 网格 grid 中&#xff0c;每个单元格可以有以下三个值之一&#xff1a; 值 0 代表空单元格&#xff1b;值 1 代表新鲜橘子&#xff1b;值 2 代表腐烂的橘子。 每分钟&#xff0c;腐烂的橘子 周围 4 个方向上相邻 的新鲜橘子都会腐烂。 返回 直到单元格中没有…...

如何本地搭建群晖虚拟机并实现无quickconnect服务环境远程访问

文章目录 前言本教程解决的问题是&#xff1a;按照本教程方法操作后&#xff0c;达到的效果是前排提醒&#xff1a; 1. 搭建群晖虚拟机1.1 下载黑群晖文件vmvare虚拟机安装包1.2 安装VMware虚拟机&#xff1a;1.3 解压黑群晖虚拟机文件1.4 虚拟机初始化1.5 没有搜索到黑群晖的解…...

[Java基础揉碎]final关键字

目录 介绍 在某些情况下&#xff0c;程序员可能有以下需求&#xff0c;就会使用到final final注意事项和讨论细节 1) final修饰的属性又叫常量&#xff0c;一般用XX_XX_XX来命名 2) final修饰的属性在定义时&#xff0c;必须赋初值&#xff0c;并且以后不能再修改&#…...

用OceanBase binlog service 轻松进行数据回滚

背景 在日常的数据库运维过程中&#xff0c;难免会遭遇数据误操作的情形&#xff0c;比如因疏忽而执行了非预期的delete或update操作&#xff0c;这时就需要进行数据回滚。如果在OceanBase中启用了回收站功能&#xff0c;并设置了合适的undo_retention&#xff0c;那么我们可以…...

【C++】学习记录--condition_variable 的使用

condition_variable使用步骤如下&#xff1a;创建一个condition_variable对象创建一个互斥锁mutex对象&#xff0c;用来保护共享资源的访问在需要等待条件变量的地方&#xff0c;使用unique_lock<mutec>对象锁定互斥锁并调用condition_variable::wait()、condition_varia…...

Linux之时间子系统(四): tick 层模块(periodic 和dynamic )

一、时间子系统的软件架构 二、tick 层模块的文件 tick-common.c tick-oneshot.c tick-sched.c tick-broadcast.c tick-broadcast-hrtimer.c 这三个文件属于tick device layer。 tick-common.c文件是periodic tick模块&#xff0c;用于管理周期性tick事件。 tick-oneshot.c文…...

Docker Command

小试牛刀 # 查看docker版本 docker -v docker --version # 查看帮助 docker --help # 永远的Hello World docker run hello-world镜像操作 查看本地已有的镜像 docker images -a :列出本地所有的镜像&#xff08;含中间映像层&#xff09; -q :只显示镜像ID --digests :显示…...

Linux系统部署Paperless-Ngx文档管理系统结合内网穿透实现公网访问

文章目录 1. 部署Paperless-ngx2. 本地访问Paperless-ngx3. Linux安装Cpolar4. 配置公网地址5. 远程访问6. 固定Cpolar公网地址7. 固定地址访问 Paperless-ngx是一个开源的文档管理系统&#xff0c;可以将物理文档转换成可搜索的在线档案&#xff0c;从而减少纸张的使用。它内置…...

6.shell case控制语句

case控制语句 1.什么是case case条件语句相当于多分支的if/elif/else条件语句&#xff0c;主要还是用来做条件判断的,常被应用于实现系统服务启动脚本。 case语句中&#xff0c;会将case获取的变量值与表达式部分的值1、值2、值3等逐个进行比较&#xff0c;如果变量值和某个表…...

如何判断HDMI接口版本是1.4还是2.0呢?

如何判断HDMI接口版本是1.4还是2.0呢&#xff1f; HDMI是一种用于传输高质量音频和视频信号的接口标准。随着技术的不断发展&#xff0c;HDMI接口也经历了多次升级和改进。在市场上&#xff0c;常见的HDMI接口版本包括1.4和2.0。判断HDMI接口版本主要通过以下几种方法&#xff…...

【开发环境搭建篇】NodeJS的安装和配置

作者介绍&#xff1a;本人笔名姑苏老陈&#xff0c;从事JAVA开发工作十多年了&#xff0c;带过大学刚毕业的实习生&#xff0c;也带过技术团队。最近有个朋友的表弟&#xff0c;马上要大学毕业了&#xff0c;想从事JAVA开发工作&#xff0c;但不知道从何处入手。于是&#xff0…...

【Docker】docker和docker-compose一键安装脚本(linux)

一、准备和运行脚本 当前脚本下载的docker和docker-compose兼容系统架构为x64&#xff0c;可以根据自己实际系统版本更改下载链接 1. 在控制台使用vim新建: vim install-docker.sh2. 复制内容并粘贴&#xff1a; #!/usr/bin/env bash # 设置脚本在遇到错误时终止执行 set -…...

在 Windows 中安装配置并启动运行 Jenkins【图文详细教程】

安装 Jenkins 的系统要求&#xff1a; 最少 256MB 可用内存最少 1GB 可用磁盘空间JDK 8 / 11 /17&#xff08;Jenkins 是用 Java 写的&#xff0c;打包成 war 包&#xff09; 查看 JDK 的版本 Java JDK 在 Windows 中安装可以参考&#xff1a;https://www.yuque.com/u27599042/…...

C# 读取txt文本所有行

引用&#xff1a;System.IO; Path.Combine(); //将字符串组合成一个路径 Path.GetFullPath(); //返回指定路径的绝对路径 File.ReadAllLines(); //读取文本框返回一个数组 File.ReadAllText(); //读取文本框返回一个字符串 File.ReadAllBytes(); //读取文本框返回字节 …...

STM32使用常见错误合集(正在更新版)

本文章记录一些学习STM32的一些错误问题&#xff0c;师承江科大哈哈哈 一、编译、烧录类问题 1、烧录不成功&#xff0c;Keil提示RDDI-DAP Error【场景&#xff1a;PWM驱动直流电机】 解决方案&#xff1a;将电机断开再进行烧录&#xff0c;断开后就可以美美烧录不报错啦~ …...

Java Random类

一、Random类 在项目开发中&#xff0c;经常需要使用随机数值&#xff0c;例如&#xff0c;网站登录中的验证码&#xff0c;或者需要以一定概率实现的某种效果&#xff08;如游戏程序中的物品掉落等&#xff09;&#xff0c;就需要Java提供的Random类&#xff0c;该类用于生成…...

【Spring Cloud】微服务通信概述

SueWakeup 个人主页&#xff1a;SueWakeup 系列专栏&#xff1a;学习技术栈 个性签名&#xff1a;人生乏味啊&#xff0c;我欲令之光怪陆离 本文封面由 凯楠&#x1f4f7; 友情赞助播出 目录 前言 1. Dubbo&#xff08;Spring Cloud Alibaba&#xff09;和 Spring Cloud 的适…...

接口测试中缓存处理策略

在接口测试中&#xff0c;缓存处理策略是一个关键环节&#xff0c;直接影响测试结果的准确性和可靠性。合理的缓存处理策略能够确保测试环境的一致性&#xff0c;避免因缓存数据导致的测试偏差。以下是接口测试中常见的缓存处理策略及其详细说明&#xff1a; 一、缓存处理的核…...

铭豹扩展坞 USB转网口 突然无法识别解决方法

当 USB 转网口扩展坞在一台笔记本上无法识别,但在其他电脑上正常工作时,问题通常出在笔记本自身或其与扩展坞的兼容性上。以下是系统化的定位思路和排查步骤,帮助你快速找到故障原因: 背景: 一个M-pard(铭豹)扩展坞的网卡突然无法识别了,扩展出来的三个USB接口正常。…...

Linux应用开发之网络套接字编程(实例篇)

服务端与客户端单连接 服务端代码 #include <sys/socket.h> #include <sys/types.h> #include <netinet/in.h> #include <stdio.h> #include <stdlib.h> #include <string.h> #include <arpa/inet.h> #include <pthread.h> …...

Vue3 + Element Plus + TypeScript中el-transfer穿梭框组件使用详解及示例

使用详解 Element Plus 的 el-transfer 组件是一个强大的穿梭框组件&#xff0c;常用于在两个集合之间进行数据转移&#xff0c;如权限分配、数据选择等场景。下面我将详细介绍其用法并提供一个完整示例。 核心特性与用法 基本属性 v-model&#xff1a;绑定右侧列表的值&…...

高频面试之3Zookeeper

高频面试之3Zookeeper 文章目录 高频面试之3Zookeeper3.1 常用命令3.2 选举机制3.3 Zookeeper符合法则中哪两个&#xff1f;3.4 Zookeeper脑裂3.5 Zookeeper用来干嘛了 3.1 常用命令 ls、get、create、delete、deleteall3.2 选举机制 半数机制&#xff08;过半机制&#xff0…...

处理vxe-table 表尾数据是单独一个接口,表格tableData数据更新后,需要点击两下,表尾才是正确的

修改bug思路&#xff1a; 分别把 tabledata 和 表尾相关数据 console.log() 发现 更新数据先后顺序不对 settimeout延迟查询表格接口 ——测试可行 升级↑&#xff1a;async await 等接口返回后再开始下一个接口查询 ________________________________________________________…...

【Redis】笔记|第8节|大厂高并发缓存架构实战与优化

缓存架构 代码结构 代码详情 功能点&#xff1a; 多级缓存&#xff0c;先查本地缓存&#xff0c;再查Redis&#xff0c;最后才查数据库热点数据重建逻辑使用分布式锁&#xff0c;二次查询更新缓存采用读写锁提升性能采用Redis的发布订阅机制通知所有实例更新本地缓存适用读多…...

Leetcode33( 搜索旋转排序数组)

题目表述 整数数组 nums 按升序排列&#xff0c;数组中的值 互不相同 。 在传递给函数之前&#xff0c;nums 在预先未知的某个下标 k&#xff08;0 < k < nums.length&#xff09;上进行了 旋转&#xff0c;使数组变为 [nums[k], nums[k1], …, nums[n-1], nums[0], nu…...

认识CMake并使用CMake构建自己的第一个项目

1.CMake的作用和优势 跨平台支持&#xff1a;CMake支持多种操作系统和编译器&#xff0c;使用同一份构建配置可以在不同的环境中使用 简化配置&#xff1a;通过CMakeLists.txt文件&#xff0c;用户可以定义项目结构、依赖项、编译选项等&#xff0c;无需手动编写复杂的构建脚本…...

用鸿蒙HarmonyOS5实现中国象棋小游戏的过程

下面是一个基于鸿蒙OS (HarmonyOS) 的中国象棋小游戏的实现代码。这个实现使用Java语言和鸿蒙的Ability框架。 1. 项目结构 /src/main/java/com/example/chinesechess/├── MainAbilitySlice.java // 主界面逻辑├── ChessView.java // 游戏视图和逻辑├──…...