python 二分查找 :bisect模块

bisect模块的源码:

"""Bisection algorithms."""

def insort_right(a, x, lo=0, hi=None):

    if lo < 0:
        raise ValueError('lo must be non-negative')
    if hi is None:
        hi = len(a)
    while lo < hi:
        mid = (lo+hi)//2
        if x < a[mid]: hi = mid
        else: lo = mid+1
    a.insert(lo, x)

insort = insort_right   # backward compatibility

def bisect_right(a, x, lo=0, hi=None):

    if lo < 0:
        raise ValueError('lo must be non-negative')
    if hi is None:
        hi = len(a)
    while lo < hi:
        mid = (lo+hi)//2
        if x < a[mid]: hi = mid
        else: lo = mid+1
    return lo

bisect = bisect_right   # backward compatibility

def insort_left(a, x, lo=0, hi=None):

    if lo < 0:
        raise ValueError('lo must be non-negative')
    if hi is None:
        hi = len(a)
    while lo < hi:
        mid = (lo+hi)//2
        if a[mid] < x: lo = mid+1
        else: hi = mid
    a.insert(lo, x)


def bisect_left(a, x, lo=0, hi=None):

    if lo < 0:
        raise ValueError('lo must be non-negative')
    if hi is None:
        hi = len(a)
    while lo < hi:
        mid = (lo+hi)//2
        if a[mid] < x: lo = mid+1
        else: hi = mid
    return lo

# Overwrite above definitions with a fast C implementation
try:
    from _bisect import *
except ImportError:
    pass

方法介绍

bisect模块采用经典的二分算法查找元素。模块提供下面几个方法:

bisect.bisect_left(a, x, lo=0, hi=len(a)):返回待插入值应该放置的位置下标,如果 a 中有和x相同的元素,就在返回该元素左边的下标,即在左边插入

定位x在序列a中的插入点,并保持原来的有序状态不变。参数lo和hi用于指定查找区间。如果x已经存在于a中,那么插入点在已存在元素的左边。函数的返回值是列表的整数下标。

bisect.bisect_right(a, x, lo=0, hi=len(a))

和上面的区别是插入点在右边。函数的返回值依然是一个列表下标整数。

bisect.bisect(a, x, lo=0, hi=len(a))

等同于bisect_right()。

注意,前面这三个方法都是获取插入位置,也就是列表的某个下标的,并不实际插入。但下面三个方法实际插入元素,没有返回值。

bisect.insort_left(a, x, lo=0, hi=len(a))

将x插入有序序列a内,并保持有序状态。相当于a.insert(bisect.bisect_left(a, x, lo, hi), x)。碰到相同的元素则插入到元素的左边。这个操作通常是 O(log n) 的时间复杂度。

bisect.insort_right(a, x, lo=0, hi=len(a))

同上,只不过碰到相同的元素则插入到元素的右边。

bisect.insort(a, x, lo=0, hi=len(a))

等同于insort_right()。

单调栈

单调栈

单调栈实际上就是栈,只是限制要比普通的栈更严格而已了。要求是每次入栈的元素必须要有序(如果新元素入栈不符合要求,则将之前的元素出栈,直到符合要求再入栈),使之形成单调递增/单调递减的一个栈。

  • 单调递增栈:只有比栈顶小的才能入栈,否则就把栈顶出栈后,再入栈。出栈时可能会有一些计算。适用于求解第一个大于该位置元素的数。
  • 单调递减栈:与单调递增栈相反。适用于求解第一个小于该位置元素的数。

如何判断

单调递增/递减栈是根据出栈后的顺序来决定的。例如,栈内顺序[1, 2, 6],出栈后顺序[6, 2, 1],这就是单调递减栈。

适用场景

单调栈一般用于解决 第一个大于 xxx 或者 第一个小于 xxx 这种题目。

int[] ans = new int[T.Length];
Stack<int> stack = new Stack<int>();

for(int i = 0; i < T.Length; i++) {
    while(stack.Count > 0 && T[i] > T[stack.Peek()]) {
        int curI = stack.Pop();
        ans[curI] = i - curI;
    }
    stack.Push(i);
}

python3中的heapq 堆

heapq实现了一个适合与Python的列表一起使用的最小堆排序算法。

满二叉树

树中除了叶子节点,每个节点都有两个子节点

完全二叉树

在满足满二叉树的性质后,最后一层的叶子节点均需在最左边

