leecode做题打卡:算法
2021/10/22 11:10:21
本文主要是介绍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 天 二分查找
今天的题目:二分查找,主要有以下三个题目:
- 704. 二分查找.
- 278. 第一个错误的版本.
- 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
提示
:
- 你可以假设 nums 中的所有元素是不重复的。
- n 将在 [1, 10000]之间。
- 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 <= 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 <= nums.length <= 104
- -104 <= nums[i] <= 104
- nums 为无重复元素的升序排列数组
- -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做题打卡:算法的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-11-23增量更新怎么做?-icode9专业技术文章分享
- 2024-11-23压缩包加密方案有哪些?-icode9专业技术文章分享
- 2024-11-23用shell怎么写一个开机时自动同步远程仓库的代码?-icode9专业技术文章分享
- 2024-11-23webman可以同步自己的仓库吗?-icode9专业技术文章分享
- 2024-11-23在 Webman 中怎么判断是否有某命令进程正在运行?-icode9专业技术文章分享
- 2024-11-23如何重置new Swiper?-icode9专业技术文章分享
- 2024-11-23oss直传有什么好处?-icode9专业技术文章分享
- 2024-11-23如何将oss直传封装成一个组件在其他页面调用时都可以使用?-icode9专业技术文章分享
- 2024-11-23怎么使用laravel 11在代码里获取路由列表?-icode9专业技术文章分享
- 2024-11-22怎么实现ansible playbook 备份代码中命名包含时间戳功能?-icode9专业技术文章分享