Python数据结构与算法——常见⾯试题0. 数据结构定义
堆栈：list 原⽣即可⽀持堆栈操作：
list.append()：⼊栈；
list.pop()：出栈；
not list：堆栈是否为空；
链表节点：
class ListNode(object):
def __init__(self, x):
self.val = x
< = None
1. 链表
翻转链表：
def reverseList(head):
cur, prev = head, None
while cur:
<, prev, cur = prev, cur,
return prev
快速排序python实现
# 跳出while循环时，cur 为 None
2. 排序
快速排序（quick sort）
形式⼀：借助 partition 辅助函数
def partition(seq):
pivot, seq = seq[0], seq[1:]
low = [x for x in seq if x <= pivot]
high = [x for x in seq if x not in low]
return low, pivot, high
def qsort(seq):
if len(seq) <= 1: return seq
low, pivot, high = partition(seq)
return qsort(low)+[pivot]+qsort(high)
形式⼆：直接返回数组
def qsort(arr):
if len(arr) <= 1:
return arr
pivot = arr[len(arr)//2]
left = [x for x in arr if x < pivot]
middle = [x for x in arr if x == pivot]
right = [x for x in arr if x > pivot]
return qsort(left) + middle + qsort(right)

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。