堆是一种数据结构,它是一颗完全二叉树。最小堆则是在堆的基础增加了新的规则,它的根结点的值是最小的,而且它的任意结点的父结点的值都小于或者等于其左右结点的值。因为二进制堆可以使用有组织的列表或数组来表示,所以元素N的子元素位于位置2 * N + 1和2 * N + 2。这种布局使重新安排堆成为可能,因此在添加或删除项时不需要重新分配那么多内存
区分堆(heap)与栈(stack):堆与二叉树有关,像一堆金字塔型泥沙;而栈像一个直立垃圾桶,一列下来。

最大堆

最大堆确保父堆大于或等于它的两个子堆。

最小堆

建堆:

 heapify()

最小堆要求父堆小于或等于其子堆。Python的heapq模块实现了一个最小堆。

要创建一个堆,可以使用list来初始化为 [] ,或者你可以通过一个函数 heapify() ,来把一个list转换成堆。

定义了以下函数:heapq.heappush(heapitem)

将 item 的值加入 heap 中,保持堆的不变性。

heapq.heappop(heap)

弹出并返回 heap 的最小的元素,保持堆的不变性。如果堆为空,抛出 IndexError 。使用 heap[0] ,可以只访问最小的元素而不弹出它。

heapq.heappushpop(heapitem)

将 item 放入堆中,然后弹出并返回 heap 的最小元素。该组合操作比先调用 heappush() 再调用 heappop() 运行起来更有效率。

heapq.heapify(x)

将list x 转换成堆,原地,线性时间内。heapq.heapreplace(heapitem)

弹出并返回 heap 中最小的一项,同时推入新的 item。 堆的大小不变。 如果堆为空则引发 IndexError

这个单步骤操作比 heappop() 加 heappush() 更高效,并且在使用固定大小的堆时更为适宜。 pop/push 组合总是会从堆中返回一个元素并将其替换为 item

返回的值可能会比添加的 item 更大。 如果不希望如此,可考虑改用 heappushpop()。 它的 push/pop 组合会返回两个值中较小的一个,将较大的值留在堆中。

heapq.nlargest(niterablekey=None)

从 iterable 所定义的数据集中返回前 n 个最大元素组成的列表。 如果提供了 key 则其应指定一个单参数的函数,用于从 iterable 的每个元素中提取比较键 (例如 key=str.lower)。 等价于: sorted(iterable, key=key, reverse=True)[:n]

heapq.nsmallest(niterablekey=None)

从 iterable 所定义的数据集中返回前 n 个最小元素组成的列表。 如果提供了 key 则其应指定一个单参数的函数,用于从 iterable 的每个元素中提取比较键 (例如 key=str.lower)。 等价于: sorted(iterable, key=key)[:n]

python 全局变量 global 和 nonlocal

两个关键词都用于允许在一个局部作用域中使用外层的变量。

  • global 表示将变量声明为全局变量
  • nonlocal 表示将变量声明为外层变量(外层函数的局部变量,而且不能是全局变量)
  • python引用变量的顺序如下:
  1. 当前作用域局部变量
  2. 外层作用域变量
  3. 当前模块中的全局变量
  4. python内置变量

比如:

a=1
def test(x):
   global x
   a=x
因为a外层变量是全局变量,所以要加global


def test2():
  a=1
  def test(x)
     nonlocal x
     a=x
因为a外层变量不是是全局变量,也是一个外层的局部变量,所以要加nonlocal

python 在新建一个变量时,默认作用域为当前局部作用域。如果不声明global or nonglocal,就认为是一个局部变量。

内部函数,不修改外层变量可以访问外层变量。

a = 1
def fun():
    print(a) # 在函数内部找不到对 a 的定义,则去外层查询。输出1。
fun()

内部函数,修改同名外层变量,则python会认为是定义了一个新的局部变量,与外层变量无关了。

a = 1
def fun():
a = 2 # 声明了一个局部变量,与外面等于1的那个a没有关系了
print(a) # 输出2
fun()
print(a) # 输出1

在内部函数修改同名全局变量之前调用变量名称,则引发Unbound-LocalError

a = 1
def fun():
    print(a) # 先引用
    a = 2 # 再修改
fun()

如果我们想要强制访问外层变量 a,便可以使用 global 关键字

a = 1
def fun():
    global a # a为全局变量
    print(a) # 输出1
    a = 2 # 改变的是全局变量,因此出了这个局部作用域,仍然有效
fun()
print(a) # 输出2
注意,这个时候,不要将 global 换为 nonlocal 关键字,不然会报错:

