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

二分查找与搜索树的高频问题(算法村第九关白银挑战)

基于二分查找的拓展问题

山峰数组的封顶索引

852. 山脉数组的峰顶索引 - 力扣(LeetCode)

给你由整数组成的山脉数组 arr ,返回满足 arr[0] < arr[1] < ... arr[i - 1] < arr[i] > arr[i + 1] > ... > arr[arr.length - 1] 的下标 i

你必须设计并实现时间复杂度为 O(log(n)) 的解决方案。

提示:

  • 3 <= arr.length <= 105
  • 0 <= arr[i] <= 106
  • 题目数据保证 arr 是一个山脉数组
二分查找
public int peakIndexInMountainArray(int[] arr)
{int low = 1;    //mid - 1 >= 0int high = arr.length - 2;  // mid + 1 <= arr.length - 1while (low <= high){int mid = low + (high - low >> 1);//找到山峰if(arr[mid] > arr[mid - 1] && arr[mid] > arr[mid + 1])return mid;//山峰左侧(递增)else if(arr[mid] > arr[mid - 1] && arr[mid] < arr[mid + 1])low = mid + 1;//山峰右侧(递减)elsehigh = mid - 1;}return -1;
}

旋转排序数组的最小值

无重复元素

153. 寻找旋转排序数组中的最小值 - 力扣(LeetCode)

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

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

注意,数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]]

给你一个元素值 互不相同 的数组 nums ,它原来是一个升序排列的数组,并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素

你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。

二分查找

在这里插入图片描述

在这里插入图片描述

nums [pivot] >= nums [high] 时,移动 low

在这里插入图片描述

