当前位置: 首页 > news >正文

二分查找3

1. 有序数组中的单一元素(540)

题目描述:
在这里插入图片描述
算法原理:
二分查找解题关键就在于去找到数组的二段性,这里数组的二段性是从单个数字a开始出现然后分隔出来的,如果mid落入左半部分那么当mid为偶数时nums[mid+1]等于nums[mid],当mid为奇数时nums[mid]等于nums[mid-1],mid落入右半部分则相反。
细节:
循环内的判断条件首先需要判断mid是偶数还是奇数,接着还要判断相等的关系,是比较麻烦的。我们发现规律当mid为偶数异或1时就会得到mid+1,当mid为奇数异或1时就会得到mid-1,因此我们的判断条件直接简化为nums[mid]是否等于nums[mid^1]。
代码如下:

class Solution {public int singleNonDuplicate(int[] nums) {int left = 0, right = nums.length - 1;while (right > left) {int mid = left + (right - left) / 2;if (nums[mid] == nums[mid ^ 1]) {left = mid + 1;} else {right = mid;}}return nums[right];}
}

题目链接

2. 寻找旋转排序数组中的最小值 II(154)

题目描述:
在这里插入图片描述

算法原理:
nums数组的二段性体现在nums[right],前半部分旋转过去的值是大于等于nums[right]的,后半部分的值都是小于等于nums[right]。不过这题需要注意的地方就是因为数值是可以重复的,所以当nums[mid]等于nums[right]的时候我们是不知道mid是落在前半部分还是后半部分的,为了解决这种情况我们直接将right向左移动一位即可,移动之后因为我们求的是最小值,所以不会影响结果,并且达到了一种去重的效果。
代码如下:

class Solution {public int findMin(int[] nums) {int left = 0, right = nums.length - 1;while (left < right) {int mid = left + (right - left) / 2;if (nums[mid] > nums[right]) {left = mid + 1;} else if (nums[mid] < nums[right]) {right = mid;} else {right -= 1;}}return nums[right];}
}

题目链接

3. 搜索二维矩阵(74)

题目描述:
在这里插入图片描述

算法原理:
这一题可以使用朴素二分查找的思想来解决,将多维数组看作一维的数组,此时铺开来left=0、right=m*n-1,得到的mid位置的值在二维数组中可以表示为matrix[mid/n]matrix[mid%n],这里的m就是数组的维度数,n就是每个维度的元素个数。
代码如下:

class Solution {public boolean searchMatrix(int[][] matrix, int target) {int m = matrix.length;int n = matrix[0].length;int left = 0, right = m * n - 1;while (left <= right) {int mid = left + (right - left) / 2;if (matrix[mid / n][mid % n] > target) {right = mid - 1;} else if (matrix[mid / n][mid % n] < target) {left = mid + 1;} else {return true;}}return false;}
}

题目链接

相关文章:

二分查找3

1. 有序数组中的单一元素&#xff08;540&#xff09; 题目描述&#xff1a; 算法原理&#xff1a; 二分查找解题关键就在于去找到数组的二段性&#xff0c;这里数组的二段性是从单个数字a开始出现然后分隔出来的&#xff0c;如果mid落入左半部分那么当mid为偶数时nums[mid1]…...

从零开始学习嵌入式----C语言框架梳理与后期规划

目录 一、环境搭建. 二、见解 三、C语言框架梳理 四、嵌入式学习规划流程图&#xff08;学习顺序可能有变&#xff09; 一、环境搭建. C语言是一门编程语言&#xff0c;在学习的时候要准备好环境。我个人比较喜欢用VS,具体怎么安装请百度。学习C语言的时候&#xff0c;切忌…...

ESP32 步进电机精准控制:打造高精度 DIY 写字机器人,实现流畅书写体验

摘要: 想让你的 ESP32 不再仅仅是控制灯光的工具吗&#xff1f; 本文将带你使用 ESP32 开发板、步进电机和简单的机械结构打造一个能够自动写字的机器人。我们将深入浅出地讲解硬件连接、软件代码以及控制逻辑&#xff0c;并提供完整的项目代码和电路图&#xff0c;即使是 Ardu…...

传知代码-图神经网络长对话理解(论文复现)

代码以及视频讲解 本文所涉及所有资源均在传知代码平台可获取 概述 情感识别是人类对话理解的关键任务。随着多模态数据的概念&#xff0c;如语言、声音和面部表情&#xff0c;任务变得更加具有挑战性。作为典型解决方案&#xff0c;利用全局和局部上下文信息来预测对话中每…...

部署前端项目

常见部署方式有&#xff1a;静态托管服务、服务器部署 1. 静态托管服务 使用平台部署代码&#xff0c;比如 GitHub。 | 创建一个仓库&#xff0c;仓库名一般是 yourGithubName.github.io。 | 将打包后的静态文件文件上传到仓库。 | 在“Settings”&#xff08;选项&#xff0…...

使用POI实现Excel文件的读取(超详细)

