搜索二维矩阵 II - LeetCode 热题 21

大家好!我是曾续缘💗

今天是《LeetCode 热题 100》系列

发车第 21 天

矩阵第 4 题

❤️点赞 👍 收藏 ⭐再看,养成习惯

搜索二维矩阵 II

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

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

示例 1:

输入:matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5
输出:true

示例 2:

输入:matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 20
输出:false

提示:

  • m == matrix.length
  • n == matrix[i].length
  • 1 <= n, m <= 300
  • -109 <= matrix[i][j] <= 109
  • 每行的所有元素从左到右升序排列
  • 每列的所有元素从上到下升序排列
  • -109 <= target <= 109
难度:💖💖

解题方法

对于矩阵中的某个点matrix[i][j]来说,观察到向左移动数字减小,向下移动数字增大,类似于二分查找树的性质。同样地,向上移动数字减小,向右移动数字增大,也类似于二分查找树。

如果我们限制只能向左或向下移动,这就相当于在遍历二分查找树;同理,如果限制只能向右或向上移动,也可以看作是在遍历二分查找树。

接下来,我们需要找到二分查找树的根节点,使其包含矩阵中的所有值。可以选择左下角和右上角两个点作为二分查找树的根节点。

以左下角为例:

  • 如果目标值大于当前值,则向上移动。
  • 如果目标值小于当前值,则向右移动。
  • 如果相等,则直接返回 true。
  • 如果移出矩阵范围,说明到达空结点,返回 false。

Code

