当前位置: 首页 > 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;}
http://www.lryc.cn/news/115372.html

相关文章:

  • linux 下安装部署flask项目
  • 在Vue里,将当前窗口截图,并将数据base64转为png格式传给服务器
  • Echarts图表Java后端生成Base64图片格式,POI写入Base64图片到Word中
  • 【AI】《动手学-深度学习-PyTorch版》笔记(十二):从零开始实现softmax回归
  • 汽车用功率电感器
  • 上传图片视频
  • 【UE5】UE5与Python Socket通信中文数据接收不全
  • 一些有难度的c++题目思路讲解--第一期2023/8/8 小Q的修炼与旷野大计算
  • Node.js:path文件路径操作模块
  • 基于 CentOS 7 构建 LVS-DR 群集
  • 机器学习笔记 - 使用 Tensorflow 从头开始​​构建您自己的对象检测器
  • IELAB-网络工程师的路由答疑10问(2)
  • 聚观早报|iPhone 15预计9月22日上市;一加Open渲染图曝光
  • react-use-gesture
  • 智能中的“一体两面”
  • 前端渲染数据
  • 【Linux操作系统】深入了解系统编程gdb调试工具
  • linux 安装go 1.18版本
  • LLVM笔记2 Intermediate Representation (IR)
  • 篇五:原型模式:复制对象的秘密
  • 为什么ip地址一直在变化
  • 10.物联网操作系统之低功耗管理
  • SQL SERVER 2019 数据库还原测试库的方法
  • leetcode 62. 不同路径
  • ad+硬件每日学习十个知识点(25)23.8.5(常见芯片类型、数字隔离芯片、IO扩展芯片TCAL6416)
  • fetch-github-hosts间隔一年大更新v2.6发布,多端支持
  • K最近邻算法:简单高效的分类和回归方法(三)
  • 【数据分析专栏之Python篇】五、pandas数据结构之Series
  • 中间件多版本冲突的4种解决方案和我们的选择
  • 对 async/await 的理解