详解python算法常用技巧与内置库

近些年随着python的越来越火,python也渐渐成为了很多程序员的喜爱。许多程序员已经开始使用python作为第一语言来刷题。

最近我在用python刷题的时候想去找点python的刷题常用库api和刷题技巧来看看。类似于C++的STL库文档一样,但是很可惜并没有找到,于是决定结合自己的刷题经验和上网搜索做一份文档出来,供自己和大家观看查阅。

1.输入输出:

1.1 第一行给定两个值n,m,用空格分割,第一个n决定接下来有n行的输入,m决定每一行有多少个数字,m个数字均用空格分隔.

解决办法:python的input函数接收到的输入默认都是字符串,所以我们使用 字符串切割、强制类型转换、列表生成器就可以完美解决输入问题。代码如下:

# 接收两个值,使用n,m分别接收列表中的两个值
n, m = [int(x) for x in input().split()]

# 构造输入列表的列表
num_list = []

for i in range(n):
	# python可以不用在意m的值,将所有数值接收进来然后使用len判断长度
	tmp_list = [int(x) for x in input().split()]
	num_list.append(tmp_list)

同理,若是用逗号(,)分隔的话,split函数中传入相同的值就行。

1.2 输出一行数字

由于python的print函数默认利用换行作为结束符,所以我们需要将它修改成我们需要的间隔,代码如下:

for i in range(10):
	print(i, end=' ')

end是print函数中的一个参数,决定输出的结束字符,这里修改成空格代表输出一行数字,用空格间隔,其它字符可以自行修改。

2.空列表生成,字符串修改,列表遍历

2.1 代码编写过程中,有时候会需要一个带有长度的,有初始值的空列表,生成方式如下:

# 1. 用乘法生成一个初始值为False的长度为100的一维列表
visited = [False] * 100

# 2. 利用列表生成器生成一个n*m的二维的初始值为0的列表
visited = [[0 for i in range(m)] for j in range(n)]

2.2 在python当中字符串是无法原地修改的,如果每次修改都生成一个新字符串,那么对修改次数很多且字符串很当的情况,开销是很大的。所以一般是把字符串转为列表进行修改最后再转回来。

string = 'I love to eat chicken'
# 将字符串转换成列表
string_list = list(string)

# .......对字符串列表进行修改
# Code

# 将字符串列表重新拼接成字符串
#string = ''.join(string_list)

2.3 python中列表遍历有许多种不同的方式,最直接的办法是直接对列表进行迭代遍历,但是因为我们往往是基于索引对数组进行操作且需要修改数组的值,所以更推荐用以下代码中的第二三中办法:

num_list = [i for i in range(10)]

# 1. 直接迭代列表
for item in num_list:
	# Code
	pass

# 2. 通过索引进行迭代
for i in range(len(num_list)):
	print(num_list[i])

# 3. 通过enumerate函数进行迭代
for index, value in enumerate(num_list):
	# index为当前元素的索引,value为当前元素的值
	print(index, value)

3. collections库的使用

3.1 deque队列

deque 是python中的队列(FIFO先进先出),队列在进行队首弹出的时候会比list要快。

尤其在使用BFS(深度优先搜索)的时候,队列是必须要使用到的。部分deque使用代码如下:

from collections import deque

# 初始化一个最大长度为3的队列
d = deque([1,2,3], maxlen=3)

# 因为初始化队列最大长度为3,再添加元素会把队头元素挤出
d.append(4)

# 初始化一个不限制长度的队列
d = deque()

# 添加元素到队尾部
d.append(1)
d.append(2)
d.append(3)

# 将队首的元素弹出返回
print(d.popleft())

# 弹出队尾元素并返回值
print(d.pop())

# 在队首插入元素
d.appendleft(0)

3.2 Counter计数器

Counter 是一个计数器,可以对一个序列计数,计算序列中某个元素出现的数量。

以下是示例代码:

import collections

