力扣hot100:240.搜索二维矩阵II(脑子)

吉大21级算法分析与设计的一道大题,由于每一行都是排好序的直接逐行二分 可以达到:O(mlogn)。但是这里追求更广的思路可以使用其他方法。
矩阵四分:
在矩阵中用中心点比较,如果target大于中心点的值,则由于升序排列,以中心点为右下角的小矩阵就不用再查找了,因为他们一定比target小。剩下三个矩形都可能比中心点大,因此在剩下三个矩阵中继续查找;如果target小于中心点,以中心点为右下角的小矩阵可能包含,并且中心点的左下方和右上方都有可能比中心点小,因此仍然需要继续查找。
每次可以去掉矩阵中的¼,对于每一个小矩阵它们是整个矩阵的¼,分析如下:
class Solution {
public:bool searchMatrix(vector<vector<int>>& matrix, int target) {tar=target;return find(matrix,0,matrix.size()-1,0,matrix[0].size()-1);}
private:bool find(vector<vector<int>>& matrix,int row_left,int row_right,int col_top,int col_bottom){if(row_left>row_right||col_top>col_bottom||col_bottom>=matrix[0].size()||row_right>=matrix.size()) return false;if(row_left==row_right&&col_top==col_bottom&&tar!=matrix[row_left][col_bottom]) return false;int mid_row=(row_left+row_right)>>1;int mid_col=(col_top+col_bottom)>>1;if(tar==matrix[mid_row][mid_col]) return true;if(tar>matrix[mid_row][mid_col])return find(matrix,mid_row+1,row_right,col_top,mid_col)||find(matrix,row_left,mid_row,mid_col+1,col_bottom)||find(matrix,mid_row+1,row_right,mid_col+1,col_bottom);else return find(matrix,row_left,mid_row,col_top,mid_col)||find(matrix,mid_row+1,row_right,col_top,mid_col)||find(matrix,row_left,mid_row,mid_col+1,col_bottom);}
private:int tar;
};
Z字形查找:
Krahets - 力扣(LeetCode):

用二叉树来看就特别清晰了。任何一个结点均满足,左儿子小于它,右儿子大于它。如果target比它大,同一行左边一定不再满足要求,如果target比它小,同一列下边一定不再满足要求。由于我们是从右上角开始的,依次进行,每一步都使得解只能在划定的范围内,因此这样做是正确的,时间复杂度为O(m+n)。
class Solution {
public:bool searchMatrix(vector<vector<int>>& matrix, int target) {int m=0,n=matrix[0].size()-1;while(m<matrix.size()&&n>=0&&matrix[m][n]!=target){if(matrix[m][n]>target) --n;else ++m;}cout<<m<<' '<<n;if(m<matrix.size()&&n>=0) return true;return false;}
};
暴力解法:
防止题目做多了不会暴力了()