目录 一 导入poi相关的maven坐标 二 实现创建并且写入文件 2.1实现步骤 2.2实现代码 2.3效果展示 ​编辑 2.4注意 三 实现从Excel文件中读取数据 3.1实现步骤 3.2实现代码 3.3结果展示 一 导入poi相关的maven坐标 <!-- Apache poi --><dependency><gro…...

Debezium系列之:记录一次数据库某张表部分数据未同步到hive表的原因

Debezium系列之:记录一次数据库某张表部分数据未同步到hive表的原因 一、背景二、查找数据丢失流程三、数据丢失原因四、解决方法一、背景 反馈mysql数据库中某张表的数据没有同步到hive中,现在需要排查定位下原因数据丢失一般常见需求排查的方向: 数据是否采集到hdfs上采集…...

爆破器材期刊

《爆破器材》简介   《爆破器材》自1958年创刊以来&#xff0c;深受广大读者喜爱&#xff0c;是中国兵工学会主办的中央级技术刊物&#xff0c;在国内外公开发行&#xff0c;近几年已发行到10个国家和地区。《爆破器材》杂志被美国著名检索机构《化学文摘》&#xff08;CA&a…...

Nginx Websocket 协议配置支持

前后分离的 Web 架构应用&#xff0c;在开发环境启动是可以直接连接支持 websocket 协议&#xff0c;因为没有中间件做转发处理。 当我们对前端进行编译后&#xff0c;通过 nginx 反向代理访问时&#xff0c;需要在nginx 配置文件中增加一些特定的头信息&#xff0c;让服务端识…...

【生成式对抗网络】GANs在数据生成、艺术创作,以及在增强现实和虚拟现实中的应用

一、GANs在数据生成中的应用 生成对抗网络&#xff08;Generative Adversarial Networks, GANs&#xff09;在数据生成领域具有显著的应用价值。GANs通过生成器&#xff08;Generator&#xff09;和判别器&#xff08;Discriminator&#xff09;两个相互竞争的神经网络&#x…...

大模型面试(三)

这次是某家公司的一个电话面试&#xff0c;问的过程还比较简单直接。 问&#xff1a;我们在大模型开源项目的应用上遇到了什么困难&#xff1f; 这个。。有两个困难&#xff0c;一个是RAG的优化&#xff0c;一开始RAG是比较慢的&#xff0c;而且召回率不高&#xff1b; 后来…...

pycharm中快捷键汇总

Pycarm指令汇总 Ctrl鼠标 单击&#xff0c;能直接查看其用法 Ctrl/ 快速注释 CtrlC 在pycharm的terminal中可以停止运行, 其他的地方可以复制。 CtrlV 粘贴 CtrlA 全选 CtrlP 查看&#xff08;&#xff09;中需要填写什么参数 Altenter 自动不补全所需要的库...

TCP/IP协议族结构和协议

TCP/IP协议族是互联网及许多其他网络的基础,它由一系列相互关联的协议组成,用于实现网络通信。TCP/IP协议族采用ARPANET参考模型,大致可以分为四个层次:链路层、网络层、传输层和应用层。每个层次都有特定的协议和功能,确保数据能够从一个网络设备传输到另一个网络设备。 …...

大模型一些概念的理解 - 线性层、前向传播、后向传播

文章目录 前言一、线性层1. 什么是线性层&#xff1f;2. 通俗解释3. 示例 二、前向传播1. 什么是前向传播&#xff1f;2. 通俗解释3. 示例 三、后向传播1. 什么是后向传播&#xff1f;2. 通俗解释3. 具体步骤 四、示例五、在 PyTorch 中的后向传播 前言 最近提问里有问到一些名…...

AWS 云安全性:检测 SSH 暴力攻击

由于开源、低成本、可靠性和灵活性等优势&#xff0c;云基础设施主要由基于linux的机器主导&#xff0c;然而&#xff0c;它们也不能幸免于黑客的攻击&#xff0c;从而影响云的安全性。攻击Linux机器最流行的方法之一是通过SSH通道。 什么是 SSH 安全外壳协议&#xff08;Sec…...

7.9数据结构

思维导图 作业 doubleloop.h #ifndef __DOUBLELOOP_H__ #define __DOUBLELOOP_H__#include <stdio.h> #include <stdlib.h>typedef int datatype; typedef struct node {union{int len;datatype data;};struct node *pri;//前驱指针struct node *next;//后继指针…...

Python 文件操作:打开数据处理的大门

在 Python 的学习之旅中&#xff0c;文件操作是一个非常实用且必不可少的技能。不论是数据分析还是日常的数据处理&#xff0c;良好的文件操作技巧都能让你的编程之路更加顺畅。今天&#xff0c;我将带你走进 Python 文件操作的世界&#xff0c;不仅教你如何读写文件&#xff0…...

单对以太网连接器多场景应用

