数据结构与算法-4算法策略

1
2
3
4
5
6
7
8
9

def two_sum(nums, target):
    """哈希表优化：O(n) 时间复杂度"""
    seen = {}
    for i, num in enumerate(nums):
        complement = target - num
        if complement in seen:
            return [seen[complement], i]
        seen[num] = i
    return []

1
2
3

原数组：[4, 5, 3₁, 3₂, 2, 9, 0]
稳定排序结果：[0, 2, 3₁, 3₂, 4, 5, 9]  ✓ 两个 3 的顺序保持不变
不稳定排序结果：[0, 2, 3₂, 3₁, 4, 5, 9]  ✗ 两个 3 的顺序可能改变

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

def selection_sort(nums: list[int]):
    n = len(nums)
    # 外循环：未排序区间为 [i, n-1]
    for i in range(n - 1):
        # 内循环：找到未排序区间内的最小元素
        min_index = i
        for j in range(i + 1, n):
            if nums[j] < nums[min_index]:
                min_index = j  # 记录最小元素的索引
        # 将该最小元素与未排序区间的首个元素交换
        nums[i], nums[min_index] = nums[min_index], nums[i]


alist = [54, 226, 93, 17, 77, 31, 44, 55, 20]
selection_sort(alist)
print(alist)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

def bubble_sort(nums: list[int]):
    n = len(nums)
    # 外循环：未排序区间为 [0, i]
    for i in range(n - 1, 0, -1):
        swapped = False
        # 内循环：将未排序区间 [0, i] 中的最大元素交换至该区间的最右端
        for j in range(i):
            if nums[j] > nums[j + 1]:
                # 交换 nums[j] 与 nums[j + 1]
                nums[j], nums[j + 1] = nums[j + 1], nums[j]
                swapped = True
        if not swapped:  # 提前终止优化
            break


alist = [54, 226, 93, 17, 77, 31, 44, 55, 20]
bubble_sort(alist)
print(alist)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

def insertion_sort(nums: list[int]):
    # 从第二个元素位置开始，每轮循环结束，前 i 个元素都是排好序的
    for i in range(1, len(nums)):
        base = nums[i]  # 相当于右手上待找到正确位置的牌
        j = i - 1
        # 往前查找位置
        while j >= 0 and nums[j] > base:
            nums[j + 1] = nums[j]  # 将 nums[j] 向右移动一位
            j -= 1
        nums[j + 1] = base  # 将 base 赋值到正确位置


alist = [54, 26, 93, 17, 77, 31, 44, 55, 20]
insertion_sort(alist)
print(alist)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

def shell_sort(nums: list[int]):
    n = len(nums)
    # 将步长初始化为列表长度整除 2
    gap = n // 2

    while gap > 0:
        for i in range(gap, n):
            j = i

            # 根据条件交换元素
            # 确保相距一个步长的两个元素是前小后大
            while j >= gap and nums[j - gap] > nums[j]:
                nums[j - gap], nums[j] = nums[j], nums[j - gap]
                j -= gap
                # j 减去一个 gap 再进入 while 循环
                # 因为列表长度很长，可能会有好几个的 gap

        # 缩小步长，直到最大步长等于 0 为止
        gap = gap // 2


nums = [54, 26, 93, 17, 77, 31, 44, 55, 20]
shell_sort(nums)
print(nums)

 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

def partition(nums: list[int], left: int, right: int) -> int:
    """哨兵划分"""
    # 以 nums[left] 为基准数
    i, j = left, right
    while i < j:
        while i < j and nums[j] >= nums[left]:
            j -= 1  # 从右向左找首个小于基准数的元素
        while i < j and nums[i] <= nums[left]:
            i += 1  # 从左向右找首个大于基准数的元素
        # 元素交换
        nums[i], nums[j] = nums[j], nums[i]
    # 将基准数交换至两子数组的分界线
    nums[i], nums[left] = nums[left], nums[i]
    return i  # 返回基准数的索引


def quick_sort(nums: list[int], left: int, right: int):
    """快速排序"""
    # 子数组长度为 1 时终止递归
    if left >= right:
        return
    # 哨兵划分
    pivot = partition(nums, left, right)
    # 递归左子数组、右子数组
    quick_sort(nums, left, pivot - 1)
    quick_sort(nums, pivot + 1, right)


nums = [54, 26, 93, 17, 77, 31, 44, 55, 20]
quick_sort(nums, 0, len(nums) - 1)
print(nums)

 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

