【python与数据结构】（leetcode算法预备知识）

笔记为自我总结整理的学习笔记，若有错误欢迎指出哟~

Python 中常见的数据类型

1.数字类型：

• 整数（int）：表示整数值，例如 1、-5、100。
• 浮点数（float）：表示带有小数部分的数字，例如 3.14、-0.5、2.0。
• 复数（complex）：表示实部和虚部的复数，例如 2+3j。

2.布尔类型（bool）：

• 表示真（True）或假（False）的逻辑值。

3.字符串类型（str）：

• 表示文本数据，使用单引号或双引号括起来，例如 ‘Hello’、“World”。

4.列表类型（list）：

• 表示有序的可变序列，可以包含不同类型的元素，使用方括号括起来，例如 [1, 2, ‘a’, True]。

5.元组类型（tuple）：

• 类似于列表，但是不可变，使用圆括号括起来，例如 (1, 2, ‘a’, True)。

6.集合类型（set）：

• 表示无序且唯一的元素集合，使用花括号括起来，例如 {1, 2, 3}。

7.字典类型（dict）：

• 表示键值对的映射关系，使用花括号括起来，例如 {‘name’: ‘Alice’, ‘age’: 25}。

数据结构

1.数组（Array）

列表类型（list）

2.链表（Linked List）

class ListNode:def __init__(self,x):self.val = xself.next = None

3.哈希表（Hash Table）

字典类型（dict）

4.队列（Queue）

list

进队：append()

出队：pop(0)

l = [1,2,3,4,5]l.append(6)
l
#[1, 2, 3, 4, 5, 6]l.pop(0)
l
#[2, 3, 4, 5, 6]

deque(类似双端队列)

deque 是 Python 中的一个内置模块 collections 中的类，用于实现双端队列（double-ended queue）。双端队列是一种具有队列和栈特性的数据结构，支持在两端进行插入和删除操作。

deque 提供了以下常用操作：

1. 创建双端队列：
   • 使用 deque() 函数创建一个空的双端队列。
   • 例如：from collections import deque，d = deque()。
2. 在队列两端插入元素：
   • 使用 append(item) 在队列的右端插入一个元素。
   • 使用 appendleft(item) 在队列的左端插入一个元素。
   • 例如：d.append(1)，d.appendleft(2)。
3. 在队列两端删除元素：
   • 使用 pop() 删除并返回队列右端的元素。
   • 使用 popleft() 删除并返回队列左端的元素。
   • 例如：d.pop()，d.popleft()。
4. 访问队列两端的元素：
   • 使用 [-1] 索引访问队列右端的元素。
   • 使用 [0] 索引访问队列左端的元素。
   • 例如：d[-1]，d[0]。
5. 获取队列长度：
   • 使用 len(d) 获取队列中的元素个数。
6. 判断队列是否为空：
   • 使用 not d 或 len(d) == 0 判断队列是否为空。

deque 还支持其他一些方法，如旋转队列、计数元素出现次数、反转队列等。双端队列在实际应用中常用于需要高效地在两端进行插入和删除操作的场景，比如实现缓存、任务调度等。

右进：append()

右出：pop()

左进：appendleft()

左出：popleft()

from collections import deque
q = deque([1,2,3])q.append(4)
q
#deque([1, 2, 3, 4])q.pop()
q
#deque([1, 2, 3])q.appendleft(4)
q
#deque([4, 1, 2, 3])q.popleft()
q
#deque([1, 2, 3])

使用：先进后出

#使用方法1：队头<---   队列   <---队尾
#append()	队尾
#popleft()	队头from collections import deque
q = deque([1,2,3])q.append(4)
q
#deque([1, 2, 3, 4])q.popleft()
q
#deque([2, 3, 4])

#使用方法2：队尾--->   队列   --->队头
#appendleft()	队尾
#pop()	队头from collections import deque
q = deque([1,2,3])q.appendleft(4)
q
#deque([4, 1, 2, 3])q.pop()
q
#deque([4, 1, 2])

5.栈（Stack）

list

进栈：append()

出栈：pop()

l = [1,2,3,4,5]l.append(6)
l
#[1, 2, 3, 4, 5, 6]l.pop()
l
#[1, 2, 3, 4, 5]

deque

右进：append()

右出：pop()

左进：appendleft()

左出：popleft()

使用：先进先出，后进后出

6.堆（Heep）

heapq 是 Python 中的一个内置模块，提供了堆（heap）算法的实现。堆是一种特殊的树形数据结构，满足以下性质：

• 堆是一棵完全二叉树；
• 堆中的每个节点都必须大于等于（或小于等于）其子节点。

Python 中的 heapq 模块提供了以下常用函数：

1. heapify(iterable)：
   • 将一个可迭代对象转化为堆，时间复杂度为O*(*n)。
   • 例如：heapq.heapify([3, 1, 4, 1, 5, 9])。
2. heappush(heap, item)：
   • 将一个元素加入堆中，时间复杂度为 O(logn)。
   • 例如：heapq.heappush([3, 1, 4, 1, 5, 9], 2)。
3. heappop(heap)：
   • 弹出堆中最小的元素，时间复杂度为 O(logn)。
   • 例如：heapq.heappop([1, 1, 3, 4, 5, 9])。
4. heapreplace(heap, item)：
   • 弹出堆中最小的元素，并将新元素加入堆中，时间复杂度为 O*(*logn)。
   • 例如：heapq.heapreplace([1, 1, 3, 4, 5, 9], 2)。
5. nlargest(n, iterable[, key])：
   • 返回可迭代对象中最大的 n 个元素，时间复杂度为 O*(*nlogk)，其中 k=min(n,len(iterable))。
   • 例如：heapq.nlargest(3, [1, 2, 3, 4, 5, 6, 7, 8, 9])。
