69. X的平方根

给你一个非负整数 x ，计算并返回 x 的 算术平方根 。

由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。

注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。

思路——二分查找法

由于x平方根的整数部分ans是满足k^2≤x的最大k值，因此我们可以对k进行二分查找，从而得到答案。

解题

小巧思：RTL法则→跳出循环

class Solution 
{
public:
    int mySqrt(int x) 
    {
        int l=0,r=x,ans=-1;
        while(l<=r)
        {
            int mid=l+(r-l)/2;
            if((long long)mid*mid<=x)
            {
                ans=mid;
                l=mid+1;
            }
            else
                r=mid-1;
        }
        return ans;
    }
};

367. 有效的完全平方数

给你一个正整数 num 。如果 num 是一个完全平方数，则返回 true ，否则返回 false 。

完全平方数 是一个可以写成某个整数的平方的整数。换句话说，它可以写成某个整数和自身的乘积。

不能使用任何内置的库函数，如  sqrt 。

思路

若正整数 x 满足 x×x=num，则 x 一定满足 1≤x≤num。

细节

因为我们在移动左侧边界 left 和右侧边界 right 时，新的搜索区间都不会包含被检查的下标 mid，所以搜索区间的边界始终是我们没有检查过的。因此，当left=right 时，我们仍需要检查 mid=(left+right)/2。

class Solution 
{
public:
    bool isPerfectSquare(int num) 
    {
        int l=0,r=num;
        while(l<=r)
        {
            int mid=l+(r-l)/2;
            long square = (long) mid*mid;
            if(square<num)
                l=mid+1;
            else if(square>num)
                r=mid-1;
            else    
                return true;
        }
        return false;
    }

};

27. 移除元素

视频讲解：双指针实现O(n)大小解题方式

一层for循环做两层for循环

定义fast、slow两个指针，fast寻找新数组所需要元素即删除val目标值后的元素值，slow是新数组的下标值。

双指针法： 通过一个快指针和慢指针在一个for循环下完成两个for循环的工作。

定义快慢指针

• 快指针：寻找新数组的元素 ，新数组就是不含有目标元素的数组
• 慢指针：指向更新 新数组下标的位置

给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素。元素的顺序可能发生改变。然后返回 nums 中与 val 不同的元素的数量。

class Solution 
{
public:
    int removeElement(vector<int>& nums, int val) 
    {
        int slowIndex=0;
        for(int fastIndex=0;fastIndex<nums.size();fastIndex++)
        {
            if(nums[fastIndex]!=val)
            {
                nums[slowIndex]=nums[fastIndex];
                slowIndex++;
            }
        }
        return slowIndex;    
    }
};

明日作业