Leetcode | Python刷Leetcode注意点

想尝试拿python刷刷leetcode，随手记一点注意事项

一些不一样的写法⁍

三元表达式⁍

r = a if condition else b

True or False⁍

大写

没有自增和自减⁍

i += 1/i -= 1

最大值/最小值⁍

1 2	`max_value = float('inf') # math.inf min_value = float('-inf') # -math.inf`

进制转换⁍

转10进制
1
int(str, base)
转2进制
1
bin(int) -> str # '0b10'
转8进制
1
oct(int) -> str # '0o77'
转16进制
1
hex(int) -> str # '0xff'

运算⁍

# 除法
a = 3/2 # 1.5
a = int(-3/2) # -1
a = math.floor(-3/2) # -2
a = math.ceil(-3/2) # -1
# 幂
x**y == pow(x,y)
# 根号
math.sqrt(4) # 2.0
# 绝对值
abs(-4) # 4

指定排序⁍

# 获取列表的第二个元素
def takeSecond(elem):
    return elem[1]
# 列表
random = [(2, 2), (3, 4), (4, 1), (1, 3)]
# 指定第二个元素排序
random.sort(key=takeSecond)

####
>>> b = [[1,3],[4,2],[2,6]]
>>> c = sorted(b,key = lambda x:x[1])
>>> c
[[4, 2], [1, 3], [2, 6]]
>>> d = sorted(b) # x[0] by default
>>> d
[[1, 3], [2, 6], [4, 2]]

二维数组赋值⁍

1	`dp = [[0]*target for _ in range(n)]`

数据结构⁍

str[^1]⁍

不可变有序序列

常用函数

format(*args, **kwargs)  # 用法丰富多样, 算法中可用于字符串形式的进制转换(练习: LeetCode [191. Number of 1 Bits](https://leetcode.com/problems/number-of-1-bits/))
split(sep=None, maxsplit=-1)  # 以sep来分割字符串
strip([chars])  # 去除首末两端的字符, 默认是 \r,\n," "
join(iterable)  # 将iterable内的元素拼接成字符串,如','.join(['leet', 'code']) #="leet,code"
replace(old, new[, count])  # 字符串替换, old to new
count(sub[, start[, end]])  # 统计子字符串sub的个数
startswith(prefix[, start[, end]])  # 以prefix开始的字符串
endswith(suffix[, start[, end]])  # 以suffix结束的字符串

常用的功能

拼接(加), s1 + s2
切片, s[start: end: space]
重复(乘), s * 10

tuple⁍

元组, 也叫静态列表. 内置的数据结构, 可以直接使用, 无须导入.

元组常用于多变量赋值和多值返回, 只是一般在使用的时候没有加上小括号, 以显得python的牛逼之处.
需要注意的是, 当tuple里只有一个元素时, 需要在该元素之后加上,, 如 t=(1,), 否则它就不是tuple, 而是该元素的类型.
同样支持拼接, 切片, 重复等操作
提供的函数仅有index和count

list⁍

经常使用的数据结构, 可以实现简单的队列, 栈等.

常用功能: 拼接, 重复, 切片

强大的切片功能, 可用于取值, 替换, 删除等

lst[i:j] = t, 其中 t 是可迭代序列
del lst[i:j], 相当于 lst[i:j] = [].

常用函数

lst.sort(*, key=None, reverse=False)
lst.append(val)  # 也可以 lst = lst + [val]
lst.clear()  # 清空列表
lst.count(val)  # val个数
lst.extend(t)  # or s += t  # += 其实调用的是 __iadd__ 方法
lst.pop(val=lst[-1])  # (默认)从末端移除一个值
lst.remove(val)  # 移除 val
lst.reverse()  # 反转
lst.insert(i, val)  # 在 i 处插入 val

字典/哈希表⁍

dict⁍

初始化： map={}
查找key： value=map[key]
加入key或更改key的值： map[key]=value
判断key是否存在： if key in/not in map
遍历key：for key in map

常用方法

pop(key[, default])  # 通过键去删除键值对(若没有该键则返回default(没有设置default则报错))
setdefault(key[, default])  # 设置默认值
update([other])  # 批量添加
get(key[, default])  # 通过键获取值(若没有该键可设置默认值, 预防报错)
clear()  # 清空字典
keys()  # 将字典的键组成新的可迭代对象
values()  # 将字典中的值组成新的可迭代对象
items()  # 将字典的键值对凑成一个个元组, 组成新的可迭代对象

OrderedDict⁍

有序字典, 使得插入的顺序有序. (官方解释: Dictionary that remembers insertion order)

同样也继承于 dict, 所以可以使用 dict 所拥有的方法.

添加的方法:

1 2	`popitem(last=True) # (默认)从末尾去除一个元素 move_to_end(key, last=True) # 将key移到(默认)末尾`

集合⁍

set, 主要用于去重的操作.

需要注意的是

它的定义. 只能使用实例的方式定义, 如s= set();s={1,2,4,8}, 而不能这样定义s={}. 因为这样定义的是一个字典, 不能使用集合的方法.
无序特性. 有时候你会在 N 次输出同一个集合的时候, 发现它是有序的, 但是请你也一定不要相信集合是有序的.

常用函数

