week6

2021-08-21

如题目＞▽＜

find-first-and-last-position-of-element-in-sorted-array（lc）

链接：

https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array//

思路：

先左面二分到头，再右面二分到头，别写歪了就行

class Solution {
public:
    vector<int> res={-1,-1};
    vector<int> searchRange(vector<int>& nums, int target) {
        int l=0,r=nums.size(),r1=0,mid1=0;
        bool flg=0;
        while(l<r){
            int mid=l+(r-l)/2;
            if(nums[mid]<target){
                l=mid+1;
            }
            else if(nums[mid]>target){
                r=mid;
            }
            else{
                res[0]=mid;
                if(!flg){
                    r1=r;
                    mid1=mid;
                }
                r=mid;
                flg=1;
            }
        }
        l=mid1;
        r=r1;
        if(res[0]!=-1)
        while(l<r){
            int mid=l+(r-l)/2;
            if(nums[mid]<target){
                l=mid+1;
            }
            else if(nums[mid]>target){
                r=mid;
            }
            else{
                res[1]=mid;
                l=mid+1;
            }
        }
        return res;
    }
};

sqrtx（lc）

链接：

https://leetcode-cn.com/problems/sqrtx/

思路：

从0开始的二分，为了不使mid*mid超出int，使用除法，但当mid=0时就出问题了，所以x=1，0时要特判

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

sqrtx（lc）

链接：

https://leetcode-cn.com/problems/sqrtx/

思路：

从0开始的二分，为了不使mid*mid超出int，使用除法（和上题一样，多一个判断相乘与原数相不等相等而已），沙雕力扣没有自动类型转换！！！坑死我了

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

remove-element（lc）

链接：

https://leetcode-cn.com/problems/remove-element/

思路：

快慢指针跑一遍

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

remove-duplicates-from-sorted-array（lc）

链接：

https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array/

思路：

快慢指针都放在位置1处，当两个指针不一样时，慢指针再前进。数组为空时需要特判

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int l=1,r=0;
        if(nums.size()==0)
        return 0;
        for(r=1;r<nums.size();r++){
            if(nums[r]!=nums[l-1]){
                nums[l++]=nums[r];
            }
        }
        return l;
    }
};

move-zeroes（lc）

链接：

https://leetcode-cn.com/problems/move-zeroes/submissions/

思路：

第一道快慢指针跑法，跑完后面全设成0

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int l=0;
        for(int r=0;r<nums.size();r++){
            if(nums[r]!=0){
                nums[l++]=nums[r];
            }
        }
        for(;l<nums.size();l++){
            nums[l]=0;
        }
    }
};