【读书笔记】高效算法128例

砂糖桑
Sep 7, 2022
Last edited: 2022-9-7
type
Post
status
Published
date
Sep 7, 2022
slug
alg-128
summary
阅读《高效算法：竞赛、应试与提高必修128例》做的笔记。（阅读中）
tags
读书笔记
category
Python
icon
password
Property
Sep 7, 2022 10:39 AM
第一章 引言输入输出重定向标准输入高效地输入输出的方式复杂度基本数据结构列表字典堆算法排序查找

第一章 引言

编程竞赛主要使用的语言是C++和Java，Python近年来也正不断被支持。为了解决因编程语言不同而导致的程序执行时间的差异问题，OJ对使用不同语言的解答方案给出了不同的时间限制。
大致上，C++比Java快2倍时间，比Python快4倍时间。
由于Python的可读性和易用性，本书使用Python 3来描述算法。下面列举一些常用的Python语言细节。

输入输出

重定向标准输入

一般的练习题都会给出一组输入，这些输入往往是存储在文件中的，所以需要重定向标准输入。在本地运行测试用例的时候我们也可以将输入放在文件中，不用在命令行中一个一个地输入。
Linux或Mac OS中重定向的方式为：python a.py < test.in > test.out。如果想要将输出存储在test.out的同时打印在终端上，那么应该使用tee命令：python a.py test.in | tee test.out。
Windows中，由于cmd没有tee命令，powershell的标准输入重定向不是<，所以采用折中的方式，在powershell中执行命令：cmd /c 'python a.py < test.in' | tee test.out：
notion image

高效地输入

  • input()函数将输入以字符串的形式按行读取，不会返回行尾的字符串。
  • sys模块中有一个类似的方法sys.stdin.readline()，也是以字符串的形式按行读取，但是不会删除行尾的换行符。
经验表明，后者的速度是前者的4倍，熟练使用readline()可以加快程序的输入效率。
输入的结果经常配合字符串的split方法和map函数就行拆分和类型转换。如在一行中输入一组整数，以空格间隔，要获取到这一组整数并存储在列表中：
 import sys
 numbers = list(map(int, sys.stdin.readline().split()))
 print(numbers)
split方法默认以空格作为分隔符。通常的输入每行都是以空格分隔，所以使用默认的即可。
notion image
下面是一个比较完整的例子。
问题：读取三个矩阵 A、B、C，并测试是否 AB = C。
输入：第一行输入一个整数，表示三个矩阵的维数；后面3*n行，每n行表示一个矩阵，每行有n列。
输出：True或False
样例：
 2
 1 1
 1 1
 1 0
 0 1
 1 1
 1 1
 结果为True
使用numpy进行矩阵乘法和矩阵相当的判断，代码如下：
 from sys import stdin
 import numpy as np
 
 def read_int():
     return int(stdin.readline())
 
 def read_array(typ):
     return list(map(typ, stdin.readline().split()))
 
 def read_matrix(n):
     m = []
     for _ in range(n):
         m.append(read_array(int))
     return m
 
 if __name__ == "__main__":
     n = read_int()
     A = np.array(read_matrix(n))
     B = np.array(read_matrix(n))
     C = np.array(read_matrix(n))
     print((np.matmul(A, B) == C).all())
notion image

输出的方式

程序的输出必须使用print函数。重点关注输出字符串时字符串格式化的几种方式。
这个知识点总结自《深入理解Python特性》。
  1. “旧式”方法
      2. 使用%操作符来进行位置格式化。兼容性较高，使用比较普遍。
      # 一一对应
print("我的名字叫%s，%d岁" %('吉良吉影', 33))
# 使用别名
print("我的名字叫%(name)s，%(age)d岁" %{'age':33, 'name':'吉良吉影'})
  1. “新式”方法
      2. “新式”方法使用format。它可以从技术上替代“旧式”方法。它首先出现在Python 3上，然后又移植到Python 2上，所以兼容性也比较好。平时比较推荐使用这种方式。
      # 一一对应
print("我的名字叫{}，{}岁".format("吉良吉影",33))
# 使用别名
print("我的名字叫{name}，{age}岁".format(age=33, name="吉良吉影"))
      注意新式和旧式使用别名的区别。
  1. 字面值插值
      2. Python 3.6增加了另一种格式化字符串的方法，称为格式化字符串字面值。这种方法可以直接在字符串中嵌入Python表达式，所以比前面的方法更受欢迎。
      name = '吉良吉影'
age = 33
print(f"我的名字叫{name}，{age}岁")
      唯一的缺点就是在低版本的Python中可能使用不了。

复杂度

下面给出针对不同的输入数据长度要求在1秒钟内给出结果的算法的可接受时间复杂度。
notion image
要注意，这些数字取决于编程语言和执行程序的硬件设备，以及要执行的运算类型，如整数运算、浮点数运算或调用数学函数。所以不是绝对的。

基本数据结构

列表

python语言自带的列表类型可以实现数据结构中的栈、队列和双向队列。
  1. s.append(x)：向列表末尾插入元素x。
  1. s.pop(i)：删除并返回下标为i的元素。（C++中pop不会返回）
  1. s.insert(i, x)：向列表下标为i的位置插入元素x。
  1. s.__len__()：获取列表的长度，当结果为0时列表为空。
以上方法可以实现栈和队列的元素增删。对于给定下标i的方法，i=0为首元素，i=-1为尾元素。
可以使用类对数据结构进行进一步的封装。以队列为例：
 class MyQueue(object):
     def __init__(self, input=[]):
         self.sequence = input[:]
 
     def __len__(self):
         return self.sequence.__len__()
 
     def push(self, obj):
         self.sequence.append(obj)

     def pop(self):
         # 这里也可以使用异常
         if self.__len__()==0: return
         self.sequence.pop(0)

     def __repr__(self):
         return f'{self.sequence}'