# 一共有三种初始方法
# 1. 传入一个序列
print(collections.Counter(['a', 'b', 'c', 'a', 'b', 'b']))
# 2.传入一个字典
print(collections.Counter({'a':2, 'b':3, 'c':1}))
# 3.直接利用=传参
print(collections.Counter(a=2, b=3, c=1))

# 也可以无参数构造,利用update函数更新
c = collections.Counter()
print('Initial :', c)
# Initial: Counter()

c.update('abcdaab')
print('Sequence:', c)
# Sequence: Counter({'a': 3, 'b': 2, 'c': 1, 'd': 1})

c.update({'a':1, 'd':5})
print('Dict:', c)
# Dict: Counter({'d': 6, 'a': 4, 'b': 2, 'c': 1})

# 可以通过访问字典的访问方式访问Counter对象
for letter in 'abcde':
 print('%s : %d' % (letter, c[letter]))

# elements()方法可以返回一个包含所有Counter数据的迭代器
c = collections.Counter('extremely')
c['z'] = 0
print(list(c.elements()))
# ['e', 'e', 'e', 'm', 'l', 'r', 't', 'y', 'x']

# most_common()返回前n个最多的数据
c=collections.Counter('aassdddffff')
for letter, count in c.most_common(2):
 print('%s: %d' % (letter, count))
# f: 4
# d: 3

# Counter对象可以进行加减交并,直接使用运算符 +、-、&、|
# +会将两个字典中相同字符的出现次数相加,-会给出第一个Counter相对于第二个的差集。交集给出两个计数器当中都有的元素,且计数被赋值为较小的那个,并集为两个计数器的元素出现最多的那个。

c1 = collections.Counter(['a', 'b', 'c', 'a', 'b', 'b'])
c2 = collections.Counter('alphabet')

print ('C1:', c1)
print ('C2:', c2)

print ('\nCombined counts:')
print (c1 + c2)

print ('\nSubtraction:')
print (c1 - c2)

print ('\nIntersection (taking positive minimums):')
print (c1 & c2)

print ('\nUnion (taking maximums):')
print (c1 | c2)

# 以下为输出:
C1: Counter({'b': 3, 'a': 2, 'c': 1})
C2: Counter({'a': 2, 'l': 1, 'p': 1, 'h': 1, 'b': 1, 'e': 1, 't': 1})

Combined counts:
Counter({'a': 4, 'b': 4, 'c': 1, 'l': 1, 'p': 1, 'h': 1, 'e': 1, 't': 1})

Subtraction:
Counter({'b': 2, 'c': 1})

Intersection (taking positive minimums):
Counter({'a': 2, 'b': 1})

Union (taking maximums):
Counter({'b': 3, 'a': 2, 'c': 1, 'l': 1, 'p': 1, 'h': 1, 'e': 1, 't': 1})

3.3 defaultdict——带有默认值的字典

一般情况下创建的字典dict是不含有默认值的,即若是字典中不包含a这个key,调用dct{a}的话就会报错。

在进行算法设计和数据结构设计的时候我们希望任意给定一个key都能从字典中取出值来,哪怕只是一个默认值,这个时候我们就需要用到defaultdict

例如在用字典表示图中一个节点的相连节点的时候,我们希望将这个节点作为一个key,然后与它相连的节点组成一个列表作为它的value,这个时候我们就可以使用defaultdict(list)来创建一个默认值为列表的字典。

# list的默认值为空列表
list_dict = collections.defaultdict(list)
# int的默认值为0
int_dict = collections.defaultdict(int)

print(list_dict['a'])
print(int_dict['a'])

# 输出:[]
# 输出:0

3.4 小结

collection中常被用来写算法和数据结构的就是这几个,其它比如排序字典和命名元组很少会用上。

4.排序

4.1 对列表排序

对列表排序有两种方法,一种是使用列表内置的sort函数,sort函数直接在列表原地修改,无返回值,可以通过参数key自定义比较的key和比较函数。

