代码随想录-训练营-day1

704. 二分查找 - 力扣（LeetCode）

老生常谈的题目，但是在这里我们希望脱离这个题目，来聊聊二分查找的一些易错点：

首先是我们取right时，该取nums.size()-1呢还是nums.size()，会造成什么区别呢？然后是while(left<right)里这个left和right之间的关系运算符，有时是<有时是<=；然后是我们的left与right的更新方式：有时是left=mid有时是left=mid+1；这三个点搞不清楚的话老是出现莫名奇妙的报错，令人非常的困扰。

总的来说我们有两种写法：左闭右闭的区间与左闭右开的区间（一般左边不开）

当我们是左闭右闭时，我们的right的值是可以取到的，那自然我们的right就得是nums.size()-1(nums序号中最后一位)；同理，我们的right可取，那我们自然可以考虑left等于right的情况（当left==right时，[left,right]没有越界且这个元素依然需要检查）；最后，当我们的nums[mid]>target时：我们的区间需要更换为[newLeft,right]，其中这个newLeft假如是mid的话，我们其实已经知道nums[mid]!=target了，所以newLeft来到mid+1即可。

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

当我们是左闭右开的时候，right就会取nums.size()，这样的话left当然不存在等于right的情况（因为right根本就不可取），然后我们注意更新left和right时，假如仍然需要更新左边界，那本质上由于是左闭右开的区间，我们的newLeft依然可以取mid+1（因为mid处已经检查过），但是更新右边界的话，由于我们本身的右边界不可取，我们就可以将右边界更新为mid，这样我们实际可取的区间也是从mid-1开始。

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

这两种算法孰优孰劣？我并没有太直观的感受，不过我个人更喜欢左闭右闭的做法：更统一，更直观。

27. 移除元素 - 力扣（LeetCode）

这是一个充分体现数组性质的题目：数组中没有删除元素的操作，我们只能通过覆盖的方式来实现等效的效果，且数组每覆盖一个元素都会引起该元素之后（或者之前）的数组元素移动。

这题的暴力解法就是遍历两次，第一次我们找到与val相同的数组元素后从该小标开始遍历往后的所有元素，让这些元素整体向前移动一位，然后数组长度减一。

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int size = nums.size();
        for (int i = 0; i < size; i++) {
            if (nums[i] == val) { // 发现需要移除的元素，就将数组集体向前移动一位
                for (int j = i + 1; j < size; j++) {
                    nums[j - 1] = nums[j];
                }
                i--; // 因为下标i以后的数值都向前移动了一位，所以i也向前移动一位
                size--; // 此时数组的大小-1
            }
        }
        return size;

    }
};

然后是正常解法：双指针，快指针去找符合我们要求的（不等于val的数组元素）数组元素，然后将符合要求的元素更新到慢指针处，每更新一次慢指针往前一位，同时维护一个新数组的长度，最后返回这个长度即可。

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

这个题还有一个点在于：我们不可以直接返回新的nums.size()作为结果，因为移除元素后的数组会有Null来填充原来的空位，你返回nums.size()依然是之前的大小。

977. 有序数组的平方 - 力扣（LeetCode）

首先依然是暴力解法：

class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        for(int &num:nums){
            num*=num;
        }
        sort(nums.begin(), nums.end());
        return nums;
    }
};

非常的直观，我们每个数都自己平方后用sort函数来排序即可。

那现在我们该用一些不那么暴力的方法了，首先我们注意到原来的数组就是一个递增数组，那么平方后就是两边高中间低，这时非常容易想到我们的左右指针：我们的左右指针也是一个从两边往中间收拢的一个过程。

我们需要新建一个数组（不建议在原来的数组上修改），然后我们从左右指针开始平方后比较大小，大的那个就放在新数组的末位，然后更新指针。

class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        int left=0,right=nums.size()-1,n=nums.size()-1;
        vector<int> res(nums.size(),0);
        while(left<=right){
            if(nums[right]*nums[right]>=nums[left]*nums[left]){
                res[n--]=nums[right]*nums[right];
                --right;
            }
            else{
                res[n--]=nums[left]*nums[left];
                ++left;
            }
        }
        return res;
    }
};

这样我们就完成了这个题的双指针写法。

第一天的题显然整体还是偏向简单和基础，我们复习了双指针的基本用法与二分法，还有数组的一些基本性质。