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

● 今日学习的文章链接和视频链接

● 自己看到题目的第一想法

1. 704二分法：

方法一：
整个数组是 左闭右闭区间 [ ]

1. left指针指向数组开始下标， right 指针指向数组最后下表nums.size()-1, mid为 (left+right) /2
2. 循环条件 left<=right
3. nums[mid] nums[mid] > target 左移right right = mid-1
   nums[mid] = target 返回 mid
   找不到 返回 -1

方法二：
整个数组是 左闭右开区间 [ )

1. left指针指向数组开始下标， right 指针指向数组最后下表nums.size(), mid为 (left+right) /2
2. 循环条件 left< right
3. nums[mid] nums[mid] > target 左移right right = mid
   nums[mid] = target 返回 mid
   找不到 返回 -1

2.注意：区间边界问题

整个数组是 左闭右闭区间 [ ]
整个数组是 左闭右开区间 [ )

3.具体代码

方法一：

class Solution {
public:
    int search(vector<int>& nums, int target) {
    int left = 0, right = nums.size()-1;
        while(left<=right){
            
                int mid = (left+right)/2;
                if(nums[mid] == target){
                    return mid;
                }else if(nums[mid] >target){
                    right = mid-1; 
                }else if(nums[mid]< target){
                    left = mid+1;
                }else{
                    return mid;
                }
                
           
        }return -1; 

    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

方法二：

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left =0;
        int right = nums.size();

        while(left< right){
            int mid = (left +right)/2;
            if(nums[mid] < target){
                left =mid+1;
            }else if(nums[mid]  > target){
                right = mid;
            }else{
                return mid ;
            }
        }

        return -1;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

2. 27移除元素

思路

方法一：双指针

1. 定义下标 快指针fast ， 慢指针slow
2. 循环条件 fast <= nums.size()-1
3. nums[fast] == val 则fast++;
   nums[fast] != val 则 nums[slow] = nums[fast], slow++, fast++;
   slow最终指向没有val值 数组最后一个元素的下标。

方法二：
4. 定义left =0 right =nums.size()-1
5. 循环条件 left<=right
6. 左边找到nums[left]==val 的下标
右边找到nums[right] !=val 的下标
交换 nums[left] =nums[right] left++; right–;
结果： return left;

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int left =0;
        int right = nums.size()-1;
        while(left<=right){
            while(left<=right && nums[left] != val){
                left++;
            }
            while(left<=right && nums[right] == val){
                right--;
            }
            if(left<=right){
                nums[left] = nums[right];
                left++;
                right--;
            }

        }
        return left;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

注意

slow指：更新后 新数组下标
fast 指：寻找新数组的元素

代码

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int slow =0;
        int fast =0;
        for(fast = 0; fast <nums.size(); fast++){
            if(nums[fast]  != val){
                nums[slow] = nums[fast];
                slow++;
            }
        }

        return slow;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

● 看完代码随想录之后的想法

● 自己实现过程中遇到哪些困难

● 今日收获，记录一下自己的学习时长