第二种就是使用python的sorted函数,这个函数自由度比较高,可以自己设定比较函数和比较的key,返回一个新的列表。

如果需要自定义比较的函数,需要从库functools导入函数cmp_to_key函数,将比较函数转为key,使用代码如下:

def custom_sort(x,y):
 if x>y:
 	# 返回-1代表需要排在前面
  return -1
 if x<y:
 	# 返回1代表需要排在后面
  return 1
 return 0

lst = [i for i in range(10, -1, -1)]
print(lst)

lst.sort()
print(lst)

print(sorted(lst, key=cmp_to_key(custom_sort)))

# 输出如下:
# [10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
# [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
# [10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0]

4.2 对字典/元组列表排序

若是需要对字典(将字典利用item函数转化成元组列表)或者元组列表这种每一个item有两个值的序列进行排序,这个时候就需要利用sorted函数中的key来决定取哪个值排序。代码如下:

# 利用字符串创建计数器字典
d = dict(collections.Counter('Hello World'))
print(d)
# 排序
print(sorted(d.items(), key=lambda x: x[1], reverse=True))

# 输出如下:
# {'H': 1, 'e': 1, 'l': 3, 'o': 2, ' ': 1, 'W': 1, 'r': 1, 'd': 1}
# [('l', 3), ('o', 2), ('H', 1), ('e', 1), (' ', 1), ('W', 1), ('r', 1), ('d', 1)]

5.排列组合

python内置的模块itertools中集成了一些与迭代有关的函数,其中就有排列组合函数。

5.1 排列

排列函数permutations接收一个列表,返回这个列表内所有元素的全排列列表。

from itertools import permutations
print(list(permutations([1,2,3])))

# 输出如下:
# [(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1)]

5.2 组合

组合函数combinations接收两个参数,第一个为一个需要进行组合的列表,第二个参数为一个正整数,代表从列表中抽取多少个元素进行组合,返回一个组合列表。

from itertools import combinations
print(list(combinations([1,2,3],2)))

# 输出如下:
# [(1, 2), (1, 3), (2, 3)]

6.小技巧

6.1 在python中分了可变类型和不可变类型,当函数传参的时候:

  • 若是不可变类型如字符串,则传递参数的时候会深拷贝一份,在新的数据上修改并不改变原数据若是可变类型如列表,则传递参数的时候传递的是引用,属于浅拷贝,在函数中对新列表进行操作会影响到原来的列表。
  • 若是确实需要传递可变类型进入函数,则可以在函数内部第一行进行一次深拷贝如:
def test(num_list:list):
	# 进行深拷贝
	num_list = num_list[:]

6.2 当删除列表中的元素的时候,列表后面的元素会自动往前移动,导致出错

例如,列表为[1,2,3,4,5,6],想要删除列表中的偶数,如果直接找到一个偶数然后利用其索引删除,如下代码所示(错误示范),那么很抱歉,出问题了。

# 此处为错误示范!!!!!!!!
lst = [1, 2, 3, 4, 5, 6]
for i in range(len(lst)):
 if lst[i] % 2 == 0:
  lst.pop(i)

print(lst)

# 上面这段代码没有输出,因为报索引越界错误了。

下面的代码才是正确示范:

lst = [1, 2, 3, 4, 5, 6]
lst = [i for i in lst if i % 2 != 0]

print(lst)

# 输出如下:
# [1, 3, 5]

若是需要更复杂的筛选手段,可以在if i%2 !=0那里更改成一个函数判断,函数内部就实现筛选方法。

6.3 访问字典元素要使用get方法

前文说过,普通的dict字典是没有默认值的,所以这个时候如果直接利用中括号放置key来查找value的话是有可能会报错的。

那么为了避免这种情况,在利用字典的key来取value的时候,需要利用字典的get函数。

get函数的第一个参数为key,第二个参数为可选(默认为None),当字典中找不到传入的key的时候,会返回第二个参数所赋的值。