6. nsmallest(n, iterable[, key])：
   • 返回可迭代对象中最小的 n 个元素，时间复杂度为 O*(*nlogk)，其中 k=min(n,len(iterable))。
   • 例如：heapq.nsmallest(3, [9, 8, 7, 6, 5, 4, 3, 2, 1])。

heapq 模块可以用于实现堆排序、优先队列等算法，同时也可以用于解决一些常见的算法问题，如求 top-k 问题、求中位数等。在使用 heapq 模块时，需要注意元素的比较方式，可以通过传递 key 参数来指定比较函数。

from heapq import * a = [1,2,3,4,5]
heapify(a)
a
#[1, 2, 3, 4, 5]heappush(a,-1)
a
#[-1, 2, 1, 4, 5, 3]heappop(a)
a
#[1, 2, 3, 4, 5]nlargest(3,a)
#[5, 4, 3]nsmallest(3,a)
#[1, 2, 3]

7.树（Tree）

数据类型常见操作

1.数字类型

• abs()：绝对值
• max()/min()：最大值/最小值
• pow(x,y)：x^y
• sqrt(x)：根号x

abs(-5)
#5max(1,3,6)
#6min(1,-1,4)
#-1pow(3,3)
#27import math
math.sqrt(9)
#3.0

2.布尔类型

bool(0)
#Falsebool(2)
#Truebool(-1)
#True

3.字符串类型

• len(s)：字符串长度，空格也算
• max(s)：最大字符
• max(s)：最小字符
• s.count(‘H’)：统计H的个数
• s.isupper()：是否为大写
• s.islower()：是否为小写
• s.isdigit()：是否为数字
• s.lower()：转换为小写
• s.upper()：转换为大写
• s.swapcase()：大小写转换
• s.split()：分割字符串

s="Hello world"len(s)
#11max(s)
#'w's.count("l")
#3s.isupper()
#Falses.islower()
#Falses.isdigit()
#Falses.lower()
#'hello world's.upper()
#'HELLO WORLD's.swapcase()
#'hELLO WORLD's.split()
#['Hello', 'world']

• s.strip()：去除两边字符串
• s.lstrip()：去除左边字符串
• s.rstrip()：去除右边字符串
• s.replace()：交换字符串。

注意：strip()不能去除字符串中间的空格，去除中间空格用replace()

a='   hello world   '
a.strip()
#'hello world'a.lstrip()
#'hello world   'a.rstrip()
#'   hello world'a.replace(' ','')
#'helloworld'

4.列表类型

a = [1,54,2,22,4]

• 增加
  • a.append(元素)
  • a.insert(位置,元素)

a.append(25)
a
#[1, 54, 2, 22, 4, 25]a.insert(0,2)
a
#[2, 1, 54, 2, 22, 4, 25]

• 更新
  • a[位置]=元素

a[0]=3
a
#[3, 1, 54, 2, 22, 4, 25]

• 删除
  • a.pop(位置) 默认最后元素
  • a.remove(元素)

a.pop()
#25a.remove(3)
a
#[1, 54, 2, 22, 4]

• 遍历

  • for x in a:

    ​ print(x)

  • for i in range(len(a)):

    ​ print(a[i])

  • b=[x**2 for x in a]:

    ​ print(x)

for x in a:print(x)
'''
1
54
2
22
4
'''for i in range(len(a)):print(a[i])
'''
1
54
2
22
4
'''b=[x**2 for x in a]
b
#[1, 2916, 4, 484, 16]

• len(l)：列表长度
• max(l)：最大元素，列表为同一类型
• max(l)：最小元素，列表为同一类型
• l.reverse()：翻转
• l.sort(reverse = True) ：降序排序
• in：元素是否再列表
• 切片
• l.clear()：清空列表

l=[1,2,3,4,5,6]
len(l)
#6max(l)
#6min(l)
#1l.reverse()
l
#[6, 5, 4, 3, 2, 1]l.sort(reverse = False) #降序
l
#[1, 2, 3, 4, 5, 6]4 in l
#Truel[0:2]
#[1, 2]l.clear()
l
#[]

5.元组类型

a=(1,1.5,'abc')

• 查找

a[0]
#1a[2]
#'abc'

• len(a)
• in
• 切片

len(a)
#31 in a
#Truea[0:2]
#(1, 1.5)

6.集合类型

• 增加
  • a.add()
  • a.update()
• 删除
  • a.remove()

a={1,1.5,'abc'}
a.add(2)
a
#{1, 1.5, 2, 'abc'}a.update({4,5})
a
#{1, 1.5, 2, 4, 5, 'abc'}a.remove(1.5)
a
#{1, 2, 4, 5, 'abc'}

• in
• 集合间的操作
  • a-b：a有b没有
  • a|b：a有或b有
  • a&b：a、b都有
  • a^b：a、b不同时有

a={1,2,3}
b={3,4,5}a-b
#{1, 2}a|b
#{1, 2, 3, 4, 5}a&b
#{3}a^b
#{1, 2, 4, 5}

7.字典类型

• 增/改
  • dict[key]=value
• 删
  • dict.pop(key)
• in
  • key in dict

s = {'age':18,'name':'小明'}s['age']=19
s
#{'age': 19, 'name': '小明'}s['city']='长沙'
s
#{'age': 19, 'name': '小明', 'city': '长沙'}s.pop('city')
s
#{'age': 19, 'name': '小明'}'age' in s
#True

• 遍历
  • key
  • value
  • k,v

for key in s:print(key)
#age
#namefor value in s.values():print(value)
#19
#小明for k,v in s.items():print(k,v)
#age 19
#name 小明