add(elem)  # 向集合中添加数据
update(*others)  # 迭代着增加
clear()  # 清空集合
discard(elem)  # 删除集合中指定的值(不存在则不删除)

队列⁍

# Python 通常使用双端队列 collections.deque
from collections import deque

queue = deque()

queue.append(1) # 元素 1 入队
queue.append(2) # 元素 2 入队
queue.popleft() # 出队 -> 元素 1
queue.popleft() # 出队 -> 元素 2

# deque的其他一些方法
queue.clear()  # 清空队列
queue.count(val)  # 返回指定元素的出现次数
queue.extend(iterable)  # 从队列右边扩展一个序列的元素
queue.extendleft(iterable)  #  从队列左边扩展一个列表的元素
queue.insert(val[, start[, stop]])  # 在指定位置插入元素
queue.pop()  # 获取最右边一个元素，并在队列中删除
queue.reverse()  # 队列反转
queue.remove(val)  # 删除指定元素
queue.rotate(n=1)  # 把右边元素放到左边

堆队列⁍

可实现优先级队列的数据结构. 可以解决 top n 问题, 如从1亿个数里面找出最大或最小的100个数

import heapq
nums = [randint(1, 1000) for x in range(100)]
print(heapq.nlargest(3, nums))
print(heapq.nsmallest(3, nums))

常用函数

import heapq

heap = []  # 建堆
heapq.heappush(heap,item)  # 往堆中插入新值
item = heapq.heappop(heap)  # 弹出最小的值
item = heap[0]  # 查看堆中最小的值, 不弹出
heapq.heapify(x)  # 以线性时间将一个列表转为堆
item = heapq.heapreplace(heap,item)  # 弹出一个最小的值, 然后将 item 插入到堆当中. 堆的整体的结构不会发生改变.
heapq.heappoppush(heap, item)  # 弹出最小的值.并且将新的值插入其中.
heapq.merge(*iterables, key=None, reverse=False)  # 将多个堆进行合并
heapq.nlargest(n, iterable, key=None)  # 从堆中找出最大的 n 个数，key的作用和sorted( )方法里面的key类似, 用列表元素的某个属性和函数作为关键字
heapq.nsmallest(n, iterable, key=None)  # 从堆中找出最小的 n 个数, 与 nlargest 相反

二叉树⁍

初始化⁍

class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

遍历⁍

深度遍历⁍

递归⁍

class Solution:
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        result = []
        def preOrder(root):
            if root==None:
                return
            result.append(root.val) # 前序
            preOrder(root.left)
            preOrder(root.right)
        return result

迭代⁍

先出最左的就要遍历到最左！中间的就直接处理

前序

class Solution:
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        result = []
        stack = []
        if root == None:
            return []
        stack.append(root)
        while st:
            node = stack.pop() 
            result.append(node.val) # 中
            if node.right:
                result.append(node.right.val) # 右
            if node.left:
                result.append(node.left.val) # 左
        return result

中序

class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        if not root:
            return []
        result = []
        stack = []
        # 注意循环条件
        while root or stack:
            if root:
                # 先将中节点压栈，等会处理
                stack.append(root)
                root = root.left
            else: # 左节点全部遍历完
                # 中节点出栈，加入结果集
                root = stack.pop()
                result.append(root.val)
                root = root.right
        return result

后序

一种思路是按前序处理，最后数组翻转return result[::-1]

这里尝试用栈来写

class Solution:
    def postorderTraversal(self, root: TreeNode) -> List[int]:
        if not root:
            return []
        
        res = []
        stack = []
        # 前置节点
        prev = []

        while root or stack:
            if root:
                stack.append(root)
                root = root.left
            else: # 遍历完左节点
                # 取出节点
                root = stack.pop()
                # 下一个就是看右节点
                if not root.right or root.right == prev:
                    # 如果右节点已经遍历过了
                    # 将结果加进去（中）
                    res.append(root.val)
                    # 中节点变右节点
                    prev = root
                    root = None
                else:
                    # 否则系欸但入栈
                    stack.append(root)
                    root = root.right
        
        return res

统一写法：在后面加上None节点，调整顺序即可

class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        result = []
        st = []
        if root:
            st.append(root)
        while st:
            node = st.pop()
            if node != None:
                if node.right: #添加右节点（空节点不入栈）
                    st.append(node.right)
                
                st.append(node) #添加中节点
                st.append(None) #中节点访问过，但是还没有处理，加入空节点做为标记。
                
                if node.left: #添加左节点（空节点不入栈）
                    st.append(node.left)
            else: #只有遇到空节点的时候，才将下一个节点放进结果集
                node = st.pop() #重新取出栈中元素
                result.append(node.val) #加入到结果集
        return result

层序⁍

class Solution:
    """二叉树层序遍历迭代解法"""

    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        result = []
        if root:
            return []
        # 引入队列
        from collections import deque
        que = deque([root])
        
        while que:
            levelRes = []
            for _ in range(len(que)):
                node = que.popleft()
                levelRes.append(node.val)
                if node.left:
                    que.append(node.left)
                if node.right:
                    que.append(node.right)
            res.append(levelRes)
        return result

python 在LeetCode中常用的数据结构 - 知乎 (zhihu.com)