这是因为 nonlocal 表示外层变量,但是一旦外层变量是全局变量,则只能用 global。如果将这段代码全部放到一个函数中,则可以使用 nonlocal :

def outer_fun():
a = 1
def fun():
nonlocal a # a为外层变量
print(a) # 输出1
a = 2
fun()
print(a) #输出2
outer_fun()

注意:可以发现,之前的将 global 换为 nonlocal 的报错,和这次的将 nonlocal 改为 global 的报错,错误类型是不同的。前者是 nonlocal a 这一行报错,后者是 print(a) 这一行报错。也就是说,在使用 nonlocal a 之前,必须保证外层的确已经定义过 a 了,但是在 global a 的时候,可以允许全局变量中还没有定义过a,可以留在后面定义。比如将 print(a) 之前加上对a的定义,便不会出错:

def outer_fun():
a = 1
def fun():
global a # a为全局变量,与上面等于1的 a 没有关系
a = 3 # 定义全局变量
print(a) # 输出3
a = 2
fun()
print(a) #输出1,局部变量
outer_fun()
print(a) # 输出2,全局变量

分治算法

分治法的设计思想是:将一个难以直接解决的大问题,分割成一些规模较小的相同问题,以便各个击破,分而治之。

   分治策略是:对于一个规模为n的问题,若该问题可以容易地解决(比如说规模n较小)则直接解决,否则将其分解为k个规模较小的子问题,这些子问题互相独立且与原问题形式相同,递归地解这些子问题,然后将各子问题的解合并得到原问题的解。这种算法设计策略叫做分治法。

   如果原问题可分割成k个子问题,1<k≤n,且这些子问题都可解并可利用这些子问题的解求出原问题的解,那么这种分治法就是可行的。由分治法产生的子问题往往是原问题的较小模式,这就为使用递归技术提供了方便。在这种情况下,反复应用分治手段,可以使子问题与原问题类型一致而其规模却不断缩小,最终使子问题缩小到很容易直接求出其解。这自然导致递归过程的产生。分治与递归像一对孪生兄弟,经常同时应用在算法设计之中,并由此产生许多高效算法。

 分治法所能解决的问题一般具有以下几个特征:

    1) 该问题的规模缩小到一定的程度就可以容易地解决

    2) 该问题可以分解为若干个规模较小的相同问题,即该问题具有最优子结构性质。

    3) 利用该问题分解出的子问题的解可以合并为该问题的解;

    4) 该问题所分解出的各个子问题是相互独立的,即子问题之间不包含公共的子子问题。

第一条特征是绝大多数问题都可以满足的,因为问题的计算复杂性一般是随着问题规模的增加而增加;

第二条特征是应用分治法的前提它也是大多数问题可以满足的,此特征反映了递归思想的应用;

第三条特征是关键,能否利用分治法完全取决于问题是否具有第三条特征,如果具备了第一条和第二条特征,而不具备第三条特征,则可以考虑用贪心法或动态规划法

第四条特征涉及到分治法的效率,如果各子问题是不独立的则分治法要做许多不必要的工作,重复地解公共的子问题,此时虽然可用分治法,但一般用动态规划法较好

分治法在每一层递归上都有三个步骤:

    step1 分解:将原问题分解为若干个规模较小,相互独立,与原问题形式相同的子问题;

    step2 解决:若子问题规模较小而容易被解决则直接解,否则递归地解各个子问题

    step3 合并:将各个子问题的解合并为原问题的解。

可使用分治法求解的一些经典问题
 (1)二分搜索(2)大整数乘法 (3)Strassen矩阵乘法(4)棋盘覆盖(5)合并排序(6)快速排序(7)线性时间选择
(8)最接近点对问题(9)循环赛日程表(10)汉诺塔

例如:

求最大连续和:

给出一个长度为n的序列A1,A2,A3·····An,求最大连续和。如序列(6,-1 , 5, 4,-7), 该序列中的最大和是6 +( – 1)+ 5 + 4 = 14。

思路分析:

基本思路是使用枚举法,三重嵌套循环,时间复杂度为n的三次方

我们来用分治法解决这个问题

1.划分问题:将序列分成元素个数尽可能相等的两半。

2.递归求解:分别求出位于左半和右半的最佳序列。

3.合并问题:求出起点位于左半,终点位于右半的最大连续和序列,和子问题最优解比较。

