首页 › Python论坛 › 如何用Python参加算法竞赛

大审 發表於 2023-1-14 17:56:00

如何用Python参加算法竞赛

<h1 id="如何用python参加算法竞赛">如何用Python参加算法竞赛</h1>
<h2 id="前言">前言</h2>
<p><strong>本文适合有一定c++基础且初步了解Python，并想开发自己第二竞赛用语言的人群阅读。</strong></p>
<p><strong>本文仅介绍Python3，更低版本Python请自行了解。</strong></p>
<p>Python的优点在于在应对代码编写简单的题目时，在无电子板子的赛场环境可以一定缩短codeing时间。但在面对代码编写要求较高、时间限制较紧的情况，并<strong>无法取代c++</strong>。因此c++仍然是打算法竞赛的第一选择。</p>
<p>Python的适用场合有如下几种：</p>
<ol>
<li>代码简单的，如一些思维题、构造题等</li>
<li>字符串处理，Python提供的字符串处理函数比c++丰富许多。</li>
<li>对拍器和数据生成器</li>
</ol>
<p>本文由Mxrush和caidd共同编写。</p>
<p><strong>caidd</strong>附：</p>
<p>注一：</p>
<p>python与其他语言不同的一点在于，同样的算法，用标准库的永远比自己写的速度快。因为标准库算法大部分是用C语言写的，python由于语言限制永远到达不了C的速度，也即标准库的速度。</p>
<p>注二：</p>
<p>python的官方中文文档比起一些别的语言已经算非常好了，如果看别人代码或者题解有不懂的函数或容器，可以直接搜官方文档的对应内容。本文对于一些内容也不会讲太细，可以直接搜官方文档看</p>
<p>注三：</p>
<p>python语言并不适合递归算法，因为其递归深度，语言自身就有限制，就算去除限制，其也会开辟大量空间。蓝桥杯也会依据语言出题，python组用递归算法的题很少很少。所以平时应多注意迭代算法的积累，以及递归算法转迭代算法的方式</p>
<h2 id="python基本数据类型">Python基本数据类型</h2>
<p>python的基本数据类型有六种，数值、字符串、列表、元组、字典、集合，常用的有int，str，bool，float，list，tuple，dict，set</p>
<h3 id="int整数">int（整数）</h3>
<p>没有长度限制，大数字乘法复杂度<span class="math inline">\(O(nlogn)\)</span>（补：因为当int达到高精度时，内部会使用FFT算法加速多项式乘法），非常方便。</p>
<h3 id="float浮点数">float（浮点数）</h3>
<p>大概注意一下精度就行，<span class="math inline">\(\)</span></p>
<h3 id="bool布尔">bool（布尔）</h3>
<p>有<code>True</code>，<code>False</code>两个值（注意大小写）</p>
<h3 id="list列表">list（列表）</h3>
<p>最常用的数据类型之一，可当成C++中数组。</p>
<p>由于python中没有C++的栈，该结构可作栈使用</p>
<pre><code class="language-python">a = list(map(int, input().split()))#将读入创建为一个整数list
len(a)#返回a的长度
a#访问a中第i个元素
a[-i]#访问a中倒数第i个元素
a#列表切片，返回
#列表切片还可以写成
a[:] # 常用于拷贝
a[::-1] # 翻转
a[::2]
a[:5]
a
a
#三维分别代码起点，终点（左闭右开），步长。可以参照下文中的range函数介绍一起理解。
a.sort()#升序排序
a.sort(reversed = True)#降序排序
</code></pre>
<p>还可以append添加元素，pop删除尾部最后一个元素（O(1)），删除中间元素（最坏O(n)），count计数（O(n)），index定位元素（O(n)），并且重载了加法（即同维数组连接）</p>
<p>加法示例</p>
<pre><code class="language-python">a =
b =
print(a + b)
#
</code></pre>
<h3 id="tuple元组">tuple（元组）</h3>
<p>和list差不多，初始化用括号</p>
<pre><code class="language-python">a = (1, 2, 3)
</code></pre>
<p>支持list的很多操作，唯独不能对一个tuple自身进行修改</p>
<p>所以 dict 因为要求 key 值不可变，当想对插入一个 （list，int）键值对时，必须将 list 转为 tuple</p>
<h3 id="str字符串">str（字符串）</h3>
<p>和 C++ 中字符串类似，但是无法修改其中字符，因此经常用如下方法转换为一个list再进行操作。</p>
<pre><code class="language-python">s = '1323'
s = list(s)
</code></pre>
<p>重载了加法，加法即是字符串连接</p>
<p>同时也有count，index，find等函数</p>
<p>多了一个C++没有，很好用的 split</p>
<p><strong>split</strong></p>
<p>默认以不可见字符进行分割，也可传入固定字符，以固定字符进行分割字符串，将子串存入list中</p>
<pre><code class="language-python">s = 'hellomy name is caidd!!!'
print(s.split())# ['hello', 'my', 'name', 'is', 'caidd!!!']
print(s.split('my'))# ['hello', ' name is caidd!!!']
</code></pre>
<h3 id="dict字典">dict（字典）</h3>
<p>相当于C++的map容器，但是其内部是哈希表实现的，无序，大部分操作都是 <span class="math inline">\(O(1)\)</span> 的</p>
<p>需要注意的是，其通过下标访问一个不存在的key时，会报异常，这点可以用后文的defaultdict解决</p>
<pre><code class="language-python">d = {'str': 1, 'int': 2, 'float': 3}
print(d['str'], d['int'], d['float'])
# 1, 2, 3
d['str'] += 1
print(d['str'])
# 2
d['list'] = 4
d.pop('str')# 删除键值
for i in d:# 等价于d.keys()
    print(i)
