leetcode-二分

JAY.LIN 收录于未分类

2025-03-11 约 2929 字预计阅读 6 分钟

https://bing.ee123.net/img/rand?artid=146183725

leetcode-二分

二分查找704

leetcode 75

leetcode 374

二分适用于整数且直到待查找范围

from bisect import bisect_right #导入二分库

输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4
left和right 求mid
nums[mid] < target ,小了，要大点，在右边，左指针往右
nums[mid] > target ,大了，要小点，在左边，右指针往左

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): #结束条件为left>right
            mid=(right-left)//2 +left #求出mid为中间值
            num=nums[mid]
            if(num == target):
                return mid
            elif num<target: #小于target了，num要大一点 ，在右边
                left=mid+1 #在右边，左指针要往右
            else:
                right=mid-1 #在左边，右指针要往左
        return -1 #找不到
            

输入: nums = [1,3,5,6], target = 5
输出: 2
没找到的话返回应该插入的位置,找不到返回left

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): #结束条件为left>right
            mid=(right-left)//2 +left #求出mid为中间值
            num=nums[mid]
            if(num == target):
                return mid
            elif num<target: #小于target了，num要大一点 ，在右边
                left=mid+1 #在右边，左指针要往右
            else:
                right=mid-1 #在左边，右指针要往左
        return left #找不到
            

输入: letters = ["c", "f", "j"]，target = "a"
输出: "c"
解释：letters 中字典上比 'a' 大的最小字符是 'c'。
from bisect import bisect_right #导入二分库
找不到返回待插入位置
bisect.bisect和bisect.bisect_right返回 大于x的第一个下标 (相当于C++中的upper_bound)
bisect.bisect_left返回 大于等于x的第一个下标 (相当于C++中的lower_bound)。
j = bisect.bisect_right(rides, start, hi = i - 1, key = lambda x : x[1])
1
rides：这是一个列表，已经按顺序排列。
start：这是我们要在rides中查找的元素。
hi = i - 1：这是查找的上界。具体而言，在[0, hi)这个左闭右开区间中，寻找满足rides[x][1] > start且x最小的case，返回x。如果没有找到，则返回hi。
key = lambda x : x[1]：这是用于比较的元素。默认情况下，bisect_right比较元素x的值，而这里表示比较元素x的下标等于1的元素的值（说明元素x是一个列表或元组等等），即x[1]。

from bisect import bisect_right
class Solution(object):
    def nextGreatestLetter(self, letters, target):
        """
        :type letters: List[str]
        :type target: str
        :rtype: str
        """
        return letters[bisect_right(letters,target)] if target<letters[-1] else letters[0]

或者使用next函数
next(iterator,default)
iterator表示迭代器
default表示迭代器耗尽的默认值

加个if直接是第一个大于3的，>=3就是返回>=3的
加个找不到next的默认值，就返回第一个

class Solution(object):
    def nextGreatestLetter(self, letters, target):
        """
        :type letters: List[str]
        :type target: str
        :rtype: str
        """
        # return letters[bisect(letters,target)] if target<letters[-1] else letters[0]
        return next((letter for letter in letters if letter>target),letters[0])
        

输入：grid = [[4,3,2,-1],[3,2,1,-1],[1,1,-1,-2],[-1,-1,-2,-3]]
输出：8
解释：矩阵中共有 8 个负数。

找负数个数

#!/usr/bin/python3
# _*_ coding: utf-8 _*_
#
# Copyright (C) 2024 - 2024 Cry, Inc. All Rights Reserved 
#
# @Time    : 2024/3/20 11:35
# @Author  : Cry
# @File    : 统计负数.py
# @IDE     : PyCharm
# 输入为递减的m*n数列
import bisect


