代码随想录二刷第一天(Python)

704. 二分查找

题目链接：https://leetcode.cn/problems/binary-search/

题目描述：给定一个 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

题解：

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left,right = 0,len(nums) -1  #定义左闭右闭的区间

        while left <= right:
            middle = left + (right - left)//2
            if nums[middle] > target:
                right = middle - 1
            elif nums[middle] < target:
                left = middle + 1
            else:
                return middle
        return -1
1
2
3
4
5
6
7
8
9
10
11
12
13

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left,right = 0,len(nums)  #定义左闭右开的区间
        while left < right:
            middle = left + (right - left)//2
            if nums[middle] > target:
                right = middle
            elif nums[middle] < target:
                left = middle + 1
            else:
                return middle
        return -1
1
2
3
4
5
6
7
8
9
10
11
12

总结：二刷此题还是比较简单，解答也比较快，就是注意开区间还是闭区间，两种情况都能解答，注意细节处理就行。

35. 搜索插入位置

题目链接：https://leetcode.cn/problems/search-insert-position/description/

题目描述：给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。请必须使用时间复杂度为 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 = 7
输出: 4

题解：

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        left,right = 0,len(nums) - 1 #定义左闭右闭区间
        while left <= right:
            middle = left + (right - left) // 2
            if nums[middle] > target:
                right = middle - 1
            elif nums[middle] < target:
                left = middle + 1
            else:
                return middle
        return right + 1
1
2
3
4
5
6
7
8
9
10
11
12

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        left,right = 0,len(nums) #定义左闭右开区间
        while left < right:
            middle = left + (right - left) // 2
            if nums[middle] > target:
                right = middle
            elif nums[middle] < target:
                left = middle + 1
            else:
                return middle
        return right
1
2
3
4
5
6
7
8
9
10
11
12

总结：此题和704题一样，就是最后没查到数据处理不同，其他思路都是一样。

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

题目链接：https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/description/

题目描述：给你一个按照非递减顺序排列的整数数组 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]

题解：

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        def getRightBorder(nums: List[int], target: int)->int:
            left,right = 0, len(nums) - 1
            rightBorder = -2
            while left <= right:
                middle = left + (right - left)//2
                if nums[middle] > target:
                    right = middle - 1
                else:# 寻找右边界，nums[middle] == target的时候更新left
                    left = middle + 1
                    rightBorder = left
            return rightBorder
        def getLeftBorder(nums: List[int], target: int)->int:
            left,right = 0,len(nums) - 1
            leftBorder = -2
            while left <= right:
                middle = left + (right - left)//2
                if nums[middle] >= target:
                    right = middle - 1
                    leftBorder = right
                else:#寻找左边界，nums[middle] == target的时候更新right
                    left = middle + 1
            return leftBorder

        rightBorder = getRightBorder(nums, target)
        leftBorder = getLeftBorder(nums, target)
        if leftBorder == -2 or rightBorder == -2:
            return [-1,-1] #第一种情况：target在所有数左边或在所有数右边
        elif rightBorder - leftBorder > 1: #第二种情况：target范围在数组之间，能找到
            return [leftBorder + 1, rightBorder - 1]
        else:#第三种情况：target范围在数组之间，但找不到
            return [-1,-1]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

总结：此题在解答过程中要找出三种情况，第一种情况是target 在数组范围的右边或者左边；第二种情况是target 在数组范围中，且数组中存在target；第三种情况是target 在数组范围中，且数组中不存在target。之后要考虑如何找出左边界和右边界，我采用了两个二分法，分别找出左边界和右边界，采用左闭右闭的区间.

69. x 的平方根

题目链接：https://leetcode.cn/problems/sqrtx/description/

题目描述：给你一个非负整数 x ，计算并返回 x 的 算术平方根 。由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。

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

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

题解：

class Solution:
    def mySqrt(self, x: int) -> int:
        left,right,ans = 0,x,-1
        while left <= right:
            middle = left + (right - l)//2
            if middle * middle <=x:
                ans = middle
                left = middle + 1
            else:
                right = middle - 1
        return ans
1
2
3
4
5
6
7
8
9
10
11

367. 有效的完全平方数

题目链接：https://leetcode.cn/problems/valid-perfect-square/description/

题目描述：给你一个正整数 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 不是一个整数。

题解：

class Solution:
    def isPerfectSquare(self, num: int) -> bool:
        left,right,ans = 0,num,-1
        while left <= right:
            middle = left + (right - left)//2
            if middle * middle < num:
                left = left + 1
            elif middle * middle > num:
                right = middle - 1
            else:
                return True
        return False
1
2
3
4
5
6
7
8
9
10
11
12