'''
int
float
list
'''
for i in d.values():
    print(i)
'''
2
3
4
'''
for k, v in d.items():
    print(k, v)
'''
int 2
float 3
list 4
'''
if 'int' in d:# 查询
    print('yes')
# d['str'] += 1 会报错，抛异常
</code></pre>
<h3 id="set集合">set（集合）</h3>
<p>set是一个数学意义集合（不可重，无序）的程序实现（内部由哈希表实现）。支持各种集合操作。</p>
<pre><code class="language-python">s = set()# 创建一个空集合
s.add(1)# 加入元素 O(1)
s.remove(1)# 删除1 O(1)
if 1 in s:# 查找1是否在集合内 O(1)
</code></pre>
<p>该类型重载了位运算，可以灵活的求集合交，并，补</p>
<pre><code class="language-python">a = {1, 2, 3}
b = {3, 4, 5}
print(a &amp; b)# 交集 {3}
print(a | b)# 并集 {1, 2, 3, 4, 5}
print(a - b)# 差集 {1, 2}
print(a ^ b)# 对称差集 {1, 2, 4, 5}
</code></pre>
<p>其可迭代，故也可以</p>
<pre><code class="language-python">for i in s:
</code></pre>
<p>这样遍历</p>
<h3 id="类型转换">类型转换</h3>
<p>类型可以函数化，并互相转换</p>
<p>如最常用的 int，str 转换</p>
<pre><code class="language-python">a = 120
a = str(a) # 字符串 120
a = a[::-1] # 字符串 021
a = int(a) # 整型 21
</code></pre>
<p>还有 list 与 set 互相转换以实现去重操作</p>
<h2 id="python基础语法">Python基础语法</h2>
<p>本部分，我将直接列出c++基础语法，并给出在Python上的等价替代。</p>
<h3 id="主函数体">主函数体</h3>
<p>c++main函数基础结构：</p>
<pre><code class="language-cpp">int main() {
        return 0;
}
</code></pre>
<p>Python主函数并不是必要的，完全直接在空文件编写代码，如：</p>
<pre><code class="language-cpp">int main() {
    for (int i = 0;i &lt; 10;i ++) {
      printf("%d\n", i);
    }
        return 0;
}
</code></pre>
<p>在Python中可以直接写为：</p>
<pre><code class="language-python">for i in range(10):
    print(i)
</code></pre>
<p>当然，如果实在不习惯，想要和c++风格更加类似，可以按如下写法：</p>
<pre><code class="language-python">if __name__ == "__main__":
    for i in range(10):
      print(i)
</code></pre>
<p>第一行<code>if __name__ == "__main__":</code>的意思：字面上，这是一个if判断，而<code>__name__</code>是一个内置的特殊变量，当我们希望将一个python模块（就是写好的py文件）导入其他python模块时，就只会执行<code>if __name__ == "__main__":</code>的语句，比如：</p>
<pre><code class="language-python">print(123)
if __name__ == "__main__":
    for i in range(10):
      print(i)
