数组-二分查找-搜索插入位置/在排序数组中查找元素的第一个和最后一个位置/x 的平方根/有效的完全平方数

news/2024/4/19 3:23:15/文章来源:https://blog.csdn.net/sueong/article/details/129065565

二分查找

35搜索插入位置

https://leetcode.cn/problems/search-insert-position/submissions/

class Solution:def searchInsert(self, nums: List[int], target: int) -> int:l = 0r = len(nums)-1# // 整数除法 int /浮点数除法while(l<=r):mid = l + (r - l)//2if nums[mid] > target:r = mid - 1elif nums[mid]< target:l = mid + 1else:return mid# 因为l>r # 跳出循环 有可能插入在数组的末端 即此时下标 l=len（nums）-1 + 1(多插入的位置)， r=l-1# 因此返回的是数组末端最后 """// 分别处理如下四种情况// 目标值在数组所有元素之前 [0,0)// 目标值等于数组中某一个元素 return middle// 目标值插入数组中的位置 [left, right) ，return right 即可// 目标值在数组所有元素之后的情况 [left, right)，因为是右开区间，所以 return right"""return r + 1

// 第一种二分法
func searchInsert(nums []int, target int) int {l, r := 0, len(nums) - 1for l <= r{m := l + (r - l)/2if nums[m] == target{return m}else if nums[m] > target{r = m - 1}else{l = m + 1}}return r + 1
}

https://programmercarl.com/0035.%E6%90%9C%E7%B4%A2%E6%8F%92%E5%85%A5%E4%BD%8D%E7%BD%AE.html#%E5%85%B6%E4%BB%96%E8%AF%AD%E8%A8%80%E7%89%88%E6%9C%AC

34在排序数组中查找元素的第一个和最后一个位置

给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target，返回 [-1, -1]。

你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

示例 1：

输入：nums = [5,7,7,8,8,10], target = 8 输出：[3,4]
示例 2：

输入：nums = [5,7,7,8,8,10], target = 6 输出：[-1,-1]
示例 3：

输入：nums = [], target = 0 输出：[-1,-1]

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

 
class Solution(object):def find_left(self,nums,target):l=0r=len(nums)-1while l<=r:mid=(l+r)//2# 如果找到了 继续找左边界 找第一个>=target 的值if nums[mid]==target:r=mid-1elif nums[mid]>target:r=mid-1else:l=mid+1# 因为l>r 此时跳出循环 r条件是mid-1 有可能是第一种nums[mid]==target的情况 # 所以看看l是不是符合(因为此时l=r+1 所以l有可能是mid )  if nums[l]== target:return l;else:return -1;def find_right(self,nums,target):l=0r=len(nums)-1while l<=r:mid=(l+r)//2# 如果找到了 继续找右边界 找最后一个<=target 的值if nums[mid]==target:l=mid+1elif nums[mid]>target:r=mid-1else:l=mid+1# 因为l>r 此时跳出循环 l条件是mid+1 有可能是第一种nums[mid]==target的情况 # 所以看看r是不是符合(因为此时l-1=r 所以r有可能是mid )  if nums[r]== target:return r;else:return -1;def searchRange(self, nums, target):""":type nums: List[int]:type target: int:rtype: List[int]"""# 数组递增 最后一个数比target小 或者第一个数比targe大if len(nums)==0 or nums[0]>target or nums[-1]<target:return[-1,-1]ll=self.find_left(nums,target)rr=self.find_right(nums,target)return[ll,rr]


func find_left(nums []int, target int) int {l := 0r := len(nums) - 1for l <= r{mid := l + (r - l)/2 if nums[mid] > target{r =  mid -  1}else if nums[mid] ==  target{r = mid  - 1}else{l = mid + 1}}if nums[l] == target{return l}else{return -1}}
func find_right(nums []int, target int) int {l := 0r := len(nums) - 1for l <= r{mid := l + (r - l)/2 if nums[mid] > target{r =  mid -  1}else if nums[mid] == target{l = mid + 1}else{l = mid + 1}}if nums[r] == target{return r}else{return -1}}
func searchRange(nums []int, target int) []int {if len(nums) == 0||nums[0]>target||nums[len(nums)-1]<target{return []int{-1, -1}}else{ll:=find_left(nums,target)rr:=find_right(nums,target)return[]int{ll,rr}}
}

69.x 的平方根

给你一个非负整数 x ，计算并返回 x 的算术平方根。

由于返回类型是整数，结果只保留整数部分，小数部分将被舍去。

注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。

示例 1：

输入：x = 4 输出：2
示例 2：

输入：x = 8 输出：2 解释：8 的算术平方根是 2.82842…, 由于返回类型是整数，小数部分将被舍去。

来源：力扣（LeetCode）链接：https://leetcode.cn/problems/sqrtx
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路：
在这里插入图片描述

class Solution:def mySqrt(self, x: int) -> int:l = 0r = xres = 0while l<=r:mid = l+(r-l)//2# 因为是取整，所以mid*mid不会更好等于x 所以会在这个过程中一直更新res,# 小于的情况，就是往右边找mid，扩大mid# =的情况，res就刚好是mid，找到了x的平方根if mid*mid <= x:res = midl = mid + 1else:r = mid -1return res

func mySqrt(x int) int {l:=0r:=xres:=0for l <= r{mid := l + (r - l)/2if mid * mid <= x{res = midl = mid + 1}else{r = mid - 1}}return res}

367.有效的完全平方数

给你一个正整数 num 。如果 num 是一个完全平方数，则返回 true ，否则返回 false 。

完全平方数是一个可以写成某个整数的平方的整数。换句话说，它可以写成某个整数和自身的乘积。

不能使用任何内置的库函数，如 sqrt 。

示例 1：

输入：num = 16 输出：true 解释：返回 true ，因为 4 * 4 = 16 且 4 是一个整数。
示例 2：

输入：num = 14 输出：false 解释：返回 false ，因为 3.742 * 3.742 = 14 但 3.742
不是一个整数。

来源：力扣（LeetCode）链接：https://leetcode.cn/problems/valid-perfect-square
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

class Solution:def isPerfectSquare(self, num: int) -> bool:l = 0r = numres = 0while l<=r:mid = l+(r-l)//2# 因为是取整，所以mid*mid不会更好等于x 所以会在这个过程中一直更新res,# 小于的情况，就是往右边找mid，扩大mid# =的情况，res就刚好是mid，找到了x的平方根if mid*mid <= num:res = midl = mid + 1else:r = mid -1# 判断是不是整数相乘if res * res == num:return Trueelse:return False

func isPerfectSquare(num int) bool {l:=0r:=numres:=0for l <= r{mid := l + (r - l)/2if mid * mid <= num{res = midl = mid + 1}else{r = mid - 1}}if res * res == num{return true}else{return false}
}