leetcode 算法刷题系列-第1天

admin
电脑知识
11小时前
14热度
0评论

704.二分查找

题目描述:要求编写一个函数，它接收一个按升序排列且无重复元素的整数数组 nums 和一个目标值 target 作为参数。函数需在数组中使用二分查找算法来定位目标值，若存在则返回其索引，若不存在则返回 -1。

第一种情况:左闭右闭,即[left,right]

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) left=mid+1;
            else if(nums[mid]>target) right=mid-1;
            else return mid;
        }
        return -1;
    }
};

第二种情况:左闭右开,即[left,right)

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) right=mid;
            else if(nums[mid]<target) left=mid+1;
            else return mid;
        }
        return -1;
    }
};

算法思路：二分查找

前提条件：输入数组必须为有序数组。
核心思想：通过不断缩小搜索范围来定位目标值。
时间复杂度：O(log n)。
实现关键：
1. 区间定义：首先明确搜索区间是左闭右开 [left, right) 还是左闭右闭 [left, right]。这是正确编写循环和边界条件的基础。
2. 循环比较：在循环体内，计算中间索引 mid，将 nums[mid] 与 target 进行比较。
3. 边界调整：
  - 若 nums[mid] == target，直接返回 mid。
  - 若 nums[mid] < target，说明目标在右侧，调整左边界 left。
  - 若 nums[mid] > target，说明目标在左侧，调整右边界 right。
4. 终止条件：循环结束后，若未找到目标，则返回 -1。
注意事项：区间定义方式直接影响循环条件（while (left < right) 或 while (left <= right)）和边界赋值方式（left = mid + 1 或 right = mid - 1），必须始终保持一致性。

27.移除元素

题目描述:给定一个整数数组 nums 和一个目标值 val，你的任务是在该数组中原地删除所有与 val 值相同的元素。数组元素的相对顺序允许改变。请返回处理后的数组中不等于 val 的元素个数。

第一种方法:暴力法

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int size=nums.size();
        for(int i=0;i<size;i++){
            if(nums[i]==val){
                for(int j=i+1;j<size;j++){
                    nums[j-1]=nums[j];
                }
                i--;
                size--;
            }
        }
        return size;
    }
};

这个解法的时间复杂度是O(n^2),可能会过不了,但是力扣上可以过

第二种解法:双指针解法

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

这种解法的好处就是优化了一下时间复杂度,变成了O(n)

算法思路：双指针（快慢指针）

核心思想：使用两个同向移动的指针（通常起始于数组开头），以不同策略遍历数组，实现原地操作。
指针分工：
- 快指针 (fast)：进行“探索性”遍历，逐个检查每个元素是否满足条件。
- 慢指针 (slow)：指向下一个“有效数据”应该被存放的位置，代表当前已构建的新数组的末尾。
执行步骤：
1. 初始化 slow, fast 指针。
2. fast 指针遍历每一个元素。
3. 当 fast 所指元素符合要求时，执行 nums[slow] = nums[fast] 进行覆盖保存，然后同时将 slow 和 fast 后移。
4. 当 fast 所指元素不符合要求时，仅 fast 后移，slow 停留。
最终结果：slow 指针的最终位置即为新数组的长度，其左侧的所有元素即为所有保留下来的有效元素。
优势：时间复杂度 O(n)，空间复杂度 O(1)，完美符合数组元素只能覆盖的原则。

977.有序数组的平方

题目描述:给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。

这道题乍一看挺简单的,其实实际上确实也挺简单的(开个玩笑),并且这道题也有两种解法

第一种解法:暴力法

很多人看到这道题第一想法就是将这个数组的所有元素先进行平方处理,然后再进行排序操作,包括我第一眼看到这道题也是这种想法

class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        for(int i=0;i<nums.size();i++){
            nums[i]*=nums[i];
        }
        sort(nums.begin(),nums.end());
        return nums;
    }
};

第二种解法:双指针法

class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        int k=nums.size()-1;
        vector<int> result(nums.size(),0);
        for(int i=0,j=nums.size()-1;i<=j;){
            if(nums[i]*nums[i]<nums[j]*nums[j]){
                result[k--]=nums[j]*nums[j];
                j--;
            }
            else{
                result[k--]=nums[i]*nums[i];
                i++;
            }
        }
        return result;
    }
};

温馨提示:当一道题目与数组下标有关的时候,一定要搞清楚数组下标的开始和结束,不然的话容易溢出导致答案错误。

比如是从0开始,那么就是到这个数组的长度-1结束。

思路总结:因为数组是有序的,可能一个负数平方之后就成为了最大数,而且数组平方后的最大值肯定在数组的两端,不是在最左端就是在最右端,不可能是在最中间,所以这里我们就可以考虑用双指针法,用i指向初始位置,j指向终止位置,然后再用一个新的数组来保存结果,这样我们最后return这个定义的新数组。