</code></pre>
<p><code>print(123)</code>就不会被执行。</p>
<p>但对于算法竞赛来说，一般不需要多模块操作，该写法只是为了更好的向c++代码风格靠拢。</p>
<h3 id="运算符">运算符</h3>
<p>python中新添 ** 乘方运算符</p>
<p>无自增 ++ 运算符，无自减运算符 --</p>
<p><strong>条件连接符</strong></p>
<p>python 中均以英文表示条件连接，可读性好些</p>
<table>
<thead>
<tr>
<th>python</th>
<th>C</th>
</tr>
</thead>
<tbody>
<tr>
<td>and</td>
<td>&amp;&amp;</td>
</tr>
<tr>
<td>or</td>
<td>||</td>
</tr>
<tr>
<td>not</td>
<td>!</td>
</tr>
</tbody>
</table>
<h3 id="基础语句">基础语句</h3>
<p><strong>循环：</strong></p>
<pre><code class="language-python">for i in range(n):
    # do something
i = 0
while i &lt; n:
    # do something
</code></pre>
<p>需要注意的是，<code>for i in range(n):</code>实际上是对<code>range</code>生成的对象遍历，可以简单理解为对一个<span class="math inline">\(\)</span>的列表遍历，因此我们在循环中修改<span class="math inline">\(i\)</span>并不会改变之后的循环。比如：</p>
<pre><code class="language-python">for i in range(n):
    i += 1
</code></pre>
<p>并不会让循环按照<span class="math inline">\(0 \rightarrow2\rightarrow4···\)</span>的顺序进行。</p>
<p>可见，Python中的for循环不如c++中的灵活，因此while的使用频率大大提高了。</p>
<p><strong>关于range函数：</strong></p>
<p><code>range(start, end, offset)</code></p>
<p>三个参数分别代表，起点，终点和步长</p>
<p>range返回的区间是左闭右开的，也就是<span class="math inline">\([start,end)\)</span></p>
<p>第1和第3个参数可以缺省。</p>
<p>给几个使用实例</p>
<pre><code class="language-python">for i in range(n): #遍历[0,n)
for i in range(1, n): #遍历[1,n)
for i in range(0, n, 2):#遍历[0,n)，步长为2
for i in range(n - 1, -1, -1):#倒遍历[0,n - 1)
</code></pre>
<p><strong>分支：</strong></p>
<p>和c++差别不大，给个实例：</p>
<pre><code class="language-python">if x % 3 == 0:
    # do something
elif x % 3 == 1:
    # do something
else:
    # do something
</code></pre>
<p>可以发现区别只在于Python将<code>else if</code>合并为了<code>elif</code>。</p>
<p>但因为引入了<code>in</code>这个关键字，有了一些更加方便的用法</p>
<pre><code class="language-python"># a是一个list x是一个int
if x not in a:
    # do something
#可以发现不用再用for逐个判断a是否有x，直接可以用in关键字就可以判断了，
#但复杂度仍然是O(n)并没变小
#不止是list，一些可迭代的高级数据类型也支持这种使用方法
</code></pre>
<h3 id="函数">函数</h3>
<p>Python中函数定义方法很简单：</p>
<pre><code class="language-python">def func(x):
    # do something
    return
</code></pre>
<p>Python允许函数定义出现在函数内部</p>
<pre><code class="language-python">def func1():
    print(1)
    def func2():
      print(2)
           func2()
func1()
</code></pre>
<p><strong>Output：</strong></p>
<blockquote>
<p>1</p>
<p>2</p>
</blockquote>
<p>Python允许函数返回多个值</p>
<pre><code class="language-python">def func(x):
    return x + 1, x + 2
x, y = func(10)
print(x, y)
</code></pre>
<p><strong>Output:</strong></p>
<blockquote>
<p>11 12</p>
</blockquote>
<p>Python中函数内部如果想<strong>修改</strong>外部数字变量，需要使用<code>nonlocal</code>或者<code>global</code>关键字</p>
<pre><code class="language-python">t = 10
def func(x):
    global t
    t += 1
    return x + 1, x + 2