class Solution {public boolean searchMatrix(int[][] matrix, int target) {int m = matrix.length, n = matrix[0].length;int i = 0, j = n - 1; // 右上角while(i < m && j >= 0){if(matrix[i][j] == target){return true;}if(matrix[i][j] > target){j--;}else{i++;}}return false;}
}

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

如若内容造成侵权/违法违规/事实不符,请联系一条长河网进行投诉反馈,一经查实,立即删除!

相关文章

软件架构风格_2.调用/返回体系结构风格

调用/返回风格是指在系统中采用了调用与返回机制。利用调用-返回实际上是一种分而治之的策略&#xff0c;其主要思想是将一个复杂的大系统分解为若干子系统&#xff0c;以便降低复杂度&#xff0c;并且增加可修改性。程序从其执行起点开始执行该构件的代码&#xff0c;程序执行…

Groovy 介绍、下载、语法

Groovy 简介 Groovy 可以被视为Java 的一种脚本化改良版&#xff0c;Groovy 也是运行在 JVM 上&#xff0c;可以很好地与 Java 代码及其相关库进行交互操作。Groovy 是一种成熟的面向对象编程语言&#xff0c;既可以面向对象编程&#xff0c;又可以用作纯粹的脚本语言。大多数…

融资融券有什么优点和缺点?融资利率和费率多少?

融资融券是一种证券信用交易&#xff0c;指投资者向具有融资融券业务资格的证券公司提供担保物&#xff0c;借入资金买入证券或者借入证券并卖出的行为 融资融券的优点有&#xff1a; 增加交易资金。投资者可以通过融资融券账户&#xff0c;向证券公司借入资金&#xff0c;增加…

sa-token非Web上下文无法获取Request

0x02 非Web上下文无法获取Request 问题定位 在我们使用sa-token安全框架的时候&#xff0c;有时候会提示&#xff1a;**SaTokenException:非Web上下文无法获取Request**** 错误截图&#xff1a; 在官方网站中&#xff0c;查看常见问题排查&#xff1a; 非Web上下文无法获取…

QT使用数据库和proC数据库

一&#xff0c;QT使用数据库 数据库就是保存数据的文件。可以存储大量数据&#xff0c;包括插入数据、更新数据、截取数据等。用专业术语来说&#xff0c;数据库是“按照数据结构来组织、存储和管理数据的仓库”。 什么时候需要数据库&#xff1f;在嵌入式里&#xff0…

每日一题(leetcode169):多数元素-哈希、随机、分治

哈希&#xff1a; class Solution { public:int majorityElement(vector<int>& nums) {int lennums.size();unordered_map<int,int> map;for (int i0;i<len;i){if(map.find(nums[i])map.end()){map[nums[i]]1;}else{map[nums[i]];}}int seqlen/2;int ansnu…

FebHost:注册人工智能.AI域名的优势?

近年来,人工智能技术的飞速发展,让AI在各行各业扮演着愈发重要的角色。在这一背景下,.AI域名凭借其独特的优势,正成为越来越多AI从业者的首选。那么,.AI域名到底有哪些亮点,值得广大AI企业和个人关注呢?记者进行了深入探访。 专业形象加分 彰显技术实力 要说.AI域名的最大优势…

yolov5关键点检测-实现溺水检测与警报提示(代码+原理)

基于YOLOv5的关键点检测应用于溺水检测与警报提示是一种结合深度学习与计算机视觉技术的安全监控解决方案。该项目通常会利用YOLOv5强大的实时目标检测能力&#xff0c;并通过扩展或修改网络结构以支持人体关键点检测&#xff0c;来识别游泳池或其他水域中人们的行为姿态。 项…

为何网易游戏会选择引入OceanBase数据库

本文作者&#xff1a;田维繁&#xff0c;网易游戏关系型数据库小组负责人 作为中国游戏开发领域的佼佼者&#xff0c;网易游戏始终站在网络游戏自主研发的前沿。其产品及周边产品线丰富多样&#xff0c;因此&#xff0c;为满足各种业务场景的需求&#xff0c;需要多种不同的数据…

delphi获取windows右下角任务栏图标信息

今天在群里,看有人问怎么获取windows右下角任务栏图标信息 win7 x64 测试通过 unit Unit1;interfaceusesWinapi.Windows, Winapi.Messages, System.SysUtils, System.Variants, System.Classes, Vcl.Graphics,Vcl.Controls, Vcl.Forms, Vcl.Dialogs,commctrl, Vcl.StdCtr…

烂笔头笔记:Windows 11下照片查看器显示偏色问题修复

本文出处&#xff1a;http://blog.csdn.net/chaijunkun/article/details/137278931&#xff0c;转载请注明。由于本人不定期会整理相关博文&#xff0c;会对相应内容作出完善。因此强烈建议在原始出处查看此文。 最近在研究HDR视频的截图算法&#xff0c;目的就是生成色彩正确…

并发编程01-深入理解Java并发/线程等待/通知机制

为什么我们要学习并发编程&#xff1f; 最直白的原因&#xff0c;因为面试需要&#xff0c;我们来看看美团和阿里对 Java 岗位的 JD&#xff1a; 从上面两大互联网公司的招聘需求可以看到&#xff0c; 大厂的 Java 岗的并发编程能力属于标配。 而在非大厂的公司&#xff0c; 并…

如何在 Android 上恢复已删除的短信

在 Android 上恢复短信是一件棘手的事情。以下是限制、您的选择以及如何为未来做好准备。 丢失手机数据令人心碎。无论您不小心删除了某些内容&#xff0c;还是手机被盗或损坏&#xff0c;您不可替代的照片、亲人的消息等都可能会立即消失。 如果您需要从 Android 手机恢复一…

腾讯云最新活动及优惠券领取入口整理汇总

腾讯云作为国内领先的云服务提供商&#xff0c;始终致力于为广大用户提供更优质、更便捷的云服务体验。为了帮助用户更好地了解和参与腾讯云的活动&#xff0c;本文将对腾讯云的最新活动及优惠券领取入口进行整理汇总。 一、优惠券领取入口 领取入口&#xff1a;点此领取 领券…

OSPF实验1

1,配置IP地址 [R1]dis ip interface brief Interface IP Address/Mask Physical Protocol GigabitEthernet0/0/0 200.1.1.1/24 up up GigabitEthernet0/0/1 10.1.1.1/24 up …

Linux学习笔记————C 语言版 LED 灯实验

这里写目录标题 一、实验程序编写二、 汇编部分实验程序编写三、C 语言部分实验程序编写四、编译下载验证 汇编 LED 灯实验中&#xff0c;我们讲解了如何使用汇编来编写 LED 灯驱动&#xff0c;实际工作中是很少用到汇编去写嵌入式驱动的&#xff0c;毕竟汇编太难&#xff0c;而…

加密、签名、验签、证书、对称加密、非对称加密【部分知识点】

文章目录 前言如图一些概念区分不可逆加密可逆加密签名和验签 前言 总结一些涉及到OTA升级相关的数据加密知识点&#xff0c;仅作为笔记记录&#xff0c;仅部分总结&#xff0c;细节部分可以私聊我。 如图 一些概念区分 不可逆加密 哈希算法是一个统称&#xff0c;它分为MD…

HarmonyOS 应用开发之同应用跨设备数据同步

概述 场景介绍 跨设备数据同步功能&#xff08;即分布式功能&#xff09;&#xff0c;指将数据同步到一个组网环境中的其他设备。常用于用户应用程序数据内容在可信认证的不同设备间&#xff0c;进行自由同步、修改和查询。 例如&#xff1a;当设备1上的应用A在分布式数据库…

打印日志(JAVA)

1、通过导入包的形式 package com.example.demo;import org.slf4j.Logger; import org.slf4j.LoggerFactory; import org.springframework.web.bind.annotation.RequestMapping; import org.springframework.web.bind.annotation.RestController; RequestMapping("/log&q…

信息系统项目管理师——第17章项目干系人管理

本章节内容属于10大管理知识领域&#xff0c;选择、案例、论文都会考。 选择题&#xff0c;稳定考1-2分左右&#xff0c;新教材基本考课本原话&#xff0c;这个分不能丢。 案例题&#xff0c;本期考的概率一般。 论文题&#xff0c;202205期考过。 1管理基础 管理的重要性 为…