C/C++教程

leecode做题打卡:算法

本文主要是介绍leecode做题打卡:算法,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

LeeCode做题打卡

  • 题集:算法
    • 第 1 天 二分查找
      • 第1天 第一题 :[704. 二分查找](https://leetcode-cn.com/problems/binary-search/)
      • 第1天 第二题 :[278. 第一个错误的版本](https://leetcode-cn.com/problems/first-bad-version/)
      • 第1天 第三题 :[35. 搜索插入位置](https://leetcode-cn.com/problems/search-insert-position/)

题集:算法

这是LeeCode上边的题集,计划是维持14天,每天的主要内容都是不一样的,我会把每天所作的工作,写在我的CSDN中,用来记录我每天的所思所想,为了自己的未来加油!MaHone。

第 1 天 二分查找

今天的题目:二分查找,主要有以下三个题目:

  1. 704. 二分查找.
  2. 278. 第一个错误的版本.
  3. 35. 搜索插入位置.

第1天 第一题 :704. 二分查找

题目

// 细则
给定一个 n 个元素有序的(升序)整型数组 nums 和一个目标值target,
写一个函数搜索 nums 中的 target,
如果目标值存在返回下标,否则返回 -1。

示例

// 示例 1:
输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4

// 示例 2:
输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1

提示

  1. 你可以假设 nums 中的所有元素是不重复的。
  2. n 将在 [1, 10000]之间。
  3. nums 的每个元素都将在 [-9999, 9999]之间。

写法:这是一个典型的二分查找,用一个左指针、右指针,然后在不断刷新中间指针,进行比较、判断,最后进行输出

代码

class Solution {
    public int search(int[] nums, int target) {
        
        int left = 0;
        int right = nums.length - 1;//注意
        //右指针开始的位置是最后一个元素,index为num.length - 1

        while(left <= right){//循环条件
            int mid = (right + left) / 2;//不断刷新中间指针
            if(nums[mid] == target){
                return mid; //找到target,输出index
            }else if(nums[mid] < target){
                left = mid + 1;//小于,left右移
            }else if(nums[mid] > target){
                right = mid - 1;//大于,right左移
            }
        }
        return -1;

    }
}

第1天 第二题 :278. 第一个错误的版本

题目

// 细则
你是产品经理,目前正在带领一个团队开发新的产品。
不幸的是,你的产品的最新版本没有通过质量检测。
由于每个版本都是基于之前的版本开发的,所以错误的版本之后的所有版本都是错的。

假设你有 n 个版本 [1, 2, ..., n],
你想找出导致之后所有版本出错的第一个错误的版本。

你可以通过调用 bool isBadVersion(version) 接口
来判断版本号 version 是否在单元测试中出错。
实现一个函数来查找第一个错误的版本。
你应该尽量减少对调用 API 的次数。

示例

// 示例 1:
输入:n = 5, bad = 4
输出:4
解释:
调用 isBadVersion(3) -> false 
调用 isBadVersion(5) -> true 
调用 isBadVersion(4) -> true
所以,4 是第一个错误的版本。

// 示例 2:
输入:n = 1, bad = 1
输出:1

提示

  1. 1 <= bad <= n <= 231 - 1

写法:根据提示,n 的范围特别大,所以不能采用普通的遍历循环查找,采用二分法,如果是 true,右指针更新,说明左边有错误版本;如果是 false,左指针更新,可能不是最后一个错误版本。

代码

/* The isBadVersion API is defined in the parent class VersionControl.
      boolean isBadVersion(int version); */

public class Solution extends VersionControl {
    public int firstBadVersion(int n) {
        int left = 1, right = n;
        while(left < right){
            int mid = left + (right - left) / 2; 

            if(isBadVersion(mid)){
                right = mid; //正确更新右指针
            }else {
                left = mid + 1;//错误更新左指针
            }
        }
        return left;//返回最后一个错误版本
    }
}

第1天 第三题 :35. 搜索插入位置

题目

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

请必须使用时间复杂度为 O(log n) 的算法。

示例

// 示例 1:
输入: nums = [1,3,5,6], target = 5
输出: 2

// 示例 2:
输入: nums = [1,3,5,6], target = 2
输出: 1

// 示例 3:
输入: nums = [1,3,5,6], target = 0
输出: 0

// 示例 4:
输入: nums = [1], target = 0
输出: 0

提示

  1. 1 <= nums.length <= 104
  2. -104 <= nums[i] <= 104
  3. nums 为无重复元素升序排列数组
  4. -104 <= target <= 104

写法:根据提示,请必须使用时间复杂度为 O(log n) 的算法。采用二分法,当target小于nums[mid]时,更新ans和右指针;当target大于num[mid]时候,更新左指针;最后输出ans。

代码

class Solution {
    public int searchInsert(int[] nums, int target) {
        int n = nums.length;
        int left = 0,right = n - 1, ans = n;
        while(left <= right){
            int mid = ((right - left)>>1) +left;
            if(target <= nums[mid]){
                ans = mid;
                right = mid - 1;
            }else{
                left = mid + 1;
            }
        }
        return ans;
    }


}
这篇关于leecode做题打卡:算法的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!