int maxsum(int l,int r){
if(l==r)return a[l];
int m=(l+r)/2;
int Max=max(maxsum(l,m),maxsum(m+1,r));//(分解)情况1:完全在左区间,或者完全在右区间

//(合并)情况2:横跨左右两个区间
int suml=a[m],t=0;
for(int i=m;i>=l;i--)
    suml=max(suml,t+=a[i]);
int sumr=a[m+1];t=0;
for(int i=m+1;i<=r;i++)
    sumr=max(sumr,t+=a[i]);

return max(Max,suml+sumr);//取两种情况中最大的

}

给你一个由数字和运算符组成的字符串 expression ,按不同优先级组合数字和运算符,计算并返回所有可能组合的结果。你可以 按任意顺序 返回答案。

输入:expression = "2-1-1"
输出:[0,2]
解释:
((2-1)-1) = 0 
(2-(1-1)) = 2

解题思路

对于一个形如 x op yop 为运算符,x 和 y 为数) 的算式而言,它的结果组合取决于 x 和 y 的结果组合数,而 x 和 y 又可以写成形如 x op y 的算式。

因此,该问题的子问题就是 x op y 中的 x 和 y以运算符分隔的左右两侧算式解

然后我们来进行 分治算法三步走

  1. 分解:按运算符分成左右两部分,分别求解
  2. 解决:实现一个递归函数,输入算式,返回算式解
  3. 合并:根据运算符合并左右两部分的解,得出最终解
class Solution:
    def diffWaysToCompute(self, input: str) -> List[int]:
        # 如果只有数字,直接返回
        if input.isdigit():
            return [int(input)]

        res = []
        for i, char in enumerate(input):
            if char in ['+', '-', '*']:
                # 1.分解:遇到运算符,计算左右两侧的结果集
                # 2.解决:diffWaysToCompute 递归函数求出子问题的解
                left = self.diffWaysToCompute(input[:i])
                right = self.diffWaysToCompute(input[i+1:])
                # 3.合并:根据运算符合并子问题的解
                for l in left:
                    for r in right:
                        if char == '+':
                            res.append(l + r)
                        elif char == '-':
                            res.append(l - r)
                        else:
                            res.append(l * r)

        return res

leetcodeday138–复制带随机指针的链表

给你一个长度为 n 的链表,每个节点包含一个额外增加的随机指针 random ,该指针可以指向链表中的任何节点或空节点。

构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成,其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点,并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 

例如,如果原链表中有 X 和 Y 两个节点,其中 X.random --> Y 。那么在复制链表中对应的两个节点 x 和 y ,同样有 x.random --> y 。

返回复制链表的头节点。

用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示:

  • val:一个表示 Node.val 的整数。
  • random_index:随机指针指向的节点索引(范围从 0 到 n-1);如果不指向任何节点,则为  null 。

你的代码  接受原链表的头节点 head 作为传入参数。

示例 1:

输入:head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
输出:[[7,null],[13,0],[11,4],[10,2],[1,0]]

示例 2:

输入:head = [[1,1],[2,1]]
输出:[[1,1],[2,1]]

示例 3:

输入:head = [[3,null],[3,0],[3,null]]
输出:[[3,null],[3,0],[3,null]]

提示:

  • 0 <= n <= 1000
  • -104 <= Node.val <= 104
  • Node.random 为 null 或指向链表中的节点。

关键:需要一个哈希表记录已经访问过的节点。如果 节点访问过,则不用入队。

# @lc app=leetcode.cn id=138 lang=python3
#
# [138] 复制带随机指针的链表
#

# @lc code=start
"""
# Definition for a Node.
class Node:
    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):
        self.val = int(x)
        self.next = next
        self.random = random
"""

from collections import deque
class Solution:
    def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':
        
        if not head:
            return head

        visited = {}

        # 将题目给定的节点添加到队列
        queue = deque([head])
        # 克隆第一个节点并存储到哈希表中
        visited[head] = Node(head.val)

        # 广度优先搜索
        while queue:
            # 取出队列的头节点
            n = queue.popleft()
            # 遍历该节点的邻居
            neighbors=[n.next,n.random] 
            i=0
            for neighbor in neighbors:
                
                if  neighbor!=None and neighbor not in visited:
                    # 如果没有被访问过,就克隆并存储在哈希表中
                    visited[neighbor] = Node(neighbor.val)
                    # 将邻居节点加入队列中
                    queue.append(neighbor)
                    # 更新当前节点的邻居列表
                if neighbor!=None and i==0:
                    visited[n].next=visited[neighbor]
                if neighbor!=None and i==1:
                    visited[n].random=visited[neighbor]
                i=i+1


        return visited[head]
# @lc code=end

leetcodeday136 –只出现一次的数字

