立志重刷代码随想录60天冲冲冲!!——第一天

704. 二分查找

第一天,二分查找比较简单。需要注意开闭区间和取值范围

我全以全闭区间为例

全闭需要left <= right,且缩小范围时不包括mid

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0;
        int 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;
    }
};

35.搜索插入位置

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

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

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

今日时间太晚了,代码暂时先不写了。大致上思路就是:找到第一个target和最后一个target

第一个target:还是简单二分,然后target == nums[mid]时,再次添加right = mid - 1

最后一个target:简单二分,然后target == nums[mid]时,再次添加left = mid + 1

具体代码希望周末有时间补上!

27. 移除元素

左指针,新数组更新的位置

右指针,新数组的元素

右指针!=val的时候,左指针才会+1

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

        while(right < len_nums){
            nums[left] = nums[right];
            if(nums[right] != val){
                left++;
            }
            right++;
        }
        return left;
    }
};

代码随想录更新 文章被收录于专栏

冲冲冲冲冲冲!

全部评论

相关推荐

吴offer选手:学到了,下次面试也放张纸在电脑上,不然老是忘记要说哪几个点
点赞 评论 收藏
分享
05-12 11:09
已编辑
门头沟学院 后端
SmileDog12138:没必要放这么多专业技能的描述。这些应该是默认已会的,写这么多行感觉在凑内容。项目这块感觉再包装包装吧,换个名字,虽然大家的项目基本都是网上套壳的,但是你这也太明显了。放一个业务项目,再放一个技术项目。技术项目,例如中间件的一些扩展和尝试。
点赞 评论 收藏
分享
评论
1
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务