代码随想录算法训练营打卡第一天

@代码随想录算法训练营第1天 | Leetcode704 二分查找， 27 移除元素

704 二分查找

视频链接： https://www.bilibili.com/video/BV1fA4y1o715

第一遍读题思考（五分钟内，如果没有思路就写暴力解法思路，暴力解法思路也不清晰就写无）

本题是在一个升序数组中寻找某个特定的值。初始的想法就是涉及到一个while循环，循环的离开条件就是找到目标值，或者搜索空间长度为1.

1. 在循环里，首先用数组（搜索空间）中值与目标数字做比较：
2. 如果数组长度为1，直接比较并返回result或者-1
3. 如果等于：result += 搜索空间长度的一半减1作为下标，返回result。
4. 如果中值小于目标：则搜索空间变为原始数组的右半边，如果原始搜索空间长度是偶数，则包括中值（左闭）,result += len(原数组)/2。如果是奇数，则不包括中值（左开），result += len(原数组)/2 + 1。返回第一步。
5. 如果中值大于目标：则搜索空间变为原始数组的右半边，如果原始搜索空间长度是偶数，则包括中值（左闭）。如果是奇数，则不包括中值（左开）。两种情况result += 0。返回第一步。

代码随想录解法思路

从左闭右闭或者左闭右开的思路处理二分法，推出循环的条件更简洁，通过left<=right or left < right即可。也不需要对result进行多重判断，直接返回middle即可。具体思路就是直接用left和right去定义搜索空间，然后进入while循环找中值判断，基于左闭右闭或者左闭右开的原则进行left或者right的重新赋值。主要注意的有两点，一个是在while循环的时候要根据[]或者[)的原则判断left<=right或者left<right是否是合法区间。第二个点在与比完大小后，赋值给left或者right的时候是否包含middle，如果是[ ]就不需要包含，因为middle已经比较过了。如果是[ )就需要包含。

c++代码具体实现注意事项

实际编写的时候遇到超出时间限制这个错误，发现是在每次循环中。middle的赋值都是用的nums.size()/2，但实际上应该使用left与right加和的一半作为middle。

学习时长

30分钟

27 移除元素

*文章链接：*https://www.bilibili.com/video/BV12A4y1Z7LP

第一遍读题思考（五分钟内，如果没有思路就写暴力解法思路，暴力解法思路也不清晰就写无）

因为之前看过类似的题，大概知道是双指针法，但是具体操作不清楚。

代码随想录解法思路

快慢双指针，两个指针从同一位置出发（数组头部）。检查快指针的值是否是需要删除的数值，如果不是：快指针指向的值赋值给慢指针，快指针++，慢指针++。如果是：快指针++。直到快指针到数组结尾。此时返回慢指针的值就是删除操作后的数组长度。

c++代码具体实现注意事项

比较简单，没有报错，一次成功。

学习时长

30 分钟

34 二分查找

今天第一天任务比较轻松，所以多刷一到二分查找的题加深左闭右闭的记忆。

文章链接：

第一遍读题思考（五分钟内，如果没有思路就写暴力解法思路，暴力解法思路也不清晰就写无）

题目要求在一个非递减的数组中找到某个值的左右边界。用二分法查找值，找到值之后在while中继续嵌套一个while以该位置为中心向左和向右遍历直到找到left bound和right bound。

leetcode解法思路

定义私有函数searchBound，让寻找left和right bound分别进行。在单独的进程中，如果left进程中找到了target，让right = middle - 1.反之亦然。比while嵌套while要简洁。

c++代码具体实现注意事项

具体实现中记住[]或者[)的不同之处，其他的没什么难点。

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        return {searchRangeBound(nums, target, "left"), searchRangeBound(nums, target, "right")};
    }
private:
    int searchRangeBound(vector<int>& nums, int& target, const string& bound){
        int left = 0;
        int right = nums.size() - 1;
        int res{-1};
        while(left<=right){
            int middle = (left + right)>>1;
            if(nums[middle] < target){
                left = middle + 1;
            }
            else if(nums[middle] > target){
                right = middle - 1;
            }
            else{
                res = middle;
                if(bound == "left"){
                    right = middle - 1;
                }
                else if(bound == "right"){
                    left = middle + 1;
                }
                else{
                    cerr << "wrong type (bound == 'left' or 'right')" << endl;
                }
            }
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

学习时长

20分钟

其余总结

在写middle=(left+right)/2的时候在c++中可能存在溢出error，所以可以写成middle = left + (right-left)>>2