x, y = func(10)
print(x, y)
</code></pre>
<p>如果将<code>global t</code>注释掉程序会报错。</p>
<p>如果想要使用的变量不是被定义在全局区，而是某个函数体内部则要使用<code>nonlocal</code>关键字</p>
<pre><code class="language-python">def work():
    t = 10
    def func(x):
      nonlocal t
      t += 1
      return x + 1, x + 2
    x, y = func(10)
    print(x, y)
work()
</code></pre>
<h3 id="头文件">“头文件”</h3>
<p>Python除内置库外，有一些功能需要手动导入模块，有如下几种方法</p>
<pre><code class="language-python">import math #导入math库
from math import *#导入math库下所有变量和函数
from math import sin, cos#导入math库下的sin，cos函数
</code></pre>
<p>第一种方法和后两种调用时有所区别</p>
<p>第一种：</p>
<pre><code class="language-python">import math #导入math库
print(math.sin(10))
</code></pre>
<p>后两种：</p>
<pre><code class="language-python">from math import sin, cos#导入math库下的sin，cos函数
print(sin(10))
</code></pre>
<p>可见区别就是使用时是否要明确库名，一般在算法竞赛中为了代码简洁，推荐使用后者，但如果要使用<code>from math import *</code>的方法，将存在一定变量名冲突的风险。</p>
<p>因此，更推荐部分导入。</p>
<h3 id="宏定义">“宏定义”</h3>
<p>Python中没有宏定义，但有替代可以缩短一定码量。如下：</p>
<pre><code class="language-python">def abcdefgasdas(x):
    print(x)
   
abcdefgasdas(10)
func = abcdefgasdas
func(10)
</code></pre>
<p>我们定义一个及其鬼畜的函数<code>abcdefgasdas(x)</code>并在之后给其“取别名”为<code>func</code>，调用<code>func</code>就等价调用了<code>abcdefgasdas</code>从而在某些要调用内置函数时，起一个更短的名字，降低码量。</p>
<p>附：之所以可以这样是因为python之中，一切皆对象，故可以一切皆变量（包括函数）</p>
<h3 id="输入输出">输入输出</h3>
<p><strong>输入</strong></p>
<p>Python中的读入和C++还是有很大不同的，需要一定时间适应。</p>
<p>Python读入时都是调用<code>input()</code>其将返回标准输入中的一行数据（不包括末尾的<code>\n</code>），其返回的类型统一为字符串，因此还要对其进行变量类型转换。</p>
<p>在算法竞赛中，读入一行数字一般分为可数的几个整数，和一个很长的数组两种形式，我举例说明如何读入：</p>
<p><strong>Input</strong></p>
<blockquote>
<p>5</p>
<p>1 3</p>
<p>2 4</p>
<p>2 5</p>
<p>3 2</p>
<p>1 2 3 4 5</p>
</blockquote>
<pre><code class="language-python"># 上面是常用的读入一棵树，并给点赋权值的一种输入格式
# 读入方法如下
n = int(input()) # int()函数将input()获取的一行字符串转换为整数
for i in range(n - 1):
    x, y = map(int, input().split())# 因为一行有多个整数，首先对input()获取的字符串
    #用split()函数切割，该方法将返回一个以' '和'\n'为分隔符切片后的字符串列表
    #用map()函数就可以将这个列表中字符串数据全转换为整数，并赋给左值
    # do something
