大灰羊
0%

数据结构与算法总结

发表于 更新于 分类于
本文字数： 7.7k 阅读时长 ≈ 7 分钟

数据结构与算法总结

一、数据结构

  • 单链表
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
# 链表
class Node:
	def __init__(self,item):
		self.item = item
		self.next = None
class Linklist:
	# 链表的创建
	def create_linkelist_head(li):
		# 头插法 -> 先将新结点的next指向head头结点 ，再将新结点设置为头结点head
		head = Node(li[0])
		for elem in li[1:]:
			node = Node(elem)
			node.next = head
			head = node
		return head

	def create_linklist_tail(li):
		# 尾插法 -> 通过头结点和尾部指针tail(总是指向最后一个结点) 
		head = Node(li[0])
		tail = head
		for elem in li[1:]:
			node = Node(elem)
			tail.next = node
			tail = node
		return tail

	# 链表的遍历
	def print_linklist(lk):
		while lk:
			print(lk.item)
			lk = lk.next
  • 双链表

2. 队列(Queue)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
"""
	队列：
		定义： 是一个数据集合，仅允许在列表的一端进行插入，另一端进行删除
			     插入的一端为 队尾 -> 入队或者进队 ，删除的一端为 队头 -> 出队
		性质 ： 先进先出(First-in,First-out)

"""
# 使用标准库的队列
from collections import deque

q = deque([1,2,3], 5) # 创建队列 第一个参数 将[1,2,3] 添加进队列里面，第二个参数控制队列长度 
q.append(1) # 队尾进队
print(q.popleft()) # 队首出队

# 用于双向队列
q.appendleft(1) # 队首进队
q.pop() # 队尾出队

# 队列实现Linux的tail命令 : 打印一个文件的后几行内容
def tail(n):
	with open("xxx.txt","r") as f:
		q = deque(f,n):
		return q
print(q)

3. 栈(Stack)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Stack:
	def __init__(self):
		self.stack = []

	def push(self,elem):
		self.stack.append(elem)

	def pop(self):
		return self.stack.pop()

	def get_top(self):
		if len(self.stack) > 0:
			return self.stack[-1]
		else:
			return None
	def is_empty(self):
		return len(self.stack) == 0

4. 哈希表(Hash Table)

1

5.树(Tree)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
from squeue import *
# 利用顺序队列实现树的层次遍历
"""
    二叉树的简单实践
        思路：
            1.使用链式存储, 一个Node表示一个结点
            2.结点使用两个属性变量表示树的左右子树，即左连接和右连接
"""
# 二叉树结点
class Node:
    # 初始化结点
    def __init__(self,val,right = None,left = None):
        self.val = val
        self.right = right
        self.left = left

# 二叉树遍历类
class Bitree:
    def __init__(self,root = None):
        self.root = root

    # 先序遍历
    def preorder(self,node):
        if node is None:    # 中止条件
            return
        print(node.val,end="")
        self.preorder(node.left)
        self.preorder(node.right)


    # 中序遍历
    def inorder(self,node):
        if node is None:
            return
        self.inorder(node.left)
        print(node.val,end="")
        self.inorder(node.right)

    # 后续遍历
    def postorder(self,node):
        if node is None:
            return
        self.postorder(node.left)
        self.postorder(node.right)
        print(node.val,end = "")

    def levelorder(self,node):
        sq = Squeue()
        sq.enqueue(node)
        while not sq.is_empty():
            ndoe = sq.dequeue()
            print(node.val,end = "")
            if node.left:
                sq.dequeue(node.left)
            if node.right:
                sq.dequeue(node.right)

二、算法

1. 查找

  • 顺序查找(Linear Search)

  • 二分查找(Binary Search)

    思路： 二分查找需要在已排好序的列表中进行 

1
2
3
4
5
6
7
8
9
10
11
12
13
def binart_search(li,val):
	low = 0
	high = len(li) - 1
	while low <= high:
		mid = (low + high) // 2
		if li[mid] == val:
			return mid
		elif li[mid] > val:
			high = mid - 1
		else:
			low = mid + 1
	return None

