leetcode刷题(python)——(九)
01.04.03 练习题目（第 09 天）
1. 0704. 二分查找
1.1 题目大意
描述：给定一个升序的数组 n u m s nums nums，和一个目标值 t a r g e t target target。
要求：返回 t a r g e t target target 在数组中的位置，如果找不到，则返回 -1。
说明：
- 你可以假设 n u m s nums nums 中的所有元素是不重复的。
- n n n 将在 [ 1 , 10000 ] [1, 10000] [1,10000]之间。
- n u m s nums nums 的每个元素都将在 [ − 9999 , 9999 ] [-9999, 9999] [−9999,9999]之间。
示例：
- 示例 1：
输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4
思路
基本的二分查找算法
我的题解
class Solution(object):
def search(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
left ,right = 0,len(nums) - 1
while(left < right + 1):
mid = (left + right) / 2
if nums[mid] < target: left = mid + 1
elif nums[mid] > target: right = mid - 1
else: return mid
return -1
- 示例 2：
输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1
2. 0035. 搜索插入位置
2.1 题目大意
描述：给定一个排好序的数组 n u m s nums nums，以及一个目标值 t a r g e t target target。
要求：在数组中找到目标值，并返回下标。如果找不到，则返回目标值按顺序插入数组的位置。
说明：
- 1 ≤ n u m s . l e n g t h ≤ 1 0 4 1 \le nums.length \le 10^4 1≤nums.length≤104。
- − 1 0 4 ≤ n u m s [ i ] ≤ 1 0 4 -10^4 \le nums[i] \le 10^4 −104≤nums[i]≤104。
- n u m s nums nums 为无重复元素的升序排列数组。
- − 1 0 4 ≤ t a r g e t ≤ 1 0 4 -10^4 \le target \le 10^4 −104≤target≤104。
示例：
- 示例 1：
输入：nums = [1,3,5,6], target = 5
输出：2
思路
同样使用二分查找逼近目标位置，若目标值不存在则返回其下标
我的题解
class Solution(object):
def searchInsert(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
left,right = 0, len(nums) - 1
while(left <= right):
mid = (left + right) / 2
if nums[mid] < target: left = mid + 1
elif nums[mid] > target: right = mid - 1
else : break
if nums[mid] >= target: return mid
elif nums[mid] < target: return mid + 1
3. 0374. 猜数字大小
3.1 题目大意
描述：猜数字游戏。给定一个整数
n
n
n 和一个接口 def guess(num: int) -> int:，题目会从
1
∼
n
1 \sim n
1∼n 中随机选取一个数
x
x
x。我们只能通过调用接口来判断自己猜测的数是否正确。
要求：要求返回题目选取的数字 x x x。
说明：
def guess(num: int) -> int:返回值：- − 1 -1 −1：我选出的数字比你猜的数字小，即 p i c k < n u m pick < num pick<num；
- 1 1 1：我选出的数字比你猜的数字大 p i c k > n u m pick > num pick>num；
- 0 0 0：我选出的数字和你猜的数字一样。恭喜！你猜对了！ p i c k = = n u m pick == num pick==num。
示例：
- 示例 1：
输入：n = 10, pick = 6
输出：6
- 示例 2：
输入：n = 1, pick = 1
输出：1
思路
使用二分查找，但是需要注意的是，二分查找有时会使我们陷入死循环，所以在查找时,需要在更新边界时+1或-1，这时当跳出循环时，left == rigt而mid可能不再是所求结果
我的题解
# The guess API is already defined for you.
# @param num, your guess
# @return -1 if num is higher than the picked number
# 1 if num is lower than the picked number
# otherwise return 0
# def guess(num):
class Solution(object):
def guessNumber(self, n):
"""
:type n: int
:rtype: int
"""
left, right = 1, n
while left < right:
mid = (left + right) // 2
if guess(mid) <= 0: right = mid
else:left = mid + 1
return right
原文地址：https://blog.csdn.net/weixin_46640900/article/details/138234808
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！