当前位置: 首页 > 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 的适…...

基于算法竞赛的c++编程(28)结构体的进阶应用

结构体的嵌套与复杂数据组织 在C中&#xff0c;结构体可以嵌套使用&#xff0c;形成更复杂的数据结构。例如&#xff0c;可以通过嵌套结构体描述多层级数据关系&#xff1a; struct Address {string city;string street;int zipCode; };struct Employee {string name;int id;…...

微软PowerBI考试 PL300-选择 Power BI 模型框架【附练习数据】

微软PowerBI考试 PL300-选择 Power BI 模型框架 20 多年来&#xff0c;Microsoft 持续对企业商业智能 (BI) 进行大量投资。 Azure Analysis Services (AAS) 和 SQL Server Analysis Services (SSAS) 基于无数企业使用的成熟的 BI 数据建模技术。 同样的技术也是 Power BI 数据…...

边缘计算医疗风险自查APP开发方案

核心目标:在便携设备(智能手表/家用检测仪)部署轻量化疾病预测模型,实现低延迟、隐私安全的实时健康风险评估。 一、技术架构设计 #mermaid-svg-iuNaeeLK2YoFKfao {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg…...

在HarmonyOS ArkTS ArkUI-X 5.0及以上版本中,手势开发全攻略:

在 HarmonyOS 应用开发中&#xff0c;手势交互是连接用户与设备的核心纽带。ArkTS 框架提供了丰富的手势处理能力&#xff0c;既支持点击、长按、拖拽等基础单一手势的精细控制&#xff0c;也能通过多种绑定策略解决父子组件的手势竞争问题。本文将结合官方开发文档&#xff0c…...

[ICLR 2022]How Much Can CLIP Benefit Vision-and-Language Tasks?

论文网址&#xff1a;pdf 英文是纯手打的&#xff01;论文原文的summarizing and paraphrasing。可能会出现难以避免的拼写错误和语法错误&#xff0c;若有发现欢迎评论指正&#xff01;文章偏向于笔记&#xff0c;谨慎食用 目录 1. 心得 2. 论文逐段精读 2.1. Abstract 2…...

华为OD机试-食堂供餐-二分法

import java.util.Arrays; import java.util.Scanner;public class DemoTest3 {public static void main(String[] args) {Scanner in new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别while (in.hasNextLine()) { // 注意 while 处理多个 caseint a in.nextIn…...

04-初识css

一、css样式引入 1.1.内部样式 <div style"width: 100px;"></div>1.2.外部样式 1.2.1.外部样式1 <style>.aa {width: 100px;} </style> <div class"aa"></div>1.2.2.外部样式2 <!-- rel内表面引入的是style样…...

Android 之 kotlin 语言学习笔记三(Kotlin-Java 互操作)

参考官方文档&#xff1a;https://developer.android.google.cn/kotlin/interop?hlzh-cn 一、Java&#xff08;供 Kotlin 使用&#xff09; 1、不得使用硬关键字 不要使用 Kotlin 的任何硬关键字作为方法的名称 或字段。允许使用 Kotlin 的软关键字、修饰符关键字和特殊标识…...

《C++ 模板》

目录 函数模板 类模板 非类型模板参数 模板特化 函数模板特化 类模板的特化 模板&#xff0c;就像一个模具&#xff0c;里面可以将不同类型的材料做成一个形状&#xff0c;其分为函数模板和类模板。 函数模板 函数模板可以简化函数重载的代码。格式&#xff1a;templa…...

初探Service服务发现机制

1.Service简介 Service是将运行在一组Pod上的应用程序发布为网络服务的抽象方法。 主要功能&#xff1a;服务发现和负载均衡。 Service类型的包括ClusterIP类型、NodePort类型、LoadBalancer类型、ExternalName类型 2.Endpoints简介 Endpoints是一种Kubernetes资源&#xf…...