代码随想录Day1

 · 2023-12-25 · 次阅读

代码随想录DAY1

数组理论基础

c++ vector 和数组有差别，虽然底层是用array实现的

C++ 二维数组是把二维的数组接在一起形成一条直线

二分查找

  • 给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
1
2
3
输入: nums = [-1,0,3,5,9,12], target = 9     
输出: 4       
解释: 9 出现在 nums 中并且下标为 4 
1
2
3
输入: nums = [-1,0,3,5,9,12], target = 2     
输出: -1        
解释: 2 不存在 nums 中因此返回 -1
  • 你可以假设 nums 中的所有元素是不重复的。
  • n 将在 [1, 10000]之间。
  • nums 的每个元素都将在 [-9999, 9999]之间。

暴力解

  1. 错误的测试代码01
1
2
3
4
5
6
7
8
9
10
11
12
13
14
int search(int* nums, int numsSize, int target) {
    int i=1,j=numsSize;
        for(;;){
            if(i==j) return -1;
            if(nums[i]==target){
                return i;
            }
            if(nums[j]==target){
                return j;
            }
            i++;
            j--;
        }
}

there are a few issues with the code:

  1. Array Indexing: In C and many other programming languages, array indexing starts at 0, not 1. Therefore, you should initialize i to 0, not 1.

  2. Loop Termination: The code uses an infinite loop (for(;;)) and relies on i and j being equal to terminate. This may lead to an infinite loop if the target element is not found in the array. You should add a condition to break the loop when necessary.

  3. Missing Return: If the target element is not found in the array, the function does not have a return statement. You should return -1 as the default value to indicate that the target is not in the array.

Here’s an improved version of the code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int search(int* nums, int numsSize, int target) {
    int i = 0, j = numsSize - 1; // Start from the first and last elements

    while (i <= j) { // Use a while loop for clarity
        if (nums[i] == target) {
            return i; // Found the target at index i
        }
        if (nums[j] == target) {
            return j; // Found the target at index j
        }
        i++;
        j--;
    }

    return -1; // Target not found in the array
}

This code initializes i to 0 and j to numsSize - 1, uses a while loop with proper termination conditions, and returns -1 if the target element is not found in the array.

以上解法是暴力求解，用二分法要重新设计

二分法

二分查找涉及的很多的边界条件，逻辑比较简单，但就是写不好。例如到底是 while(left < right) 还是 while(left <= right)，到底是right = middle呢，还是要right = middle - 1呢？

写二分法经常写乱，主要是因为对区间的定义没有想清楚，区间的定义就是不变量。要在二分查找的过程中，保持不变量，就是在while寻找中每一次边界的处理都要坚持根据区间的定义来操作，这就是循环不变量规则。

写二分法，区间的定义一般为两种，左闭右闭即[left, right]，或者左闭右开即[left, right)。

借助C++库函数

1
2
3
4
5
6
7
8
9
10
11
class Solution {

public:

int search(vector<int>& nums, int target) {

return binary_search(nums.begin(),nums.end(),target) ? lower_bound(nums.begin(),nums.end(),target)-nums.begin() : -1;

}

};

lower_bound函数[first, last) 中查找第一个不小于（即大于或等于）指定 val 的元素。这个范围应该是已排序的，或者至少以 val 为基准进行了划分。该函数返回指向该元素的迭代器,表达式lower_bound(nums.begin(), nums.end(), target) - nums.begin()计算找到的元素相对于向量开头的索引。

搜索插入位置

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

你可以假设数组中无重复元素。

示例 1:

  • 输入: [1,3,5,6], 5
  • 输出: 2

示例 2:

  • 输入: [1,3,5,6], 2
  • 输出: 1

示例 3:

  • 输入: [1,3,5,6], 7
  • 输出: 4

示例 4:

  • 输入: [1,3,5,6], 0
  • 输出: 0

1、 错误测试1

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
class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int l=0;
        int r=nums.size()-1;
        int flag=0;
        int mid=0;
        while(l<=r){
            mid=l+(r-l)/2;
            if(nums[mid]>target){
                r=mid-1;
                flag=1;
            }
            else if(nums[mid]<target){
                l=mid+1;
                flag=2;
            }
            else{
                return mid;
                flag=3;
            }
        }
        if(flag==1)return mid-1;
        else if(flag==2)return mid+1;
        else if(flag==3)return mid;
        return -1;
    }
};

