50

教你用 Python 高效刷 Leetcode

 4 years ago
source link: https://www.tuicool.com/articles/BjQrAfE
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.

由于Python语法的简洁性,用python来刷leetcode往往能用比别的语言更少的代码量AC。但是如果不是对python很熟悉就会比较尴尬了,如果有些功能明明有高效的内置方法因为不知道要自己实现、或者不了解其复杂度提交时出现超时。

我总结了一下自己在刷leetcode时关于python这个语言的经常被使用的数据结构和内置方法。

基础

离开数据结构,算法就是空中楼阁,所以了解python内置的数据类型用法和其效率是非常有必要的

list

list作为最常见的内置数据结构,其不仅可以当作C语言的数组来使用,一些python特有的特性往往可以事半功倍

append 在list的结尾追加一个元素

sort 对list进行排序,在list长度小的时候使用插入排序,在长度大的时候使用快排,所以其时间复杂度可以视为O(nlgn)

pop 将最后一个元素从list内部弹出并返回

切片  python强大的语法糖之一,不仅可以用非负数索引,负数索引的合理使用可以节省不少代码量

set

set本质是哈希表,会对其内部元素去重,检查一个元素是否在set内部的时间复杂度是O(1)

常用的方法为

add 添加一个元素,就算是用一个元素多次添加,其内部也仅保留一份

pop 随机弹出一个元素并返回

dict

同set一样,dict本质也是哈希表,但是set是单个元素,dict是key-value的组合

setdefault 接受两个入参key、default, 如果dict存在key则不做任何操作,如果不存在key,则创建一个 key其value为default

get  同setdefault一样接受两个参数key、default,如果存在key,则返回其value,否则返回default

pop 同setdefault一样接受两个参数key、default,如果存在key,则删除key返回其value,否则返回default

str

字符串也是一个经常在算法中常用的数据结构,在python中str是不可变对象,支持”+“操作当时效率不高需要慎用

split 用指定的分隔符将str分割为list

strip 返回str去掉首尾的空白符后新的str,原来的str不受影响

join 用str作为连接符连接参数里面的每一个元素,常常用来替代”+“

进阶

这里介绍几个常用的内置函数

int 将一个参数转为int类型,在遇到字母等字符时会抛出错误

sum 返回参数的求和

min 返回多个参数的最小值

max 返回多个参数的最大值

abs 返回一个数字的绝对值

高级

这里对于数据结构的知识点要求就比较高了,仅仅介绍常用方法,如果不了解其特性的还请自己查阅资料

queue 队列

put 入队操作

get 出队操作

qsize 返回当前队列的长度

list 栈

这里又有list,是因为python没有单独的栈,在需要栈的时候往往使用list

append 入栈

pop 出栈

heapq 堆

仅支持最小堆,有个小技巧:如果最大堆,取反之后再放入堆,取出的时候再取反

heapfiy 将一个list转为最小堆

heappush 往一个最小堆添加元素

heappop 弹出堆中的最小值并返回


About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK