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

编程导航算法村第九关 | 二分查找

编程导航算法村第九关 | 二分查找

  • LeetCode852.这个题的要求有点啰嗦,核心意思就是在数组中的某位位置i开始,从0到i是递增的,从i+1 到数组最后是递减的,让你找到这个最高点。
    详细要求是:符合下列属性的数组 arr 称为山脉数组 :arr.length >= 3存在 i(0 < i < arr.length - 1)使得:

    arr[0] < arr[1] < … arr[i-1] < arr[i]

    arr[i] > arr[i+1] > … > arr[arr.length - 1]
  • 思路:
    • 使用二分查找:
      • 首先确定左右边界
      • 因为必然不是第一个与最后一个,取值范围便是1,length-2
      • 分三种情况讨论
      • 左边递增区域
      • 右边递增区域
      • 找见最大值
public int peakIndexInMountainArray(int[] arr) {int left = 1;int right = arr.length - 2;while (left < right) {int mid = left + ((right - left) >> 1);
//            符合条件的情况if (arr[mid - 1] < arr[mid] && arr[mid] > arr[mid + 1]) {return mid;}if (arr[mid] > arr[mid - 1] && arr[mid] < arr[mid + 1]) {left = mid + 1;}if (arr[mid] < arr[mid - 1] && arr[mid] > arr[mid + 1]) {right = mid - 1;}}return left;}

旋转数字的最小数字

LeetCode153 已知一个长度为 n 的数组,预先按照升序排列,经由1到n次旋转后,得到输入数组。例如原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到:

若旋转 4 次,则可以得到 [4,5,6,7,0,1,2]

若旋转 7 次,则可以得到 [0,1,2,4,5,6,7]

 public int findMin(int[] nums) {
//    如果最小值在中间
//    最小值在左边开端、右边开端int left = 0;int right = nums.length - 1;while (left < right) {int mid = left + ((right - left) >> 1);if (nums[mid] < nums[right]) {right = mid;}else {left = mid + 1;}}return nums[left];}

找缺失数字

剑指offer题目: 一个长度为n-1的递增排序数组中的所有数字都是唯一的,并且每个数字都在范围0~n-1之内。在范围0~n-1内的n个数字中有且只有一个数字不在该数组中,请找出这个数字。

  • 思路:
    • 找出第一个num[i]!=i的值就是返回值
public int missingNumber(int[] nums) {int left = 0;int right = nums.length - 1;while (left <= right) {int mid = left + ((right - left) >> 1);if (nums[mid] == mid) {left = mid + 1;} else {right = mid - 1;}}return left;}

优化求平方根

剑指offer题目
实现函数 int sqrt(int x).计算并返回x的平方根这个题的思路是用最快的方式找到n*n=x的n。这里涉及到四舍五入,所以采用折半进行比较:

  • 思路:在此处需要使用除法,如果使用乘法则可能会导致越界的问题
 public int mySqrt(int x) {int left = 1;int right = x;while (left <= right) {int mid = left + ((right - left) >> 1);if (x / mid > mid) {left = mid + 1;} else if (x / mid < mid) {right = mid - 1;} else if (x / mid == mid) {return mid;}}return right;}

二叉搜索树

2.1 二叉搜索树中搜索特定值
LeetCode 700.给定二叉搜索树(BST)的根节点和一个值。

  public TreeNode searchBST(TreeNode root, int val) {if (root == null) {return null;}if (root.val == val) {return root;}
//        if (root.left != null && root.right != null) {return   searchBST(root.val > val ? root.left : root.right,val);
//        }}

验证二叉搜索树

  • LeetCode98.给你一个二叉树的根节点 root ,判断其是否是一个有效的二叉搜索树。
  • 需要按照中序遍历,判断左子树是否是二叉搜索树,记录当前节点的值,要保证后面节点的值要大于前面所有节点的值
 private long pre = Long.MIN_VALUE;public boolean isValidBST(TreeNode root) {if (root == null) {return true;}if (!isValidBST(root.left)) {return false;}if (root.left != null) {if (root.val <= root.left.val) {return false;}}if (root.right != null) {if (root.val >= root.right.val) {return false;}}if (root.val <= pre) {return false;}pre =  root.val;if (!isValidBST(root.right)) {return false;}return true;}

相关文章:

编程导航算法村第九关 | 二分查找

编程导航算法村第九关 | 二分查找 LeetCode852.这个题的要求有点啰嗦&#xff0c;核心意思就是在数组中的某位位置i开始&#xff0c;从0到i是递增的&#xff0c;从i1 到数组最后是递减的&#xff0c;让你找到这个最高点。 详细要求是&#xff1a;符合下列属性的数组 arr 称为山…...

linux 下安装部署flask项目

FlaskDemo 命名为test.py # codingutf-8 from flask import Flaskapp Flask(__name__)app.route("/") def index():return "test"if __name__ __main__:app.debug True# 这里host一定要写0.0.0.0 写127.0.0.1的无法访问 ——_——app.run(host"0.…...

在Vue里,将当前窗口截图,并将数据base64转为png格式传给服务器

目录 前言 1、将当前窗口截图&#xff0c;并将数据存储下来 2、定义将base64转png的方法 3、完整代码 总结 前言 记录来源于需求 1、将当前窗口截图&#xff0c;并将数据存储下来 export default { data() {return {image: // 存储数据} }mounted() {setTimeout(() >…...

Echarts图表Java后端生成Base64图片格式,POI写入Base64图片到Word中

Echarts图表Java后端生成请看上篇&#xff0c;此篇为Base64图片插入Word文档中Java后台生成ECharts图片,并以Base64字符串返回_青冘的博客-CSDN博客 try {XWPFParagraph xwpfParagraphimage doc.createParagraph(); // 创建图片段落xwpfParagraphimage.setAlignment(Paragraph…...

【AI】《动手学-深度学习-PyTorch版》笔记(十二):从零开始实现softmax回归

AI学习目录汇总 1、什么是特征? 对于图像算法,每个像素可以视为一个特征,例如图像的分辨率为28x28,则有784个特征。而且常常将二维的图像像素矩阵展开为长度为784的向量。 2、权重和偏置的规模 本例中,将使用Fashion-MNIST数据集,它是一个服装分类数据集,可以将服装…...

汽车用功率电感器

支持车载用被动元件的可靠性认证测试标准“AEC-Q200”的绕线铁氧体功率电感器 LCXH 系列实现商品化&#xff0c;推出了“LCXHF3030QK”等 6 个尺寸的 64 款商品。 这些商品均是用于汽车车身类及信息娱乐等信息类的电源电路用扼流线圈及噪音滤波器的功率电感器。 LCXH 系列与民生…...

上传图片视频

分布式文件系统MinIo MinIO提供多个语言版本SDK的支持&#xff0c;下边找到java版本的文档&#xff1a; 地址&#xff1a;https://docs.min.io/docs/java-client-quickstart-guide.html MinIO测试&#xff08;上传、删除、下载&#xff09; public class MinioTest {MinioC…...

【UE5】UE5与Python Socket通信中文数据接收不全

最近在使用UE的Socket模块与Python服务器进行通信时遇到了一些坑&#xff0c;特此记录一下。 先来复现一下问题&#xff0c;这里只截取关键代码。 UE端&#xff1a; bool ASoc::SendMsg(const FString& Msg) {TSharedRef<FInternetAddr> TargetAddr ISocketSubsy…...

一些有难度的c++题目思路讲解--第一期2023/8/8 小Q的修炼与旷野大计算

说明: 本期博客将分为10篇讲解一些有点挑战的题目,第一期是所有人都可以看到,但后面的关注我才能看到哦!有望大家的支持!谢谢! 题目链接(按顺序) [NOI2013] 小Q的修炼 - 洛谷 小Q的修炼[NOI2013] 小Q的修炼 - 洛谷 [NOI2016] 旷野大计算 - 洛谷旷野大计算[NOI2016] 旷野…...

Node.js:path文件路径操作模块

path 用于文件路径操作 官方文档 https://nodejs.org/api/path.html 一个不错的解释 ┌─────────────────────┬────────────┐│ dir │ base │├──────┬ ├──────┬─────┤│ ro…...

基于 CentOS 7 构建 LVS-DR 群集

文章目录 一、LVS-DR集群介绍1.LVS的基本工作原理2. LVS-DR模式工作原理 二、 LVS-DR模式应用特点三、LVS – DR 模式集群构建1.前期环境准备2.配置LVS3.配置RS 一、LVS-DR集群介绍 1.LVS的基本工作原理 当用户向负载均衡调度器&#xff08;Director Server&#xff09;发起请…...

机器学习笔记 - 使用 Tensorflow 从头开始​​构建您自己的对象检测器

一、简述 之前的文章是利用了VGG16的预训练模型,然后构造完全连接的层标头以输出预测的边界框坐标,但是不包含对象标签的分类。 机器学习笔记 - 使用Keras、TensorFlow框架进行自定义数据集目标检测训练_keras 制作 目标检测 数据集_坐望云起的博客-CSDN博客学习如何训练自定…...

IELAB-网络工程师的路由答疑10问(2)

各位小伙伴们&#xff0c;接下来的问题可能有些难度&#xff0c;你们做好准备了吗&#xff1f; 7. 动态路由协议做了啥&#xff1f; 这次咱们先解决第一个比较棘手的问题--路由协议&#xff0c;相信初学的同学对于路由协议的学习总是或多或少有些问题&#xff0c;呐&#xff…...

聚观早报|iPhone 15预计9月22日上市;一加Open渲染图曝光

【聚观365】8月7日消息 iPhone 15预计9月22日上市一加Open渲染图曝光Redmi K60至尊版细节曝光小米14 Pro屏幕细节曝光vivo V3正式发布&#xff0c;执着自研“影像芯片” iPhone 15预计9月22日上市 上周有多位消息人士透露&#xff0c;多家合作的电信运营商已要求员工不要在9月…...

react-use-gesture

介绍 react-use-gesture 是一个基于 React Hooks 的库&#xff0c;用于处理手势事件。它提供了一种简单且灵活的方式来处理用户的手势操作&#xff0c;例如拖动、缩放、旋转等。 使用 安装 react-use-gesture&#xff1a; npm install react-use-gesture 导入所需的模块和钩…...

智能中的“一体两面”

一体两面指的是一个事物或问题同时具有两个相互依存、互为对立的方面或特征。一体表示两个方面或特征是不可分割、相互联系的整体&#xff0c;两面表示这两个方面或特征又是相互对立、互相影响的。常用于描述矛盾问题或复杂事物的本质。例如&#xff0c;事物的存在与发展、利益…...

前端渲染数据

在前端对接受后端数据处理后返回的接收值的时候&#xff0c;为了解决数据过于庞大&#xff0c;而对数据进行简化处理例如性别&#xff0c;经常会使用1&#xff0c; 0这俩个来代替文字的男&#xff0c;女。以下就是前端渲染的具体实现。 以下是部分代码 <el-table-columnpr…...

【Linux操作系统】深入了解系统编程gdb调试工具

在软件开发过程中&#xff0c;调试是一个非常重要的步骤。无论是在开发新的软件还是维护现有的代码&#xff0c;调试都是解决问题的关键。对于Linux开发者来说&#xff0c;GDB是一个非常有用的调试工具。在本文中&#xff0c;我们将探讨Linux中使用GDB进行调试的方法和技巧。 …...

linux 安装go 1.18版本

首先去官网找到对应的版本 直接下载下来&#xff08;如果服务器可以直接访问到go 官网也可以wget直接下载到服务器&#xff09; 然后把该包上传到linux 的/usr/local 目录下 然后直接解压安装该包&#xff1a; sudo tar -C /usr/local -zxvf go1.18.10.linux-amd64.tar.gz 然…...

LLVM笔记2 Intermediate Representation (IR)

参考链接&#xff1a;https://llvm.org/devmtg/2019-04/slides/Tutorial-Bridgers-LLVM_IR_tutorial.pdf https://zhuanlan.zhihu.com/p/163063995 https://zhuanlan.zhihu.com/p/163328574 文章目录 IR的布局1. IR语法2.IR递归函数3.使用迭代的方式4.全局变量5.LLVM’s type s…...

Docker 离线安装指南

参考文章 1、确认操作系统类型及内核版本 Docker依赖于Linux内核的一些特性&#xff0c;不同版本的Docker对内核版本有不同要求。例如&#xff0c;Docker 17.06及之后的版本通常需要Linux内核3.10及以上版本&#xff0c;Docker17.09及更高版本对应Linux内核4.9.x及更高版本。…...

论文解读:交大港大上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(二)

HoST框架核心实现方法详解 - 论文深度解读(第二部分) 《Learning Humanoid Standing-up Control across Diverse Postures》 系列文章: 论文深度解读 + 算法与代码分析(二) 作者机构: 上海AI Lab, 上海交通大学, 香港大学, 浙江大学, 香港中文大学 论文主题: 人形机器人…...

突破不可导策略的训练难题:零阶优化与强化学习的深度嵌合

强化学习&#xff08;Reinforcement Learning, RL&#xff09;是工业领域智能控制的重要方法。它的基本原理是将最优控制问题建模为马尔可夫决策过程&#xff0c;然后使用强化学习的Actor-Critic机制&#xff08;中文译作“知行互动”机制&#xff09;&#xff0c;逐步迭代求解…...

相机Camera日志实例分析之二:相机Camx【专业模式开启直方图拍照】单帧流程日志详解

【关注我&#xff0c;后续持续新增专题博文&#xff0c;谢谢&#xff01;&#xff01;&#xff01;】 上一篇我们讲了&#xff1a; 这一篇我们开始讲&#xff1a; 目录 一、场景操作步骤 二、日志基础关键字分级如下 三、场景日志如下&#xff1a; 一、场景操作步骤 操作步…...

2021-03-15 iview一些问题

1.iview 在使用tree组件时&#xff0c;发现没有set类的方法&#xff0c;只有get&#xff0c;那么要改变tree值&#xff0c;只能遍历treeData&#xff0c;递归修改treeData的checked&#xff0c;发现无法更改&#xff0c;原因在于check模式下&#xff0c;子元素的勾选状态跟父节…...

SpringBoot+uniapp 的 Champion 俱乐部微信小程序设计与实现,论文初版实现

摘要 本论文旨在设计并实现基于 SpringBoot 和 uniapp 的 Champion 俱乐部微信小程序&#xff0c;以满足俱乐部线上活动推广、会员管理、社交互动等需求。通过 SpringBoot 搭建后端服务&#xff0c;提供稳定高效的数据处理与业务逻辑支持&#xff1b;利用 uniapp 实现跨平台前…...

【HTML-16】深入理解HTML中的块元素与行内元素

HTML元素根据其显示特性可以分为两大类&#xff1a;块元素(Block-level Elements)和行内元素(Inline Elements)。理解这两者的区别对于构建良好的网页布局至关重要。本文将全面解析这两种元素的特性、区别以及实际应用场景。 1. 块元素(Block-level Elements) 1.1 基本特性 …...

Spring Cloud Gateway 中自定义验证码接口返回 404 的排查与解决

Spring Cloud Gateway 中自定义验证码接口返回 404 的排查与解决 问题背景 在一个基于 Spring Cloud Gateway WebFlux 构建的微服务项目中&#xff0c;新增了一个本地验证码接口 /code&#xff0c;使用函数式路由&#xff08;RouterFunction&#xff09;和 Hutool 的 Circle…...

在Ubuntu24上采用Wine打开SourceInsight

1. 安装wine sudo apt install wine 2. 安装32位库支持,SourceInsight是32位程序 sudo dpkg --add-architecture i386 sudo apt update sudo apt install wine32:i386 3. 验证安装 wine --version 4. 安装必要的字体和库(解决显示问题) sudo apt install fonts-wqy…...

嵌入式学习笔记DAY33(网络编程——TCP)

一、网络架构 C/S &#xff08;client/server 客户端/服务器&#xff09;&#xff1a;由客户端和服务器端两个部分组成。客户端通常是用户使用的应用程序&#xff0c;负责提供用户界面和交互逻辑 &#xff0c;接收用户输入&#xff0c;向服务器发送请求&#xff0c;并展示服务…...