跳转至

算法

第一章、基本概念

算法是一种解决问题的方法和步骤集合。在计算机科学中，算法是指通过有限的步骤来解决问题的方法，它是计算机程序的核心。

在算法学中，时间复杂度和空间复杂度是衡量算法优劣的两个重要指标。其中，时间复杂度表示算法执行所需的时间；空间复杂度表示算法执行所需的内存空间。

数据结构是一种在计算机中组织和存储数据的方式。常见的数据结构包括数组、链表、栈、队列、哈希表、树等。

第二章、数据结构

2.1 数组

数组是一种线性数据结构，它由一组连续的内存空间组成，每个元素都可以通过下标来访问。数组的访问时间复杂度为O(1)，但插入和删除操作的时间复杂度较高，为O(n)。

例如，下面是一个包含5个元素的数组：

Python
1
arr = [1, 2, 3, 4, 5]

2.2 链表

链表也是一种线性数据结构，它由一组通过指针相连的节点组成，每个节点包含两个部分：数据和指向下一个节点的指针。链表的访问时间复杂度为O(n)，但插入和删除操作的时间复杂度较低，为O(1)。

例如，下面是一个包含5个节点的链表：

Python
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Node:
    def __init__(self, val):
        self.val = val
        self.next = None

head = Node(1)
node1 = Node(2)
node2 = Node(3)
node3 = Node(4)
node4 = Node(5)

head.next = node1
node1.next = node2
node2.next = node3
node3.next = node4

2.3 栈

栈是一种基于先进后出（LIFO）原则的线性数据结构，它可以用数组或链表实现。栈只允许在表尾进行插入和删除操作，即压入和弹出操作，时间复杂度均为O(1)。

例如，下面是一个用数组实现的栈：

Python
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Stack:
    def __init__(self):
        self.data = []

    def push(self, val):
        self.data.append(val)

    def pop(self):
        if not self.is_empty():
            return self.data.pop()

    def is_empty(self):
        return len(self.data) == 0

2.4 队列

队列是一种基于先进先出（FIFO）原则的线性数据结构，它可以用数组或链表实现。队列只允许在表头进行删除操作，即出队操作；在表尾进行插入操作，即入队操作。时间复杂度均为O(1)。

例如，下面是一个用数组实现的队列：

Python
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Queue:
    def __init__(self):
        self.data = []
        self.front = 0

    def enqueue(self, val):
        self.data.append(val)

    def dequeue(self):
        if not self.is_empty():
            val = self.data[self.front]
            self.front += 1
            return val

    def is_empty(self):
        return len(self.data) == self.front

2.5 哈希表

哈希表是一种基于散列表（Hash Table）实现的数据结构。它通过将键值映射到一个固定长度的数组中来实现。哈希表的插入、查找和删除操作的时间复杂度均为O(1)，但空间复杂度较高。

例如，下面是一个用字典实现的哈希表：

Python
1
2
3
4
hash_table = {}
hash_table['key1'] = 'val1'
hash_table['key2'] = 'val2'
hash_table['key3'] = 'val3'

2.6 树

树是一种非线性的数据结构，它由若干个节点组成，每个节点可以有若干个子节点，节点之间存在一定的层次关系。树的遍历方式有前序遍历、中序遍历和后序遍历等。树的时间复杂度取决于其深度，通常为O(log n)。

例如，下面是一个二叉树的定义：

Python
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

root = TreeNode(1)
node1 = TreeNode(2)
node2 = TreeNode(3)
node3 = TreeNode(4)
node4 = TreeNode(5)

root.left = node1
root.right = node2
node1.left = node3
node2.right = node4

第三章、排序算法

3.1 冒泡排序

冒泡排序是一种交换排序方法，它的基本思想是比较相邻两个元素的大小，如果左边的元素大于右边的元素，则交换它们的位置，直至排序完成。冒泡排序的时间复杂度为O(n^2)。

例如，下面是一个用python实现的冒泡排序：

Python
1
2
3
4
5
6
7
def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(n-i-1):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
    return arr

3.2 选择排序

选择排序是一种选择最小值的排序方法，它的基本思想是从未排序的部分中找到最小值并将其放到已排序的部分的末尾，直至排序完成。选择排序的时间复杂度为O(n^2)。

例如，下面是一个用python实现的选择排序：

Python
1
2
3
4
5
6
7
8
9
def selection_sort(arr):
    n = len(arr)
    for i in range(n):
        min_idx = i
        for j in range(i+1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]
    return arr

3.3 插入排序

插入排序是一种将未排序的元素插入到已排序的部分的相应位置的排序方法，它的基本思想是将一个新元素插入到已排序的序列中，使得插入后的序列仍然有序。插入排序的时间复杂度为O(n^2)。

例如，下面是一个用python实现的插入排序：

Python
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
def insertion_sort(arr):
    n = len(arr)
    for i in range(1, n):
        key = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > key:
            arr[j+1] = arr[j]
            j -= 1
        arr[j+1] = key
    return arr

3.4 快速排序

快速排序是一种分治的排序方法，它的基本思想是选择一个基准值（pivot），将序列中小于等于基准值的元素放在基准值左边，大于等于基准值的元素放在基准值右边，然后对左右两个子序列分别进行递归排序，直至排序完成。快速排序的时间复杂度为O(nlogn)。

例如，下面是一个用python实现的快速排序：

Python
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
def quick_sort(arr, left, right):
    if left < right:
        pivot = partition(arr, left, right)
        quick_sort(arr, left, pivot-1)
        quick_sort(arr, pivot+1, right)
    return arr