给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。

说明:

你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗?

示例 1:

输入: [2,2,1]
输出: 1

示例 2:

输入: [4,1,2,1,2]
输出: 4
# @lc app=leetcode.cn id=136 lang=python3
#
# [136] 只出现一次的数字
#

# @lc code=start
class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        return reduce(lambda x, y: x ^ y, nums)
# @lc code=end

reduce() 函数会对参数序列中元素进行累积。

reduce(function, iterable[, initializer])

函数将一个数据集合(链表,元组等)中的所有数据进行下列操作:用传给 reduce 中的函数 function(有两个参数)先对集合中的第 1、2 个元素进行操作,得到的结果再与第三个数据用 function 函数运算,最后得到一个结果。

def add(x, y) :            # 两数相加
    return x + y
sum1 = reduce(add, [1,2,3,4,5])   # 计算列表和:1+2+3+4+5
sum2 = reduce(lambda x, y: x+y, [1,2,3,4,5])  # 使用 lambda 匿名函数
print(sum1)
print(sum2)

leetcodeday129–求根节点到叶节点数字之和

给你一个二叉树的根节点 root ,树中每个节点都存放有一个 0 到 9 之间的数字。

每条从根节点到叶节点的路径都代表一个数字:

  • 例如,从根节点到叶节点的路径 1 -> 2 -> 3 表示数字 123 。

计算从根节点到叶节点生成的 所有数字之和 。

叶节点 是指没有子节点的节点。

示例 1:

输入:root = [1,2,3]
输出:25
解释:
从根到叶子节点路径 1->2 代表数字 12
从根到叶子节点路径 1->3 代表数字 13
因此,数字总和 = 12 + 13 = 25
# [129] 求根节点到叶节点数字之和
#

# @lc code=start
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def sumNumbers(self, root: TreeNode) -> int:
        nums=[0]
        def subisBalanced(root,deep):
            if root.left!=None:
                deepl=deep*10+root.left.val
                subisBalanced(root.left,deepl)          
            if  root.right!=None:
                deepr=deep*10+root.right.val 
                subisBalanced(root.right,deepr)
            
            if  root.left==None and root.right==None:
                nums[0]=nums[0]+deep    
                return
        if root==None:
            return 0
        else:
            subisBalanced(root,root.val)
            return nums[0]
# @lc code=end

leetcodeday128–最长连续序列

给定一个未排序的整数数组 nums ,找出数字连续的最长序列(不要求序列元素在原数组中连续)的长度。

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

示例 1:

输入:nums = [100,4,200,1,3,2]
输出:4
解释:最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。

示例 2:

输入:nums = [0,3,7,2,5,8,4,6,0,1]
输出:9

提示:

  • 0 <= nums.length <= 105
  • -109 <= nums[i] <= 109
# @lc app=leetcode.cn id=128 lang=python3
#
# [128] 最长连续序列
#

# @lc code=start
class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        if nums==[]:
            return 0
        nums.sort()
        m=1
        x=1
        for i in range(len(nums)-1):
            if nums[i]==nums[i+1]:
                continue
            if nums[i]==nums[i+1]-1:
                x=x+1          
                m=max(m,x)
            else:
                x=1
        return m

# @lc code=end

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        longest_streak = 0
        num_set = set(nums)

        for num in num_set:
            if num - 1 not in num_set:
                current_num = num
                current_streak = 1

                while current_num + 1 in num_set:
                    current_num += 1
                    current_streak += 1

                longest_streak = max(longest_streak, current_streak)

        return longest_streak

leetcodeday125–验证回文串

给定一个字符串,验证它是否是回文串,只考虑字母和数字字符,可以忽略字母的大小写。

说明:本题中,我们将空字符串定义为有效的回文串。

示例 1:

输入: "A man, a plan, a canal: Panama"
输出: true
解释:"amanaplanacanalpanama" 是回文串

示例 2:

输入: "race a car"
输出: false
解释:"raceacar" 不是回文串

提示:

  • 1 <= s.length <= 2 * 105
  • 字符串 s 由 ASCII 字符组成
# @lc app=leetcode.cn id=125 lang=python3
#
# [125] 验证回文串
#

# @lc code=start
class Solution:
    def isPalindrome(self, s: str) -> bool:
        s=''.join(list(filter(str.isalnum,  s))).lower()
        
        print(s)
        i=0
        j=len(s)-1
        while i<=j:
            if s[i]==s[j]:
                i+=1
                j-=1
            else:
                return False
        return True

# @lc code=end