w = list(map(int, input().split()))
#w因为类型是列表，因此还要多一个list()，这是一个构造方法，将map对象转为list数据类型
</code></pre>
<p>字符串读入方法就很简单了</p>
<pre><code class="language-python">s = input()
</code></pre>
<p><strong>读入优化</strong></p>
<p>Python中的<strong>真</strong>读入优化需要码量巨大，在正式比赛中并不常用，但仍然可以使用如下方法提高一定的读入效率。</p>
<pre><code class="language-python">import sys
input = sys.stdin.readline
</code></pre>
<p>将其放在Python文件头部即可。可以提高一定效率，但没有c++那般明显。</p>
<p><strong>PS：使用该方法行末的<code>\n</code>将不会被忽略，在读入字符串数据时尤其要注意</strong></p>
<p><strong>输出</strong></p>
<p>使用<code>print()</code>进行输出</p>
<pre><code class="language-python">print(10) # 输出10并换行
print(1,2,3) # 输出1 2 3并在末尾换行
print(1, end = ' ') # 输出1并再末尾输出一个' '
</code></pre>
<p>将输出数据类型转换为字符串，并且将所有中间输出全部加入到此字符串中，最后一次性输出，有时可以提高一定效率，但并不明显。</p>
<h3 id="文件读写">文件读写</h3>
<p>由于前几年蓝桥杯 C++ 组有需要文件读写的情况，所以在此稍微讲解常用用法，具体可见标准库</p>
<p><strong>r</strong> 以只读方式打开文件。文件的指针将会放在文件的开头。</p>
<pre><code class="language-python">file = open(r'input.txt', 'r')# 字符串前的r表示后续紧跟的字符串不进行转义，即原始字符串
a = file.readline()# 后面调用这个方法即可如input函数一样使用
</code></pre>
<p><strong>w+</strong>打开一个文件用于读写。如果该文件已存在则打开文件，并从开头开始编辑，即原有内容会被删除。如果该文件不存在，创建新文件。</p>
<pre><code class="language-python">file = open(r'input.txt', 'w+')
file.write('hello\n')# write方法不如print会自动换行，若要换行需要手动加换行符
</code></pre>
<h2 id="python库和函数">Python库和函数</h2>
<p>介绍一些常用的库和函数，着重和C++的STL对比。</p>
<h3 id="简单函数">简单函数</h3>
<pre><code class="language-python"># 下列函数可以传入数字或者可迭代数据类型，常传入list
# 以list为例说明功能
max()# 返回list的最大值，也可传入多个单体值返回最大，如max(1, 2, 3, 4)
min()# 返回list的最小值，同max用法
sum()# 返回list的和
any()# 如果list中有True，返回True
all()# 如果list中全部为True，返回True
</code></pre>
<h3 id="数学函数">数学函数</h3>
<pre><code class="language-python"># 内置的，求幂取模用的是快速幂算法，O(log(n))，n为指数
pow()# 该函数有一个内置的，math库里也有一个，需要注意的是内置的更好，支持求幂取模，求逆元（带膜，指数取-1即可）
abs()# 绝对值
</code></pre>
<p><strong>math</strong> 库中的</p>
<pre><code class="language-python">factorial()# 阶乘值
ceil()       # 向上取整
floor()      # 向下取整
comb()       # 求组合值
perm()       # 求排列值
gcd()      # 最大公约数
lcm()      # 最小公倍数
exp()      # e ** x 即 e 的 x 次方
log()      # 以e为底的对数值
log2()       # 以2为底的对数值
log10()      # 以10为底的对数值
sqrt()       # 求平方根
pi         # 圆周率的常量值，精度很高
e            # 自然常数
             # 三角函数一堆，不说了，自己查
</code></pre>
<h3 id="sort">sort</h3>
<p>自定义排序，Python不如C++灵活。首先它只可以对整个序列排序，而无法对部分序列排序，其次自定义方法不如C++的lamda表达式方便。</p>
<pre><code class="language-python">#自定义排序方法
import functools
a =
def compare_personal(x,y):
    if x &gt; y: return -1 #如果x&gt;y，让x在y前面，返回-1
    return 1#否则让x在后面，返回1
a.sort(key = functools.cmp_to_key(compare_personal))
print(a)# 输出为
#当然如果只是想得到降序序列，有很简单的方法:
a.sort(reversed = True)
</code></pre>
<p>当然，很多时候我们只是想让它根据列表的某一维度排序，这时也可以用python的lambda表达式，代码量少很多。</p>
<pre><code class="language-python">#a = [,,]
a.sort(key = lambda A: (A,-A))#按第1维升序，第二维降序排列
</code></pre>
<p><code>sort</code>是没有返回值的原地排序，如果我们希望获取到这个排序后列表，且不想改变原来的列表时，可以用<code>sorted</code>函数。自定义</p>
<pre><code class="language-python">b = sorted(a， key = lambda A: (A,-A))
</code></pre>
<h3 id="map-映射">map （映射）</h3>
<p>通过一个函数，对可迭代对象的所有值对象进行修改（创建副本，非原地修改）</p>
<pre><code class="language-python">a =
print(list(map(abs, a)))
#
</code></pre>
<h3 id="collections">collections</h3>
<p>这个库里常用的有deque，defaultdict，Counter</p>
<h4 id="deque">deque</h4>
<p>deque对标c++中的双端队列，可以快速在头尾弹出和加入元素。速度比普通队列快，因此在需要队列的场合，统一使用deque</p>
<pre><code class="language-python">q = deque()         # 创建空队列
q = deque()# 创建元素为1,2,3的队列
q.append(1)         # 尾插
q.appendleft(1)   # 头插
q.extend()   # 尾插可迭代对象
q.extendleft() # 头插可迭代对象
q.pop()             # 将队列尾部的数据弹出，并作为返回值。
q.popleft()         # 将队列头部的数据弹出，并作为返回值。
</code></pre>
<h4 id="defaultdict">defaultdict</h4>
<p>即当键值不存在时，有默认返回值的 dict，其余操作差不多</p>
<pre><code class="language-python">from collections import defaultdict

