「代码随想录算法训练营」第一天(补) | 数组 part1

704. 二分查找

题目链接:https://leetcode.cn/problems/binary-search/
题目难度:简单
文章讲解:https://programmercarl.com/0704.二分查找.html
视频讲解: https://www.bilibili.com/video/BV1fA4y1o715
题目状态:通过

个人思路:

就是简单的二分查找思路,判断数组中间的值是否等于目标值,不等于就更新范围。

具体代码:

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int low = 0, high = nums.size() - 1;
        return Binary(nums, low, high, target);
    }
    int Binary(vector<int> &nums, int low, int high, int target) {
        if(low > high) return -1;

        int mid = low + (high - low) / 2;
        if(nums[mid] == target) {
            return mid;
        }
        else if(nums[mid] > target) {
            return Binary(nums, low, mid - 1, target);
        }
        else {
            return Binary(nums, mid + 1, high, target);
        }
    }
};

27. 移除元素

题目链接:https://leetcode.cn/problems/remove-element/
题目难度:简单
文章讲解:https://programmercarl.com/0027.移除元素.html
视频讲解: https://www.bilibili.com/video/BV12A4y1Z7LP
题目状态:通过

个人思路:

一开始要打算直接用erase函数的,但是感觉这应该不是考察的重点,然后就使用了双指针。

  1. 当左边指针i对应的值等于要删除的元素时,将位于右边的指针j的值覆盖到左边指针,并且j++
  2. 当左边指针i对应的值不等于要删除的元素时,i++

具体代码:

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

卡哥思路我还真没想过,使用快慢指针

热门相关:许你盛世安宁   狂飙快递员   我真不是暴发户   Hello,校草大人!   罪女入宫被团宠