def partition(arr, left, right):
    pivot = arr[left]
    while left < right:
        while left < right and arr[right] >= pivot:
            right -= 1
        arr[left] = arr[right]
        while left < right and arr[left] <= pivot:
            left += 1
        arr[right] = arr[left]
    arr[left] = pivot
    return left

第四章、查找算法

4.1 顺序查找

顺序查找也称为线性查找，它的基本思想是从序列的头部开始依次查找，直至找到目标值或遍历完整个序列。它的时间复杂度为O(n)。

例如，下面是一个用python实现的顺序查找：

Python
1
2
3
4
5
def sequential_search(arr, target):
    for i in range(len(arr)):
        if arr[i] == target:
            return i
    return -1

4.2 二分查找

二分查找也称为折半查找，它的基本思想是将有序序列均分成两个部分，如果中间值等于目标值，则返回中间值的位置；否则根据中间值与目标值的大小关系，在左半部分或右半部分继续进行查找，直至找到目标值或子序列长度为1。二分查找的时间复杂度为O(log n)。

例如，下面是一个用python实现的二分查找：

Python
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
def binary_search(arr, target):
    left, right = 0, len(arr)-1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

第五章、图论算法

5.1 深度优先遍历

深度优先遍历（Depth First Search, DFS）是一种图遍历的算法，它的基本思想是尽可能深地搜索图的各个分支。DFS可以用递归或栈来实现。

例如，下面是一个用python实现的深度优先遍历：

Python
1
2
3
4
5
6
7
8
def dfs(graph, start, visited=None):
    if visited is None:
        visited = set()
    visited.add(start)
    print(start)
    for next in graph[start] - visited:
        dfs(graph, next, visited)
    return visited

5.2 广度优先遍历

广度优先遍历（Breadth First Search, BFS）是一种图遍历的算法，它的基本思想是从起点开始，先访问所有邻接点，再按照相同的方式访问所有与邻接点相邻但未访问过的点，以此类推，直至遍历完整个图。BFS可以用队列来实现。

例如，下面是一个用python实现的广度优先遍历：

Python
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])
    visited.add(start)
    while queue:
        node = queue.popleft()
        print(node)
        for next in graph[node] - visited:
            visited.add(next)
            queue.append(next)

第六章、动态规划算法

6.1 最长公共子序列

最长公共子序列（Longest Common Subsequence, LCS）是指在两个序列中都出现的最长子序列。例如，在序列“ABCDGH”和“AEDFHR”中，最长公共子序列是“ADH”，长度为3。

最长公共子序列问题可以通过动态规划算法来解决。其基本思路是：将待求解的问题分成若干个子问题，先求解子问题，再通过子问题的解得到原问题的解。在最长公共子序列问题中，使用一个二维数组来存储子问题的解，其中dp[i][j]表示序列s1前i个元素和序列s2前j个元素的最长公共子序列长度。如果s1[i-1] == s2[j-1]，则dp[i][j] = dp[i-1][j-1] + 1；否则dp[i][j] = max(dp[i-1][j], dp[i][j-1])。

例如，下面是一个用python实现的最长公共子序列：

Python
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
def longest_common_subsequence(s1, s2):
    m, n = len(s1), len(s2)
    dp = [[0] * (n+1) for _ in range(m+1)]
    for i in range(1, m+1):
        for j in range(1, n+1):
            if s1[i-1] == s2[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]

第七章、贪心算法

7.1 零钱兑换

假设你有无限数量的各种不同面值的硬币，现在需要计算出最少需要多少个硬币才能凑出给定的金额。例如，总金额为11，可以通过1、2、5三种面值的硬币凑出，其中最少需要3个硬币。

零钱兑换问题可以通过贪心算法来解决。其基本思路是：先选用面值最大的硬币，然后依次选用面额递减的硬币，直至凑够要求的金额。如果当前选择的硬币不能凑成剩余的金额，就退回到上一枚硬币，选取面值更小的硬币继续尝试。需要注意的是，贪心算法只能在特定条件下得到最优解。

例如，下面是一个用python实现的零钱兑换：

Python
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
def coin_change(coins, amount):
    coins.sort(reverse=True)
    count = 0
    for coin in coins:
        if amount == 0:
            return count
        if coin <= amount:
            count += amount // coin
            amount = amount % coin
    return -1 if amount != 0 else count

第八章、回溯算法

8.1 八皇后问题

八皇后问题是一个经典的回溯算法问题，它的基本思想是在8×8的棋盘上放置8个皇后，使得每个皇后都不能互相攻击。即任意两个皇后不能处于同一行、同一列或同一斜线上。

八皇后问题可以通过回溯算法来解决。其基本思路是：考虑到每个皇后必须放在不同的行上，所以可以使用一个数组来表示每个皇后的位置。在放置第i个皇后时，从第i行开始，依次尝试放置在每一列上，并判断当前位置是否合法（即不在同一行、同一列或同一斜线上），如果合法则继续放置下一个皇后；如果不合法，则回溯到上一个状态，继续尝试下一个位置。如果所有皇后都放置完成，则得到一个可行解。

例如，下面是一个用python实现的八皇后问题：

Python
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
def conflict(state, nextX):
    nextY = len(state)
    for i in range(nextY):
        if abs(state[i]-nextX) in (0, nextY-i):
            return True
    return False

def queens(num=8, state=()):
    for pos in range(num):
        if not conflict(state, pos):
            if len(state) == num-1:
                yield (pos,)
            else:
                for result in queens(num, state+(pos,)):
                    yield (pos,) + result

print(list(queens(8)))