class mysort():
    def set_random_pivot(self, nums, low, high):
        """
        随机选择基准值
        再将基准值与数组的第一个元素互换
        """
        pivot = random.randint(low, high)
        nums[low], nums[pivot] = nums[pivot], nums[low]
        return nums

    def partition(self, nums, low, high):
        """
        快速排序核心内容
        找到基准值的“正确”位置
        """
        # 取出基准值
        pivot = nums[low]
        # 设置左右指针
        left, right = low, high
        while left < right:
            # 先让 right 指针向左移动寻找小于基准值的位置
            while left<right and nums[right]>=pivot:    #注意这里的右指针是大于等于基准值时均可向左移动
                right -= 1
            nums[left] = nums[right]

            # 再让 left 指针向右移动寻找大于基准值的位置
            while left<right and nums[left]<=pivot:
                left += 1
            nums[right] = nums[left]

        # 之后将基准值放在 left 指向的位置
        nums[left] = pivot

        # 返回安放好的基准值的位置 left
        return left

    def quickly_sort(self, nums, low, high):
        """
        递归完成排序
        """
        if low >= high:    #注意这个停止条件，low 需要与 high 重合或者超过它
            return

        # nums = self.set_random_pivot(nums, low, high)    #随机选择基准值【可选】
        ind = self.partition(nums, low, high)

        self.quickly_sort(nums, low, ind-1)    #ind左侧排序
        self.quickly_sort(nums, ind+1, high)    #ind右侧排序

        return nums

nums = [3,2,1,5,6,4]
nums = [3,2,3,1,2,4,5,5,6]
mysort().quickly_sort(nums, 0, len(nums)-1)

 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

def quick_sort(alist, start, end):
    # 递归的退出条件
    if start >= end:
        return

    # 设定起始元素为要寻找位置的基准元素
    mid = alist[start]

    # low 为序列左边的【由左向右移动的游标】
    low = start
    # high 为序列右边的【由右向左移动的游标】
    high = end

    while low < high:
        # 如果游标未重合
        # high 游标向左寻找小于基准元素的元素
        while low < high and alist[high] >= mid:
            high -= 1
        # 游标重合或者找到了元素
        alist[low] = alist[high]

        # 如果游标未重合
        # low 游标向右寻找大于基准元素的元素
        while low < high and alist[low] <= mid:
            low += 1
        # 游标重合或者找到了元素
        alist[high] = alist[low]

    # 退出循环后，low 与 high 游标重合
    # 此时两游标所指位置为【基准元素的正确位置】
    alist[low] = mid

    # 对基准元素左边的子序列进行快速排序
    quick_sort(alist, start, low-1)
    # 对基准元素右边的子序列进行快速排序
    quick_sort(alist, low+1, end)


alist = [54,26,93,17,77,31,44,55,20]
quick_sort(alist,0,len(alist)-1)
print(alist)

 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

# 归并排序
def merge_sort(alist):
    # 递归的退出条件
    if len(alist) <= 1:
        return alist

    # 二分分解
    num = len(alist)//2
    # 递归操作
    left = merge_sort(alist[:num])    # 不包含 num
    right = merge_sort(alist[num:])    # 包含 num
    # 合并
    return merge(left, right)


def merge(left, right):
    # 将两个【有序数组】left[] 和 right[] 合并成一个大的有序数组
    # 用于遍历两个数组的下标指针
    l, r = 0, 0
    result = []

    while l<len(left) and r<len(right):
        # 两个数组若其中有一个遍历完，就跳出 while 循环
        if left[l] < right[r]:
            result.append(left[l])
            l += 1
        else:
            result.append(right[r])
            r += 1

    result += left[l:]
    result += right[r:]
    # 特殊情况是两个数组长度相等，那么上述两句就不起作用
    return result