public int findMin(int[] nums){int left = 0;int right = nums.length - 1;while (left < right)  // left == right 时找到最低点(最小值){int mid = left + (right - left >> 1);if(nums[mid] < nums[right])right = mid; //让 right 去触碰最低点(因为无法确定mid是不是最低点下标,故不能跳过它。如果是比较数值,那可以直接跳过,即 right = mid + 1)elseleft = mid + 1;  // left 迫近最低点,与 right 汇合}return nums[left];   //left == right == mid}
有重复元素

154. 寻找旋转排序数组中的最小值 II - 力扣(LeetCode)

二分查找

重复元素要一个个排除

public int findMin(int[] nums){int left = 0;int right = nums.length - 1;while (left < right)  // left == right 时找到最低点(最小值){int mid = left + (right - left >> 1);if(nums[mid] < nums[right])right = mid; //让 right 去触碰最低点else if(nums[mid] > nums[right])left = mid + 1;  // left 迫近最低点,与 right 汇合elseright--; //处理重复元素要一步一步来}return nums[left];   //left == right == mid}

缺失的数字

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

LCR 173. 点名 - 力扣(LeetCode)

某班级 n 位同学的学号为 0 ~ n-1。点名结果记录于升序数组 records。假定仅有一位同学缺席,请返回他的学号。

示例 1:

输入: records = [0,1,2,3,5]
输出: 4

示例 2:

输入: records = [0, 1, 2, 3, 4, 5, 6, 8]
输出: 7

提示:

1 <= records.length <= 10000
二分查找
public static 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; //让 left 去触碰缺失的元素,碰到后就不动了,交给 right 结束循环elseright = mid - 1;}return left;
}public static void main(String[] args)
{// n = 3 个数字, 数组长度(元素个数)为 n - 1 = 2, 元素范围 [0,2]int[] nums = {0, 1};System.out.println(missingNumber(nums)); // 输出 2// n = 7 个数字, 数组长度(元素个数)为 n - 1 = 6, 元素范围 [0,6]int[] nums2 = {0, 1, 2, 3, 5, 6};System.out.println(missingNumber(nums2)); // 输出 4
}

x 的平方根

LCR 072. x 的平方根 - 力扣(LeetCode)

给定一个非负整数 x ,计算并返回 x 的平方根,即实现 int sqrt(int x) 函数。

正数的平方根有两个,只输出其中的正数平方根。

如果平方根不是整数,输出只保留整数的部分,小数部分将被舍去。

示例 1:

输入: x = 4
输出: 2

示例 2:

输入: x = 8
输出: 2
解释: 8 的平方根是 2.82842...,由于小数部分将被舍去,所以返回 2

提示:

  • 0 <= x <= 231 - 1
二分查找实现
public int mySqrt(int x)
{int left = 1;int right = x;int ans = 0;while (left <= right){int mid = left + (right - left >> 1);if(x / mid >= mid)  //x >= mid²{ans = mid;  //向下取整逼近答案left = mid + 1;}elseright = mid - 1;}return ans;
}

更多题目

34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣(LeetCode)

875. 爱吃香蕉的珂珂 - 力扣(LeetCode)

29. 两数相除 - 力扣(LeetCode)

中序遍历与搜索树

简单来说,如果一棵二叉树是搜索树,则中序遍历序列是一个递增序列。

比较规范的定义是:

  • 若它的左子树不空,则左子树上所有节点的值均小于它的根节点的值;
  • 若它的右子树不空,则右子树上所有节点的值均大于它的根节点的值;

它的左、右子树也分别为二叉排序树。

下面两棵树的中序序列分别是{3,6,9,10,14,16,19},{3,6,9,10},因此都是搜索树。

在这里插入图片描述

二叉搜索树中的搜索

700. 二叉搜索树中的搜索 - 力扣(LeetCode)

给定二叉搜索树(BST)的根节点 root 和一个整数值 val

你需要在 BST 中找到节点值等于 val 的节点。 返回以该节点为根的子树。 如果节点不存在,则返回 null

示例 1:

img
输入:root = [4,2,7,1,3], val = 2
输出:[2,1,3]

示例 2:

img
输入:root = [4,2,7,1,3], val = 5
输出:[]
递归
public TreeNode searchBST(TreeNode root, int val)
{if (root == null || root.val == val)return root;if (val < root.val) //进入左子树搜索return searchBST(root.left, val);else    //否则进入右子树搜索return searchBST(root.right, val);
}
迭代
public TreeNode searchBST(TreeNode root, int val)
{while (root != null){if (root.val == val)break;else if (val < root.val)root = root.left;elseroot = root.right;}return root;
}

验证二叉搜索树

98. 验证二叉搜索树 - 力扣(LeetCode)

给你一个二叉树的根节点 root ,判断其是否是一个有效的二叉搜索树。

有效 二叉搜索树定义如下:

  • 节点的左子树只包含 小于 当前节点的数。
  • 节点的右子树只包含 大于 当前节点的数。
  • 所有左子树和右子树自身必须也是二叉搜索树。

示例 1:

img
输入:root = [2,1,3]
输出:true

示例 2:

img
输入:root = [5,1,4,null,null,3,6]
输出:false
解释:根节点的值是 5 ,但是右子节点的值是 4

提示:

  • 树中节点数目范围在[1, 104]
  • -231 <= Node.val <= 231 - 1
中序遍历+实时检查

二叉搜索树「中序遍历」序列是升序的,所以我们在中序遍历时,实时检查当前节点的值是否大于前一个节点的值即可。

long pre = Long.MIN_VALUE;
public boolean isValidBST(TreeNode root)
{if (root == null)return true;//检查左子树是否为二叉搜索树if(!isValidBST(root.left))  //等待左子树的返回结果。如果左子树下某个元素不满足要求,则退出所有递归return false;//检查当前节点是否大于等于前一个节点if (root.val <= pre)return false;pre = root.val;//检查右子树是否为二叉搜索树return isValidBST(root.right);  //等待右子树的返回结果
}
中序遍历+是否升序
public boolean isValidBST(TreeNode root)
{ArrayList<Integer> res = new ArrayList<>();inOrder(root,res);for (int i = 1; i < res.size(); i++)if (res.get(i - 1) >= res.get(i))return false;return true;
}public void inOrder(TreeNode root, ArrayList<Integer> res)
{if (root == null)return;inOrder(root.left, res);res.add(root.val);inOrder(root.right, res);
}

更多题目

530. 二叉搜索树的最小绝对差 - 力扣(LeetCode)

501. 二叉搜索树中的众数 - 力扣(LeetCode)

相关文章:

二分查找与搜索树的高频问题(算法村第九关白银挑战)

基于二分查找的拓展问题 山峰数组的封顶索引 852. 山脉数组的峰顶索引 - 力扣&#xff08;LeetCode&#xff09; 给你由整数组成的山脉数组 arr &#xff0c;返回满足 arr[0] < arr[1] < ... arr[i - 1] < arr[i] > arr[i 1] > ... > arr[arr.length - 1…...

Python爬虫快速入门

Python 爬虫Sutdy 1.基本类库 request(请求) 引入 from urllib import request定义url路径 url"http://www.baidu.com"进行请求,返回一个响应对象response responserequest.urlopen(url)读取响应体read()以字节形式打印网页源码 response.read()转码 编码 文本–by…...

部署MinIO

一、安装部署MINIO 1.1 下载 wget https://dl.min.io/server/minio/release/linux-arm64/minio chmod x minio mv minio /usr/local/bin/ # 控制台启动可参考如下命令, 守护进程启动请看下一个代码块 # ./minio server /data /data --console-address ":9001"1.2 配…...

RK3566环境搭建

环境&#xff1a;vmware16&#xff0c;ubuntu 18.04 安装依赖库&#xff1a; sudo apt-get install repo git ssh make gcc libssl-dev liblz4-tool expect g patchelf chrpath gawk texinfo chrpath diffstat binfmt-support qemu-user-static live-build bison flex fakero…...

精确掌控并发:滑动时间窗口算法在分布式环境下并发流量控制的设计与实现

这是《百图解码支付系统设计与实现》专栏系列文章中的第&#xff08;15&#xff09;篇&#xff0c;也是流量控制系列的第&#xff08;2&#xff09;篇。点击上方关注&#xff0c;深入了解支付系统的方方面面。 上一篇介绍了固定时间窗口算法在支付渠道限流的应用以及使用redis…...

Python展示 RGB立方体的二维切面视图

代码实现 import numpy as np import matplotlib.pyplot as plt# 生成 24-bit 全彩 RGB 立方体 def generate_rgb_cube():# 初始化一个 256x256x256 的三维数组rgb_cube np.zeros((256, 256, 256, 3), dtypenp.uint8)# 填充立方体for r in range(256):for g in range(256):fo…...

03 顺序表

目录 线性表顺序表练习 线性表(Linear list)是n个具有相同特性的数据元素的有限序列。线性表是一种在实际中广泛使用的数据结构&#xff0c;常见的线性表&#xff1a;顺序表、链表、栈、队列、字符串。。。 线性表在逻辑上时线性结构&#xff0c;是连续的一条直线。但在物理结…...

2023年全球软件开发大会(QCon北京站2023)9月:核心内容与学习收获(附大会核心PPT下载)

随着科技的飞速发展&#xff0c;全球软件开发大会&#xff08;QCon&#xff09;作为行业领先的技术盛会&#xff0c;为世界各地的专业人士提供了交流与学习的平台。本次大会汇集了全球的软件开发者、架构师、项目经理等&#xff0c;共同探讨软件开发的最新趋势、技术与实践。本…...

ChatGPT 和 文心一言 的优缺点及需求和使用场景

ChatGPT和文心一言是两种不同的自然语言生成模型&#xff0c;它们有各自的优点和缺点。 ChatGPT&#xff08;Generative Pre-trained Transformer&#xff09;是由OpenAI开发的生成式AI模型&#xff0c;它在庞大的文本数据集上进行了预训练&#xff0c;并可以根据输入生成具有上…...

架构师之超时未支付的订单进行取消操作的几种解决方案

今天给大家上一盘硬菜&#xff0c;并且是支付中非常重要的一个技术解决方案&#xff0c;有这块业务的同学注意自己尝试一把哈&#xff01; 一、需求如下&#xff1a; 生成订单30分钟未支付&#xff0c;自动取消 生成订单60秒后,给用户发短信 对上述的需求&#xff0c;我们给…...

【容器固化】 OS技术之OpenStack容器固化的实现原理及操作

1. Docker简介 要学习容器固化&#xff0c;那么必须要先了解下Docker容器技术。Docker是基于GO语言实现的云开源项目&#xff0c;通过对应用软件的封装、分发、部署、运行等生命周期的管理&#xff0c;达到应用组件级别的“一次封装&#xff0c;到处运行”。这里的应用软件&am…...

设置 SSH 通过密钥登录

我们一般使用 PuTTY 等 SSH 客户端来远程管理 Linux 服务器。但是&#xff0c;一般的密码方式登录&#xff0c;容易有密码被暴力破解的问题。所以&#xff0c;一般我们会将 SSH 的端口设置为默认的 22 以外的端口&#xff0c;或者禁用 root 账户登录。其实&#xff0c;有一个更…...

1.6 面试经典150题 - 买卖股票的最佳时机

买卖股票的最佳时机 给定一个数组 prices &#xff0c;它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。 你只能选择 某一天 买入这只股票&#xff0c;并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。 返回你可以从这笔交易…...

locust快速入门--使用分布式提高测试压力

背景&#xff1a; 使用默认的locust启动命令进行压测时&#xff0c;尽管已经将用户数设置大比较大&#xff08;400&#xff09;&#xff0c;但是压测的时候RPS一直在100左右。需要增加压测的压力。 问题原因&#xff1a; 如果你是通过命令行启动的或者参考之前文章的启动方式…...

K8s(三)Pod资源——pod亲和性与反亲和性,pod重启策略

目录 pod亲和性与反亲和性 pod亲和性 pod反亲和性 pod状态与重启策略 pod状态 pod重启策略 本文主要介绍了pod资源与pod相关的亲和性&#xff0c;以及pod的重启策略 pod亲和性与反亲和性 pod亲和性&#xff08;podAffinity&#xff09;有两种 1.podaffinity&#xff0c;…...

免费的域名要不要?

前言 eu.org的免费域名相比于其他免费域名注册服务&#xff0c;eu.org的域名后缀更加独特。同时&#xff0c;eu.org的域名注册也比较简单&#xff0c;只需要填写一些基本信息&#xff0c;就可以获得自己的免费域名。 博客地址 免费的域名要不要&#xff1f;-雪饼前言 eu.org…...

高通sm7250与765G芯片是什么关系?(一百八十一)

简介&#xff1a; CSDN博客专家&#xff0c;专注Android/Linux系统&#xff0c;分享多mic语音方案、音视频、编解码等技术&#xff0c;与大家一起成长&#xff01; 优质专栏&#xff1a;Audio工程师进阶系列【原创干货持续更新中……】&#x1f680; 优质专栏&#xff1a;多媒…...

[Python进阶] Python操作MySQL数据库:pymysql

7.7 操作MySQL数据库&#xff1a;pymysql 7.7.1 准备工作(创建mysql数据库) PHPStudy介绍&#xff1a; phpstudy是一款非常有用的PHP开发工具&#xff0c;旨在帮助开发者更加便捷地进行PHP程序的开发与调试。它提供了一个友好的图形用户界面&#xff0c;使得用户能够方便地进…...

Vue3实现带点击外部关闭对应弹出框(可共用一个变量)

首先&#xff0c;假设您在单文件组件(SFC)中使用了Vue3&#xff0c;并且有两个div元素分别通过v-if和v-else来切换显示一个带有.elpopver类的弹出组件。在这种情况下&#xff0c;每个弹出组件应当拥有独立的状态管理&#xff08;例如&#xff1a;各自的isOpen变量&#xff09;。…...

可视化试题(一)

1. 从可视化系统设计的角度出发&#xff0c;通常需要根据系统将要完成的任务的类型选择交互技术。按照任务类型分类可以将数据可视化中的交互技术分为选择、&#xff08; 重新配置 &#xff09;、重新编码、导航、关联、&#xff08; 过滤 &#xff09;、概览和细节等八…...

(二)原型模式

原型的功能是将一个已经存在的对象作为源目标,其余对象都是通过这个源目标创建。发挥复制的作用就是原型模式的核心思想。 一、源型模式的定义 原型模式是指第二次创建对象可以通过复制已经存在的原型对象来实现,忽略对象创建过程中的其它细节。 📌 核心特点: 避免重复初…...

Neo4j 集群管理:原理、技术与最佳实践深度解析

Neo4j 的集群技术是其企业级高可用性、可扩展性和容错能力的核心。通过深入分析官方文档,本文将系统阐述其集群管理的核心原理、关键技术、实用技巧和行业最佳实践。 Neo4j 的 Causal Clustering 架构提供了一个强大而灵活的基石,用于构建高可用、可扩展且一致的图数据库服务…...

【学习笔记】深入理解Java虚拟机学习笔记——第4章 虚拟机性能监控,故障处理工具

第2章 虚拟机性能监控&#xff0c;故障处理工具 4.1 概述 略 4.2 基础故障处理工具 4.2.1 jps:虚拟机进程状况工具 命令&#xff1a;jps [options] [hostid] 功能&#xff1a;本地虚拟机进程显示进程ID&#xff08;与ps相同&#xff09;&#xff0c;可同时显示主类&#x…...

[免费]微信小程序问卷调查系统(SpringBoot后端+Vue管理端)【论文+源码+SQL脚本】

大家好&#xff0c;我是java1234_小锋老师&#xff0c;看到一个不错的微信小程序问卷调查系统(SpringBoot后端Vue管理端)【论文源码SQL脚本】&#xff0c;分享下哈。 项目视频演示 【免费】微信小程序问卷调查系统(SpringBoot后端Vue管理端) Java毕业设计_哔哩哔哩_bilibili 项…...

【Linux】Linux 系统默认的目录及作用说明

博主介绍&#xff1a;✌全网粉丝23W&#xff0c;CSDN博客专家、Java领域优质创作者&#xff0c;掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域✌ 技术范围&#xff1a;SpringBoot、SpringCloud、Vue、SSM、HTML、Nodejs、Python、MySQL、PostgreSQL、大数据、物…...

MinIO Docker 部署:仅开放一个端口

MinIO Docker 部署:仅开放一个端口 在实际的服务器部署中,出于安全和管理的考虑,我们可能只能开放一个端口。MinIO 是一个高性能的对象存储服务,支持 Docker 部署,但默认情况下它需要两个端口:一个是 API 端口(用于存储和访问数据),另一个是控制台端口(用于管理界面…...

JDK 17 序列化是怎么回事

如何序列化&#xff1f;其实很简单&#xff0c;就是根据每个类型&#xff0c;用工厂类调用。逐个完成。 没什么漂亮的代码&#xff0c;只有有效、稳定的代码。 代码中调用toJson toJson 代码 mapper.writeValueAsString ObjectMapper DefaultSerializerProvider 一堆实…...

英国云服务器上安装宝塔面板(BT Panel)

在英国云服务器上安装宝塔面板&#xff08;BT Panel&#xff09; 是完全可行的&#xff0c;尤其适合需要远程管理Linux服务器、快速部署网站、数据库、FTP、SSL证书等服务的用户。宝塔面板以其可视化操作界面和强大的功能广受国内用户欢迎&#xff0c;虽然官方主要面向中国大陆…...

RFID推动新能源汽车零部件生产系统管理应用案例

RFID推动新能源汽车零部件生产系统管理应用案例 一、项目背景 新能源汽车零部件场景 在新能源汽车零部件生产领域&#xff0c;电子冷却水泵等关键部件的装配溯源需求日益增长。传统 RFID 溯源方案采用 “网关 RFID 读写头” 模式&#xff0c;存在单点位单独头溯源、网关布线…...

关于疲劳分析的各种方法

疲劳寿命预测方法很多。按疲劳裂纹形成寿命预测的基本假定和控制参数&#xff0c;可分为名义应力法、局部应力一应变法、能量法、场强法等。 1名义应力法 名义应力法是以结构的名义应力为试验和寿命估算的基础&#xff0c;采用雨流法取出一个个相互独立、互不相关的应力循环&…...