2.排序

  • 基本

    • 冒泡排序(Bubble Sort)
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    def bubble_sort1(li):
    	for i in range(len(li) - 1):
    		exchange = False
    		for j in range(len(li) - i - 1):
    			if li[j] > li[j + 1]:
    				li[j],li[j+ 1] = li[j + 1],li[j]
    				exchange = True
    		if not exchange:
    			return
    • 选择排序(Select Sort)
      • 思路：循环n-1趟，每趟记录最小值的下标，结束后进行元素交换
    1
    2
    3
    4
    5
    6
    7
    8
    def select_sort(li):
    	for i in range(len(li) - 1):
    		min_loc = i
    		for j in range(i + 1,len(li)):
    			if li[j] < li[min_loc]:
    				min_loc = j
    		if min_loc != i:
    			li[i],li[min_loc] = li[min_loc],li[i]
    • 插入排序(Insert Sort)
      • 思路：记录下有序区的最后一张牌，与之后无序区的元素进行比较，在将其插入到合适的位置
    1
    2
    3
    4
    5
    6
    7
    8
    def insert_sort(li):
    	for i in range(1,len(li)):
    		tmp = li[i]
    		j = i - 1
    		while j >= 0 and li[j] > tmp:
    			li[j + 1] = li[j]
    			j -= 1
    		li[j + 1] = tmp

  • 高阶

    • 归并排序(Merge Sort)
      • 思路：是利用归并的思想实现的排序方法，该算法采用经典的分治（divide-and-conquer）策略（分治法将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案”修补”在一起，即分而治之)
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    def merge(li,low,mid,high):
    	i = low
    	j = mid + 1
    	ltmp = []
    	while i <= mid and j <= high:
    		if li[i] > li[j]:
    			ltmp.append(li[j])
    			j += 1
    		else:
    			ltmp.append(li[i])
    			i += 1
    	while i <= mid:
    		ltmp.append(li[i])
    		i += 1
    	while j <= high:
    		ltmp.append(li[j])
    		j += 1
    	li[low:high + 1] = ltmp

    def merge_sort(li,low,high):
    	if low < high:
    		mid = (low + high) // 2
    		merge_sort(li,low,mid)
    		merge_sort(li,mid + 1,high)
    		merge(li,low,mid,high)

    • 快速排序(Quick Sort)

      • 快速排序算法是冒泡排序的一种改进，快速排序也是通过逐渐消除待排序的无序序列中逆序元素来实现排序的

        算法思想：

        (1) 我们从待排序的记录序列中选取一个记录(通常第一个)作为基准元素(称为key)key=arr[left]，然后设置两个变量，left指向数列的最左部，right指向数据的最右部。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    def partition(li,left,right):
    	tmp = li[left]
    	while left < right:
    		while left <= right and li[right] > tmp:
    			right -= 1
    		li[left],li[right] = li[right],li[left]
    		while left <= right and li[left] < tmp:
    			left += 1
    		li[right],li[left] = li[left] ,li[right]
    	li[left] = tmp
    	return left
    def quick_sort(li,left,right):
    	if left < right:
    		mid = partition(li,left,right)
    		quick_sort(li,left,mid)
    		quick_sort(li,mid + 1,right)

    • 希尔排序(Shell Sort)

      • 思路：基于插入排序优化效率，缩短了时间
        • 1、时间复杂度
          最好情况：o(nlogn)
      最坏情况：o(n^2)
          2、算法思想：
          （1）待排序序列分成多个子序列；
          （2）每个子序列进行直接插入排序；
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      def shell_sort_gap(li,gap):
      	for i in range(gap,len(li)):
      		tmp = li[i]
      		j = i - gap
      		while j >= 0 and li[j] > tmp:
      			li[j + gap] = li[j]
      			j -= gap 
      		li[j + gap] = tmp
      def shell_sort(li):
      	d = len(li) // 2
      	while d >= 1:
      		shell_sort_gap(li,d)
      		d //= 2

3.贪心算法

  • 背包问题
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
"""
	思路:
		贪心 —> 先拿最多最有价值的物品，最后拿价值最小的物品
"""

goods = [(60,10),(100,20),(120,30)] # 三个物品的 价格 重量
goods.sort(key = lambda x : x[0] / x[1],reverse = True) # 按照单价从大到小排序
def fractional_backpack(goods,w):
	m = [0 for _ in range(len(goods))] # 存物品的个数
	total_value = 0 # 存总价值
	for i , (price,weight) in enumerate(goods):
		if w >= weight: # 背包容量大于物品重量 -> 全拿
			m[i] = 1
			total_value += price
			w -= weight
		else: # w < weight 背包容量小于物品重量 -> 能拿多少拿多少
			m[i] =  w / weight 
			total_value += w / weight * price
			break
	return m,total_value