alist = [54,26,93,17,77,31,44,55,20]
sorted_alist = merge_sort(alist)
print(sorted_alist)

 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 heap_sort(nums):
    n = len(nums)

    def sift_down(start, end):
        root = start
        while True:
            child = 2 * root + 1
            if child > end:
                break
            if child + 1 <= end and nums[child] < nums[child + 1]:
                child += 1
            if nums[root] < nums[child]:
                nums[root], nums[child] = nums[child], nums[root]
                root = child
            else:
                break

    # 建堆：从最后一个非叶子节点下沉
    for i in range(n // 2 - 1, -1, -1):
        sift_down(i, n - 1)

    # 逐个取出堆顶
    for i in range(n - 1, 0, -1):
        nums[0], nums[i] = nums[i], nums[0]
        sift_down(0, i - 1)

 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

import heapq
def heap_operations():
    heap = [4, 2, 1, 3]

    # heapify
    heapq.heapify(heap)

    # top
    top = heap[0]

    # heappop
    top = heapq.heappop(heap)

    # heappush
    heapq.heappush(heap, 5)

    # heappushpop = push + pop
    heapq.heappushpop(heap, 0)

    # heapreplace = pop + push
    heapq.heapreplace(heap, 0)

    data = [10, 5, 18, 2, 37, 3, 8, 7, 19, 1]
    heapq.heapify(data)
    old, new = 8, 22  # increase the 8 to 22
    i = data.index(old)
    data[i] = new
    # _siftup, from root to leaf, when increase
    heapq._siftup(data, i)

    old, new = 10, 4  # decrease the 10 to 4
    i = data.index(old)
    data[i] = new
    # _siftdown, from leaf to root, when decrease
    heapq._siftdown(data, 0, i)

    # find n largest by queue 从队列中找出前 n 个最大的
    heapq.nlargest(data, 3)

    # find n smallest by queue
    heapq.nsmallest(data, 3)

    # Merge multiple sorted inputs into a single sorted output
    # e.g. merge timestamped entries from multiple log files
    heapq.merge([1, 3, 5, 7], [0, 2, 4, 8], [5, 10, 15, 20], [], [25])

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

def counting_sort(nums, max_val):
    """计数排序"""
    count = [0] * (max_val + 1)
    for num in nums:
        count[num] += 1

    sorted_idx = 0
    for val, freq in enumerate(count):
        for _ in range(freq):
            nums[sorted_idx] = val
            sorted_idx += 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

def bucket_sort(nums, bucket_size=5):
    if not nums:
        return nums

    # 确定数据范围
    min_val, max_val = min(nums), max(nums)
    bucket_count = (max_val - min_val) // bucket_size + 1
    buckets = [[] for _ in range(bucket_count)]

    # 分配到各桶
    for num in nums:
        buckets[(num - min_val) // bucket_size].append(num)

    # 各桶内排序并合并
    result = []
    for bucket in buckets:
        bucket.sort()
        result.extend(bucket)
    return result

 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

def radix_sort(nums):
    """基数排序（按最低位优先）"""
    max_val = max(nums)
    exp = 1

    while max_val // exp > 0:
        counting_sort_by_exp(nums, exp)
        exp *= 10

def counting_sort_by_exp(nums, exp):
    n = len(nums)
    output = [0] * n
    count = [0] * 10

    for num in nums:
        digit = (num // exp) % 10
        count[digit] += 1

    for i in range(1, 10):
        count[i] += count[i - 1]

    for i in range(n - 1, -1, -1):
        digit = (nums[i] // exp) % 10
        output[count[digit] - 1] = nums[i]
        count[digit] -= 1

    for i in range(n):
        nums[i] = output[i]

1
2
3
4
5

# 计算阶乘
def factorial(n):
    if n <= 1:
        return 1
    return n * factorial(n - 1)

1
2
3
4
5

def tail_factorial(n, acc=1):
    """尾递归形式"""
    if n <= 1:
        return acc
    return tail_factorial(n - 1, acc * n)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

# 斐波那契数列（带备忘录的递归）
def fib(n, memo=None):
    if memo is None:
        memo = {}
    if n in memo:
        return memo[n]
    if n <= 1:
        return n
    memo[n] = fib(n - 1, memo) + fib(n - 2, memo)
    return memo[n]

# 爬楼梯（自底向上）
def climb_stairs(n):
    if n <= 2:
        return n
    dp = [0] * (n + 1)
    dp[1], dp[2] = 1, 2
    for i in range(3, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

# 区间调度问题：选择最多不重叠的区间
def interval_schedule(intervals):
    intervals.sort(key=lambda x: x[1])  # 按结束时间排序
    count, current_end = 0, 0
    for start, end in intervals:
        if start >= current_end:
            count += 1
            current_end = end
    return count

# 钱币找零：尽可能使用大面额
def coin_change(coins, amount):
    coins.sort(reverse=True)
    count = 0
    for coin in coins:
        count += amount // coin
        amount %= coin
    return count

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

def backtrack(nums, path, result):
    if 满足终止条件:
        result.append(path[:])  # 记录解
        return

    for choice in 可选元素:
        if 满足剪枝条件:
            path.append(choice)      # 做选择
            backtrack(nums, path, result)  # 递归
            path.pop()               # 撤销选择

 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

# 全排列
def permute(nums):
    result = []
    def backtrack(path, used):
        if len(path) == len(nums):
            result.append(path[:])
            return
        for i, num in enumerate(nums):
            if not used[i]:
                used[i] = True
                path.append(num)
                backtrack(path, used)
                path.pop()
                used[i] = False
    backtrack([], [False] * len(nums))
    return result

# N 皇后
def solve_n_queens(n):
    result = []
    def backtrack(row, cols, diag1, diag2, board):
        if row == n:
            result.append([''.join(row) for row in board])
            return
        for col in range(n):
            d1, d2 = row - col, row + col
            if col in cols or d1 in diag1 or d2 in diag2:
                continue
            board[row][col] = 'Q'
            backtrack(row + 1, cols | {col}, diag1 | {d1}, diag2 | {d2}, board)
            board[row][col] = '.'
    backtrack(0, set(), set(), set(), [['.' for _ in range(n)] for _ in range(n)])
    return result