__repr__方法的作用是定义print对象时的内容。如果不为类添加__repr__方法，那么打印对象时的输出为：
notion image
自定义了__repr__方法后，输出列表的内容：
notion image

字典

字典就是键值对的集合，它对应的数据结构是map。
Python对字典的优化是很好的，其内部的运行方式以散列表结构为基础。字典的读写时间复杂度总体上是常数。但如果键的形式是1,2,3,4…，使用列表更好。

堆

（二叉）堆是一种完全二叉树。一个完全二叉树，可以使用数组来表示：
notion image
  • 根节点的下标为1，那么结点i的两个子节点的下标就是i*2和i*2+1。
  • 根节点的下标为0，那么结点i的两个子节点的下标就是i*2+1和i*2+2。
堆分为大顶堆和小顶堆。大顶堆每个结点的值大于其子节点；小顶堆反之。要实现堆的构造，可以使用heapq模块中的heapify函数；此外，该模块还提供了插入新元素的函数heappush和抽出最小元素的函数heappop()。
heapq实现的是小顶堆。要实现大顶堆，只需要将堆中的元素取相反数，即可实现小顶堆与大顶堆的转换。
 import heapq
 
 # 小顶堆的实现
 class MySmallHeap(object):
     def __init__(self, seq=[]):
         self.__heap = seq[:]
         heapq.heapify(self.__heap)
 
     def push(self, obj):
         heapq.heappush(self.__heap, obj)
 
     def pop(self):
         # 删除堆中最小元素
         return heapq.heappop(self.__heap)
 
     def __repr__(self):
         return f'{self.__heap}'
 
 # 大顶堆的实现
 class MyLargeHeap(object):
     @staticmethod
     def rev(num):
         return -num
 
     def __init__(self, seq=[]):
         self.__heap = list(map(MyLargeHeap.rev, seq))
         heapq.heapify(self.__heap)
 
     def push(self, obj):
         heapq.heappush(self.__heap, -obj)
 
     def pop(self):
         # 删除堆中最大元素
         return -heapq.heappop(self.__heap)
 
     def __repr__(self):
         return f'{list(map(MyLargeHeap.rev, self.__heap))}'
notion image
要从原理上维持一个堆还是有点麻烦的（忘记怎么实现的了）。Python为我们提供了封装好的堆的方法，所以会方便很多。
此外，heapq还提供了很实用的获取列表中最大n个数的函数nlagest和最小n个数的函数nsmallest：
notion image

算法

排序

Python自带的排序函数的时间复杂度为O(nlogn)，性能还是可以的。
  • sorted函数：返回一个排好序的列表。
  • sort方法：直接修改原来列表的顺序。
这两种排序默认都是从小到大。如果想要从大到小排序，需要添加参数reverse=True。
notion image
和C++一样，还可以自定义排序规则（需要引入functools.cmp_to_key）。
比如现在列表的元素是代表学生信息的字典，想要按照学生的年龄从小到大排序：
from functools import cmp_to_key

def cmp(x, y):
    # 前者减去后者：从小到大
    return x['age'] - y['age']

if __name__ == '__main__':
    stds = [
        {'name': '小蓝', 'age': 18},
        {'name': '小红', 'age': 19},
        {'name': '小黄', 'age': 17},
    ]
    print(sorted(stds, key=cmp_to_key(cmp)))
notion image
不过这种自定义排序还是比较简单的，可以直接使用lambda表达式：
if __name__ == '__main__':
    stds = [
        {'name': '小蓝', 'age': 18},
        {'name': '小红', 'age': 19},
        {'name': '小黄', 'age': 17},
    ]
    print(sorted(stds, key=lambda x:x['age']))
像这种比较复杂的排序，就需要自定义cmp函数：
矩形排序_网易雷火笔试题_牛客网
矩形排序
矩形排序_网易雷火笔试题_牛客网
https://www.nowcoder.com/questionTerminal/1e53179d01574379a5f85c7666d098d9
矩形排序_网易雷火笔试题_牛客网
notion image
notion image
from functools import cmp_to_key
import sys

def cmp(x, y):
    s1, s2 = x['w']*x['h'], y['w']*y['h']
    if s1 != s2: return s1 - s2

    r1, r2 = min(x['w']/x['h'],x['h']/x['w']), min(y['w']/y['h'],y['h']/y['w'])
    if r1 != r2: return r2 - r1

    return x['w'] - y['w']

if __name__ == '__main__':
    n = int(sys.stdin.readline())
    nums = list(map(int, sys.stdin.readline().split()))

    # 数据格式化
    squares = []
    for i in range(int(nums.__len__()/2)):
        square={'w':nums[i*2], 'h':nums[i*2+1]}
        squares.append(square)

    # 排序
    squares.sort(key=cmp_to_key(cmp))
    for square in squares:
        print(f"{square['w']} {square['h']}", end=' ')
本地测试是没问题的，提交AC。
notion image

查找

最典型的查找算法就是二分查找。算法模板如下：
def binary_search(nums, target):
    low, high = 0, nums.__len__()-1
    mid = (high + low) // 2
    while nums[mid] != target:
        if nums[mid] < target: low = mid + 1
        else: high = mid - 1
        mid = (high + low) // 2
        if low > high: return -1
    return mid
实际上，Python在bisect模块中提供了用于二分查找的函数：bisect.bisect_left()。它可以找到元素最左边的插入点。（数组有序的时候可以，数组无序这个函数也可以运作但是意义不明）
notion image
 
Python
“三高”MySQL实战Unreal蓝图-day2