print(fractional_backpack(goods,10))

  • 活动选择问题
1
2
3
4
5
6
7
8
9
10
11
12
activities = [(1,4),(3,5),(0,6),(5,7),(5,9),(6,10),(8,11),(8,12),(2,14),(12,16)]
activities.sort(key = lambda x : x[1])

def activities_selection(a):
	res = [a[0]]
	for i in range(1,len(a)):
		if a[i][0] >= res[-1][1]: # 当前活动的开始时间小于最后一个活动的结束时间 -> 不冲突
			res.append(a[i])
		
	return res
print(activities_selection(activities))

  • 拼接最大数字问题
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
"""
	有n个非负整数，降旗按照字符串拼接的方式拼接为一个整数，求其最大值

		思路:
			按照字符串首位大小进行排序 
			注: 当 a = "1286" b = "128" a + b > b + a
			 	当 a = "7286" b = "728" 	a + b < b + a

"""


from functools import cmp_to_key

li = [32,94,128,1286,6,71]

def xy_cmp(x,y):
	if x + y < y + x:
		return 1
	elif x + y > y + x:
		return -1
	else:
		return 0
 
def numbers_join(li):
	li = list(map(str,li)) 
	li.sort(key = cmp_to_key(xy_cmp))
	return "".join(li)

print(numbers_join(li))

4. 动态规划

  • 最长公共子序列
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
'''
1143. 最长公共子序列
给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。

一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。

例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。
两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。

 

示例 1：

输入：text1 = "abcde", text2 = "ace" 
输出：3  
解释：最长公共子序列是 "ace" ，它的长度为 3 。
示例 2：

输入：text1 = "abc", text2 = "abc"
输出：3
解释：最长公共子序列是 "abc" ，它的长度为 3 。
示例 3：

输入：text1 = "abc", text2 = "def"
输出：0
解释：两个字符串没有公共子序列，返回 0 。'''

def longCommonSubsequence(m,n):
	x = len(m)
	s = len(n)
	lst = [[0 for _ in range(s + 1)] for _ in range(x + 1)]
	# for _ in lst:
	# 	print(_)
	for i in range(1,x + 1):
		for j in range(1,s + 1):
			if m[i - 1] == n[j - 1]:	# 最后一位匹配 ，看左上角
				lst[i][j] = lst[i - 1][j - 1] + 1
			else:
				lst[i][j] = max(lst[i - 1][j],lst[i][j - 1])
	# print()
	# for _ in lst:
	# 	print(_)
	return lst[x][s]


def longestCommonSubsequence(text1: str, text2: str) -> int:
        m, n = len(text1), len(text2)
        dp = [[0] * (n + 1) for _ in range(m + 1)]
        
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if text1[i - 1] == text2[j - 1]:
                    dp[i][j] = dp[i - 1][j - 1] + 1
                else:
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
        
        return dp[m][n]

# 重构解 -> 回溯法
def LCS(x,y):
	m,n = len(x),len(y)
	c = [[0] * (n + 1) for _ in range(m + 1)]
	b = [[0] * (n + 1) for _ in range(m + 1)]
	for i in range(1,m + 1):
		for j in range(1,n + 1):
			# 1 表示最后一个元素相等，从左上方拿最大值 
			# 2 表示最后一位不相同，从左边拿最大值
			# 3 表示最后一位不相同，从上方拿到最大值
			if x[i - 1] == y[j - 1]:
				c[i][j] = c[i - 1][j - 1]
				b[i][j] = 1
			elif c[i][j - 1] > c[i - 1][j]:
				c[i][j] = c[i][j - 1]
				b[i][j] = 2
			else:
				c[i][j] = c[i - 1][j]
				b[i][j] = 3

	return c[m][n] , b


def LCS_trackback(x,y):
	c , b = LCS(x,y)
	i = len(x)
	j = len(y)
	lst = []
	while i > 0 and j > 0:
		if b[i][j] == 1: # 最后一位匹配，
			lst.append(x[i-1])
			i -= 1
			j -= 1
		elif b[i][j] == 2: # 不匹配 来自于左方
			j -= 1
		else: # == 3 来自于上方
			i -= 1
	s = "".join(reversed(lst))
	return s


print(LCS_trackback("abcde","ace"))