进入电子信息相关行业，掌握常用数据结构与算法是基础能力。本文是系列讲解视频的学习总结，以备后续回顾提升。
数据结构
算法的时间复杂度
1、什么是时间复杂度
指算法的执行效率，算法的执行时间与算法的输入值之间的关系。
def test(num): # 输入num，决定循环次数，即问题规模N
total = 0 # 执行时间a
for i in range(num):
total += i # 执行时间b
return total # 执行时间c
O(a+N*b+c)=O(N)
2、大O表示法
常用时间复杂度案例分析
O(1)
def O1(num):
i = num # a
j = num*2 # b
return i + j
算法执行时间a+b,执行时间与num无关系,所以该算法时间复杂度为O(1)。
没有循环一般为O(1).
O(log n)
def OlogN(num):
i = 1 # a
while (i<num): # N
i = i*2 # 该语句执行时间为b，i以2倍速度增长，循环次数n满足2^n =N，即$n=log_2(N)$
return i
执行时间 b * logN，时间复杂度O(log N)。
O(n)
def ON(num):
total = 0
for i in range(num): # num = N
total += i # b
return total
有循环结构，不为O(1)，只看循环体复杂度就好了。执行时间Nb，O(Nb)=O(N)。
O(n log n)
def ONlogN(num1,num2):
total = 0
j = 0
for i in range(num1): #M
while(j<num2): # N (a+b)log N
total += i + j #a
j = j * 2 #b
return total
O(M* (a+b)log N) = O(MlogN) -> O(NlogN)
O(n^2)
def ON2(num):
total = 0
for i in range(num): # N
for j in range(num): # N
total += i + j # a
return total
O(aN^2)=O(n^2)
O(M+N)
def OMN(num1,num2):
total = 0
for i in range(num1): #M
total += i # a
for j in range(num2): # N
total += j # b
return total
O(aM+bN)=O(M+N)
3、复杂度比较
O(1) < O(log N) < O(N) < O(N log N) < O(N^2) < O(2^N) < O(n!)
算法的空间复杂度
一般一个算法的时间复杂度和空间复杂度都要进行评估。
1、什么是空间复杂度
指算法的存储空间与输入值之间的关系。
def test(num):
total = 0 # total占存储空间设为a
for i in range(num):
total += i #total只占int，存储空间不变
return total
空间复杂度 O(1)
def test(nums):
array = [] # total占存储空间为list
for num in nums:
array.append(num) #array占空间与nums元素个数成正比
return array
空间复杂度 O(N)
2、常用空间复杂度
一般关注O(1) 、O(N)，很少关注O(N^2)、O(logN)、O(N log N)。
实际分析查看变量，变量为常量，O(1)，比如 total。如果是数组，多个数集合在一起，可能为O(N)、O(N^2)。
此外，需要关注递归，存在递归栈保存信息，一般为O(N)。
O(1) < O(N) < O(N^2)
工作面试时，可考虑两种算法都写出来，与面试官交流。实际工作中，一般考虑时间复杂度最优，因为目前存储设备成本一般较时间成本低。
数组
数组：在连续的内存空间中，存储一组相同类型的元素。
区分元素与索引，元素指数组的值，索引指该值的编号，从0开始。
区分数组的访问和搜索，a = [1,2,3]，访问第二个元素：a[1]=2，访问指通过索引取值；搜索指查找元素对应的索引。
数据结构的四大基本操作，需要记住其时间复杂度。对比不同数据结构，就是考虑四种基本操作的时间复杂度。
访问 Access O(1)
搜索 Search O(N)
插入 Insert O(N)
删除 Delete O(N)
特点：适合读多写少
常用操作
# 1、创建数组
# python需要注意是同类型数据
a = []
# 2、添加元素
# 时间复杂度 O(1)
a.append(1)
a.append(2)
a.append(3)
# [1,2,3]
print(a)
# 3、插入元素
# 时间复杂度 O(N)
a.insert(2,99)
# [1,2,99,3]
print(a)
# 4、访问元素
# 时间复杂度O(1)
temp = a[2]
# 99
print(temp)
# 5、更新元素
# 时间复杂度 O(1)
a[2] =88
# [1,2,88,3]
print(a)
# 6、删除元素
# remove 方法 ，时间复杂度O(N)
a.remove(88)
# [1,2,3]
print(a)
# pop方法，时间复杂度
a.pop(1) # O(N)
# [1,3]
print(a)
a.pop() # 删除最后一个元素，O(1)
# [1]
print(a)
# 7、获取数组长度
a = [1,2,3]
size = len(a)
# 3
print(size)
# 8、遍历数组
# 时间复杂度 O(N)
for i in a:
print(i)
for index,element in enumerate(a):
print("Index at",index,"is :",element)
for i in range(0,len(a)):
print("i:",i,"element:",a[i])
# 9、查找元素
# 时间复杂度 O(N)
index = a.index(2) # 找到元素2的索引
# 1
print(index)
# 10、数组排序
# 时间复杂度 O(N log N)
# 从小到大
a = [3,1,2]
a.sort()
#[1,2,3]
print(a)
# 从大到小
a.sort(reverse=True) # python3.8之后没有该参数，使用a.reverse()永久地修改原有的列表、元组等可迭代对象
# [3,2,1]
print(a)
练习题
给定一个二进制数组 nums ， 计算其中最大连续 1 的个数。
示例 1：
- 输入：nums = [1,1,0,1,1,1]
- 输出：3
解释：开头的两位和最后的三位都是连续 1 ，所以最大连续 1 的个数是 3.
示例 2:
- 输入：nums = [1,0,1,1,0,1]
- 输出：2
提示：
- 1 <= nums.length <= 105
- nums[i] 不是 0 就是 1.
分析
写一个特例分析，分析所需变量，设计算法（伪代码），翻译伪代码。
# 伪代码
func(nums) -> int:
if nums is null or nums.length == 0:
return 0
count = 0
result = 0
for ( i = 0; i < nums.length; i ++):
if nums[i] == 1:
count = count +1
else :
result = max(result,count)
count =0
return max(result,count)
# python
class Solution:
# Time Complexity: O(N)
# Space Complexity: O(1)
def findMaxConsecutiveOnes(self,nums):
"""
:type nums: List[int]
:rtype: int
"""
if nums is None or len(nums) == 0:
return 0
count = 0
result = 0
for num in nums:
if num == 1:
count += 1
else:
result = max(result,count)
count = 0
return max(result,count)
链表
单端链表
单端链表由一系列节点组成，节点包含元素和指向下一个节点的next指针。双端链表不同的是多了prev指针，可以从表头到表尾或表尾到表头两个方向遍历或迭代链表。
访问 Access O(N)
搜索 Search O(N)
插入 Insert O(1)
删除 Delete O(1)
特点：适合读少写多
常用操作
from collections import deque
# 1、创建链表
linkedlist = deque()
# 2、添加元素
# 时间复杂度 O(1)
linkedlist.append(1)
linkedlist.append(2)
linkedlist.append(3)
# [1,2,3]
print(linkedlist)
# 3、插入元素
# 时间复杂度 O(N)
linkedlist.insert(2,99)
# [1,2,99,3]
print(linkedlist)
# 4、访问元素
# 时间复杂度 O(N)
element = linkedlist[2]
# 99
print(element)
# 5、搜索元素
# 时间复杂度 O(N)
index = linkedlist.index(99)
# 2
print(index)
# 6、更新元素
# 时间复杂度 O(N)
linkedlist[2] = 88
# [1,2,88,3]
print(linkedlist)
# 7、删除元素
# 时间复杂度 O(N)
# del linkedlist[2] # 删除索引对应元素
linkedlist.remove(88) #删除元素
# [1,2,3]
print(linkedlist)
# 8、获取链表长度
# 时间复杂度 O(1)
length = len(linkedlist)
# 3
print(length)
练习题
给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。
示例 1：
- 输入：head = [1,2,6,3,4,5,6], val = 6
- 输出：[1,2,3,4,5]
示例 2：
- 输入：head = [], val = 1
- 输出：[]
示例 3：
- 输入：head = [7,7,7,7], val = 7
- 输出：[]
提示：
- 列表中的节点数目在范围 [0, 104] 内
- 1 <= Node.val <= 50
- 0 <= val <= 50
# 伪代码
func(head,val) -> linkedlist:
dummy = listnode(0)
dummy.next = head
prev = dummy
while(head != null )
if (head.val == val):
prev.next = head.next
head = head.next
else:
prev = head
head = head.next
return dummy.next
class Solution:
# N为链表大小
# 时间复杂度 O(N)
# 空间复杂度 O(1)
def removeElement(self,head : ListNode,val : int) -> ListNode:
dummy = ListNode(0)
dummy.next = head
prev = dummy
while head is not None:
if head.val == val:
prev.next = head.next
else:
prev = prev.next
head = head.next
return dummy.next
...