704. 二分查找

第一想法

二分查找母题；

有闭区间和开区间两种解法：

闭区间：right 初始化为 nums.size()-1 ,是实右边界；在进入 while 循环时就要注意需要判断 left == right；同时每次移动边界都要从已经找到的地方往右或往左移动一步；

开区间：right 初始化为 nums.size() ,是虚右边界；在进入 while 循环时就要注意写 left < right；移动时左边界是 mid+1， 而右边界是 mid；

看完题解后的想法

——

实现中遇到的困难

采用实变界进入循环的判断忘记了需要判断left == right；

代码

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0;
        int 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;
    }
};

27. 移除元素

第一想法

第一想法就是维护两个指针，left 找到 val 位置，而 right 从右边找不为val的值，当左右相遇说明找完了；

看完题解后的想法

——

实现中遇到的困难

最开始right = nums.size()-1就导致了需要额外判断刚开始左右重合时的情况；

并且因为需要左右重叠去找，计数也有点困难；

这里可以让右边的移动不用那么快，而是一步步移动，即使是 val，left 被赋值之后也不会动，直到 right 找到不为val的值；

并且为了简化初始的判断，让 right = nums.size() ；这样right的位置就自带了计数功能；

代码

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int left = 0;
        int right = nums.size();

        while (left < right) {
            if (nums[left] == val) {
                nums[left] = nums[right-1];
                right--;
            } else {
                left++;
            }
        }

        return right;
    }
};

977. 有序数组的平方

第一想法

有序，说明最大值可能出现在两端；

要按照升序排列平方数的话，就需要双指针比较，哪个大哪个放在后面然后再移动放了数据的指针；

看完题解后的想法

——

实现中遇到的困难

——

代码

class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        int left = 0;
        int right = nums.size()-1;
        vector<int> res(nums.size(), 0);

        for (int i = nums.size()-1; i >=  0; i--) {
            if (nums[left] * nums[left] > nums[right] * nums[right]) {
                res[i] = nums[left] * nums[left];
                left++;
            } else {
                res[i] = nums[right] * nums[right];
                right--;
            }
        }

        return res;
    }
};

今日收获

复习了二分查找的开区间和闭区间；

踩坑了双指针法的边界条件；