a = defaultdict(int)# 默认返回int类型的默认值，若写list，则键值不存在时返回空列表
print(a['caidd'])   # 0，此时创建了一个键值对
if a['rmx']:          # 此时创建了一个键值对
    print('yes')
print(a)            # defaultdict(&lt;class 'int'&gt;, {'caidd': 0, 'rmx': 0})
</code></pre>
<p>由于defaultdict对于key下标运算返回的是value的引用，若不存在则只能创建一个对象再返回，因此通过下标判断存在与否的方式不推荐，建议使用 in 来判断是否存在</p>
<p>用下标运算来插入与修改</p>
<h4 id="counter">Counter</h4>
<p>调用Counter函数计数，返回一个 defaultdict(int)</p>
<pre><code class="language-python">from collections import Counter

a =
cnt = Counter(a)
print(cnt)   # Counter({1: 3, 3: 2, 2: 1, 5: 1})
print(cnt)# 3
cnt += 1
print(cnt)# 2
print(cnt)# 0
</code></pre>
<p><strong>PS：dict、set和其子类都是用的hash实现，而不是c++中的红黑树，因此没有自动排序功能，目前没有太好的替代。</strong></p>
<p>如果是非标准库的话，有Sorted Container，比较好用。让我们祝福它早日进标准库</p>
<h3 id="heapq优先队列">heapq（优先队列）</h3>
<p>Python中其实有优先队列，但是速度没有heapq快，因此用heapq代替。</p>
<p>heapq提供函数对一个list进行原地的小根堆的维护。</p>
<pre><code class="language-python">from heapq import heapify, heappop, heappush

q =
heapify(q)# 一次堆排序
heappush(q, 3)# 放入1，并进行一次堆排序
print(heappop(q))# 弹出堆头 3
</code></pre>
<p>heapq并没有提供方便的重载为大根堆的方法，如果想使用大根堆，一般的技巧是加入值取负值，弹出后再恢复。</p>
<p>基础操作差不多这么多，还有一些其他功能可自行了解。</p>
<h3 id="zipenumerate函数">zip、enumerate函数</h3>
<p>这两个函数，都是使得枚举进一步简单化的函数。</p>
<p>zip函数可以同时访问不同list的同偏移量的元素</p>
<pre><code class="language-python">a =
b =
for x, y in zip(a, b):
    print(x, y)
</code></pre>
<p><strong>Output：</strong></p>
<blockquote>
<p>1 5<br>
2 4<br>
3 3<br>
4 2<br>
5 1</p>
</blockquote>
<p>enumerate则是在访问list中元素时，同时给出元素的下标，下标默认从0开始。</p>
<pre><code class="language-python">a =
for i, x in enumerate(a):
    print(i, x)
</code></pre>
<p><strong>Output:</strong></p>
<blockquote>
<p>0 1<br>
1 2<br>
2 3<br>
3 4<br>
4 5</p>
</blockquote>
<h3 id="itertools">itertools</h3>
<p>这个库里的大多函数方法，都是返回一个可迭代对象，因此若要变成list还需list()转换</p>
<h4 id="permutationscombinations">permutations、combinations</h4>
<p>permutations，combinations分别是返回一个可迭代对象（一般是list）的所有排列和组合。使用时需要导入<code>itertools</code>模块</p>
<p>用法如下：</p>
<pre><code class="language-python">from itertools import permutations, combinations
a =
for p in permutations(a):
    print(p)
