脚本宝典收集整理的这篇文章主要介绍了力扣——算法入门计划第一天,脚本宝典觉得挺不错的,现在分享给大家,也给大家做个参考。
目录
🍕题目一
🍔思路
🍟代码
🍕 题目二
🍔思路F1a;
🍟代码
🍕题目三
🍔思路:
🍟代码:
704. 二分查找
🍔思路
从中间开始查找,因为列表是有序的(而且是升序的),
目标值小于中间的数,就向左走(左边的数小)
目标值大于中间的数,就向右走(右边的数大)
class Solution:
def se@R_304_2413@(self, nums: List[int], target: int) -> int:
left = 0
right = len(nums)-1
while left<=right:
mid = (left+right)//2
if target == nums[mid]:
return mid
elif target<nums[mid]:
right=;mid-1
else:
left = mid+1
return -1
l = [-1,0,3,5,9,12]
s = Solution()
PRint(s.search(l,5))
278. 第一个错误的版本
🍔思路:
先一个左指针,一个右指针,区间从【1到n】 注意这个细节,决定返回什么
(1)while(l<=r): 判断左指针是否小于右指针(就是mid值是否有效)
(2)if(isBadVersion(mid)): r=mid - 1
(3)else: l=mid + 1
其他情况就是mid值小于目标值,左指针向左移动
(4)最后返回 左指针的值是因为
具体看这种特殊情况 因为当mid值小于目标值,是左指针动,所以返回左指针
# The isBadVersion API is already defined for you.
# @param version, an integer
# @return an integer
# def isBadVersion(version):
class Solution:
def FirstBadVersion(self, n):
"""
:tyPE n: int
:rtype: int
"""
l=1
r=n
while(l<=r):
mid=(l+r)//2
if(isBadVersion(mid)):
r=mid - 1
else:
l=mid + 1
return l
35. 搜索插入位置
@H_597_126@
🍔思路:
(1)while(l < r) 因为采用左闭右开区间[left,right)右开, 所以不能有=,区间不存在
(2)
if nums[mid] < target: # 中点小于目标值,在右侧,可以得到相等位置 l = mid + 1 # 左闭,所以要+1
(3)right = mid # 右开,真正右端点为mid-1
(4)return left
# 此算法结束时保证left = right,返回谁都一样
和上面的第二题算法不同哦,因为区间选取不同
第二题,只能返回左指针
class Solution:
def searchInsert(self, nums: List[int], target: int) -> int:
l = 0
r = len(nums)
while(l < r):
mid = (l+r)//2
if(nums[mid]<target):
l = mid + 1
else:
r = mid
return l
以上是脚本宝典为你收集整理的力扣——算法入门计划第一天全部内容,希望文章能够帮你解决力扣——算法入门计划第一天所遇到的问题。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。