Leetcode刷题系列

提示：这里可以添加系列文章的所有文章的目录，目录需要自己手动添加
本系列文章将会记录我的刷题情况，刷题方法根据B站大学莱刷题视频里的题目进行，我会按照类型进行分类，一个类型会有多个同类型不同难道的题目。

二分法刷题模版学习前言一、二分法适应条件二、解题步骤

1.确定二分的边界2.二分框架模版代码3.check方法设计4.区间更新 三、实际题目应用

1.x的平方根2.搜索插入位置 总结

提示：这里可以添加本文要记录的大概内容：

本篇文章将会介绍二分法类型算法题求解模版，参考链接：B站大学莱的视频教程。

数据具有单调性数据可以通过条件拆分成两部分（存在两端性质）
以实际题目为例，如leetcode 69 题求算术平方根

确定二分的边界编写二分框架的代码设计一个check(性质)，一个判断方法，将数据分成两段的方法判断区间如何更新如果更新方法写的是left = mid , right = mid -1, 需要在计算mid的时候+1

一般以0为左边界，输入数据为有边界，具体情况具体判断

模版代码如下：

public int bsearch_1(int left, int right) {
        while (left < right) {
            int mid = left + right >> 1;
            if (check(mid)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }

具体情况具体判断

情况一

通过check方法，将去接分为两段，当所求点为后半段区间点端点，而此时mid 大于所求点，则区间更新方法

	left 不变
	right = mid （此时mid处于蓝色段，与所求点可能相等，因此取相等）

情况二

通过check方法，将去接分为两段，当所求点为后半段区间点端点，而此时mid 小于所求点，则区间更新方法

	left = mid + 1 （此时mid处于红色段，不会与所求点相等，因此可以+1）
	right 不变

情况三

通过check方法，将去接分为两段，当所求点为前半段区间点端点，而此时mid 小于所求点，则区间更新方法

	left = mid  （此时mid处于红色段，可能与所求点相等，因此取相等）
	right 不变

情况四

通过check方法，将去接分为两段，当所求点为前半段区间点端点，而此时mid 大于所求点，则区间更新方法

	left = 不变  
	right = mid - 1 （此时mid处于蓝色段，不会与红色段所求点相等，因此-1）
	特别的 在计算mid的时候. mid = ( left + right + 1 ) / 2 ,其他则不用 +1

题目链接：leetcode第69题 x 的平方根

题目描述

	给你一个非负整数 x ，计算并返回 x 的 算术平方根 。
	由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。
	注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。

解题思路

	所求的算术平方根的解在0～x区间内，初始时，left = 0, right = x, 区间内的数字可以分为三种情况
	t*t>x、t*t=x、t*t x,不断缩小区间，最后区
	间缩小为一个点，即为所求。
	为什么不能是t*t>=x 和 t*t < x，因为题目要求的是向下取整，小数部分舍去，就存在 小于根号x 的小数
	不满足 t*t>= x， 比如 x =8, 8的平方根是：2.8284271247461903, 算术平方根是2， 从2～2.8之间就不
	满足t*t >=x，前面图中蓝色的线段就不是连续的了。

具体代码

	public static int mySqrt(int x) {
        int left = 0;
        int right = x;
        while (left < right) {
            // 根据 步骤5 right = mid - 1 计算mid的时候需要 +1 避免死循环
            int mid = left + right + 1 >> 1;
            // 所求点在 红色 段最有边端点
            if (mid <= x / mid) {
                // mid 小于所求点 情况三
                left = mid;
            } else {
                // mid 大于所求点 情况四
                right = mid - 1;
            }
        }
        return left;
    }

题目链接：35. 搜索插入位置

题目描述

	给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。
	如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
	请必须使用时间复杂度为 O(log n) 的算法。

解题思路

	所求的解在0～nums.lenth之间，初始时，left = 0, right = nums.length -1, 二分法的
	拆分check判断，用nums[t] <= target 去判断。

具体代码

	
    public static int searchInsert(int[] nums, int target) {
        if (target < nums[0]) {
            return 0;
        }
        int left = 0;
        int right = nums.length - 1;
        while (left < right) {
            int mid = left + right + 1 >> 1;
            if (nums[mid] <= target) {
                left = mid;
            } else {
                right = mid - 1;
            }
        }
        return nums[left] == target ? left : (left + 1);
    }

提示：这里对文章进行总结：

例如：以上就是今天要讲的内容，本文仅仅简单介绍了pandas的使用，而pandas提供了大量能使我们快速便捷地处理数据的函数和方法。