Python Tips - swchen1234/Algorithm GitHub Wiki

小技巧

  1. sorted(dic.items(),key=lambda d:d[0])是按照key排序，返回[(‘a’,2),(‘b’,1)]

isalpha()：判断字符串是否全是字母

isdigit()：判断字符串是否全是数字(isnumeric()也起相同作用，还能判断它国语言） ** 判断负数， 如“-2”， 用s.lstrip('-').isdigit()

is_integer()：判断浮点数是否为整数

用lst.sort() 而不是nlst = sorted(lst)， 区别在于lst.sort()是 in-place sort，改变lst, sorted会创建新list，成本比较高。

  • list.index(val) 若找不到， 报错
  • list.find(val) 完全同list.index。 若找不到， 返回-1.

用xrange： xrangge 和 range的区别是在于 range会产生list存在memory中，xrange更像是生成器，generate on demand， 所以有的时候xrange会更快

三目运算符： python 的三目运算符是这么写的 x if y else z， 考虑这种list of list: matrix = [ [1,2,3] , [4,5,6] ]

row = len(matrix) col = len(matrix[0]) if row else 0 这样写通用的原因是， 当matrix- = [], row = 0, col =0

list 填 0

lst = [0 for i in range(3)] # lst = [0,0,0] lst = [0 for i in range(3)] for j in range(2)] # lst = [[0, 0, 0], 0, 0, 0 下面这种写法危险： lst1 = [ 0, 0, 0 ] lst2 = [lst1] * 2 # lst2 = [ [0,0,0] , [0,0,0] ] lst2[0][0] = 1 # lst2 = [ [1,0,0], [1,0,0]]

  • 用self.res.append(subset[:])来进行copy赋值
  • D.get(key, default)。 如果这个key 没有在dict里面，给它一个默认值：

classmethod VS staticmethod: @staticmethod function is nothing more than a function defined inside a class. It is callable without instantiating the class first. It’s definition is immutable via inheritance.

@classmethod function also callable without instantiating the class, but its definition follows Sub class, not Parent class, via inheritance. That’s because the first argument for @classmethod function must always be cls (class).

Heap

import heapq
from collections import Counter, defaultdict
class Solution(object):
    def topKFrequent(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: List[int]
        """
        heap = [(-1*v1, k1) for k1,v1 in Counter(nums).items()]
        heapq.heapify(heap)
        result = []
        for i in range(k):
            result.append(heapq.heappop(heap)[1])
        return result

https://blog.csdn.net/guzhenping/article/details/54987308

堆最重要的特性就是heap[0]总是最小的那个元素。

nlargest/nsmallest import heapq

"""简单的数据集""" numbers = [11,22,33,-9,0,5,-11] # 测试数据集

heapq.nlargest(3,numbers) # 获得前3最大的元素

heapq.nsmallest(3,numbers) # 获得前3最小的元素

"""复杂的数据集""" people_info = [ {'name': "guzhenping", 'age':19, 'score':90}, {'name': "xiao gu", 'age':21, 'score':100} ]

max_age = heapq.nlargest(1,people_info, key=lambda people_info: people_info['age']) # 获取最大年龄的个人

min_score = heapq.nsmallest(1, people_info, key=lambda info: info['score']) # 获取最低分数的个人 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 heapify 作用：对元素进行堆排序。保证最小的元素在为第一个元素。 import heapq nums = [11, 22, 33, 44, 0, -1,20,-12] # 测试数据集

heapq.heapify(nums) # 转化成堆排序的列表

print(nums) # 输出：[-12, 0, -1, 22, 11, 33, 20, 44]。

heapq.heappop(nums) # 弹出最小的元素，同时让第二小的元素变成第一小 1 2 3 4 5 6 7 8 heappop/heappush heappop和heappush是在堆排序中常用的方法。heapq.heappop()作用：将第一个元素（最小的）弹出，然后将第二小的元素放在第一个。heapq.heappush()是插入操作。两者复杂度o(logN),N代表堆中元素的数量。 以一个优先级队列进行举例：

import heapq

class PriorityQueue: def init(self): self._queue = [] self._index = 0

def push(self, item, priority):
    heapq.heappush(self._queue, (priority, self._index, item))
    self._index += 1

def pop(self):
    data = heapq.heappop(self._queue)
    print(data)
    return data[-1]

if name == 'main': q = PriorityQueue()

q.push("guzhenping", 1)
q.push("xiao gu", 3)
q.push("xiao ping",1)

# 打印测试
while len(q._queue) != 0:
    print(q.pop())

Collections

deque from collections import deque

"""学习固定长度的deque""" q = deque(maxlen=5) # 创建一个固定长度的队列,当有新记录加入已满的队列时，会自动移除最老的记录。

q.append(1) # 添加元素

"""学习不固定长度的deque，从队列两端添加或弹出元素的复杂度为o(1).""" q = deque() # 创建一个无界限的队列，可以在队列两端执行添加和弹出操作

q.append(1) # 添加元素

q.appendleft(2) # 向左边添加一个元素

q.pop() # 弹出队列尾部的记录

q.popleft() # 弹出队列头部的记录 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

Stack/Queue/Deque

都用deque 来实现 q = deque(list) q.append(1), q.popleft() 等以上四个操作

defaultdict 用于创建有多个value对应一个key的字典。比如创建value可重复(list存储)的该字典：dic = {“a”: [1, 2 , 2, 3, 3], “b”: [1, 2]}。或创建value不可重复（set存储）的该字典：dic = {“a”: { 1, 2, 3}, “b”: {1, 2} } from collections import defaultdict

d_list = defaultdict(list) # list d['a'].append(1) d['a'].append(2) d['a'].append(2) d['a'].append(3) d['a'].append(3)

d_set = defaultdict(set) # set d['a'].add(1) d['a'].add(2) d['a'].add(3) 1 2 3 4 5 6 7 8 9 10 11 12 13 OrderedDict OrderedDict内部维护了一个双向链表，会根据元素加入的顺序来排列键的位置。一个新加入的元素被放在链表的末尾，然后，对已存在的键做重新赋值但不会改变键的顺序。作用：严格控制元素初始添加的顺序。 from collections import OrderedDict

d = OrderedDict() # 实例化 d['a'] = 1 d['b'] = 2 1 2 3 4 5 Counter 作用：统计可哈希的序列中元素出现的次数。（可哈希：一种特性，具备该特性的对象在其生命周期内必须不可变。在Python中，有整数、浮点数、字符串、元组。） from collections import Counter

test = ['a', 'a', 'b', 'c', 'b', 'd', 'a', 'c', 'e', 'f', 'd'] # 测试集

word_count = Counter(test) # 调用，传参

print(word_count) # 输出：Counter({'a': 3, 'b': 2, 'c': 2, 'd': 2, 'f': 1, 'e': 1})

word_count.most_common(3) # 获取出现频次前3的单词

word_count['a'] # 获取某个单词的频次 1 2 3 4 5 6 7 8 9 10 11 Counter还可以将两个数据集进行数学运算。如下:

from collections import Counter

test = ['a', 'a', 'b', 'c', 'b', 'd', 'a', 'c', 'e', 'f', 'd'] # 测试集

test1 = ['a', 'b', 'c', 'd', 'e', 'f'] # 另一测试集

a = Counter(test) # 统计test b = Counter(test1) # 统计test1

print(a) # 输出：Counter({'a': 3, 'b': 2, 'c': 2, 'd': 2, 'f': 1, 'e': 1}) print(b) # 输出：Counter({'b': 1, 'a': 1, 'f': 1, 'c': 1, 'd': 1, 'e': 1})

c = a + b # 统计两个数据集 print(c) # 输出：Counter({'a': 4, 'b': 3, 'c': 3, 'd': 3, 'f': 2, 'e': 2})

c = a - b # Counter({'a': 2, 'b': 1, 'c': 1, 'd': 1}) c = b - a # Counter()