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

如何做网站诊断实时热搜

如何做网站诊断,实时热搜,个人网站可以做经营性的吗,做纱窗修水管的一个网站文章目录 二分查找二分查找在排序数组中查找元素的第一个和最后一个位置搜索插入位置x 的平方根山脉数组的峰顶索引寻找峰值寻找旋转排序数组中的最小值点名 总结模版 二分查找 二分查找 没啥可说的,轻轻松松~ class Solution {public int search(int[] nums, int target) {i…

文章目录

  • 二分查找
    • 二分查找
    • 在排序数组中查找元素的第一个和最后一个位置
    • 搜索插入位置
    • x 的平方根
    • 山脉数组的峰顶索引
    • 寻找峰值
    • 寻找旋转排序数组中的最小值
    • 点名
  • 总结
      • 模版


二分查找

二分查找

在这里插入图片描述
没啥可说的,轻轻松松~

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

在排序数组中查找元素的第一个和最后一个位置

在这里插入图片描述
可以使用二分查找.

查找左端点:

  • 把区间划分成两个部分, 1. num[mid] < t , num[mid] >= t .
    把区间划分成 num[mid] < t 和 num[mid] > t ,这谁都懂,就不说了.
    关键是 “=” 给谁? 左边还是右边?
    关于为啥给右边,这里就不说了.
    我在这里只是讲一个记忆方法(左右都适用):
    求左端点,只看左括号,哪个括号在中间,“=” 就给谁.
    具体如下:在这里插入图片描述
  • 划分好区间,接下来就要想指针的移动方式了.
    在这里插入图片描述

查找右端点:

  • 把区间划分成两个部分, 1. num[mid] <= t , num[mid] > t .
    “=” 给谁,参考上面的记忆方法.

    • 求右端点,只看右括号,哪个括号在中间,“=” 就给谁.
  • 指针的移动方式,跟查找左端点的方法类似,自己写写试试~

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

坑:

  • nums 数组的长度可能为0.
  • 二分没写好,容易死循环.

我在写完以后,有个疑问:

  • 为啥循环结束后 mid 指向的值,不是我们想要的?

确实困惑了我一会,不过后来一想就明白了,因为出循环后 mid 差一次更新 ( left 或 right已经变了,但是 mid 没有变).

搜索插入位置

在这里插入图片描述
用查找左端点的方法,秒了~

坑:

  • 注意边界情况 nums[nums.length-1] < target.
class Solution {public int searchInsert(int[] nums, int target) {if(nums[nums.length-1] < target) return nums.length;int left=0,right=nums.length-1;while(left < right) {int mid = left+(right-left)/2;if(nums[mid] < target) {left = mid + 1;} else if(nums[mid] >= target){right = mid;}}return right;}
}

用左端点做完以后,我想了想,为啥不能用右端点做呢?
确实困扰了我一会,后来明白了,题目要查找的值是要 >= target 的.
而使用查找右端点的方法,会漏掉 > target 的情况:
在这里插入图片描述

x 的平方根

在这里插入图片描述
分析一下,可以把区间划分成 mid*mid <= xmid*mid > x.一看就是右端点,秒了~

坑:

  • 数值过大,要用 long 类型.
class Solution {public int mySqrt(int x) {long left = 0, right = x;while (left < right) {long mid = left + (right - left + 1) / 2;if (mid * mid <= x) {left = mid;} else {right = mid - 1;}}return (int) left;}
}

山脉数组的峰顶索引

在这里插入图片描述
没想到怎么把数组划分成两部分.
也就是 if(...) 中的条件不会写.

看了看题解,没想到还能这样做.
arr[mid - 1] < arr[mid] 划分~

class Solution {public int peakIndexInMountainArray(int[] arr) {int left = 0, right = arr.length - 1;while (left < right) {int mid = left + (right - left + 1) / 2;if (arr[mid - 1] < arr[mid]) {left = mid;} else {// 前面括号内有 +1 ,这里就 -1 .right = mid - 1;}}return left;}
}

寻找峰值

在这里插入图片描述
画图不能偷懒,要老老实实的画,写全了~

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

寻找旋转排序数组中的最小值

在这里插入图片描述
没想出来,题解是用 n-1 这个位置的数来划分区间的.

在这里插入图片描述

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

下面这个是用 0 位置来划分区间的(需要考虑一个特殊情况~).

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

点名

在这里插入图片描述
写出来了,用的二分~

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

总结

  • 当有 二段性 时,就可以用二分查找,不必有序~

    二段性: 通过某个条件,可以把数组分成两部分,根据题意可以舍弃一部分,这就叫二段性.

模版

在这里插入图片描述


本文到这里就结束啦~

在这里插入图片描述

http://www.15wanjia.com/news/27402.html

相关文章:

  • 招商网站平台网站怎么seo关键词排名优化推广
  • 做网站免费的域名俄罗斯搜索引擎yandex推广
  • 手机可怎么样做网站网站优化软件哪个好
  • 衢州网站建设招聘最新域名ip地址
  • 网站维护升级电话营销
  • 企业网站开发汇报网络营销是什么工作
  • 档案安全网站安全建设今日头条网页版入口
  • 做医院网站推广普通话绘画
  • 桂林房产百度seo视频教程
  • 推荐网站制作公司营销网站优化推广
  • 开发网站需要租服务器打开百度搜索网站
  • 阿里云找人做网站靠谱吗百度免费下载安装
  • 威海做网站推广的企业提升seo搜索排名
  • 免费建立个人网站短视频矩阵seo系统源码
  • 北京市网站设计永久免费客服系统软件
  • 注册免费域名网站北京百度竞价
  • 西地那非多少钱一盒seo外链代发
  • 商城网站 免费开源互联网推广中心
  • 做的ASP网站手机seo门户网站
  • 常州做网站需要多少钱微信销售平台
  • 畅言 wordpress插件手机优化器
  • 给自己家的公司做网站好做吗全网热搜榜
  • 用dw做淘客网站的步骤天津百度关键词推广公司
  • htm5移动网站开发岳阳seo公司
  • 个人淘宝客网站有哪些推广赚钱软件排行
  • asp 个人网站电商推广和网络推广的策略
  • 武汉定制公交app宁波seo快速排名
  • 生鲜网站制作中国十大门户网站排行
  • 怎样在内网建设一个网站seo服务顾问
  • 做内衣批发的网站广告接单网站