7.小结

以上是本人在使用python刷题的时候作的一些总结,若有不到位的地方请指出。

到此这篇关于详解python算法常用技巧与内置库的文章就介绍到这了,更多相关python算法技巧与内置库内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

(0)

相关推荐

  • Python enumerate内置库用法解析

    这篇文章主要介绍了Python enumerate内置库用法解析,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 使用enumerate,可以自动进行索引下标的赋值,本例代码中使用enumerate,进行excel单元格的赋值操作. 代码如果重复被调用,可将该代码封装成类进行使用 import openpyxl #加载excel文件 wb = openpyxl.load_workbook('test_datas/test_cases.xlsx')

  • Python基于内置库pytesseract实现图片验证码识别功能

    这篇文章主要介绍了Python基于内置库pytesseract实现图片验证码识别功能,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 环境准备: 1.安装Tesseract模块 git文档地址:https://digi.bib.uni-mannheim.de/tesseract/ 下载后就是一个exe安装包,直接右击安装即可,安装完成之后,配置一下环境变量,编辑 系统变量里面 path,添加下面的安装路径: 2.如果您想使用其他语言,请下载相应的

  • Python如何使用内置库matplotlib绘制折线图

    这篇文章主要介绍了Python如何使用内置库matplotlib绘制折线图,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 环境准备: 需要安装matplotlib,安装方式: pip install matplotlib 直接贴代码喽: #引入模块 from matplotlib import pyplot,font_manager #设置支持中文字体的显示 font=font_manager.FontProperties(fname="C:\

  • 详解python算法常用技巧与内置库

    近些年随着python的越来越火,python也渐渐成为了很多程序员的喜爱.许多程序员已经开始使用python作为第一语言来刷题. 最近我在用python刷题的时候想去找点python的刷题常用库api和刷题技巧来看看.类似于C++的STL库文档一样,但是很可惜并没有找到,于是决定结合自己的刷题经验和上网搜索做一份文档出来,供自己和大家观看查阅. 1.输入输出: 1.1 第一行给定两个值n,m,用空格分割,第一个n决定接下来有n行的输入,m决定每一行有多少个数字,m个数字均用空格分隔. 解决办法

  • 详解Python中常用的图片处理函数的使用

    目录 cvtColor函数 split()和merge() threshold()函数 自定义threshold函数进行二值化 色度函数applyColorMap cvtColor函数 这个函数有两个参数 1,src 要进行变换的原图像 2,code 转换代码标识 例子: import cv2 image=cv2.imread("ddd.jpg") image1=cv2.cvtColor(image,cv2.COLOR_BGR2BGRA) cv2.imshow(""

  • PHP函数用法详解【初始化、嵌套、内置函数等】

    本文实例讲述了PHP函数用法.分享给大家供大家参考,具体如下: 初始函数 函数:封装一段用于完成特定功能的代码. 通俗理解函数:可以完成魔鬼工作的代码块,就像积木一样,可以反复使用,在使用的时候,拿来即用. 函数定义:1)内置函数(字符串操作函数.数组操作函数)2)自定义函数 函数的基本语法格式 function 函数名([参数1.参数2,......]){ 函数体...... } 函数的定义由一下四部分组成: 关键字function function: 在声明函数时必须使用的关键字: 函数名f

  • 详解python opencv、scikit-image和PIL图像处理库比较

    进行深度学习时,对图像进行预处理的过程是非常重要的,使用pytorch或者TensorFlow时需要对图像进行预处理以及展示来观看处理效果,因此对python中的图像处理框架进行图像的读取和基本变换的掌握是必要的,接下来python中几个基本的图像处理库进行纵向对比. 项目地址:https://github.com/Oldpan/Pytorch-Learn/tree/master/Image-Processing 比较的图像处理框架: PIL scikit-image opencv-python

  • 详解python算法之冒泡排序

    python之冒泡排序 概念: 重复地走访过要排序的元素列,依次比较两个相邻的元素,如果他们的顺序(如从大到小.首字母从A到Z)错误就把他们交换过来.走访元素的工作是重复地进行直到没有相邻元素需要交换,也就是说该元素已经排序完成 这个算法的名字由来是因为越大的元素会经由交换慢慢"浮"到数列的顶端(升序或降序排列),就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样,故名"冒泡排序". 算法原理 冒泡排序算法的原理如下: 比较相邻的元素.如果第一个比第二个大,就交换他

  • 详解python之多进程和进程池(Processing库)

    环境:win7+python2.7 一直想学习多进程或多线程,但之前只是单纯看一点基础知识还有简单的介绍,无法理解怎么去应用,直到前段时间看了github的一个爬虫项目涉及到多进程,多线程相关内容,一边看一边百度相关知识点,现在把一些相关知识点和一些应用写下来做个记录. 首先说下什么是进程:进程是程序在计算机上的一次执行活动,当运行一个程序的时候,就启动了一个进程.而进程又分为系统进程和用户进程.只要是用于完成操作系统的各种功能的进程就是系统进程,它们就是处于运行状态下的操作系统本身;而所有由你

  • 详解K-means算法在Python中的实现

    K-means算法简介 K-means是机器学习中一个比较常用的算法,属于无监督学习算法,其常被用于数据的聚类,只需为它指定簇的数量即可自动将数据聚合到多类中,相同簇中的数据相似度较高,不同簇中数据相似度较低. K-MEANS算法是输入聚类个数k,以及包含 n个数据对象的数据库,输出满足方差最小标准k个聚类的一种算法.k-means 算法接受输入量 k :然后将n个数据对象划分为 k个聚类以便使得所获得的聚类满足:同一聚类中的对象相似度较高:而不同聚类中的对象相似度较小. 核心思想 通过迭代寻找

  • 详解python 支持向量机(SVM)算法

    相比于逻辑回归,在很多情况下,SVM算法能够对数据计算从而产生更好的精度.而传统的SVM只能适用于二分类操作,不过却可以通过核技巧(核函数),使得SVM可以应用于多分类的任务中. 本篇文章只是介绍SVM的原理以及核技巧究竟是怎么一回事,最后会介绍sklearn svm各个参数作用和一个demo实战的内容,尽量通俗易懂.至于公式推导方面,网上关于这方面的文章太多了,这里就不多进行展开了~ 1.SVM简介 支持向量机,能在N维平面中,找到最明显得对数据进行分类的一个超平面!看下面这幅图: 如上图中,

  • 图文详解感知机算法原理及Python实现

    目录 写在前面 1.什么是线性模型 2.感知机概述 3.手推感知机原理 4.Python实现 4.1 创建感知机类 4.2 更新权重与偏置 4.3 判断误分类点 4.4 训练感知机 4.5 动图可视化 5.总结 写在前面 机器学习强基计划聚焦深度和广度,加深对机器学习模型的理解与应用.“深”在详细推导算法模型背后的数学原理:“广”在分析多个机器学习模型:决策树.支持向量机.贝叶斯与马尔科夫决策.强化学习等. 本期目标:实现这样一个效果 1.什么是线性模型 线性模型的假设形式是属性权重.偏置与属性

  • 详解KMP算法以及python如何实现

    算法思路 Knuth-Morris-Pratt(KMP)算法是解决字符串匹配问题的经典算法,下面通过一个例子来演示一下: 给定字符串"BBC ABCDAB ABCDABCDABDE",检查里面是否包含另一个字符串"ABCDABD". 1.从头开始依次匹配字符,如果不匹配就跳到下一个字符 2.直到发现匹配字符,然后经过一个内循环严查字符串是否匹配 3.发现最后一个D不匹配,下面就该思考应该把字符串向右移动多少个位置呢?传统做法可能是移动一格,KMP算法就创新在这里.K

随机推荐