2. 暴力解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        for (int i = 0; i < nums.size(); i++) {
        // 分别处理如下三种情况
        // 目标值在数组所有元素之前
        // 目标值等于数组中某一个元素
        // 目标值插入数组中的位置
            if (nums[i] >= target) { // 一旦发现大于或者等于target的num[i]，那么i就是我们要的结果
                return i;
            }
        }
        // 目标值在数组所有元素之后的情况
        return nums.size(); // 如果target是最大的，或者 nums为空，则返回nums的长度
    }
};

二分法解

题目的前提是数组是有序数组，这也是使用二分查找的基础条件。

image-20231214210105192

第八行必须要在位移运算的时候带括号，否则会进行无效位移导致超时

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

给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target，返回 [-1, -1]。

你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

示例 1：

1
2
输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]

示例 2：

1
2
输入：nums = [5,7,7,8,8,10], target = 6
输出：[-1,-1]

示例 3：

1
2
输入：nums = [], target = 0
输出：[-1,-1]

写两个二分来进行搜索左边界和右边界

手写代码和错误修正

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        int lb=get_lb(nums,target);
        int rb=get_rb(nums,target);
        if(lb==-2||rb==-2)return{-1,-1};
        if(rb-lb>1)return{lb+1,rb-1};
        return {-1,-1};
    }
private:
    int get_rb(vector<int>&nums,int target){
        int l=0;
        int r=nums.size()-1;
        int rb=-2;
        while(r<=l){
        int mid=l+((r-l)>>1);
        if(nums[mid]>target){
            r=mid-1;
        }
        else if(nums[mid]<target){
            l=mid+1;
        }
        else{
            l=mid+1;
            rb=l;
        }
    }
    return rb;
    }
    int get_lb(vector<int>&nums,int target){
    int l=0;
    int r=nums.size()-1;
    int lb=-2;
    while(r<=l){
        int mid=l+((r-l)>>1);
        if(nums[mid]>target){
            r=mid-1;
            lb=r;
        }
        else if(nums[mid]<target){
            l=mid+1;
        }
        else{
            l=mid+1;
        }
    }
    return lb;
    }
};
  1. 循环条件错误：在 get_rb 和 get_lb 函数中，循环条件 while(r <= l) 应该是 while(l <= r)。这是因为需要在 l 小于或等于 r 时继续搜索。
  2. 边界更新逻辑：在 get_lb 函数中，当 nums[mid] > target 时，您应该直接将 r 设置为 mid - 1，而不是在额外的 lb = r 之后。同样，在 get_rb 函数中，当 nums[mid] < target 时，您应该将 l 设置为 mid + 1 而不是在之后的 rb = l。
  3. 返回值处理：在 searchRange 函数中，当找到有效的下界和上界时，您应该返回 {lb, rb} 而不是 {lb + 1, rb - 1}。根据您的辅助函数定义，lb 和 rb 已经是目标值的正确边界。
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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        int lb = get_lb(nums, target);
        int rb = get_rb(nums, target);
        if (lb == -2 || rb == -2) return {-1, -1};
        if (rb - lb >= 0) return {lb, rb};
        return {-1, -1};
    }

private:
    int get_rb(vector<int>& nums, int target) {
        int l = 0;
        int r = nums.size() - 1;
        int rb = -2;
        while (l <= r) {
            int mid = l + ((r - l) >> 1);
            if (nums[mid] > target) {
                r = mid - 1;
            } else if (nums[mid] < target) {
                l = mid + 1;
            } else {
                rb = mid;
                l = mid + 1;
            }
        }
        return rb;
    }

    int get_lb(vector<int>& nums, int target) {
        int l = 0;
        int r = nums.size() - 1;
        int lb = -2;
        while (l <= r) {
            int mid = l + ((r - l) >> 1);
            if (nums[mid] > target) {
                r = mid - 1;
            } else if (nums[mid] < target) {
                l = mid + 1;
            } else {
                lb = mid;
                r = mid - 1;
            }
        }
        return lb;
    }
};

总结

二分法主要有两种左闭右闭和左闭右开，这两周模式分别对应了l<=r和l<r的边界条件，以及分别对应了mid位置不同的取值方法，mid不能取越界的部分，左闭右闭就必须取mid+1,mid-1,左闭右开就只能取mid+1和mid,来分别做二分之后新的边界。

赏