计算机基础
数据结构与算法
力扣篇

解法描述

# 解题方法描述

# 什么是动态规划？

动态规划（Dynamic Programming，简称DP）是一种在数学、管理科学、计算机科学、经济学动态规划（Dynamic Programming，简称DP）是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。

动态规划体现的主要环节是【递归+记忆化】，即反复调用自身(俗称套娃)并利用数据结构来存储已解决的子问题的答案，以便在后续需要时可以快速查找，而无需重复计算。

例如，斐波那契数列是一个经典的用例，我们可以通过动态规划的方式来求解每一项的值：定义这样一个数列，前两项值等于序列号，后面每一项是前两项之和，这样就可以通过反复调用自身来求解每一项的值。

此外，动态规划的应用极其广泛，包括工程技术、经济、工业生产、军事以及自动化控制等领域，并在背包问题、生产经营问题、资金管理问题、资源分配问题、最短路径问题和复杂系统可靠性问题等中取得了显著的效果。

# 什么时候用回溯法？

回溯法通常用于解决组合、排列、搜索等问题，其特点是在解决问题的过程中，需要多次尝试不同的选择，直到找到符合条件的解，或者所有的选择都尝试完毕后确定无解。具体来说，当问题满足以下条件时，可以考虑使用回溯法：

问题需要求出所有可能的解。
解空间非常大，但是可以通过剪枝等方式大大减少搜索空间。
问题可以表示成树形结构，每个节点表示一种选择，可以通过深度优先搜索实现回溯。
问题的每个解都可以用一个序列表示，序列中的元素表示选择的顺序。
问题具有单调性，即问题的最优解可以通过一定规则的选择得到。

例如，求解 N 皇后问题、0-1 背包问题、全排列问题等就可以考虑使用回溯法。回溯法在实现上通常需要使用递归，因此需要注意递归的开销，以及如何剪枝，减少无用的搜索。

# 分治法解析

分治法的基本思想是：将问题分解成更小的子问题，解决子问题后再合并得到原问题的解。

对于最大子数组问题，可以采用如下的分治策略：

分解（Divide）： 将数组分成两半，分别求解左半部分和右半部分的最大子数组和。
合并（Combine）： 考虑最大子数组和跨越左右两半的情况。即求解包含中间元素的最大子数组和。
返回（Return）： 返回左半部分、右半部分和跨越中间的最大子数组和中的最大值。

# 贪心算法

贪心算法，也叫贪婪算法，是一种在求解问题时，总是做出当前看来是最好的选择的算法。

也就是说，它不从整体最优上加以考虑，算法得到的是在某种意义上的局部最优解。具体来说，贪心算法的基本思路是：通过每一步都选取局部最有利的选择，从而希望导致结果是全局最优的。

贪心算法适用于一些特定问题，可以快速得到解决方案，但需要注意的是，由贪心算法得到的解决方案并不一定是全局最优解。这是因为贪心算法在每一步都选择局部最优解，而没有考虑到这些局部最优解组合起来的整体效果。因此，贪心算法更适用于一些局部最优解能够导致全局最优解的问题。

贪心算法的应用范围非常广泛，比如零钱找回问题、E点加入S问题和MST问题等。对于这些问题，贪心算法往往能够得到迅速且精确的解决方案。

# 归并排序

归并排序是一种基于分治思想的排序算法，它将待排序的序列分成两个子序列，分别进行递归排序，然后将已排序的子序列合并成一个有序的序列。归并排序有两种主要的实现方式：自顶向下和自底向上。

自顶向下的归并排序和自底向上的归并排序都是应用了分治策略的一种有效的排序方式，不过他们在进行排序时的顺序有所不同。

# 自顶向下的归并排序

分解： 将待排序序列递归地分解成两个子序列，直到每个子序列只有一个元素为止。
合并： 将已经排好序的子序列合并，不断地合并直到整个序列有序。
递归： 通过递归实现上述分解和合并的过程。

自顶向下的归并排序是一种典型的递归算法。具体步骤如下：

mergeSort(arr, low, high) {
    if (low < high) {
        // 分解：找到中间位置将序列分成两部分
        mid = (low + high) / 2;

        // 递归地对左右两部分进行排序
        mergeSort(arr, low, mid);
        mergeSort(arr, mid + 1, high);

        // 合并：将两个已排序的子序列合并成一个有序序列
        merge(arr, low, mid, high);
    }
}

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

# 自底向上的归并排序

自底向上的归并排序采用迭代的方式实现，不需要递归。

具体步骤如下：

分组： 将原始序列看成是 n 个长度为 1 的子序列。
两两合并： 依次将相邻的两个子序列合并成一个更大的有序序列。
不断迭代： 重复合并直到整个序列有序。

自底向上的归并排序可以看作是一种迭代的归并过程。实现伪代码如下：

mergeSort(arr) {
    int n = arr.length;

    // 子序列大小从1开始，逐渐加倍
    for (int size = 1; size < n; size *= 2) {
        // 合并相邻的两个子序列
        for (int left = 0; left < n - 1; left += 2 * size) {
            int mid = Math.min(left + size - 1, n - 1);
            int right = Math.min(left + 2 * size - 1, n - 1);

            // 合并两个子序列
            merge(arr, left, mid, right);
        }
    }
}

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

# BFS 和 DFS

# Breadth First Search

BFS（广度优先搜索）的思想是：对每一层的节点进行操作，再去下一层。假设利用一个队列实现 BFS 翻转链表。

在队列中，新元素（在这里是指子树的根节点）总是被添加到队列的末尾，我们总是从队列的头部移除元素。
从队列的头部取出一个节点，如果这个节点有左子树或者右子树，就将其左子树和右子树翻转，然后将其左子树和右子树（如果存在的话）分别添加到队列的尾部。

# Depth First Search

DFS（深度优先搜索）的思想是：对某个节点先深度遍历，直到找到最深的节点后，再回溯到下一个节点。假设利用一个栈实现 DFS 翻转链表。

在栈中，新元素（在这里是指子树的根节点）总是被添加到栈的顶部，我们总是从栈的顶部移除元素。
从栈的顶部取出一个节点，然后将其左子树和右子树翻转，然后将其左子树和右子树（如果存在的话）分别添加到栈的顶部。

上次更新: 2024/9/25 11:16:13

← 刷题小记简单篇→