class Solution {
public:bool searchMatrix(vector<vector<int>>& matrix, int target) {for(int i=0;i<matrix.size();++i)for(int &num:matrix[i])if(num==target) return true;return false;}
};
相关文章:
力扣hot100:240.搜索二维矩阵II(脑子)
吉大21级算法分析与设计的一道大题,由于每一行都是排好序的直接逐行二分 可以达到:O(mlogn)。但是这里追求更广的思路可以使用其他方法。 矩阵四分: 在矩阵中用中心点比较,如果target大于中心点的值,则由于升序排列&am…...
Apache Hive(三)
一、Apache Hive 1、ETL数据清洗 数据问题 问题1:当前数据中,有一些数据的字段为空,不是合法数据 解决:where 过滤 问题2:需求中,需要统计每天、每个小时的消息量,但是数据中没有天和小时字段…...
ORM(对象关系映射)的概念,并说明在Python中如何使用
ORM(对象关系映射)的概念,并说明在Python中如何使用 ORM(对象关系映射)是一种编程技术,它实现了将关系型数据库中的数据映射到程序中的对象模型,使得开发者能够使用面向对象的方式来操作数据…...
Br 算法
基于google的brotli开源,实现Br算法。 #include <brotli/encode.h> #include <brotli/decode.h>namespace br {/*compress unsigned char* content,if ok return non empty unsigned char * */std::string compress_string(const std::string& c…...
GPT实战系列-一种构建LangChain自定义Tool工具的简单方法
GPT实战系列-一种构建LangChain自定义Tool工具的简单方法 LLM大模型: GPT实战系列-探究GPT等大模型的文本生成 GPT实战系列-Baichuan2等大模型的计算精度与量化 GPT实战系列-GPT训练的Pretraining,SFT,Reward Modeling,RLHF …...
【Docker】Memcached 容器化部署
Memcached环境标准软件基于Bitnami Memcached 构建。当前版本为1.6.24 你可以通过轻云UC部署工具直接安装部署,也可以手动按如下文档操作,该项目已经全面开源,可以从如下环境获取 配置文件地址: https://gitee.com/qingplus/qingcloud-platf…...
Langchain-Chatchat本地搭建ChatGLM3模型和提取PDF内容
文章目录 1、软件要求2、安装CUDA2.1、安装gcc2.2、安装CUDA 3、安装Anaconda33.1、下载Anaconda33.2、创建python虚拟环境 4、部署系统4.1、下载源码4.2、安装依赖4.3、下载模型4.4、初始化配置和知识库4.4.1、初始化配置4.4.2、初始化知识库 4.5、运行4.6、运行4.6.1、启动4.…...
案例分析篇03:一篇文章搞定软考设计模式考点(2024年软考高级系统架构设计师冲刺知识点总结系列文章)
专栏系列文章推荐: 2024高级系统架构设计师备考资料(高频考点&真题&经验)https://blog.csdn.net/seeker1994/category_12593400.html 【历年案例分析真题考点汇总】与【专栏文章案例分析高频考点目录】(2024年软考高级系统架构设计师冲刺知识点总结-案例分析篇-…...
套接字的地址结构,IP地址转换函数,网络编程的接口
目录 一、套接字的地址结构 1.1 通用socket地址结构 1.2 专用socket地址结构 1.2.1 tcp协议族 1.2.3 IP协议族 二、IP地址转换函数 三、网络编程接口 3.1 socket() 3.2 bind() 3.3 listen() 3.4 accept() 3.5 connect() 3.6 close() 3.7 recv()、send() 3.8 recv…...
Java回顾总结--RandomAccessFile和NIO
目录 一、RandomAccessFile1.1 为什么要有RandomAccessFile?1.2 常用方法简介1.3 RandomAccessFile 特点和优势1.3.1 既可以读也可以写1.3.2 可以指定位置读写 1.4 示例 二、NIONIO使用示例 一、RandomAccessFile 1.1 为什么要有RandomAccessFile? Ran…...
2024年3月第15届蓝桥杯青少组STEMA考试C++中高级真题试卷
第15届蓝桥杯青少组STEMA考试C中高级真题试卷(2024年3月) 题目总数:11 总分数:400 选择题 第 1 题 单选题 (110010)2(c3)16的结果是( )。 A. (240)10 B. (11110101)2 C. (366)8 D. (f6)16 第 2 题 单选题 …...
Hyperf AOP 和 注解
注解 (hyperf.wiki) AOP 面向切面编程 (hyperf.wiki) 切面 定义切面(Aspect) 根据官方教程定义一个切面。可以指定类、方法、参数和注解上生效。 <?php namespace App\Aspect;use App\Service\SomeClass; use App\Annotation\SomeAnnotation; use Hyperf\Di\Annotatio…...
【C++】string类(介绍、常用接口)
🌈个人主页:秦jh__https://blog.csdn.net/qinjh_?spm1010.2135.3001.5343🔥 系列专栏:http://t.csdnimg.cn/eCa5z 目录 string类的常用接口说明 string类对象的常见构造 编辑 string字符串的遍历(迭代器…...
SpringBoot项目中同时支持https和http协议
实用干货!看壹哥如何在SpringBoot项目中同时支持https和http协议_springboot http htpps共存-CSDN博客...
三大排序:冒泡、选择、插入
冒泡排序: 冒泡排序(Bubble Sort)是一种简单的排序算法。它通过比较相邻元素的大小,并交换它们的位置,使较大(或较小)的元素逐渐“浮”到数组的一端,从而实现排序的目的。 下面是冒…...
Android中MultiDex优化
MultiDex基本思路 当一个Dex文件太肥的时候(方法数目太多、文件太大),在打包或在安装或运行apk也会出问题。 解决方法就是将这个硕大的Dex文件拆分成若干个小的Dex文件。 刚好一个ClassLoader可以有多个DexFile。 MultiDex主要性能瓶颈 解压缩和Dex优化(…...
MySQL 8.0 的执行计划(EXPLAIN)
MySQL 8.0 的执行计划(也称为“EXPLAIN”计划)是数据库优化器为 SQL 查询生成的步骤序列。解读执行计划可以帮助数据库管理员(DBA)和开发者理解查询如何执行,识别潜在的性能问题,并据此优化查询。 下面是如…...
leetcode——二叉树问题汇总
leetcode 144. 二叉树的前序遍历 ①递归法: /*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val val; }* TreeNode(int val,…...
Android基础开发-饿汉式申请权限
1、案例,打开app时,就要申请权限 直接在onCreateView中申请所有权限就可,然后在选择的回调里边判断申请的结果 package com.example.client;import android.Manifest; import android.content.Intent; import android.content.pm.PackageMa…...
java Day7 正则表达式|异常
文章目录 1、正则表达式1.1 常用1.2 字符串匹配,提取,分割 2、异常2.1 运行时异常2.2 编译时异常2.3 自定义异常2.3.1 自定义编译时异常2.3.2 自定义运行时异常 1、正则表达式 就是由一些特定的字符组成,完成一个特定的规则 可以用来校验数据…...
IDEA运行Tomcat出现乱码问题解决汇总
最近正值期末周,有很多同学在写期末Java web作业时,运行tomcat出现乱码问题,经过多次解决与研究,我做了如下整理: 原因: IDEA本身编码与tomcat的编码与Windows编码不同导致,Windows 系统控制台…...
React第五十七节 Router中RouterProvider使用详解及注意事项
前言 在 React Router v6.4 中,RouterProvider 是一个核心组件,用于提供基于数据路由(data routers)的新型路由方案。 它替代了传统的 <BrowserRouter>,支持更强大的数据加载和操作功能(如 loader 和…...
大数据零基础学习day1之环境准备和大数据初步理解
学习大数据会使用到多台Linux服务器。 一、环境准备 1、VMware 基于VMware构建Linux虚拟机 是大数据从业者或者IT从业者的必备技能之一也是成本低廉的方案 所以VMware虚拟机方案是必须要学习的。 (1)设置网关 打开VMware虚拟机,点击编辑…...
ESP32读取DHT11温湿度数据
芯片:ESP32 环境:Arduino 一、安装DHT11传感器库 红框的库,别安装错了 二、代码 注意,DATA口要连接在D15上 #include "DHT.h" // 包含DHT库#define DHTPIN 15 // 定义DHT11数据引脚连接到ESP32的GPIO15 #define D…...
ElasticSearch搜索引擎之倒排索引及其底层算法
文章目录 一、搜索引擎1、什么是搜索引擎?2、搜索引擎的分类3、常用的搜索引擎4、搜索引擎的特点二、倒排索引1、简介2、为什么倒排索引不用B+树1.创建时间长,文件大。2.其次,树深,IO次数可怕。3.索引可能会失效。4.精准度差。三. 倒排索引四、算法1、Term Index的算法2、 …...
Go 并发编程基础:通道(Channel)的使用
在 Go 中,Channel 是 Goroutine 之间通信的核心机制。它提供了一个线程安全的通信方式,用于在多个 Goroutine 之间传递数据,从而实现高效的并发编程。 本章将介绍 Channel 的基本概念、用法、缓冲、关闭机制以及 select 的使用。 一、Channel…...
tauri项目,如何在rust端读取电脑环境变量
如果想在前端通过调用来获取环境变量的值,可以通过标准的依赖: std::env::var(name).ok() 想在前端通过调用来获取,可以写一个command函数: #[tauri::command] pub fn get_env_var(name: String) -> Result<String, Stri…...
git: early EOF
macOS报错: Initialized empty Git repository in /usr/local/Homebrew/Library/Taps/homebrew/homebrew-core/.git/ remote: Enumerating objects: 2691797, done. remote: Counting objects: 100% (1760/1760), done. remote: Compressing objects: 100% (636/636…...
STM32标准库-ADC数模转换器
文章目录 一、ADC1.1简介1. 2逐次逼近型ADC1.3ADC框图1.4ADC基本结构1.4.1 信号 “上车点”:输入模块(GPIO、温度、V_REFINT)1.4.2 信号 “调度站”:多路开关1.4.3 信号 “加工厂”:ADC 转换器(规则组 注入…...
SQL进阶之旅 Day 22:批处理与游标优化
【SQL进阶之旅 Day 22】批处理与游标优化 文章简述(300字左右) 在数据库开发中,面对大量数据的处理任务时,单条SQL语句往往无法满足性能需求。本篇文章聚焦“批处理与游标优化”,深入探讨如何通过批量操作和游标技术提…...


