LeetCode Hot 100:二分查找
LeetCode Hot 100:二分查找
35. 搜索插入位置
思路 1:lower_bound
class Solution {
public:int searchInsert(vector<int>& nums, int target) {return lower_bound(nums.begin(), nums.end(), target) - nums.begin();}
};
思路 2:二分查找
class Solution {
public:int searchInsert(vector<int>& nums, int target) {int n = nums.size();int left = 0, right = n - 1;while (left <= right) {int mid = left + (right - left) / 2;if (nums[mid] > target)right = mid - 1;else if (nums[mid] < target)left = mid + 1;elsereturn mid;}return left;}
};
74. 搜索二维矩阵
思路 1:从左下方开始查找
class Solution {
public:bool searchMatrix(vector<vector<int>>& matrix, int target) {int m = matrix.size(), n = m ? matrix[0].size() : 0;int i = 0, j = n - 1;while (i < m && j >= 0) {if (matrix[i][j] == target)return true;else if (matrix[i][j] > target)j--;elsei++;}return false;}
};
思路 2:从右上方开始查找
class Solution {
public:bool searchMatrix(vector<vector<int>>& matrix, int target) {int m = matrix.size(), n = m ? matrix[0].size() : 0;int i = m - 1, j = 0;while (i >= 0 && j < n) {if (matrix[i][j] == target)return true;else if (matrix[i][j] > target)i--;elsej++;}return false;}
};
思路 3:二分查找
class Solution {
public:bool searchMatrix(vector<vector<int>>& matrix, int target) {int m = matrix.size(), n = m ? matrix[0].size() : 0;int left = 0, right = m * n - 1;while (left <= right) {int mid = left + (right - left) / 2;int x = mid / n, y = mid % n;if (matrix[x][y] == target)return true;else if (matrix[x][y] > target)right = mid - 1;elseleft = mid + 1;}return false;}
};
34. 在排序数组中查找元素的第一个和最后一个位置
class Solution {
public:vector<int> searchRange(vector<int>& nums, int target) {if (nums.empty())return {-1, -1};int lower =lower_bound(nums.begin(), nums.end(), target) - nums.begin();if (lower == nums.size() || nums[lower] != target)return {-1, -1};int upper =upper_bound(nums.begin(), nums.end(), target) - nums.begin() - 1;return {lower, upper};}
};
33. 搜索旋转排序数组
class Solution {
public:int search(vector<int>& nums, int target) {if (nums.empty())return -1;int n = nums.size();if (n == 1)return nums[0] == target ? 0 : -1;int left = 0, right = n - 1;while (left <= right) {int mid = left + (right - left) / 2;if (nums[mid] == target)return mid;if (nums[0] <= nums[mid]) {if (nums[0] <= target && target < nums[mid])right = mid - 1;elseleft = mid + 1;} else {if (nums[n - 1] >= target && target > nums[mid])left = mid + 1;elseright = mid - 1;}}return -1;}
};
153. 寻找旋转排序数组中的最小值
class Solution {
public:int findMin(vector<int>& nums) {int left = 0, right = nums.size() - 1;while (left < right) {int mid = left + (right - left) / 2;if (nums[mid] < nums[right])right = mid;elseleft = mid + 1;}return nums[left];}
};
4. 寻找两个正序数组的中位数
class Solution {
public:double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {int m = nums1.size();int n = nums2.size();int total = m + n;if (total % 2 == 1)return getKthElement(nums1, nums2, (total + 1) / 2);elsereturn (getKthElement(nums1, nums2, total / 2) +getKthElement(nums1, nums2, total / 2 + 1)) /2.0;}int getKthElement(vector<int>& nums1, vector<int>& nums2, int k) {int m = nums1.size();int n = nums2.size();int index1 = 0, index2 = 0;while (true) {// 边界情况if (index1 == m)return nums2[index2 + k - 1];if (index2 == n)return nums1[index1 + k - 1];if (k == 1)return min(nums1[index1], nums2[index2]);// 正常情况int newIndex1 = min(index1 + k / 2 - 1, m - 1);int newIndex2 = min(index2 + k / 2 - 1, n - 1);int pivot1 = nums1[newIndex1];int pivot2 = nums2[newIndex2];if (pivot1 <= pivot2) {k -= newIndex1 - index1 + 1;index1 = newIndex1 + 1;} else {k -= newIndex2 - index2 + 1;index2 = newIndex2 + 1;}}}
};
相关文章:
LeetCode Hot 100:二分查找
LeetCode Hot 100:二分查找 35. 搜索插入位置 思路 1:lower_bound class Solution { public:int searchInsert(vector<int>& nums, int target) {return lower_bound(nums.begin(), nums.end(), target) - nums.begin();} };思路 2…...
打包方式-jar和war的区别
1、jar包 JAR包是类的归档文件,与平台无关的文件格式,其实jar包就是java的类进行编译生成的class文件进行打包的压缩包。 JAR以ZIP文件格式为基础,与ZIP不同的是,JAR不仅用于压缩和发布,还用于部署和封装库、组件和插…...
【论文+源码】基于spring boot的垃圾分类网站
创建一个基于Spring Boot的垃圾分类网站涉及多个步骤,包括环境搭建、项目创建、数据库设计、后端服务开发、前端页面设计等。下面我将引导您完成这个过程。 第一步:准备环境 确保您的开发环境中安装了以下工具: Java JDK 8 或更高版本Mav…...
【C++ STL 模板类】pair 键值对
文章目录 【 1. pair 对象的创建 】【 2. pair 对象的赋值 】【 3. pair 对象的比较 】【 4. pair对象成员的互换】 C STL 标准库提供了 pair 类模板,专门用来将 2 个普通元素 first 和 second(可以是 C 基本数据类型、结构体、类自定的类型)…...
paddleocr使用FastDeploy 部署工具部署 rknn 模型
在 PC 端转换 pdmodel 模型为 rknn 模型和在板端使用百度飞浆开发的 FastDeploy 部署工具部署 rknn 模型 以下内容是在 PC 端系统为 Ubuntu20.04,板端系统为ubuntu20.04 的环境下实现的 描述: 官网地址 rknn_zoo RKNPU2_SDK …...
Apple Vision Pro市场表现分析:IDC最新数据揭示的真相
随着AR/VR技术逐渐成熟并被更多消费者接受,2024年第二季度(Q2)成为这一领域的一个重要转折点。根据国际数据公司(IDC)发布的最新报告,整个AR/VR市场在本季度经历了显著的增长。接下来,我们将深入探讨Apple Vision Pro在这股增长浪潮中的具体表现。 市场背景 2024年Q2,…...
Mybatis-04.入门-JDBC
一.JDBC 二.原始的JDBC程序代码 (不做要求) Test public void testJdbc() throws Exception {//1. 注册驱动Class.forName("com.mysql.cj.jdbc.Driver");//2. 获取连接对象String url "jdbc:mysql://localhost:3306/mybatis";Str…...
拥抱云开发的未来:腾讯云数据库、云模板与AI智能化的应用场景探索
本文目录: 💡前言:技术的边界在不断延展🌟目录🌈什么是腾讯云云开发?💾云数据库:让数据成为开发的稳固基石🥑数据,不再只是数据 🛠云模板…...
新手铲屎官求推荐,噪音低的宠物空气净化器应该用哪款
当初选择养橘猫就是因为我听到有人说橘猫不容易掉毛才养的,谁知道养了之后和传闻中的不一样,真正的让我明白了什么叫“眼见为实”。 主要是猫掉毛就掉毛,只要我能清理的我都会清理,只要能保证养猫的同时还能保持家里卫生干净就行…...
玄机平台-应急响应-webshell查杀
首先xshell连接 然后进入/var/www/html目录中,将文件变成压缩包 cd /var/www/html tar -czvf web.tar.gz ./* 开启一个http.server服务,将文件下载到本地 python3 -m http.server 放在D盾中检测 基本可以确认木马文件就是这四个 /var/www/html/shell.p…...
LeetCode Hot 100:图论
LeetCode Hot 100:图论 200. 岛屿数量 思路 1:深度优先搜索 class Solution { private:const int dx[4] {-1, 0, 1, 0};const int dy[4] {0, 1, 0, -1};public:int numIslands(vector<vector<char>>& grid) {if (grid.empty())retu…...
tracert和ping的区别
1、简介 tracert(在 Windows 系统中)和 traceroute(在 Unix/Linux 系统中)以及 ping 都是网络诊断工具,但它们的功能和用途有所不同: ping: 用途:ping 是一个网络工具&…...
回归、分类模型的评估指标
1. 分类模型的评估指标 评估机器学习模型的好坏至关重要,它帮助我们判断模型的性能、稳定性以及在实际问题中的应用效果。不同类型的机器学习任务(分类、回归、聚类等)有不同的评估指标。以下是详细介绍常见的模型评估指标,尤其针…...
k8s中如何将pod的标准输出日志输出到一个文件
假设容器的启动命令是 grpcserver,我们将通过修改启动命令,将 grpcserver 的标准输出重定向到指定的日志文件 /var/log/app/grpcserver.log,同时保留标准输出以便 Kubernetes 日志系统仍然能够捕获日志。 目标: 将 grpcserver 的…...
软件工程文档规范要点总结
需求分析文档 1.目标用户应该体现为用例图里的执行者(执行者要标明是哪一类用户) 2.用例模型由功能概述得到,用例顺序图由基本交互过程得到,分析类图由顺序图得到 3.执行者和用例之间的关系:执行、触发、驱动 用例…...
Django 序列化serializers
在Django中,序列化通常指的是将数据库中的模型数据转换为JSON、XML或其他格式的过程。Django提供了内置的序列化工具,可以通过django.core.serializers模块进行序列化操作。 当你使用Django的序列化功能时,可以序列化以下两种对象类型&#…...
混个1024勋章
一眨眼毕业工作已经一年了,偶然进了游戏公司成了一名初级游戏服务器开发。前两天总结的时候,本来以为自己这一年没学到多少东西,但是看看自己的博客其实也有在进步,虽然比不上博客里的众多大佬,但是回头看也算是自己的…...
Java Spring Boot 项目开发示例指南
开发和扩展一个 Java Spring Boot 项目可以分为几个步骤。以下是一个简单的指南,涵盖项目的创建、基本功能的实现、以及扩展的示例。 第一步:创建 Spring Boot 项目 使用 Spring Initializr 创建项目: 访问 Spring Initializr选择项目的配置(…...
Python学习路线:从新手到专家
引言 Python 是一种高级编程语言,以其简洁清晰的语法而闻名,被广泛应用于Web开发、数据科学、人工智能、自动化脚本等领域。无论你是编程初学者还是有经验的开发者,Python 都是一个值得学习的语言。本文将提供一份详细的Python学习路线图&am…...
R实验——logistic回归、LDA、QDAKNN
数据集介绍: mpg,miles per gallon即油耗,这个数据集来自卡内基梅隆大学维护的StatLib库。1983年美国统计协会博览会使用了该数据集。这个数据集是对StatLib库中提供的数据集稍加修改的版本。根据Ross Quinlan(1993)在预测属性“mpg”中的使…...
观成科技:隐蔽隧道工具Ligolo-ng加密流量分析
1.工具介绍 Ligolo-ng是一款由go编写的高效隧道工具,该工具基于TUN接口实现其功能,利用反向TCP/TLS连接建立一条隐蔽的通信信道,支持使用Let’s Encrypt自动生成证书。Ligolo-ng的通信隐蔽性体现在其支持多种连接方式,适应复杂网…...
循环冗余码校验CRC码 算法步骤+详细实例计算
通信过程:(白话解释) 我们将原始待发送的消息称为 M M M,依据发送接收消息双方约定的生成多项式 G ( x ) G(x) G(x)(意思就是 G ( x ) G(x) G(x) 是已知的)࿰…...
ESP32 I2S音频总线学习笔记(四): INMP441采集音频并实时播放
简介 前面两期文章我们介绍了I2S的读取和写入,一个是通过INMP441麦克风模块采集音频,一个是通过PCM5102A模块播放音频,那如果我们将两者结合起来,将麦克风采集到的音频通过PCM5102A播放,是不是就可以做一个扩音器了呢…...
新能源汽车智慧充电桩管理方案:新能源充电桩散热问题及消防安全监管方案
随着新能源汽车的快速普及,充电桩作为核心配套设施,其安全性与可靠性备受关注。然而,在高温、高负荷运行环境下,充电桩的散热问题与消防安全隐患日益凸显,成为制约行业发展的关键瓶颈。 如何通过智慧化管理手段优化散…...
leetcodeSQL解题:3564. 季节性销售分析
leetcodeSQL解题:3564. 季节性销售分析 题目: 表:sales ---------------------- | Column Name | Type | ---------------------- | sale_id | int | | product_id | int | | sale_date | date | | quantity | int | | price | decimal | -…...
HDFS分布式存储 zookeeper
hadoop介绍 狭义上hadoop是指apache的一款开源软件 用java语言实现开源框架,允许使用简单的变成模型跨计算机对大型集群进行分布式处理(1.海量的数据存储 2.海量数据的计算)Hadoop核心组件 hdfs(分布式文件存储系统)&a…...
PAN/FPN
import torch import torch.nn as nn import torch.nn.functional as F import mathclass LowResQueryHighResKVAttention(nn.Module):"""方案 1: 低分辨率特征 (Query) 查询高分辨率特征 (Key, Value).输出分辨率与低分辨率输入相同。"""def __…...
Linux 中如何提取压缩文件 ?
Linux 是一种流行的开源操作系统,它提供了许多工具来管理、压缩和解压缩文件。压缩文件有助于节省存储空间,使数据传输更快。本指南将向您展示如何在 Linux 中提取不同类型的压缩文件。 1. Unpacking ZIP Files ZIP 文件是非常常见的,要在 …...
C#学习第29天:表达式树(Expression Trees)
目录 什么是表达式树? 核心概念 1.表达式树的构建 2. 表达式树与Lambda表达式 3.解析和访问表达式树 4.动态条件查询 表达式树的优势 1.动态构建查询 2.LINQ 提供程序支持: 3.性能优化 4.元数据处理 5.代码转换和重写 适用场景 代码复杂性…...
Unity UGUI Button事件流程
场景结构 测试代码 public class TestBtn : MonoBehaviour {void Start(){var btn GetComponent<Button>();btn.onClick.AddListener(OnClick);}private void OnClick(){Debug.Log("666");}}当添加事件时 // 实例化一个ButtonClickedEvent的事件 [Formerl…...
