栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

2021-06.21 lc marathon

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

2021-06.21 lc marathon

文章目录
        • 二分搜索总结
        • [剑指 Offer 53 - II. 0~n-1中缺失的数字](https://leetcode.cn/problems/que-shi-de-shu-zi-lcof/)
        • [剑指 Offer 53 - I. 在排序数组中查找数字 I](https://leetcode.cn/problems/zai-pai-xu-shu-zu-zhong-cha-zhao-shu-zi-lcof/)
        • [剑指 Offer 52. 两个链表的第一个公共节点](https://leetcode.cn/problems/liang-ge-lian-biao-de-di-yi-ge-gong-gong-jie-dian-lcof/)
        • [剑指 Offer 52. 两个链表的第一个公共节点](https://leetcode.cn/problems/liang-ge-lian-biao-de-di-yi-ge-gong-gong-jie-dian-lcof/)
        • [剑指 Offer 51. 数组中的逆序对](https://leetcode.cn/problems/shu-zu-zhong-de-ni-xu-dui-lcof/)

二分搜索总结
  1. 用库,好处方便快捷,坏处没法自定义

用python自带的bisect管理有序数组

bisect(arr,target) 返回target在数组中依然满足有序的插入位置,其等于bisect_right,即有相同元素时,选择返回最右边的位置

bisect_left(arr,target) 返回target在数组中依然满足有序的插入位置,有相同元素时,选择返回最左边的位置

insort(arr,num) 向数组中插入num元素,依然保持有序
有相同元素时,选择插入最右边的位置

insort_right(arr,num) 向数组中插入num元素,依然保持有序,有相同元素时,选择插入最左边的位置

from bisect import bisect,bisect_left,insort,insort_left

a = [1,4,6,8,12,15,20]
position = bisect.bisect(a,13)
print(position)

insort(a,20)
print(a)
  1. 仅代表个人模板

喜欢 左闭右闭的写法

能够二分搜索不包含重复数字的有序数组

left=0
right=n-1
while left <= right:
    mid=left+(right-left)//2
    if 满足条件:
        ...
    elif 落在左边区间:
        ... 
        left=mid-1
    else:#落在右边区间
        ...
        right=mid+1
  ==bisect_left 能够二分搜索包含重复数字的有序数组

                            并返回最左边的那个数字

继续左闭右闭

left=0
right=n-1
while left <= right:
    mid=left+(right-left)//2
    if 满足条件:
        right=mid #mid应该也在范围内
        # 检查是否会死锁,left==right 会
        if left==right:
            return target
    elif 落在左区间:
        left=mid-1
    else:
        right=mid+1
  ==bisect_right 能够二分搜索包含重复数字的有序数组

                            并返回最右边的那个数字
left=0
right=n-1
while left<=right:
    mid=left+(right-left)//2
    if 满足条件:
        left=mid  # 落在左区间
        #检查是否会死锁  left==right  会
        if left==right:
            return target
    elif 落在左区间:
        left=mid-1
    else:#落在右区间
        right=mid+1
剑指 Offer 53 - II. 0~n-1中缺失的数字

实际上是二分搜索,搜索到最左边的不等于自己索引的数字

left=0
    right=len(nums)-1
    while left<=right:
        mid=left+(right-left)//2
        if nums[mid]!=mid:
            right=mid
            # 是否会死锁  left==right
            if left==right:
                return left
        else:# 相等时,直接搜索的数落入mid后面的空间            
            left=mid+1
    return len(nums) #没搜索到满足条件的就会跳出

剑指 Offer 53 - I. 在排序数组中查找数字 I

搜索出该数字后,左右线性找边界

class Solution:
    def search(self, nums,target):
        left=0
        right=len(nums)-1
        l=-1
        while left<=right:
            mid=left+(right-left)//2
            if nums[mid]==target:
                l=mid
                break
            elif nums[mid]0:
            if nums[l1-1]==target:
                l1=l1-1
        while l2 

剑指 Offer 52. 两个链表的第一个公共节点

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        dump_head1=ListNode(-1)
        dump_head1.next=headA
        dump_head2 = ListNode(-1)
        dump_head2.next = headB
        n1=calnum(dump_head1)
        n2=calnum(dump_head2)
       
        p=dump_head1
        q=dump_head2
        if n2>n1:
            for i in range(n2-n1):
                q=q.next
        elif n1>n2:
            for i in range(n1-n2):
                p=p.next
        while p!=q and p!=None and q!=None:
            p=p.next
            q=q.next
        return p

            
            
def calnum(head):
    p=head
    n=0
    while p!=None:
        p=p.next
        n+=1
    return n

剑指 Offer 52. 两个链表的第一个公共节点

计算每个链的长度,长的那端先走几步,保证对齐

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        dump_head1=ListNode(-1)
        dump_head1.next=headA
        dump_head2 = ListNode(-1)
        dump_head2.next = headB
        n1=calnum(dump_head1)
        n2=calnum(dump_head2)
       
        p=dump_head1
        q=dump_head2
        if n2>n1:
            for i in range(n2-n1):
                q=q.next
        elif n1>n2:
            for i in range(n1-n2):
                p=p.next
        while p!=q and p!=None and q!=None:
            p=p.next
            q=q.next
        return p

            
            
def calnum(head):
    p=head
    n=0
    while p!=None:
        p=p.next
        n+=1
    return n
剑指 Offer 51. 数组中的逆序对

从后往前,确定每个数的“逆序对”(比后面大的数目)有多少

最终结果逆序对的总数为每个数的逆序对之和

维护一个有序数组,利用二分搜索模块bisect管理

从后往前循环原数组:

    找寻该数在有序数组的位置(考虑重复,搜索左边界)得到有多少数比它小 (logn)

    将该数插入有序数组 (logn)
from bisect import bisect_left,insort
class Solution:
    def reversePairs(self, nums):
        ls=[]
        if len(nums)==1 or len(nums)==0:
            return 0
        n=0
        ls.append(nums[-1])
        for i in range(len(nums)-2,-1,-1):
            index=bisect_left(ls,nums[i]) # logn复杂度  找到在有序数组的位置,得到有多少数比它小
            n+=index
            insort(ls,nums[i])# 插入该数 logn 复杂度
        return n

转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/985603.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号