LeetCode 课程 Task04 学习打卡(2021年11月22日~11月24日)
2021/11/24 23:17:29
本文主要是介绍LeetCode 课程 Task04 学习打卡(2021年11月22日~11月24日),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
第 08 天题目
0704. 二分查找
- 标签:二分查找
- 难度:简单
题目大意
给定一个升序的数组 nums,和一个目标值 target,返回 target 在数组中的位置,如果找不到,则返回 -1。
解题思路
纯粹考察二分查找。
算法基本原理:
设定左右节点为数组两端。不断判断两个节点中心位置与目标值的大小。
- 如果中心位置与目标值相等,则返回中心位置。
- 如果中心位置小于目标值,则将左节点设置为中心位置+1,然后继续在右侧搜索。
- 如果中心位置大于目标值,则将右节点设置为中心位置-1,然后继续在左侧搜索。
代码
class Solution: def search(self, nums: List[int], target: int) -> int: left = 0 right = len(nums)-1 ans = -1 while left <= right: mid = (left+right)//2 if nums[mid] == target: ans = mid left = mid+1 return ans if nums[mid] < target: left = mid+1 else: right = mid-1 return ans
0035. 搜索插入位置
- 标签:数组、二分查找
- 难度:简单
题目大意
给定一个排好序的数组 nums,以及一个目标值 target。在数组中找到目标值,并返回下标。如果找不到,则返回目标值按顺序插入数组的位置。
解题思路
二分查找法。利用两个指针 left 和 right,分别指向数组首尾位置。每次用 left 和 right 中间位置上的元素值与目标值做比较,如果等于目标值,则返回当前位置。如果小于目标值,则更新 left 位置为 mid + 1,继续查找。如果大于目标值,则更新 right 位置为 mid - 1,继续查找。直到查找到目标值,或者 left > right 值时停止查找。然后返回 left 所在位置,即是代插入数组的位置。
代码
class Solution: def searchInsert(self, nums: List[int], target: int) -> int: n = len(nums) left = 0 right = n - 1 ans = n while left <= right: mid = left + (right - left) // 2 if nums[mid] == target: return mid elif nums[mid] < target: left = mid + 1 else: right = mid - 1 return left
0374. 猜数字大小
- 标签:二分查找
- 难度:简单
题目大意
猜数字游戏。给定一个整数 n 和一个接口 def guess(num: int) -> int:
,题目会从 1~n 中随机选取一个数 x。我们只能通过调用接口来判断自己猜测的数是否正确。要求返回题目选取的数字 x。
解题思路
利用两个指针 left、right。left 指向数字 1,right 指向数组 n。每次从中间开始调用接口猜测是否正确。
- 如果猜测的数比选中的数大,则将 right 向左移,继续从中间调用接口猜测;
- 如果猜测的数比选中的数小,则将 left 向右移,继续从中间调用的接口猜测;
- 如果猜测正确,则直接返回该数。
代码
class Solution: def guessNumber(self, n: int) -> int: left = 1 right = n while left <= right: mid = left + (right - left) // 2 ans = guess(mid) if ans == 1: left = mid + 1 elif ans == -1: right = mid - 1 else: return mid return 0
第 09 天题目
0069. x 的平方根
- 标签:数学、二分查找
- 难度:简单
题目大意
实现 int sqrt(int x)
函数。计算并返回 x 的平方根(只保留整数部分),其中 x 是非负整数。
解题思路
因为求解的是 x 开方的整数部分。所以我们可以从 0~x 的范围进行遍历,找到 k^2 <= x 的最大结果。
为了减少时间复杂度,使用二分查找的方式来搜索答案。
代码
class Solution: def mySqrt(self, x: int) -> int: left = 0 right = x ans = -1 while left <= right: mid = (left+right)//2 if mid*mid <= x: ans = mid left = mid+1 else: right = mid-1 return ans
0167. 两数之和 II - 输入有序数组
- 标签:数组、双指针、二分查找
- 难度:简单
题目大意
给定一个升序排列的整数数组:numbers
和一个目标值 target
。
要求:从数组中找出满足相加之和等于 target
的两个数,并返回两个数在数组中下的标值。
注意:数组下标从 1
开始计数。
解题思路
这道题如果暴力遍历数组,从中找到相加之和等于 target
的两个数,时间复杂度为 O(n^2)
,可以尝试一下。
class Solution: def twoSum(self, numbers: List[int], target: int) -> List[int]: size = len(numbers) for i in range(size): for j in range(i + 1, size): if numbers[i] + numbers[j] == target: return [i + 1, j + 1] return [-1, -1]
结果不出意外的超时了。所以我们要想办法减少时间复杂度。
因为数组是有序的,所以我们可以考虑使用双指针来减少时间复杂度。具体做法如下:
- 使用两个指针
left
,right
。left
指向数组第一个值最小的元素位置,right
指向数组值最大元素位置。 - 判断两个位置上的元素的和与目标值的关系。
- 如果元素和等于目标值,则返回两个元素位置。
- 如果元素和大于目标值,则让
right
左移,继续检测。 - 如果元素和小于目标值,则让
left
右移,继续检测。
- 直到
left
和right
移动到相同位置停止检测。 - 如果最终仍没找到,则返回
[-1, -1]
。
代码
class Solution: def twoSum(self, numbers: List[int], target: int) -> List[int]: left = 0 right = len(numbers) - 1 while left < right: total = numbers[left] + numbers[right] if total == target: return [left + 1, right + 1] elif total < target: left += 1 else: right -= 1 return [-1, -1]
1011. 在 D 天内送达包裹的能力
- 标签:数组、二分查找
- 难度:中等
题目大意
传送带上的包裹必须在 D 天内从一个港口运送到另一个港口。给定所有包裹的重量数组 weights,货物必须按照给定的顺序装运。
且每天船上装载的重量不会超过船的最大运载重量。求能在 D 天内将所有包裹送达的船的最低运载量。
解题思路
船最小的运载能力,最少也要等于或大于最重的那件包裹,即 max(weights)。最多的话,可以一次性将所有包裹运完,即 sum(weights)。船的运载能力介于 [max(weights), sum(weights)] 之间。
现在要做的就是从这个区间内,找到满足可以再 D 天内运送完所有包裹的最小载重量。通过二分查找的方式,找到满足要求的最小载重量。
代码
class Solution: def shipWithinDays(self, weights: List[int], D: int) -> int: left = max(weights) right = sum(weights) while left < right: mid = (left + right) >> 1 days = 1 cur = 0 for weight in weights: if cur + weight > mid: days += 1 cur = 0 cur += weight if days <= D: right = mid else: left = mid + 1 return left
第 10 天题目
0278. 第一个错误的版本
- 标签:数组、二分查找
- 难度:简单
题目大意
给你一个整数 n,代表已经发布的版本号。还有一个检测版本是否出错的接口 isBadVersion(version):
。请找出第一次出错的版本号。
解题思路
这道题直接
代码
class Solution: def firstBadVersion(self, n): left = 1 right = n while left < right: mid = (left + right) // 2 if isBadVersion(mid): right = mid else: left = mid + 1 return left
0033. 搜索旋转排序数组
- 标签:数组、二分查找
- 难度:中等
题目大意
给定一个整数数组 nums,数组中值互不相同。给定的 nums 是经过升序排列后的又进行了「旋转」操作的。
旋转操作指的是:升序排列的数组 nums 在预先未知的第 k 个位置进行了右移操作,变成了 [nums[k]], nums[k+1], ... , nums[n-1], ... , nums[0], nums[1], ... , nums[k-1]
。
现在:给定升序并进行旋转后的数组 nums 和一个整数 target。从 nums 中找到 target 所在位置,如果找到,则返回对应下标,找不到则返回 -1。
解题思路
原本为升序排列的数组 nums 经过「旋转」之后,会有两种情况,第一种就是原先的升序序列,另一种是两段升序的序列。
* * * * * *
* * * * * *
最直接的办法就是遍历一遍,找到目标值 target。但是还可以有更好的方法。考虑用二分查找来降低算法的时间复杂度。
我们将旋转后的数组看成左右两个升序部分:左半部分和右半部分。
有人会说第一种情况不是只有一个部分吗?其实我们可以把第一种情况中的整个数组看做是左半部分,然后右半部分为空数组。
然后创建两个指针 left、right,分别指向数组首尾。让后计算出两个指针中间值 mid。将 mid 与两个指针做比较,并考虑与 target 的关系。
-
如果 mid[mid] == target,说明找到了 target,直接返回下标。
-
如果 nums[mid] ≥ nums[left],则 mid 在左半部分(因为右半部分值都比 nums[left] 小)。
- 如果 nums[mid] ≥ target,并且 target ≥ nums[left],则 target 在左半部分,并且在 mid 左侧,此时应将 right 左移到 mid - 1 位置。
- 否则如果 nums[mid] ≤ target,则 target 在左半部分,并且在 mid 右侧,此时应将 left 右移到 mid + 1。
- 否则如果 nums[left] > target,则 target 在右半部分,应将 left 移动到 mid + 1 位置。
-
如果 nums[mid] < nums[left],则 mid 在右半部分(因为右半部分值都比 nums[left] 小)。
- 如果 nums[mid] < target,并且 target ≤ nums[right],则 target 在右半部分,并且在 mid 右侧,此时应将 left 右移到 mid + 1 位置。
- 否则如果 nums[mid] ≥ target,则 target 在右半部分,并且在 mid 左侧,此时应将 right 左移到 mid - 1 位置。
- 否则如果 nums[right] < target,则 target 在左半部分,应将 right 左移到 mid - 1 位置。
代码
class Solution: def search(self, nums: List[int], target: int) -> int: left = 0 right = len(nums) - 1 while left <= right: mid = left + (right - left) // 2 if nums[mid] == target: return mid if nums[mid] >= nums[left]: if nums[mid] > target and target >= nums[left]: right = mid - 1 else: left = mid + 1 else: if nums[mid] < target and target <= nums[right]: left = mid + 1 else: right = mid - 1 return -1
0153. 寻找旋转排序数组中的最小值
- 标签:数组、二分查找
- 难度:中等
题目大意
给定一个数组 nums
,nums
是有升序数组经过「旋转」得到的。但是旋转次数未知。数组中不存在重复元素。
要求:找出数组中的最小元素。
- 旋转:将数组整体右移。
解题思路
数组经过「旋转」之后,会有两种情况,第一种就是原先的升序序列,另一种是两段升序的序列。
第一种的最小值在最左边。第二种最小值在第二段升序序列的第一个元素。
* * * * * *
* * * * * *
最直接的办法就是遍历一遍,找到最小值。但是还可以有更好的方法。考虑用二分查找来降低算法的时间复杂度。
创建两个指针 left
、right
,分别指向数组首尾。让后计算出两个指针中间值 mid
。将 mid
与两个指针做比较。
- 如果
nums[mid] > nums[right]
,则最小值不可能在mid
左侧,一定在mid
右侧,则将left
移动到mid + 1
位置,继续查找右侧区间。 - 如果
nums[mid] ≤ nums[right]
,则最小值一定在mid
左侧,或者mid
位置,将right
移动到mid
位置上,继续查找左侧区间。
代码
class Solution: def findMin(self, nums: List[int]) -> int: left = 0 right = len(nums) - 1 while left < right: mid = left + (right - left) // 2 if nums[mid] > nums[right]: left = mid + 1 else: right = mid return nums[left]
这篇关于LeetCode 课程 Task04 学习打卡(2021年11月22日~11月24日)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-10-04el-table 开启定时器下,表格的选中状态会消失是什么原因-icode9专业技术文章分享
- 2024-10-03如何安装和初始化飞牛私有云 fnOS?-icode9专业技术文章分享
- 2024-10-03如何安装 App 并连接到飞牛 NAS?-icode9专业技术文章分享
- 2024-10-03如何安装飞牛 TV 并连接到影视服务器?-icode9专业技术文章分享
- 2024-10-03如何在PVE和ESXI上安装飞牛私有云 fnOS?-icode9专业技术文章分享
- 2024-10-03fnOS国产最强NAS安装系统异常情况处理-icode9专业技术文章分享
- 2024-10-03飞牛NAS如何创建存储空间?-icode9专业技术文章分享
- 2024-10-03fnOS国产最强NAS硬盘会自动休眠吗?-icode9专业技术文章分享
- 2024-10-03fnOS国产最强NAS如何安装飞牛影视和创建媒体库?-icode9专业技术文章分享
- 2024-10-03fnOS国产最强NAS如何为家人朋友开通影视账号?-icode9专业技术文章分享