python_summary.md

Python算法总结

一些注意

初始化矩阵

下面代码生成一个所有行完全相同的矩阵M，而M[0][0]的修改会导致第一列所有元素都被修改。

M = [[0] * 5] * 5

正确的初始化方式如下

M = [[0] * 5 for _ in range(5)]
M = [[0 for _ in range(5)] for _ in range(5)]

进制与位运算

位运算

异或

规律

• 基本规律: a^a = 0 ;0^a = a
• 交换律 a^b=b^a; a^b^a = a^a^b = b

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

    def singleNumber(self, nums: List[int]) -> int:
        """
        题目的关键是其余每个元素均出现两次
        异或运算: a^a = 0 ;0^a = a
        异或运算 满足交换律 a^b^a = a^a^b = b
        """
        reduct = 0
        for i in nums:
            reduct ^= i
        return reduct
   

用整数编码的集合

经典问题: 平均分三份

假设有 n 个整数 X0 ,…, Xn-1 ，现要把这些数平均分配到 3 个集合中，且每个集合中的整数和相同。

穷举方式时间复杂度为 O(2 2n ) 的贪婪算法

基础数据结构

字符串(字典树)

线性表

字符数组、静态数组、动态数组、链表

链表

1. 链表操作时注意判空。
2. 链表有指针，返回元素指针时，不一定是返回头节点的指针。

哈希/Map

树

二叉树、二叉查找树、二叉平衡树、哈夫曼树、红黑树、B树

堆

优先队列

在 Python 语言中，堆排列是用 heapq 模块实现的。这个模块提供了把数组转化成堆的方法，即 heapify(table)。

图

基本算法

排序与查找

枚举

遍历(暴力枚举)、排列、组合，有时要用二分法

指针

滑动窗口、双指针、前缀和

递归与迭代

回溯

分治(归并和二分)

归并和二分

二分查找

二分查找的前提是已经排好序。

Python 标准模块 bisect 中提供了二分查找算法，所以在某些情况下，我们不需要自己来实现。但需注意 bisect 模块查找从下标1开始。

搜索

深度搜索、广度搜索

贪心

动态规划

系统设计

一些心得

首先，要学会有组织、成体系地思考。为此，一定不要在尚未清楚理解题目的所有细节之前，仅凭一时冲动就开始编写程序。如果你在拿起键盘之前先冷静地审视一下，就不会轻易犯下某些错误，否则，很容易写出一个根本无法实现的方案。

日常练习

1. 线下练习不要着急看题解，否则会过分依赖题解。先自己做，实在无法完成再看题解。
2. 正确的审题是成功的一半，明确输入输出。
3. 如果有可能，最好在竞赛时把读题和解题的时间分开。多给自己一点时间。在程序代码的注释中添加问题描述，如果有可能，再加上题目的URL，并明确指出算法的时间复杂度。在一段时间后，当你回头再看自己编写的程序时，一定会欣赏这种做法。尤其，这能让程序代码保持逻辑严密、结构紧凑。

好好读题

考试时部分用例错误不会具体报哪个用例错误，也不会给控制台中的输入提供正确答案。需要自己设计用例并确认用例输出。 这就要求自己能根据输入输出关系做等价类划分，考虑非法和异常的场景。

• 什么样的时间复杂度可以被接受？ 注意题目中提出的限制，在实现你的算法之前做好复杂度分析。

• 输入数据是否有条件、有保证？

  不要从题目的例子中猜测条件。不要做任何猜测。如果题目中没有说明“图是非空的”，那么某些测试用例中就有可能包含空的图。如果题目中没有说“字符串不包含空格”，那么就可能有一个测试用例包含这样的字符串。

• 使用什么样的数据类型？ 整数还是浮点数？数字是否有可能是负值？如果你使用 Java 或C++ 写程序，注意要确定中间变量的上限值，选择使用 16 位、32位或 64 位的整数。

解答题目

• 画纲要图。找到待解决问题与已知问题之间的关联，如何利用实例的特殊性？
• 如果可能，利用类库
• 掌握经典的二分查找算法、排序和字典等类库。
• 使用题目中提到的名词命名变量，名词越简短、表述越清晰越好。
• 初始化变量