代码随想录算法训练营第一天| 704、27、34、367、69

704.二分查找

链接：https://leetcode.cn/problems/binary-search/

左闭右闭区间模板

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0;
        int right = nums.size() - 1; // 定义target在左闭右闭的区间里，[left, right]
        while (left <= right) { // 当left==right，区间[left, right]依然有效，所以用 <=
            int middle = left + ((right - left) / 2);// 防止溢出 等同于(left + right)/2
            if (nums[middle] > target) {
                right = middle - 1; // target 在左区间，所以[left, middle - 1]
            } else if (nums[middle] < target) {
                left = middle + 1; // target 在右区间，所以[middle + 1, right]
            } else { // nums[middle] == target
                return middle; // 数组中找到目标值，直接返回下标
            }
        }
        // 未找到目标值
        return -1;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

1. 首先是循环条件：因为是左闭右闭的区间，所以当left = right的时下标是合法的，举个例子就是[1,1]，实际上测试案例里面就有这种···

2. 其次思考一下当nums[mid] > target的时候，那么nums[mid]一定不是我们要搜索的值，那么在接下来的区间里面就一定不要包含这个值，那么既然不要包含这个值我们更新右区间的时候就是mid = r - 1，相当于我们从[0,nums.size()-1] -> [0,nums.size() -2]

左闭右开区间模板

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0;
        int right = nums.size(); // 定义target在左闭右开的区间里，即：[left, right)
        while (left < right) { // 因为left == right的时候，在[left, right)是无效的空间，所以使用 <
            int middle = left + ((right - left) >> 1);
            if (nums[middle] > target) {
                right = middle; // target 在左区间，在[left, middle)中
            } else if (nums[middle] < target) {
                left = middle + 1; // target 在右区间，在[middle + 1, right)中
            } else { // nums[middle] == target
                return middle; // 数组中找到目标值，直接返回下标
            }
        }
        // 未找到目标值
        return -1;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

1. 首先是循环条件：因为是左闭右开的区间，所以当left = right的时下标并不合法，举个例子就是[1,1)，这一定是不包含1的，所以循环条件只能是(left < right)

2. 其次思考一下当nums[mid] > target的时候，那么nums[mid]一定不是我们要搜索的值，那么在接下来的区间里面就一定不要包含这个值，那么既然不要包含这个值我们更新右区间的时候就是mid = r ，因为本来右边就是开区间，所以即使让mid = r，最后的结果也不会是r

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

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        // 首先是寻找左边界
        if (nums.empty()) return{ -1, -1 };
        int l = 0,r = nums.size() - 1,mid;
        while(l < r)
        {
            mid = (l + r)>>1;
            if(nums[mid] >= target) r = mid;
            else l = mid + 1;
        }
        if(nums[l] != target) return {-1,-1};
        int left_index = l;
        l = 0,r = nums.size() - 1;
        while(l < r)
        {
            mid = (l + r + 1)>>1;
            if(nums[mid] <= target) l = mid;
            else r = mid - 1;
        }
        int right_index = l;
        return {left_index,right_index};
    }
};
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

使用的是我习惯的二分写法：
第一个循环是左边界模板，为什么是左边界模板呢？因为即使是当nums[mid] = target的时候，也还是在减小有边界，所以最后锁定的肯定是左边界的值；同理第二个循环是有边界模板···但是有特殊测试点需要注意：当vector为空的时候直接返回{-1,-1}

367. 有效的完全平方数

整数二分，需要注意容易爆int，所以直接开long long

class Solution {
public:
    bool isPerfectSquare(int num) {
        // 这相当于是整数二分了
        long long l = 0,r = 2147483647;
        while(l<r)
        {
            long long mid = (l + r + 1)>>1; // 这个就是典型的爆了int
            if(mid * mid <= num) l = mid;
            else r = mid-1; 
        }
        if(l * l != num) return false;
        else return true;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

69. x 的平方根

有一些小细节需要注意：

1.浮点二分

很明显是浮点二分，但是最后是需要输出整形的，也就是说最后要强转为int

2. 左右边界

由于浮点二分左右边界是不相等的，但是实际上应该输出的是右边界：因为有些数是有平方根的，譬如x = 4，如果输出的是左边界，那么很可能是(int)(1.999999) = 1，所以需要向上取整，也就是需要输出(int)r

3. 精度问题

精度设置自然是越高越高，比如while(r - l > 1e-7)这样就可以过，如果把精度设置低（比如1e-3），那么一些点是过不了的

class Solution {
public:
    int mySqrt(int x) {
        double l = 0,r = 2147483647;
        while(r - l > 1e-7)
        {
            double mid = (l+r)/2;
            if(mid * mid > x) r = mid;
            else l = mid;
        }
        return (int)r;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13

---

---

27. 移除元素

链接：https://leetcode.cn/problems/remove-element/
利用双指针算法做是更优的解法：

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
                //就是一个数组
        //快慢指针的关键是什么？就是慢指针跟着快指针走啊
        //在遇到要删除的元素之前，慢指针处都复制快指针处的值
        //一定是等到要删除的元素那里，慢指针才停下来，慢了一步
        int slow_index = 0,fast_index = -1;
        int size = nums.size();
        for(int i=0;i<size;i++)
        {
            fast_index++;
            if(val != nums[fast_index]) {nums[slow_index++] = nums[fast_index];}
        }
        return slow_index;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

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

很简单的快慢指针的问题：

// 其实本质上不还是快慢指针吗
// 首先快慢指针都是在一起的，然后快指针先动，如果快慢指针处的函数值不一样，那么慢指针会往前移动一格并且用快指针处的函数值覆盖掉当前位置的值
// 判断条件是快慢指针处的值是否相等
// 结束条件是快指针>nums.size() - 1
// 其中慢指针的索引 + 1就是新数组的长度
// 注意只能原地修改，因此不能开辟一个新的vector来做
class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int size = nums.size();
        int slow_index = 0,fast_index = 0;
        for(int fast_index=0;fast_index<size;fast_index ++ ) // 确定是每次都要移动吗？
        {
            if(nums[slow_index]!=nums[fast_index]) { nums[++slow_index] = nums[fast_index];}
        }
        return slow_index+1;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

283.移动零

仍然是快慢指针的问题，但是存在优化的空间

// 其实还是快慢指针的问题，只不过复制的值变了而已
// 这次是慢指针复制快指针的非0元素
// 结束条件是快指针的index > nums.size()-1
// 之后慢指针从当前位置向后全部填充0

// 法一：
class Solution {
public:
	void moveZeroes(vector<int>& nums) {
        int slow_index = 0,fast_index = 0;
        for(fast_index = 0;fast_index<nums.size();fast_index++)  if(nums[fast_index]!=0) {nums[slow_index++] = nums[fast_index];}
        while(slow_index < nums.size()) nums[slow_index++] = 0;
    }
};
// 法二：
class Solution {
public:
	void moveZeroes(vector<int>& nums) {
        int slow_index = 0,fast_index = 0;
        for(fast_index = 0;fast_index<nums.size();fast_index++)  if(nums[fast_index]) {swap(nums[slow_index++],nums[fast_index]);} // 如果使用交换操作最后也可以保证0都在后面
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

继续加油
！！