代码随想录算法训练营第一天|LeetCode704二分查找、LeetCode27移除元素

LeetCode704二分查找

题目链接：704二分查找

思路：
以前刷过不少题，也看过不少题解，就记得区间有不少原则，乍一想有哪些想不起来了，反正我是选择了最简单易懂的左闭右闭原则。
1、区间左闭右闭原则。
2、while进行循环判断
当目标值target < 中间值时，向左边区间找，右区间变化；
当目标值target > 中间值时，向右边区间找，左区间变化；
找到后，返回中间值（目标值）的下标；
3、找不到返回 -1。

注意：

以前刷题的看些经验贴之类的，要注意middl写成int middle = left + (right - left) / 2;这种格式，避免写成int middle = （left + right）/ 2；，因为这样有的测试用测会报越界，你想想两个很大的int型数相加岂不是很容易超过int的范围。

class Solution {
public:
    int search(vector<int>& nums, int target) {
        //左闭右闭
        int left = 0;
        int right = nums.size()-1;
        while (left <= right) {
            int middle = left + (right - left) / 2;
            if (target < nums[middle]) {
                right = middle - 1;
            }
            else if (target > nums[middle]) {
                left = middle + 1;
            }
            else return middle;
        }
        return -1;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

LeetCode27移除元素

题目链接：27移除元素

此题看到说不额外开销内存就立马想到了双指针，首先想到的是左右指针，一个往右走，一个往左走。
写完左右指针，我记得应该可以用快慢指针，很快也把快慢指针写出来了。
其中写此题的时候，发现了一个自己以前没注意的错误，就是对vector进行遍历的时候一定要注意避免写成以下错误。

for (int fast = 0; fast <= nums.size()-1; fast ++) {}
1

此格式当空时，容易报越界，因为若vector的为空时候，nums.size()会返回一个无符号的整型，与 -1 相加会越界
，原因是无符号数和有符号数相加，有符号数会被提升为无符号数，那么符号位就变成了数值位，导致越界。

正确写法

for (int fast = 0; fast < nums.size(); fast ++) {}
1

快慢指针

思路：
1、快慢指针都从0开始往右走；
2、对快指针fast进行遍历；
当快指针fast遇到不等于val的值时，就将快指针fast对应的值赋给慢指针slow，这里不用考虑快指针fast所对应的值是什么，因为后面慢 指针可能会重新赋值到，或者返回的时候，根本就返回不到那个位置。

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int slow = 0;
        for (int fast = 0; fast < nums.size(); fast ++) {
            if (nums[fast] != val) {
                nums[slow++] = nums[fast];
            }
        }
        return slow;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12

左右指针

思路：
1、判断条件左指针left小于右指针right就行；
2、left只要不等于val值就一直往右走；
3、当left等于val值时，让它与right值进行交换，并且right -1；

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 left;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16