class Solution(object):
    # 二分
    def countNegatives(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        res=0
        for list in grid:
            left,right=0,len(list)-1
            pos=-1
            while(left<=right):
                mid=(right-left)//2+left
                if(list[mid] < 0): #如果当前小于0，那么就要还往左边找
                    pos=mid
                    right=mid-1
                else:
                    left=mid+1 #否则往右边
            if(pos!=-1):
                res+=len(list)-1-pos+1
        return res
    #暴力破解
    def two(self,grid):
        res = 0
        for list in grid:
            for i in range(len(list)):
                if list[i] < 0:
                    res += len(list) - 1 - i + 1
                    break
        return res
print(Solution().countNegatives([[4,3,2,-1],[3,2,1,-1],[1,1,-1,-2],[-1,-1,-2,-3]]))
print(Solution().two([[4,3,2,-1],[3,2,1,-1],[1,1,-1,-2],[-1,-1,-2,-3]]))

分治和动态规划：
分治：小问题没有关联
动态规划：小问题-中问题-大问题，套环

输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]
找target在数组的第一个和最后一个位置

#!/usr/bin/python3
# _*_ coding: utf-8 _*_
#
# Copyright (C) 2024 - 2024 Cry, Inc. All Rights Reserved 
#
# @Time    : 2024/3/20 21:50
# @Author  : Cry
# @File    : 元素的第一个和最后一个位置.py
# @IDE     : PyCharm
# 找第一次和最后一次出现的位置，没有的话返回-1
class Solution(object):
    # 二分
    def searchRange(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        lens=len(nums)
        if(lens==0):
            return [-1,-1]
        firstPosition=self.findFirstPosition(nums,target)
        if firstPosition==-1:
            return [-1,-1]
        lastPosition=self.findLastPosition(nums,target)
        return [firstPosition,lastPosition]
    def findFirstPosition(self,nums,target):
        left=0
        right=len(nums)-1
        while(left<right):
            mid=(left+right) >> 1
            if(nums[mid]<target):
                left=mid+1
            elif nums[mid]==target:
                #[left,mid]
                right=mid
            else:#[left,mid-1]
                right=mid-1
        if nums[left]==target:
            return left
        else:
            return -1

    def findLastPosition(self,nums,target):
        left=0
        right=len(nums)-1
        while(left<right):
            mid=(right+left+1)>>1
            if(nums[mid]<target):
                left=mid+1
            elif nums[mid]==target:
                # [mid,right]
                left=mid
            else:
                right=mid-1
        return left
    #暴力
    def searchRange_baoli(self,nums,target):
        res=[]
        for i in range(len(nums)):
            if nums[i]==target:
                res.append(i)

        if len(res)==0:
            return [-1,-1]
        else:
            return [res[0],res[-1]]
# 优化二分
    def searchRange2(self,nums,target):
        if(len(nums)==0):
            return [-1,-1]
        left,right=0,len(nums)-1
        while(left<=right):
            mid=(left+right)//1
            if nums[mid]<target:
                left=mid+1
            elif nums[mid]>target:
                right=mid-1
            else:
                left,right=mid,mid
                while left >0 and nums[left-1]==target:
                    left-=1
                while right<len(nums)-1 and nums[right+1]==target:
                    right+=1
                return [left,right]
        return [-1,-1]
    #暴力 用index
    def search_index(self,nums,target):
        try:
            return [nums.index(target), nums.index(target)+nums.count(target)-1]
        except:
            return [-1,-1]
print(Solution().searchRange_baoli([5,7,7,8,8,10],8))
print(Solution().searchRange([5,7,7,8,8,10],8))
print(Solution().searchRange2([5,7,7,8,8,10],8))
print(Solution().searchRange2([1],1))
print(Solution().search_index([5,7,7,8,8,10],8))

寻找右区间

输入：intervals = [[1,2]]
输出：[-1]
解释：集合中只有一个区间，所以输出-1。

输入：intervals = [[3,4],[2,3],[1,2]]
输出：[-1,0,1]
解释：对于 [3,4] ，没有满足条件的“右侧”区间。
对于 [2,3] ，区间[3,4]具有最小的“右”起点;
对于 [1,2] ，区间[2,3]具有最小的“右”起点。

#!/usr/bin/python3
# _*_ coding: utf-8 _*_
#
# Copyright (C) 2024 - 2024 Cry, Inc. All Rights Reserved
#
# @Time    : 2024/3/21 11:59
# @Author  : Cry
# @File    : 寻找有区间.py
# @IDE     : PyCharm
#
import bisect


class Solution:
    def findRightInterval(self,intervals):
        for i,interval in enumerate(intervals): #[[2,4],[1,3]]

            interval.append(i) # 1 [2,4,0] [1,3,1]
        intervals.sort() #[[1,3,1],[2,4,2]]
        print(intervals)

        n=len(intervals)
        ans=[-1]*n
        for _,end,id in intervals: #start end index
            i=bisect.bisect_left(intervals,[end]) #二分找end
            # 找[[1, 2, 2], [2, 3, 1], [3, 4, 0]],end为2 3 4
            # 结果为找2，找每个list第一个数：[2,3,1] :1
            # 结果为找3，找每个list第一个数：[3,4,0] :2
            # 结果为找4，找每个list第一个数：找不到，插入到最后
            print(i)
            if i<n:
                ans[id]=intervals[i][2]
        return ans
    #指针
    def findRightInterval2(self, intervals):
        n = len(intervals)
        starts, ends = list(zip(*intervals)) #*intervals用来元素解压缩并作为参数传递给zip函数
        starts = sorted(zip(starts, range(n)))
        ends = sorted(zip(ends, range(n)))

        ans, j = [-1] * n, 0
        for end, id in ends:
            while j < n and starts[j][0] < end:
                j += 1
            if j < n:
                ans[id] = starts[j][1]
        return ans
print(Solution().findRightInterval([[3,4],[2,3],[1,2]]))

基于时间的键值存储

输入：
["TimeMap", "set", "get", "get", "set", "get", "get"]
[[], ["foo", "bar", 1], ["foo", 1], ["foo", 3], ["foo", "bar2", 4], ["foo", 4], ["foo", 5]]
输出：
[null, null, "bar", "bar", null, "bar2", "bar2"]

#!/usr/bin/python3
# _*_ coding: utf-8 _*_
#
# Copyright (C) 2024 - 2024 Cry, Inc. All Rights Reserved 
#
# @Time    : 2024/3/21 12:52
# @Author  : Cry
# @File    : 基于时间的键值存储.py
# @IDE     : PyCharm
import bisect


class TimeMap(object):

    def __init__(self):
        self.data={}
    def set(self, key, value, timestamp):
        """
        :type key: str
        :type value: str
        :type timestamp: int
        :rtype: None
        """
        if key not in self.data:
            self.data[key]=[]
        self.data[key].append((timestamp,value))


    def get(self, key, timestamp):
        """
        :type key: str
        :type timestamp: int
        :rtype: str
        """
        if key in self.data:
            arr=self.data[key]
            idx = bisect.bisect_right(arr, (timestamp, chr(127)))
            return "" if idx == 0 else arr[idx - 1][1]
        return ""

commands = ["TimeMap","set","get","get","get","get","set","get","get"]
inputs = [[],["ljfvbut","tatthnvvid",3],["ljfvbut",4],["ljfvbut",5],["ljfvbut",6],["ljfvbut",7],["eimdon","pdjbnnvje",8],["eimdon",9],["eimdon",10]]

output = []
obj = None
for i in range(len(commands)):
    if commands[i] == "TimeMap":
        obj = TimeMap()
        output.append(None)
    elif commands[i] == "set":
        obj.set(*inputs[i])
        output.append(None)
    elif commands[i] == "get":
        output.append(obj.get(*inputs[i]))

print(output)


# Your TimeMap object will be instantiated and called as such:

快照数组

输入：["SnapshotArray","set","snap","set","get"]
     [[3],[0,5],[],[0,6],[0,0]]
输出：[null,null,0,null,5]

class SnapshotArray(object):

    def __init__(self, length):
        """
        :type length: int
        """
        self.data=[[(0,0)] for _ in range(length)]
        self.snap_id=0


    def set(self, index, val):
        """
        :type index: int
        :type val: int
        :rtype: None
        """
        self.data[index].append((self.snap_id,val))


    def snap(self):
        """
        :rtype: int
        """
        self.snap_id+=1
        return self.snap_id-1


    def get(self, index, snap_id):
        """
        :type index: int
        :type snap_id: int
        :rtype: int
        """
        i=bisect.bisect_left(self.data[index],(snap_id+1,))-1
        return self.data[index][i][1]



# Your SnapshotArray object will be instantiated and called as such:
# obj = SnapshotArray(length)
# obj.set(index,val)
# param_2 = obj.snap()
# param_3 = obj.get(index,snap_id)

搜索旋转数组

输入：nums = [4,5,6,7,0,1,2], target = 0
输出：4

class Solution(object):
    # 二分
    def search(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        if not nums:
            return -1
        left,right=0,len(nums)-1
        while left<=right:
            mid=(left+right)>>1
            if nums[mid]==target:
                return mid
            if nums[0]<=nums[mid]:
                if nums[0]<=target<nums[mid]:
                    right=mid-1
                else:
                    left=mid+1
            else:
                if nums[mid]<target<=nums[len(nums)-1]:
                    left=mid+1

                else:
                    right=mid-1
        return -1
    # 暴力
    def search2(self, nums, target):
        if target in nums:
            for i in nums:
                if i == target:
                    return nums.index(i)
        else:
            return -1

寻找旋转排序数组中的最小值
输入：nums = [3,4,5,1,2]
输出：1
解释：原数组为 [1,2,3,4,5] ，旋转 3 次得到输入数组。
找到最小值：min(nums)
为了提升速度：
用二分：

class Solution:
    def findMin(self, nums: List[int]) -> int:
        left, right = -1, len(nums) - 1  # 开区间 (-1, n-1)
        while left + 1 < right:  # 开区间不为空
            mid = (left + right) // 2
            if nums[mid] < nums[-1]:  # 蓝色
                right = mid
            else:  # 红色
                left = mid
        return nums[right]

# 作者：灵茶山艾府
# 链接：https://leetcode.cn/problems/find-minimum-in-rotated-sorted-array/solutions/1987499/by-endlesscheng-owgd/
# 来源：力扣（LeetCode）
# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

有重复值的找最小值:

def findMin2(nums):
    n=len(nums)
    l,r=-1,n-1
    while (l+r<r):
        m=(l+r)//2
        if(nums[m]>nums[r]):
            l=m
        elif(nums[m]<nums[r]):
            r=m
        else:
            r-=1 #相等的话右边减一
    return nums[r]
    

猜数字大小

a=4
def guess(n):
    if n>a:
   		return 1
    elif n<a:
        return -1
    else:
        return 0
def guessNumber(n):
    left,right=1,n
    while(left<right):
        mid=(right-mid)//2
        g=guess(mid)
        if(g==1): #大了，左指针往mid来
            left=mid+1
        elif g==-1:
            right=mid
        else:
            return mid
    return left
            

第一个错误的版本
找到第一个出错的版本：
isBadVersion?() 1 2 3 4
f f t t
所以第一个错误版本为3

def firstBadVersion(n):
    left,right=0,n
    while(left<=right):
        mid=(right-left)//2+left
        if(isBadVersion(mid)):
            right=mid-1
        else:
            left=mid+1
    return left

lse:

return 0

def guessNumber(n):

left,right=1,n

while(left<right):

mid=(right-mid)//2

g=guess(mid)

if(g 1): #大了，左指针往mid来

left=mid+1

elif g -1:

right=mid

else:

return mid

return left


> 第一个错误的版本
>
> 找到第一个出错的版本：
>
> isBadVersion?()   1 2 3 4
>
> 			       f f  t  t
>
> 所以第一个错误版本为3
>
> 

```python
def firstBadVersion(n):
    left,right=0,n
    while(left<=right):
        mid=(right-left)//2+left
        if(isBadVersion(mid)):
            right=mid-1
        else:
            left=mid+1
    return left

目录

leetcode-二分

leetcode-二分

二分查找704

二分适用于整数 且直到待查找范围

二分适用于整数且直到待查找范围