for p in combinations(a, 2):
    print(p)
</code></pre>
<p><strong>Output:</strong></p>
<blockquote>
<p>(1, 2, 3)<br>
(1, 3, 2)<br>
(2, 1, 3)<br>
(2, 3, 1)<br>
(3, 1, 2)<br>
(3, 2, 1)<br>
(1, 2)<br>
(1, 3)<br>
(2, 3)</p>
</blockquote>
<h4 id="accumulate累计">accumulate（累计）</h4>
<pre><code class="language-python">from itertools import accumulate

a =
b = list(accumulate(a))
print(b)#
c = list(accumulate(a, initial=0))# 实际情况这种更常用，用作前缀和
print(c)#
d = list(accumulate(a, func=lambda x, y: max(x, y), initial=0))
print(d)#
</code></pre>
<h4 id="pairwise成对遍历">pairwise（成对遍历）</h4>
<pre><code class="language-python">from itertools import pairwise

a =
for k, v in pairwise(a):
    print(k, v)
'''
2 3
3 1
1 6
6 5
5 4
'''
</code></pre>
<h3 id="functools">functools</h3>
<h4 id="reduce-聚合">reduce （聚合）</h4>
<p>其位于functools库里面</p>
<p>对于可迭代对象进行使用，将可迭代对象里的所有值对象，两两聚合，最后返回一个值对象</p>
<pre><code class="language-python">import operator
from functools import reduce

a =
print(reduce(operator.add, a))# 15，同 sum
print(reduce(lambda x, y: max(x, y), a))# 5，同 max
a = [, ]
print(reduce(operator.add, a))# # operator调用的是加操作符，此处sum不可用
</code></pre>
<h2 id="python小技巧">Python小技巧</h2>
<h3 id="交换">交换</h3>
<p>没有swap函数，但可以这么写，也很方便</p>
<pre><code class="language-python">a, b = b, a
</code></pre>
<h3 id="列表其实可以是任何可以迭代对象解析式">列表（其实可以是任何可以迭代对象）解析式</h3>
<p>创建列表时，可以用如下方法简化代码</p>
<pre><code class="language-python">a =
#生成一个的列表
adj = [[] for _ in range(n)]
#生成一个二维，空列表
#等同于 vector&lt;vector&lt;int&gt;&gt; adj(n);
</code></pre>
<p>列表解析式中中括号中返回的是一个可迭代对象，这个在很多函数中都是可接受的数据类型。结合上面说的“聚合函数”，就可以这样写</p>
<pre><code class="language-python"># 求列表全体偶数和
sum(x for x in a if x % 2 == 0)
#判断列表是否严格单调递增
all(a &lt; a for i in range(1, n))
</code></pre>
<h3 id="多维数组">多维数组</h3>
<p>很可惜，python自身没有天然支持固定长度的多维数组（即如C++的<code>int a;</code>这样的），需要numpy才能很好的使用</p>
<p>但是仍然可以创建，方式如下</p>
<pre><code class="language-python">a = [ * 2 for i in range(4)]
</code></pre>
<p>这是创建了一个 4 * 2 的 二维数组</p>
<p>有人可能疑惑，为什么不能这样创</p>
<pre><code class="language-python">a = [ * 2] * 4
</code></pre>
<p>这是后果</p>
<pre><code class="language-python">a = [ * 2] * 4
a = 1
print(a)
'''
[, , , ]
'''
</code></pre>
<p>第一列全部被修改</p>
<p>最外层的乘4，相当于只是创建了四个引用，引用的都是一个 * 2</p>
<p>所以不行</p>
<h3 id="三目表达式">三目表达式</h3>
<p>和c++中的三目表达式<code>?:</code>类似，Python中也有何其类似的语法。</p>
<pre><code class="language-python">x = 10
y = 20
a = x if x == y else y
print(a)
# 输出为20，返回的是在判断x==y为假后，返回了y并赋值给a
</code></pre>
<h3 id="快速创建一个字典">快速创建一个字典</h3>
<pre><code class="language-python">mp = {}
mp = dict()
mp = {a : b for a, b in lst}#将列表元素构造为键值对放入字典
</code></pre><br><br>
来源：https://www.cnblogs.com/Mxrush/p/17052293.html

查看完整版本: 如何用Python参加算法竞赛