立志重刷代码随想录60天冲冲冲！！——第一周查缺补漏

（周末补更）

34. 在排序数组中查找元素的第一个和最后一个位置

第一个target：简单二分，然后target == nums[mid]时，再次添加right = mid - 1

最后一个target：还是简单二分，然后target == nums[mid]时，再次添加left = mid + 1

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        int len = nums.size();
        int first = -1, last = -1;

        // 寻找第一个target
        int left = 0;
        int right = len - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (target < nums[mid]) {
                right = mid - 1;
            } else if (target > nums[mid]){
                left = mid + 1;
            } else {
                // 若target == nums[mid]，right = mid - 1;
                right = mid - 1;
                first = mid;
            }
        }

        // 寻找第一个target
        left = 0;
        right = len - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (target < nums[mid]) {
                right = mid - 1;
            } else if (target > nums[mid]){
                left = mid + 1;
            } else {
                // 若target == nums[mid]，left = mid + 1;
                left = mid + 1;
                last = mid;
            }
        }

        return {first, last};
    }
};

（拓展练习）

69. x 的平方根 

class Solution {
public:
    int mySqrt(int x) {
        int left = 0;
        int right = x;
        int ans = -1; // 记录答案

        while (left <= right) {
            int mid = (left + right) / 2;
            // 有可能内存泄漏，需定义long long
            if ((long long)mid * mid > x) {
                right = mid - 1;
            } else {
                ans = mid;
                left = mid + 1;
            }
        }
        return ans;
    }
};

367. 有效的完全平方数

若right = num; 可以省略num == 1的情况；

class Solution {
public:
    bool isPerfectSquare(int num) {
        if (num == 1) {return true;} // 若right = num; 可以省略此行；

        int left = 0, right = num - 1;

        while (left <= right) {
            int mid = (left + right) / 2;
            if ((long long)mid * mid < num) {
                left = mid + 1;
            } else if ((long long)mid * mid > num) {
                right = mid - 1;
            } else {
                return true;
            }
        }
        return false;
    }
};

26. 删除有序数组中的重复项

相当不熟练，要想清楚快慢指针含义，分别处理快慢指针进位。

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int len = nums.size();
        if (len == 1) {return len;}

        int slow = 1, fast = 1;
        while (fast < len) {
            // 慢指针表示位置，快指针表示数值（无论如何都要向前走）
            // 快指针与前一格不同，就把快指针赋值给慢指针，慢指针++
            if (nums[fast] != nums[fast - 1]) {
                nums[slow] = nums[fast];
                slow++;
            }
            fast++;
        }
        return slow;
    }
};

283. 移动零

有了上一题双指针思路，这个秒

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int len = nums.size();
        int slow = 0, fast = 0;

        // 慢指针是位置，快指针是数值（快指针需不停向前）
        // 快指针指向0，快慢指针交换，慢指针++
        while (fast < len) {
            if (nums[fast] != 0) {
                swap(nums[slow], nums[fast]);;
                slow++;
            }
            fast++;
        }
    }
};