单对以太网连接器应用场景概述 单对以太网&#xff08;Single Pair Ethernet&#xff0c;简称SPE&#xff09;作为一种新兴的以太网技术&#xff0c;以其独特的优势在多个领域得到了广泛的应用。SPE通过单对电缆进行数据传输&#xff0c;支持高速数据传输&#xff0c;同时还能…...

Python pip的更新问题

你是否也出现了更新pip的情况 1、提示更新pip版本 pip install --upgrade pip2、更新操作&#xff0c;我操作了 pip install --upgrade pip更新了&#xff0c;等啊等。。。 然后就是连接超时&#xff0c;安装失败 3、我不信&#xff0c;我就要更新&#xff0c;我还要使用镜…...

[Linux][Shell][Shell基础] -- [Shebang][特殊符号][变量][父子Shell]详细讲解

目录 0.前置知识1.Shebang2.Linux特殊符号整理3.变量4.环境变量5.父子shell0.概念1.创建进程列表(创建子shell执行命令) 6.内置命令 vs 外置命令 0.前置知识 #用于注释shell脚本语⾔属于⼀种弱类型语⾔&#xff1a;⽆需声明变量类型&#xff0c;直接定义使⽤shell三剑客&#…...

华为云AI开发平台ModelArts

华为云ModelArts&#xff1a;重塑AI开发流程的“智能引擎”与“创新加速器”&#xff01; 在人工智能浪潮席卷全球的2025年&#xff0c;企业拥抱AI的意愿空前高涨&#xff0c;但技术门槛高、流程复杂、资源投入巨大的现实&#xff0c;却让许多创新构想止步于实验室。数据科学家…...

云原生核心技术 (7/12): K8s 核心概念白话解读(上):Pod 和 Deployment 究竟是什么?

大家好&#xff0c;欢迎来到《云原生核心技术》系列的第七篇&#xff01; 在上一篇&#xff0c;我们成功地使用 Minikube 或 kind 在自己的电脑上搭建起了一个迷你但功能完备的 Kubernetes 集群。现在&#xff0c;我们就像一个拥有了一块崭新数字土地的农场主&#xff0c;是时…...

2.Vue编写一个app

1.src中重要的组成 1.1main.ts // 引入createApp用于创建应用 import { createApp } from "vue"; // 引用App根组件 import App from ./App.vue;createApp(App).mount(#app)1.2 App.vue 其中要写三种标签 <template> <!--html--> </template>…...

镜像里切换为普通用户

如果你登录远程虚拟机默认就是 root 用户&#xff0c;但你不希望用 root 权限运行 ns-3&#xff08;这是对的&#xff0c;ns3 工具会拒绝 root&#xff09;&#xff0c;你可以按以下方法创建一个 非 root 用户账号 并切换到它运行 ns-3。 一次性解决方案&#xff1a;创建非 roo…...

Robots.txt 文件

什么是robots.txt&#xff1f; robots.txt 是一个位于网站根目录下的文本文件&#xff08;如&#xff1a;https://example.com/robots.txt&#xff09;&#xff0c;它用于指导网络爬虫&#xff08;如搜索引擎的蜘蛛程序&#xff09;如何抓取该网站的内容。这个文件遵循 Robots…...

Map相关知识

数据结构 二叉树 二叉树&#xff0c;顾名思义&#xff0c;每个节点最多有两个“叉”&#xff0c;也就是两个子节点&#xff0c;分别是左子 节点和右子节点。不过&#xff0c;二叉树并不要求每个节点都有两个子节点&#xff0c;有的节点只 有左子节点&#xff0c;有的节点只有…...

力扣-35.搜索插入位置

题目描述 给定一个排序数组和一个目标值&#xff0c;在数组中找到目标值&#xff0c;并返回其索引。如果目标值不存在于数组中&#xff0c;返回它将会被按顺序插入的位置。 请必须使用时间复杂度为 O(log n) 的算法。 class Solution {public int searchInsert(int[] nums, …...

push [特殊字符] present

push &#x1f19a; present 前言present和dismiss特点代码演示 push和pop特点代码演示 前言 在 iOS 开发中&#xff0c;push 和 present 是两种不同的视图控制器切换方式&#xff0c;它们有着显著的区别。 present和dismiss 特点 在当前控制器上方新建视图层级需要手动调用…...

C# 表达式和运算符(求值顺序)

求值顺序 表达式可以由许多嵌套的子表达式构成。子表达式的求值顺序可以使表达式的最终值发生 变化。 例如&#xff0c;已知表达式3*52&#xff0c;依照子表达式的求值顺序&#xff0c;有两种可能的结果&#xff0c;如图9-3所示。 如果乘法先执行&#xff0c;结果是17。如果5…...

PostgreSQL——环境搭建

一、Linux # 安装 PostgreSQL 15 仓库 sudo dnf install -y https://download.postgresql.org/pub/repos/yum/reporpms/EL-$(rpm -E %{rhel})-x86_64/pgdg-redhat-repo-latest.noarch.rpm# 安装之前先确认是否已经存在PostgreSQL rpm -qa | grep postgres# 如果存在&#xff0…...