每日算法-250405
34. 在排序数组中查找元素的第一个和最后一个位置
题目
思路
本题的核心思路是二分查找。
解题过程
- 问题分析:在一个升序排列的数组中查找一个目标值
target
的起始和结束位置。这是一个典型的二分查找应用场景。- 核心转换:题目要求找到
target
的第一个位置和最后一个位置。这可以转换为两个子问题:
- 找到第一个 大于等于
target
的元素的下标(记为left_bound
)。- 找到第一个 大于
target
的元素的下标,然后将这个下标减 1,就得到target
的最后一个位置(记为right_bound
)。这等价于找到第一个 大于等于target + 1
的元素的下标,然后减 1。- 实现
lower_bound
函数:我们可以实现一个通用的二分查找函数lower_bound(nums, k)
,用于查找数组nums
中第一个大于等于k
的元素的下标。
- 初始化指针
left = 0
,right = nums.length - 1
。- 循环条件
while (left <= right)
。- 计算中间位置
mid = left + (right - left) / 2
。- 如果
nums[mid] < k
,说明目标值k
(或第一个大于等于k
的元素)一定在mid
的右侧,更新left = mid + 1
。- 如果
nums[mid] >= k
,说明mid
可能是第一个大于等于k
的元素,或者目标在mid
的左侧。因此,我们需要继续在左半部分(包括mid
本身)查找,更新right = mid - 1
。- 循环结束后,
left
指针指向的位置就是第一个大于等于k
的元素的下标。如果数组中所有元素都小于k
,left
将会等于nums.length
。- 求解:
- 调用
lower_bound(nums, target)
得到left_index
。- 检查
left_index
:如果left_index
等于数组长度nums.length
或者nums[left_index]
不等于target
,说明数组中不存在target
,直接返回[-1, -1]
。- 调用
lower_bound(nums, target + 1)
得到right_index_plus_one
。target
的最后一个位置是right_index_plus_one - 1
。- 返回
[left_index, right_index_plus_one - 1]
。
复杂度
- 时间复杂度: O(log n) - 两次二分查找。
- 空间复杂度: O(1) - 只使用了常数级别的额外空间。
Code
class Solution {public int[] searchRange(int[] nums, int target) {// 查找第一个大于等于 target 的位置int leftIdx = lower_bound(nums, target);// 检查 leftIdx 是否越界 或 nums[leftIdx] != target// 如果是,说明 target 不存在if (leftIdx == nums.length || nums[leftIdx] != target) {return new int[] {-1, -1};}// 查找第一个大于等于 target + 1 的位置// 这个位置的前一个位置就是 target 的最后一个位置int rightIdx = lower_bound(nums, target + 1) - 1;return new int[] {leftIdx, rightIdx};}// 查找数组中第一个大于等于 k 的元素的下标private int lower_bound(int[] nums, int k) {int left = 0, right = nums.length - 1;while (left <= right) {int mid = left + (right - left) / 2;if (nums[mid] < k) {// [mid+1, right]left = mid + 1;} else { // nums[mid] >= k// [left, mid-1]right = mid - 1;}}// 循环结束后,left 就是第一个 >= k 的元素的下标return left;}
}
35. 搜索插入位置
题目
思路
同样使用二分查找。
解题过程
- 问题分析:在一个 无重复元素 的有序数组中,查找目标值
target
。如果找到,返回其下标;如果找不到,返回它应该插入的位置的下标,以保持数组有序。- 核心思想:这个问题本质上就是查找数组中第一个 大于等于
target
的元素的下标。
- 如果数组中存在
target
,那么第一个大于等于target
的元素就是target
本身,其下标即为所求。- 如果数组中不存在
target
,那么第一个大于等于target
的元素的位置,就是target
应该插入的位置。- 实现:可以直接复用上一题中的
lower_bound
查找逻辑。
- 初始化
left = 0
,right = nums.length - 1
。- 循环
while (left <= right)
。- 计算
mid
。- 如果
nums[mid] < target
,目标在右侧,left = mid + 1
。- 如果
nums[mid] >= target
,目标在mid
或其左侧,right = mid - 1
。- 循环结束后,
left
就是第一个大于等于target
的元素的下标。- 边界情况处理:
- 如果数组中所有元素都小于
target
,循环过程中left
会一直右移,最终left
变为nums.length
,这正好是target
应该插入的位置。- 如果数组中所有元素都大于
target
,循环过程中right
会一直左移,最终left
保持为0
,这也是target
应该插入的位置。- 因此,该二分查找的返回值
left
直接就是答案。
复杂度
- 时间复杂度: O(log n) - 一次二分查找。
- 空间复杂度: O(1) - 只使用了常数级别的额外空间。
Code
class Solution {public int searchInsert(int[] nums, int target) {int left = 0, right = nums.length - 1;while (left <= right) {int mid = left + (right - left) / 2;if (nums[mid] < target) {left = mid + 1; // 继续在右区间 [mid+1, right] 查找} else { // nums[mid] >= targetright = mid - 1; // 继续在左区间 [left, mid-1] 查找}}// 循环结束后,left 指向第一个大于等于 target 的元素下标// 或者,如果 target 大于所有元素,left 指向 nums.lengthreturn left;}
}
92. 反转链表 II (复习)
题目
复习心得
今天是第二次做这道题。核心思路仍然是找到
left
位置的前一个节点prev
,然后使用头插法,在left
到right
区间内,依次将cur
后面的节点curNext
移动到prev
的后面(也就是反转区间的头部)。在
while
循环里,关键在于理解节点连接的变化:
- 保存
cur
的下一个节点:ListNode curNext = cur.next;
- 让
cur
跳过curNext
,指向curNext
的下一个节点:cur.next = curNext.next;
- 将
curNext
插入到反转区间的头部,也就是prev
的后面:curNext.next = prev.next;
- 让
prev
指向新的头部curNext
:prev.next = curNext;
今天在写的时候,容易混淆的是步骤 3 和 4。一开始容易错误地写成
curNext.next = cur
,这是不对的,因为cur
是在移动的,只有在循环开始前prev.next
才指向反转区间的第一个节点。正确的做法是始终将curNext
插入到prev.next
所指向的位置。详细题解可以参考之前的笔记:每日算法-250328
Code
/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}* ListNode(int val) { this.val = val; }* ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode reverseBetween(ListNode head, int left, int right) {// 使用虚拟头节点简化边界处理(left=1 的情况)ListNode dummy = new ListNode(0);dummy.next = head;// 1. 找到 left 位置的前一个节点 prevListNode prev = dummy;for (int i = 1; i < left; i++) {prev = prev.next;}// prev.next 就是反转区间的第一个节点,记为 curListNode cur = prev.next;// 2. 执行头插法反转 left 到 right 区间的节点// 总共需要执行 right - left 次头插操作for (int i = left; i < right; i++) {// 获取 cur 的下一个节点,它将是下一个要移动到头部的节点ListNode nodeToMove = cur.next;// cur 跳过 nodeToMovecur.next = nodeToMove.next;// 将 nodeToMove 插入到 prev 的后面nodeToMove.next = prev.next;prev.next = nodeToMove;}return dummy.next;}
}
相关文章:
每日算法-250405
34. 在排序数组中查找元素的第一个和最后一个位置 题目 思路 本题的核心思路是二分查找。 解题过程 问题分析:在一个升序排列的数组中查找一个目标值 target 的起始和结束位置。这是一个典型的二分查找应用场景。核心转换:题目要求找到 target 的第一个…...
设计模式简述(四)模板方法模式
模板方法模式 描述基本定义使用 描述 当一系列业务的基本流程是相同的,对于不同的业务可以在各自子类实现 所谓模板方法指的就是父类中固定的那部分代码 其实这里的思想和前面设计原则中开闭原则的描述是一致的,父类中的模板代码就是稳定的部分&#x…...
论文修改时有哪些需要注意的问题?
论文修改是学术写作中不可或缺的环节,直接影响成果的专业性和说服力。许多作者因忽略细节或急于定稿,导致论文质量大打折扣。那么,如何修改才能提升论文的严谨性与可读性呢? 一、逻辑结构 论文修改时,先从头到尾通读…...
JAVA阻塞队列
目录 一、什么是阻塞队列?特点是什么? 二、阻塞队列的两种创建方式: 1、使用 ArrayBlockingQueue<>( ) : 2、使用 LinkedBlockingQueue<>( ) : 三、阻塞队列方法的使用: 阻塞队列关键的两个方法&…...
tomcat与spring-web
文章目录 SpringServletContainerInitializerWebApplicationInitializerWebApplicationInitializer接口AbstractContextLoaderInitializer抽象类AbstractDispatcherServletInitializer抽象类AbstractAnnotationConfigDispatcherServletInitializer抽象类 WebApplicationContext…...
将电脑控制手机编写为MCP server
文章目录 电脑控制手机后,截屏代码复习MCP server构建修改MCP的config文件测试效果困惑电脑控制手机后,截屏代码复习 def capture_window(hwnd: int, filename: str = None) -> dict:""&...
[ctfshow web入门]burpsuite的下载与使用
下载 吾爱破解网站工具区下载burpsuite https://www.52pojie.cn/thread-1544866-1-1.html 本博客仅转载下载链接,下载后请按照说明进行学习使用 打开 配置 burpsuite配置 burpsuite代理设置添加127.0.0.1:8080 浏览器配置 如果是谷歌浏览器,打开win…...
文章记单词 | 第25篇(六级)
一,单词释义 mathematical:形容词,意为 “数学的;数学上的;运算能力强的;关于数学的”trigger:名词,意为 “(枪的)扳机;(炸弹的&…...
讯飞语音合成(流式版)语音专业版高质量的分析
一、引言 在现代的 Web 应用开发中,语音合成技术为用户提供了更加便捷和人性化的交互体验。讯飞语音合成(流式版)以其高效、稳定的性能,成为了众多开发者的首选。本文将详细介绍在 Home.vue 文件中实现讯飞语音合成(流…...
【MediaPlayer】基于libvlc+awtk的媒体播放器
基于libvlcawtk的媒体播放器 libvlc下载地址 awtk下载地址 代码实现libvlc相关逻辑接口UI媒体接口实例化媒体播放器注意事项 libvlc 下载地址 可以到https://download.videolan.org/pub/videolan/vlc/去下载一个vlc版本,下载后其实是vlc的windows客户端࿰…...
复古未来主义屏幕辉光像素化显示器反乌托邦效果PS(PSD)设计模板样机 Analog Retro-Futuristic Monitor Effect
这款模拟复古未来主义显示器效果直接取材于 90 年代赛博朋克电影中的黑客巢穴,将粗糙的屏幕辉光和像素化的魅力强势回归。它精准地模仿了老式阴极射线管显示器,能将任何图像变成故障频出的监控画面或高风险的指挥中心用户界面。和……在一起 2 个完全可编…...
Kafka 如何保证消息有序性?
Kafka 保证消息顺序性,是基于 Partition(分区)级别的顺序 来实现的。下面我们详细拆解一下: ✅ 同一个 Partition 内,消息是严格有序的 Kafka 在 同一个分区(Partition)内,消息是按…...
【积木画】——第十三届蓝桥杯(2022)T7思路解析
题目描述 关键词 递推、dp 思路 显然这是一道递推题。 但是为什么我还要写在这呢?因为我虽然看了题解但是还是没想明白,综合了下面两篇 参考文献我才初步理解这题的精髓。所以还是自己写一遍为好。 我们把最终结果记为F(n)。 情况1 直接以一个竖着…...
Android studio xml布局预览中 Automotive和Autotive Distant Display的区别
在 Android Studio 中,Configure Hardware Profile 设置中的 Device Type 选项有两个不同的设置:Android Automotive 和 Android Automotive Distant Display,它们的含义和用途如下: 1. Android Automotive 含义:这个…...
第十三章:持久化存储_《凤凰架构:构建可靠的大型分布式系统》
第十三章 持久化存储 一、Kubernetes存储设计核心概念 (1)存储抽象模型 PersistentVolume (PV):集群级别的存储资源抽象(如NFS卷/云存储盘)PersistentVolumeClaim (PVC):用户对存储资源的声明请求&#…...
Nginx 基础使用(2025)
一、Nginx目录结构 [rootlocalhost ~]# tree /usr/local/nginx /usr/local/nginx ├── client_body_temp # POST 大文件暂存目录 ├── conf # Nginx所有配置文件的目录 │ ├── fastcgi.conf # fastcgi相…...
Docker基础1
本篇文章我将从系统的知识体系讲解docker的由来和在linux中的安装下载 随后的文章会介绍下载镜像、启动新容器、登录新容器 如需转载,标记出处 docker的出现就是为了节省资本和服务器资源 当企业需要一个新的应用程序时,需要为它买台全新的服务器。这样…...
【奇点时刻】GPT4o新图像生成模型底层原理深度洞察报告
个人最近一直在关注openai的新图像生成特性,以下内容基于现阶段社区及研究者们对 GPT-4O 图像生成功能的公开测试、逆向分析与技术推测综合而成,OpenAI 并未正式发布完整的技术报告,因此本文为非官方推断总结。但从多方信息与技术背景出发&am…...
Java的Selenium的特殊元素操作与定位之模态框
Modal Dialogue Box,又叫做模式对话框,是指在用户想要对对话框以外的应用程序进行操作时,必须首先对该对话框进行响应。如单击【确定】或【取消】按钮等将该对话框关闭。 alert(警告) //访问本地的HTML文件 chromeDr…...
回归预测 | Matlab实现NRBO-Transformer-LSTM多输入单输出回归预测
回归预测 | Matlab实现NRBO-Transformer-LSTM多输入单输出回归预测 目录 回归预测 | Matlab实现NRBO-Transformer-LSTM多输入单输出回归预测预测效果基本介绍程序设计参考资料 预测效果 基本介绍 1.【JCR一区级】Matlab实现NRBO-Transformer-LSTM多输入单输出回归预测…...
Python菜鸟教程(小程序)
目录 一.简易计算器 二.学生成绩分级 三.密码设置 四.作业选择 点赞收藏,评论支持 一.简易计算器 print(-------使用的运算符-------\n) print(1.加号) print(2.减号) print(3.乘号) print(4.除号) Aint(input(请输入第一个数: )) Bint(input(请输入第二个数: )) Fi…...
类的(多态性、虚函数)基础练习
练习1:(简单) #include <iostream> using namespace std; class Vehicle { public: virtual void run() const0; }; class Car: public Vehicle { public: void run() const { cout << "run a car. "<<…...
特殊的质数肋骨--dfs+isp
1.dfs全排列组数,an记得还原 2.如果范围确定且只比较质数,isp比线性筛快,主要这个范围太大了 https://www.luogu.com.cn/problem/P1218 #include<bits/stdc.h> using namespace std; #define N 100011 typedef long long ll; typed…...
智能体开发实战指南:提示词设计、开发框架与工作流详解
在大语言模型(LLM)驱动的智能体(Agent)快速发展的今天,构建一个实用、智能的Agent已不再遥不可及。无论你是开发法律助手、租房合同分析器,还是通用办公自动化助手,理解提示词工程(P…...
jetson orin nano学习(torch+OpenCV+yolov5+)
一:入门第一件事:跟着商家教程配置哈哈 指令:nvidia-smi -h 帮助命令 sudo jtop --查看nvidia的gpu状态 Tip:教程下载的pytorth,cuda,cudnn版本不一定是你项目符合的,要提前想好 1.2 安装虚拟环境包(要安…...
client-go如何监听自定义资源
如何使用 client-go 监听自定义资源 在 Kubernetes 中使用 client-go 监听自定义资源(Custom Resource,简称 CR)需要借助 Dynamic Client 或 Custom Informer,因为 client-go 的标准 Clientset 只支持内置资源(如 Pod…...
【51单片机】3-3【定时器/计数器/中断】超声波测距模块测距
1.硬件 51最小系统超声波测距模块 2.软件 #include "reg52.h"//距离小于10cm,D5亮,D6灭,反之相反现象sbit D5 P3^7;//根据原理图(电路图),设备变量led1指向P3组IO口的第7口 sbit D6 P3^6;//根据原理图&…...
C语言求3到100之间的素数
一、代码展示 二、运行结果 三、感悟思考 注意: 这个题思路他是一个试除法的一个思路 先进入一个for循环 遍历3到100之间的数字 第二个for循环则是 判断他不是素数 那么就直接退出 这里用break 是素数就打印出来 在第一个for循环内 第二个for循环外...
金仓数据库KCM认证考试介绍【2025年4月更新】
KCM(金仓认证大师)认证是金仓KES数据库的顶级认证,学员需通过前置KCA、KCP认证才能考KCM认证。 KCM培训考试一般1-2个月一次,KCM报名费原价为1.8万,当前优惠价格是1万(趋势是:费用越来越高&…...
leetcode每日一题:替换子串得到平衡字符串
引言 今天的每日一题原题是1863. 找出所有子集的异或总和再求和,比较水,直接对于集合中的每一个元素,都有取或者不取2种情况,直接递归进去求和即可。更换成前几天遇到的更有意思的一题来写这个每日一题。 题目 有一个只含有 Q,…...
2025年数字化社会与智能计算国际学术会议 (ICDSIC 2025)
基本信息 官网:www.icdsic.net 时间:2025年4月18-20日 地点:中国-深圳 主题 数字化社会 智能计算 数字化制造、经济 数字化政务、转型 数字化农业、水利、管理 数字化医疗、学习、社区 数字基建、通信、交通 数字…...
BN测试和训练时有什么不同, 在测试时怎么使用?
我们来彻底搞懂 Batch Normalization(BN) 在训练和测试阶段的区别,以及 测试时怎么用。 🧠 一句话总结: 训练时:使用 当前 mini-batch 的均值和方差 测试时:使用 整个训练集估计的“滑动平均均值…...
为什么卷积神经网络适用于图像和视频?
我们常听说“卷积神经网络(CNN)擅长图像和视频”,但其实 CNN 的核心本质远不止图像领域。我们先搞懂它为啥适合图像/视频。 🧠CNN 为什么适用于图像和视频? 主要因为 图像/视频具有空间局部性和结构平移性,…...
python爬虫:DrissionPage实战教程
如果本文章看不懂可以看看上一篇文章,加强自己的基础:爬虫自动化工具:DrissionPage-CSDN博客 案例解析: 前提:我们以ChromiumPage为主,写代码工具使用Pycharm(python环境3.9-3.10) …...
【Python爬虫高级技巧】BeautifulSoup高级教程:数据抓取、性能调优、反爬策略,全方位提升爬虫技能!
大家好,我是唐叔!上期我们聊了 BeautifulSoup的基础用法 ,今天带来进阶篇。我将分享爬虫老司机总结的BeautifulSoup高阶技巧,以及那些官方文档里不会告诉你的实战经验! 文章目录 一、BeautifulSoup性能优化技巧1. 解析…...
【动手学深度学习】卷积神经网络(CNN)入门
【动手学深度学习】卷积神经网络(CNN)入门 1,卷积神经网络简介2,卷积层2.1,互相关运算原理2.2,互相关运算实现2.3,实现卷积层 3,卷积层的简单应用:边缘检测3.1࿰…...
IPSG 功能协议
IPSG(IP Source Guard)即 IP 源保护,是一种基于 IP 地址和 MAC 地址绑定的安全功能,用于防止 IP 地址欺骗和非法的 IP 地址访问。以下是配置 IPSG 功能的一般步骤: 基于端口的 IPSG 配置 进入接口配置模式࿱…...
19.go日志包log
核心功能与接口 基础日志输出 Print 系列:支持 Print()、Println()、Printf(),输出日志不中断程序。 log.Print("常规日志") // 输出: 2025/03/18 14:47:13 常规日志 log.Printf("格式化: %s", "数据") Fatal…...
横扫SQL面试——TopN问题
横扫SQL面试 电商平台的"销量Top10商品"🛍️,内容社区的"热度Top5文章“”🔥,还是金融领域的"交易额Top3客户"💰——TopN问题无处不在! 无论是日常业务分析📊&#x…...
高级:微服务架构面试题全攻略
一、引言 在现代软件开发中,微服务架构被广泛应用于构建复杂、可扩展的应用程序。面试官通过相关问题,考察候选人对微服务架构的理解、拆分原则的掌握、服务治理的能力以及API网关的运用等。本文将深入剖析微服务架构相关的面试题,结合实际开…...
使用MATIO库读取Matlab数据文件中的cell结构数据
使用MATIO库读取Matlab数据文件中的cell结构数据 MATIO是一个用于读写Matlab数据文件(.mat)的C/C库。下面我将展示如何使用MATIO库来读取Matlab文件中的cell结构数据。 示例程序 #include <stdio.h> #include <stdlib.h> #include <matio.h>int main(int …...
pyTorch框架使用CNN进行手写数字识别
目录 1.导包 2.torchvision数据处理的方法 3.下载加载手写数字的训练数据集 4.下载加载手写数字的测试数据集 5. 将训练数据与测试数据 转换成dataloader 6.转成迭代器取数据 7.创建模型 8. 把model拷到GPU上面去 9. 定义损失函数 10. 定义优化器 11. 定义训练…...
新能源汽车电子电气架构设计中的功能安全
我是穿拖鞋的汉子,魔都中坚持长期主义的汽车电子工程师。 老规矩,分享一段喜欢的文字,避免自己成为高知识低文化的工程师: 周末洗了一个澡,换了一身衣服,出了门却不知道去哪儿,不知道去找谁,漫无目的走着,大概这就是成年人最深的孤独吧! 旧人不知我近况,新人不知我过…...
使用binance-connector库获取Binance全市场的币种价格,然后选择一个币种进行下单
一个完整的示例,展示如何使用 api 获取Binance全市场的币种价格,然后选择一个最便宜的币种进行下单操作 代码经过修改,亲测可用,目前只可用于现货,合约的待开发 获取市场价格:使用client.ticker_price()获取所有交易对的当前价格 账户检查:获取账户余额,确保有足够的资…...
HikariCP 源码核心设计解析与 ZKmall开源商城场景调优实践
HikariCP 作为 Spring Boot 默认数据库连接池,其高性能源于独特的无锁设计、轻量级数据结构和精细化生命周期管理。以下从源码解析与 ZKmall开源商城性能调优两个维度展开: 一、HikariCP 源码核心设计解析 无锁并发控制与 ConcurrentBag 容器 Concur…...
P1036 [NOIP 2002 普及组] 选数(DFS)
题目描述 已知 n 个整数 x1,x2,⋯,xn,以及 1 个整数 k(k<n)。从 n 个整数中任选 k 个整数相加,可分别得到一系列的和。例如当 n4,k3,4 个整数分别为 3,7,12,19 时,可得全部的组合与它…...
自然语言处理
自然语言处理基础 什么是自然语言处理:让计算机来理解人类所说的一种语言。自然语言处理实际就是让计算机理解人类说的话,然后像人一样进行交互,去进行对话,去生成自然语言。 自然语言处理的基本任务 词性标注:把给…...
LeetCode刷题常见的Java排序
1. 字符串排序(字母排序) 首先,你的代码实现了根据字母表顺序对字符串中的字母进行排序,忽略了大小写并且保留了非字母字符的位置。关键点是: 提取和排序字母:通过 Character.isLetter() 判断是否为字母,并利用 Character.toLowerCase() 来忽略大小写进行排序。保留非字…...
# 利用OpenCV和Dlib实现疲劳检测:守护安全与专注
利用OpenCV和Dlib实现疲劳检测:守护安全与专注 在当今快节奏的生活中,疲劳和注意力不集中是许多人面临的常见问题,尤其是在驾驶、学习等需要高度集中精力的场景中。疲劳不仅影响个人的健康和安全,还可能导致严重的事故。为了应对…...
python基础-16-处理csv文件和json数据
文章目录 【README】【16】处理csv文件和json数据【16.1】csv模块【16.1.1】reader对象【16.1.2】在for循环中, 从reader对象读取数据【16.1.3】writer对象【16.1.5】DictReader与DictWriter对象 【16.4】json模块【16.4.1】使用loads()函数读取json字符串并转为jso…...