C++数据结构和算法
斐波那契数爬楼梯使用最小花费爬楼梯【有点小坑】不同路径不同路径 II【注意初始值的设置】最小路径和343. 整数拆分96. 不同的二叉搜索树动态规划与其说是一个算法，不如说是一种方法论。1.建立状态转移方程2.缓存并复用以往结果3.按顺序从小往大算。
·
0.浅谈算法
（1）算法定义
- 算法（algorithm）是在有限时间内解决特定问题的一组指令或操作步骤，它具有以下特性。
- 1.问题是明确的，包含清晰的输入和输出定义。
- 2.具有可行性，能够在有限步骤、时间和内存空间下完成。
- 3.各步骤都有确定的含义，在相同的输入和运行条件下，输出始终相同。
（2）生活中常见的算法
例一：查字典
- 铺垫：在字典里，每个汉字都对应一个拼音，而字典是按照拼音字母顺序排列的。假设我们需要查找一个拼音首字母为 r 的字，通常会按照如图所示的方式实现。
- 具体做法：
- 1.翻开字典大约一半的页数，查看该页的首字母是什么，假设首字母为m。
- 2.因为字母表中，r位于m后面，所以排除字典前半部分，查找范围缩小到后半部分。
- 3.不断重复步骤1和步骤2的过程，直到找到字母为r的页码为止。
- 总结：查字典这个小学生必备技能，实际上就是著名的“二分查找”算法。从数据结构的角度，我们可以把字典视为一个已排序的“数组”；从算法的角度，我们可以将上述查字典的一系列操作看作“二分查找”。
例二：整理扑克
- 铺垫：我们在打牌时，每局都需要整理手中的扑克牌，使其从小到大排列。如图所示：
- 具体做法：
- 1.先摸上来第一张牌，此时无需做任何比较，直接放入。
- 2.继续摸第二张牌，从第二张牌开始往前比。
- 3.如果第二张牌比第一张牌小，则需要交换他们的位置。
- 4.再让第三张牌和前两张牌依次比较（从第二张牌开始对比），如果第三张牌比其中任何一张牌都要小，则同样需要交换位置。
- 5.以此类推，往后的每张牌都这样去比较然后进行排序。
- 总结：整理扑克牌的过程本质上是“插入排序”算法，它在处理小型数据集时非常高效。许多编程语言的排序库函数中都有插入排序的身影。
例三：找零钱
-
铺垫：假设我们在超市购买了 69 元的商品，给了收银员 100 元，则收银员需要找我们 31 元。现在收银台只有面额是1 元、5 元、10 元、20 元这四种，如何尽可能用大面额的货币去完成零钱兑换呢？
-
具体做法：
- 从可选项中拿出最大的 20 元，剩余 11 元。
- 从剩余可选项中拿出最大的 10 元，剩余 1 元。
- 从剩余可选项中拿出最大的 1 元，剩余 0 元。
- 完成找零，方案为 1+10+20 = 31 元。
- 总结：在以上步骤中，我们每一步都采取当前看来最好的选择（尽可能用大面额的货币），最终得到了可行的找零方案。从数据结构与算法的角度看，这种方法本质上是“贪心”算法。
（3）数据结构
数据结构（data structure）是组织和存储数据的方式，涵盖数据内容、数据之间关系和数据操作方法，它具有以下设计目标。
- 空间占用尽量少，以节省计算机内存。
- 数据操作尽可能快速，涵盖数据访问、添加、删除、更新等。
- 提供简洁的数据表示和逻辑信息，以便算法高效运行。
以下是一些常用的C++标准库容器，它们可以被视为程序中的数据结构：
1. 序列容器
- std::vector：动态数组，支持随机访问，内部元素连续存储。
- std::list：双向链表，适合频繁插入和删除操作。
- std::deque：双端队列，支持两端高效插入和删除。
2. 关联容器
- std::set：键值唯一的集合，元素按排序顺序存储。
- std::multiset：键值可以重复的集合，元素按排序顺序存储。
- std::map：键值对的集合，键唯一且按排序顺序存储。
- std::multimap：键值对的集合，键可重复且按排序顺序存储。
3. 容器适配器
- std::stack：后进先出（LIFO）容器。
- std::queue：先进先出（FIFO）容器。
- std::priority_queue：优先级队列，根据元素优先级排序。
4. 其他容器
- std::array：固定大小的数组。
- std::forward_list：单向链表。
- std::unordered_set：基于哈希表实现的键值唯一的集合。
- std::unordered_multiset：基于哈希表实现的键值可以重复的集合。
- std::unordered_map：基于哈希表实现的键值对的集合。
- std::unordered_multimap：基于哈希表实现的键值对的集合，键可重复。
要使用这些容器，你需要包含相应的头文件，例如 <vector>, <map>, <stack> 等。此外，C++还提供了许多算法函数（如 sort, find, copy 等），这些函数定义在 <algorithm> 头文件中，可以与上述容器一起使用以实现更复杂的功能。
（4）数据结构与算法的关系
数据结构与算法高度相关、紧密结合，具体表现在以下三个方面。
- 数据结构是算法的基石。数据结构为算法提供了结构化存储的数据，以及操作数据的方法。
- 算法是数据结构发挥作用的舞台。数据结构本身仅存储数据信息，结合算法才能解决特定问题。
- 算法通常可以基于不同的数据结构实现，但执行效率可能相差很大，选择合适的数据结构是关键。
（5）算法复杂度
<1> 时间复杂度
- 定义：用来估计算法运行时间的一个式子。
- 一般来讲，时间复杂度高的算法比复杂度低的算法慢。
- 设输入数据大小为 n ，常见的时间复杂度类型如图所示（按照从低到高的顺序排列）：
- 常数阶 O(1)
- 常数阶的操作数量与输入数据大小 n 无关，即不随着 n 的变化而变化。在以下函数中，尽管操作数量 size 可能很大，但由于其与输入数据大小 n 无关，因此时间复杂度仍为 O(1) .
// 常数阶函数
int constant(int n) {
int count = 0;
const int size = 100000;
for (int i = 0; i < size; ++i) {
count += 1;
}
return count;
}
- 线性阶 O(n)
- 线性阶的操作数量相对于输入数据大小 n 以线性级别增长。线性阶通常出现在单层循环中，例如遍历数组的时间复杂度为 O(n) ，其中 n 为数组或链表的长度：
int main() {
vector<int> nums = {1, 2, 3, 4, 5}; // 示例数组
int count = 0;
// 循环次数与数组长度成正比
for (int num : nums) {
count += 1;
}
cout<<count;
}
- 平方阶 O(n2)
- 平方阶的操作数量相对于输入数据大小 n 以平方级别增长。平方阶通常出现在嵌套循环中，外层循环和内层循环的时间复杂度都为 O(n) ，因此总体的时间复杂度为 O(n2).
// 平方阶函数
int quadratic(int n) {
int count = 0;
// 循环次数与数据大小 n 成平方关系
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
count += 1;
}
}
return count;
}
- 指数阶 O(2n)
- 生物学的“细胞分裂”是指数阶增长的典型例子：初始状态为 1 个细胞，分裂一轮后变为 2 个，分裂两轮后变为 4 个，以此类推，分裂 n 轮后有 2n 个细胞。
// 指数阶函数
int exponential(int n) {
int count = 0;
int base = 1;
// 细胞每轮一分为二，形成数列 1, 2, 4, 8, ..., 2^(n-1)
for (int i = 0; i < n; ++i) {
for (int j = 0; j < base; ++j) {
count += 1;
}
base *= 2;
}
// count = 1 + 2 + 4 + 8 + .. + 2^(n-1) = 2^n - 1
return count;
}
- 对数阶 O(logn)
与指数阶相反，对数阶反映了“每轮缩减到一半”的情况。设输入数据大小为 n ，由于每轮缩减到一半，因此循环次数是 O( log 2 n \log_2n log2n) ，简记为 O(logn)，典型的例子就是二分查找。
// 对数阶函数
int logarithmic(int n) {
int count = 0;
while (n > 1) {
n /= 2;
count += 1;
}
return count;
}
- 线性对数阶 O(n*logn)
线性对数阶常出现于嵌套循环中，两层循环的时间复杂度分别为 O(logn) 和 O(n) , 因此时间复杂度为 O(n*logn)。例如：
// 线性对数阶函数
int linear_log_recur(int n) {
if (n <= 1) {
return 1;
}
int count = linear_log_recur(n / 2) + linear_log_recur(n / 2);
for (int i = 0; i < n; ++i) {
count += 1;
}
return count;
}
主流排序算法的时间复杂度通常为 O(n*logn)
，例如快速排序、归并排序、堆排序等。
- 阶乘阶 O(n!)
阶乘阶对应数学上的“全排列”问题。给定 n 个互不重复的元素，求其所有可能的排列方案，方案数量为：
n! = n * (n-1) * (n-2) * ...*2 * 1
- 参考代码1：
// 阶乘阶函数（递归实现）
int factorial_recur(int n) {
if (n == 0) {
return 1;
}
int count = 0;
// 从 1 个分裂出 n 个
for (int i = 0; i < n; ++i) {
count += factorial_recur(n - 1);
}
return count;
}
- 参考代码2：
// 阶乘阶函数（递归实现）
int factorial_recur(int n) {
if (n == 1) {
return 1;
}
return n*factorial_recur(n-1);
}
<2> 空间复杂度
- 定义：用来估计算法内存占用大小的一个式子。
- 空间复杂度的表示方式和时间复杂度一样。
- “空间换时间”
- 常数阶 O(1)
常数阶常见于数量与输入数据大小 n 无关的常量、变量、对象。
//循环中的变量占用 O(1) 空间
for (int i = 0; i < n; ++i) {
int sum = 0;
}
- 线性阶 O(n)
线性阶常见于元素数量与 n 成正比的数组、链表、栈、队列等：
#include <iostream>
#include <vector>
using namespace std;
// 将数据复制到新数组的函数
vector<int> store_in_array(const vector<int>& data) {
// 创建一个新的 vector 来存储数据，空间复杂度为 O(n)
vector<int> arr;
for (int i : data) {
arr.push_back(i);
}
// 这里我们只是简单地将数据复制到了一个新 vector，所以其他操作的空间复杂度为 O(1)
return arr;
}
// 主函数用于测试
int main() {
vector<int> data = {1, 2, 3, 4, 5}; // 示例数据
vector<int> result = store_in_array(data);
// 打印结果
for (int num : result) {
cout << num << " ";
}
cout << endl;
return 0;
}
-
平方阶 O(n2)
-
指数阶 O(2n)
-
对数阶 O(logn)
1.枚举算法
- 枚举的定义：根据所需解决问题的条件，把该问题所有可能的解，一一列举出来，并逐个检验出问题真正解的方法。枚举法也称穷举法。
（1）判断水仙花数
水仙花数：指一个 n 位数（n≥3），它的每个位上的数字的 n 次幂之和等于它本身。例如，153是一个水仙花数，因为1^3 + 5^3 + 3^3 = 153。
题目：找出100~999整数中的所有水仙花数.
- 方法一：使用while循环
#include <iostream>
int main() {
int num = 100;
while (num < 1000) {
int a = num / 100;
int b = (num % 100) / 10;
int c = num % 10;
if (a * a * a + b * b * b + c * c * c == num) {
std::cout << num << " 是一个水仙花数" << std::endl;
}
num++;
}
return 0;
}
- 方法二：使用for循环
#include <iostream>
int main() {
for (int x = 100; x < 1000; ++x) {
int a = x / 100; // 百位数
int b = (x % 100) / 10; // 十位数
int c = x % 10; // 个位数
if (a * a * a + b * b * b + c * c * c == x) {
std::cout << x << " 是一个水仙花数" << std::endl;
}
}
return 0;
}
结果：
（2）鸡兔同笼
有一个笼子，里面有鸡和兔子。我们知道总共有7个头和18只脚，我们要找出有多少只鸡和多少只兔子。
- 解法一：假设法
先假设它们全是鸡，每少2只脚就说明有一只兔被看成了鸡；将少的脚数量除以2,就可以算出共有多少只兔，我们称这种解题方法为假设法。解题步骤：
- 假设全部是鸡，此时总的脚数：7x2 = 14 只
- 一共被看少的脚数量：18-14 = 4 只
- 兔子的数量：4/2 = 2 只
- 鸡的数量：7-2 = 5 只
- 解法二：一元一次方程
设笼子里有 x 只鸡，那么兔子有：7-x 只。根据题目，我们可以建立以下方程：
脚的总数是 2x + 4*（7-x） = 18（鸡有2只脚，兔子有4只脚，总脚数就是2倍的鸡脚数加上4倍的兔脚数）。
现在我们要来解这个方程组，找出 x 的值。计算结果为：x = 5。所以，笼子里有 5 只鸡和 2 只兔子。
- 解法三：一元二次方程
设笼子里有 x 只鸡和 y 只兔子。根据题目，我们可以建立以下方程：
- 头的总数是 x + y = 7（鸡和兔子的头数加起来）。
- 脚的总数是 2x + 4y = 18（鸡有2只脚，兔子有4只脚，总脚数就是2倍的鸡脚数加上4倍的兔脚数）。
- 现在我们要来解这个方程组，找出 x 和 y 的值。计算结果为： {x: 5, y: 2}。所以，笼子里有 5 只鸡和 2 只兔子。
- 解法四：枚举算法
以上我们用的是数学中列举方程的形式求解，我们也可以利用枚举法，通过python代码帮我们计算最终的结果。
枚举的思路如图所示：一一列举，最终得到总的脚数量为18的组合，答案即为5 只鸡和 2 只兔子。
- 使用while循环求解：
#include <iostream>
int main() {
int head = 7; // 鸡和兔总的个数
int foot = 18; // 鸡和兔总的脚数量
int chicken = 0;
int rabbit = 0;
while (true) {
rabbit = head - chicken;
if (2 * chicken + 4 * rabbit == foot) {
break;
}
chicken++;
}
std::cout << chicken << " " << rabbit << std::endl; // 输出结果 5 2
return 0;
}
- 使用for循环求解：
#include <iostream>
int main() {
int chicken = 1;
int rabbit = 6;
for (int i = 1; i <= 7; ++i) {
rabbit = 7 - chicken;
if (2 * chicken + 4 * rabbit == 18) {
std::cout << chicken << " " << rabbit << std::endl;
break;
}
chicken++;
}
return 0;
}
（3）因式分解
题目：有两个两位数，他们的乘积等于1691，求这两个数分别是多少？
#include <iostream>
int main() {
for (int i = 10; i < 100; ++i) {
for (int j = 10; j < 100; ++j) {
if (i * j == 1691) {
std::cout << i << " " << j << std::endl;
break;
}
}
}
return 0;
}
思考：以上结果为何会输出两遍？代码能否进行优化呢？
代码优化：
#include <iostream>
int main() {
for (int i = 10; i < 100; ++i) {
for (int j = i; j < 100; ++j) {
if (i * j == 1691) {
std::cout << i << " " << j << std::endl;
break;
}
}
}
return 0;
}
（4）找质数
题目：找出1到20内的所有质数
提示：质数是指大于1的自然数，除了1和它本身以外没有任何正因数（除了1和它本身外不能被其他整数整除）。换句话说，质数是只有两个正因数的数，这两个因数就是1和它自己。
#include <iostream>
int main() {
for (int num = 2; num <= 20; ++num) { // 起始值为2，对于范围在2到20的每一个数字
bool is_prime = true; // 假设num是质数
for (int i = 2; i < num; ++i) { // 对于从2到num-1的每一个数字
if (num % i == 0) { // 如果num能被i整除
is_prime = false; // num不是质数
break; // 退出内层循环
}
}
if (is_prime) { // 如果内层循环完整执行（即未中断），则说明num是质数
std::cout << num << std::endl; // 打印输出
}
}
return 0;
}
2.查找算法
（1）顺序查找
思路：
- 遍历列表。
- 找到跟目标值相等的元素，就返回他的下标。
- 遍历结束后，如果没有搜索到目标值，就返回-1。
参考代码：
#include <iostream>
using namespace std;
int main() {
int a[5] = {4,5,2,3,1};
int target = 9;
int len = sizeof(a)/sizeof(a[0]);
bool b = false;
for(int i = 0; i < len; i++) {
if(target==a[i]) {
cout<<i<<endl;
b = true;
}
}
if(b==false) {
cout<<-1<<endl;
}
}
时间复杂度：O(n)
（2）二分查找
【注意】：二分查找的前提是数字是排序好的。
思路：
- 从数组的中间元素开始，如果中间元素正好是目标值，则搜索结束。
- 如果目标值大于或者小于中间元素，则在大于或小于中间元素的那一半数组中搜索。
动画演示：
#include <iostream>
using namespace std;
int main() {
int a[5] = {4,5,8,9,15};
int target = 5;
int len = sizeof(a)/sizeof(a[0]);
int left = 0;
int right = len-1;
bool b = false;
while(left<=right){
int mid = (left+right)/2;
if(a[mid]<target){
left = mid+1;
}else if(a[mid]>target){
right = mid-1;
}else{
cout<<mid;
b = true;
break;
}
}
if(b==false) {
cout<<"找不到该数字";
}
}
时间复杂度：O(logn）
3. 排序算法
菜鸡三人组：
- 冒泡排序
- 选择排序
- 插入排序
牛逼三人组：
- 快速排序
- 堆排序（难）
- 归并排序（较难）
（1）冒泡排序
思路：
- 1.比较所有相邻的元素，如果第一个比第二个大，则交换他们。
- 2.一轮下来，可以保证最后一个数是最大的。
- 3.以此类推，执行n-1轮，就可以完成排序。
- 动画演示：
代码参考：
#include <iostream>
using namespace std;
int main() {
int a[] = {6,5,4,1,3,2};
int len = sizeof(a) / sizeof(a[0]);
for(int i = 0; i < len-1; i++) {
for(int j = 0; j < len-1; j++) {
if(a[j] > a[j+1]) {
int temp = a[j];
a[j] = a[j+1];
a[j+1] = temp;
}
}
}
for (int i = 0; i < len; i++) {
cout << a[i] << " ";
}
}
- 思考：以上代码能否进行优化呢？内层循环需要每次都遍历0~len-1次吗？？
- 回答：不需要，因为随着外层循环次数的增加，数组末尾的排序会依次确定好位置，例如，第一轮会确定6的位置，第二轮会确定5的位置。所以，内层循环不需要每次都遍历0~len-1次，只需要遍历len-1-i 次就够了。
优化后的代码：
#include <iostream>
using namespace std;
int main() {
int a[] = {6,5,4,1,3,2};
int len = sizeof(a) / sizeof(a[0]);
for(int i = 0; i < len-1; i++) {
for(int j = 0; j < len-1-i; j++) {
if(a[j] > a[j+1]) {
int temp = a[j];
a[j] = a[j+1];
a[j+1] = temp;
}
}
}
for (int i = 0; i < len; i++) {
cout << a[i] << " ";
}
}
冒泡排序时间复杂度：O(n2)
（2）选择排序
思路：
- 1.找到数组中的最小值，把他更换到列表中的第一位。（具体做法：先假设第一数为最小值，记录它的索引值，将第一数和第二个数作比较，如果第一个数大于第二个数，将最小索引值记录为第二个数，依次循环比较，一轮比较下来，最小值所在的索引位置就会被找到，并且把他更换到最开头的位置。
- 2.接着找到第二小的值，把他更换到数组中的第二位。
- 3.以此类推，执行n-1轮，就可以完成排序。
- 动画演示：
参考代码：
#include <iostream>
using namespace std;
int main() {
int a[] = {6,5,4,1,3,2};
int len = sizeof(a) / sizeof(a[0]);
for(int i = 0; i < len-1; i++) {
int min = i;
for(int j = i+1; j < len; j++) {
if(a[min] > a[j]) {
min = j;
}
}
int temp = a[min];
a[min] = a[i];
a[i] = temp;
}
for (int i = 0; i < len; i++) {
cout << a[i] << " ";
}
}
选择排序时间复杂度：O(n2)
（3）插入排序
插入排序（insertion sort）是一种简单的排序算法，它的工作原理与手动整理一副牌的过程非常相似。
基本思路：
- 在未排序区间选择一个基准元素，将该元素与其左侧已排序区间的元素逐一比较大小，并将该元素插入到正确的位置。
具体步骤：
- 从第二个元素开始，依次将元素插入已经排序好的部分。
- 遍历已排序好的部分，找到合适的插入位置。
- 将待排序的元素插入合适的位置。
- 将大于待排序元素的元素向后移动一个位置。
- 依次类推，完成插入排序。
例子：
插入排序的总体过程，类似我们打牌，摸牌后进行依次插入的过程：
举例：假如已经进行到31这个数了，31前面的数我们已经插入排序完毕了；那么对于31这个数，我们需要先将其与93比较，31<93，交换位置；接着比较31<77，交换位置；接着比较31<54，交换位置；接着比较31>26，不需要交换位置了，此时内层循环可以结束了。
动画演示：
代码参考：
#include<iostream>
using namespace std;
int main() {
int a[] = {5,3,4,7,2};
for(int i = 1; i<5; i++) {
int key = a[i];
int j = i-1;
while(j>=0 && key<a[j]) {
a[j+1] = a[j];
j-=1;
}
a[j+1] = key;
for(int z = 0; z<=4; z++) {
cout<<a[z];
}
cout<<endl;
}
}
插入排序的外层循环为for循环 + 内层循环为while循环，所以时间复杂度为 O(n2)
（4）快速排序
- 第一轮排序的代码：
#include <iostream>
#include <vector>
using namespace std;
// 遍历数组
void printVector(const vector<int>& vec) {
for (int num : vec) {
cout << num << " ";
}
cout << endl;
}
// 归位函数
void partition(vector<int>& vec, int left, int right) {
int tmp = vec[left];
while (left < right) {
while (left < right && vec[right] >= tmp) { // 从右边找出比tmp小的数
--right; // 往左移动一步
}
vec[left] = vec[right]; // 把右边的值给到左边的空缺位置
printVector(vec);
while (left < right && vec[left] <= tmp) {
++left;
}
vec[right] = vec[left];
printVector(vec);
}
vec[left] = tmp; // 将tmp进行归位
}
int main() {
vector<int> vec = {5, 7, 4, 6, 3, 1, 2, 9, 8};
printVector(vec);
partition(vec, 0, vec.size() - 1);
printVector(vec);
}
结果：
问题解析:
问: 为何是先从右往左进行查找?
答: 因为左边空出了位置, 从右往左找出比tmp小的数字, 可以放到left指针所在的位; 如果一开始从左往右查找, 右边并没有空余位置。
代码解析1:
while (left < right && vec[right] >= tmp)
问: 以上这行代码为何添加条件判断 left < right
答: 因为如果不添加, right可能会跑到left的左边, 比如5 6 7,right指针最终会移动到5所在位置的左边，vec[right]就取不到元素了
# 代码解析2:
while (left < right && vec[right] >= tmp)
问: 以上这行代码为何是 vec[right] >= tmp, 不能是vec[right] > tmp:
答: 因为如果是vec[right] > tmp, 假如列表为5 6 5 7, right指针移动到5所在位置就会停止了, 此时
列表的顺序为: 5 6 5 7, left指针也会一直停留在左边5的位置, 循环无法跳出来.
- 添加递归函数，实现左右两边也进行快速排序，最终版代码：
#include <iostream>
#include <vector>
using namespace std;
int partition(vector<int>& vec, int left, int right) {
int tmp = vec[left];
while (left < right) {
while (left < right && vec[right] >= tmp) { // 从右边找出比tmp小的数
--right; // 往左移动一步
}
vec[left] = vec[right]; // 把右边的值给到左边的空缺位置
while (left < right && vec[left] <= tmp) {
++left;
}
vec[right] = vec[left];
}
vec[left] = tmp; // 将tmp进行归位
return left;
}
void quick_sort(vector<int>& vec, int left, int right) {
if (left < right) { // 至少存在两个元素
int mid = partition(vec, left, right);
quick_sort(vec, left, mid - 1);
quick_sort(vec, mid + 1, right);
}
}
int main() {
vector<int> vec = {5, 7, 4, 6, 3, 1, 2, 9, 8};
quick_sort(vec, 0, vec.size() - 1);
for (int num : vec) {
cout << num << " ";
}
cout << endl;
}
结果：
快速排序时间复杂度：O（nlogn）
（5）归并排序
-
理解一次归并
-
一次归并动画演示：点我观看
-
一次归并的代码：
#include <iostream>
#include <vector>
void mergeOne(std::vector<int>& arr, int low, int mid, int high) {
int i = low;
int j = mid + 1;
std::vector<int> temp; // 临时存储排序后的元素
// 合并两个有序子数组
while (i <= mid && j <= high) {
if (arr[i] < arr[j]) {
temp.push_back(arr[i]);
i++;
} else {
temp.push_back(arr[j]);
j++;
}
}
// 如果左边还有元素，全部加入临时数组
while (i <= mid) {
temp.push_back(arr[i]);
i++;
}
// 如果右边还有元素，全部加入临时数组
while (j <= high) {
temp.push_back(arr[j]);
j++;
}
// 将临时数组中的元素拷贝回原数组
for (int k = low; k <= high; ++k) {
arr[k] = temp[k - low];
}
}
int main() {
std::vector<int> li = {2, 5, 7, 8, 9, 1, 3, 4, 6};
mergeOne(li, 0, 4, 8);
// 输出排序后的数组
for (int num : li) {
std::cout << num << " ";
}
std::cout << std::endl;
return 0;
}
-
归并排序整体思路：【递归解决：先分解，再合并】
-
归并排序图解：
- 归并排序最终代码：
#include <iostream>
#include <vector>
void mergeOne(std::vector<int>& arr, int low, int mid, int high) {
int i = low;
int j = mid + 1;
std::vector<int> temp; // 临时存储排序后的元素
// 合并两个有序子数组
while (i <= mid && j <= high) {
if (arr[i] < arr[j]) {
temp.push_back(arr[i]);
i++;
} else {
temp.push_back(arr[j]);
j++;
}
}
// 如果左边还有元素，全部加入临时数组
while (i <= mid) {
temp.push_back(arr[i]);
i++;
}
// 如果右边还有元素，全部加入临时数组
while (j <= high) {
temp.push_back(arr[j]);
j++;
}
// 将临时数组中的元素拷贝回原数组
for (int k = low; k <= high; ++k) {
arr[k] = temp[k - low];
}
}
void mergeSort(std::vector<int>& arr, int low, int high) {
if (low < high) {
int mid = (low + high) / 2;
mergeSort(arr, low, mid);
mergeSort(arr, mid + 1, high);
mergeOne(arr, low, mid, high);
}
}
int main() {
std::vector<int> li = {5, 2, 8, 7, 9, 3, 4, 6, 1};
mergeSort(li, 0, li.size() - 1);
// 输出排序后的数组
for (int num : li) {
std::cout << num << " ";
}
std::cout << std::endl;
return 0;
}
归并排序时间复杂度：O（nlogn）
（*）排序练习题
【1】谁考了第k名
参考代码：
#include<iostream>
using namespace std;
int main() {
int n,k;
cin>>n>>k;
// struct Student {
// int id;
// float score;
// };
// struct Student arr[n];
// 以上结构体数组可以合并写成这样
struct Student {
int id;
float score;
}arr[n];
for(int i = 0; i<n; i++) {
cin>>arr[i].id>>arr[i].score;
}
for(int j = 0; j<n-1; j++) {
for(int i = 0; i<n-1-j; i++) {
if(arr[i].score<arr[i+1].score) {
swap(arr[i].score,arr[i+1].score);
swap(arr[i].id,arr[i+1].id);
}
}
}
cout<<arr[k-1].id<<" "<<arr[k-1].score<<endl;
}
【2】奇数单增序列
参考代码：方法一
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n;
cin>>n;
vector<int> v5(n);
// 将输入数据添加到v5数组
for(int i = 0; i<v5.size(); i++) {
cin>>v5[i];
}
vector<int> arr;
// 将v5数组中所有奇数加入arr数组
for (int num: v5) {
if(num%2==1) {
arr.push_back(num);
}
}
// 对arr数组中所有元素进行冒泡排序
for(int j = 0; j<arr.size()-1; j++) {
for(int i = 0; i<arr.size()-1-j; i++) {
if(arr[i]>arr[i+1]) {
swap(arr[i],arr[i+1]);
}
}
}
// 输出arr数组中所有元素，最后一个元素不加逗号
for(int i = 0; i<arr.size(); i++) {
if(i==arr.size()-1){
cout<<arr[i];
}else{
cout<<arr[i]<<",";
}
}
}
参考代码：方法二
【扩展】：sort 函数的工作原理，它是一个通用的排序算法，位于
<algorithm>标准库中。sort 函数的第一个参数应该是数组的起始位置，第二个参数是数组的结束位置（但不包括该位置本身）。
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
int n;
cin>>n;
int a[n];
for(int i = 0; i<n; i++) {
cin>>a[i];
}
sort(a,a+n);
for(int i = 0; i<n; i++) {
if(a[i]%2==1) {
if(i==0) {
cout<<a[i];
} else {
cout<<","<<a[i];
}
}
}
}
【3】成绩排序
参考代码：
#include<iostream>
using namespace std;
int main() {
int n;
cin>>n;
struct Student {
char name[20];
int chengji;
}arr[n];
for(int i = 0; i<n; i++) {
cin>>arr[i].name>>arr[i].chengji;
}
// 冒泡排序
for(int j = 0; j<n-1; j++) {
for(int i = 0; i<n-1-j; i++) {
if(arr[i].chengji<arr[i+1].chengji) {
swap(arr[i].chengji,arr[i+1].chengji);
swap(arr[i].name,arr[i+1].name);
}
}
}
for(int i = 0; i<n; i++) {
cout<<arr[i].name<<" "<<arr[i].chengji<<endl;
}
}
【4】整数奇偶排序
参考代码：
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
int ji[10],ou[10],cnt1 = 0,cnt2 = 0;
int num;
for(int i = 0; i<10; i++) {
cin>>num;
if(num%2==1) {
ji[cnt1] = num;
cnt1++;
} else {
ou[cnt2] = num;
cnt2++;
}
}
sort(ji,ji+cnt1);
sort(ou,ou+cnt2);
for(int i = cnt1-1; i>=0; i--) {
cout<<ji[i]<<" ";
}
for(int i = 0; i<cnt2; i++) {
cout<<ou[i]<<" ";
}
}
【5】合影效果
参考代码：
#include <iostream>
#include <algorithm>
#include <iomanip>
using namespace std;
int main() {
double male[50],female[50];
int cnt1 = 0,cnt2 = 0;
int num;
cin>>num;
string s;
double h;
for(int i = 0; i<num; i++) {
cin>>s>>h;
if(s=="male") {
male[cnt1] = h;
cnt1++;
} else {
female[cnt2] = h;
cnt2++;
}
}
sort(male,male+cnt1);
sort(female,female+cnt2);
for(int i = 0; i<cnt1; i++) {
cout<<male[i]<<" ";
}
// 在输出女性身高之前设置了 cout 的精度为小数点后两位
cout << fixed << setprecision(2);
for(int i = cnt2-1; i>=0; i--) {
cout<<female[i]<<" ";
}
}
4.栈
- 定义：栈是一个数据集合，可以理解为只能在一端进行插入或者删除操作的列表。
- 特点：后进先出
- 基本操作：
- 进栈
- 出栈
- 取栈顶
题目：有效的括号
5.队列
- 队列是一个数据集合，仅允许在列表的一端进行插入，另一端进行删除。
- 进行插入的一端为队尾，插入动作称为进队或入队。
- 进行删除的一端为队头，删除动作称为出队。
- 队列的性质：先进先出。
6.链表
- 讲链表之前，先回顾数组的知识：
7.二叉树
8.深度优先搜索
9.广度优先搜索
10.图
11.贪心算法
12.动态规划
（1）动态规划算法介绍
LeetCode简单的动态规划题：
LeetCode较难的动态规划题：
总结：
动态规划与其说是一个算法，不如说是一种方法论。
该方法论主要致力于将“合适”的问题拆分成三个子目标一一击破：
- 1.建立状态转移方程
- 2.缓存并复用以往结果
- 3.按顺序从小往大算
（2）01背包”问题
概念：有N件物品和一个最多能装重量为W 的背包。第i件物品的重量是weight[i]，价值是value[i]。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。
1. 假如现在只有吉他, 验证公式:v[1][1] =1500
(1). i = 1, j = 1
(2). w[i] = w[1] = 1 j = 1
v[i][j]=max{v[i-1][j], v[i]+v[i-1][j-w[i]]} :
v[1][1] = max {v[0][1], v[1] + v[0][1-1]} = max{0, 1500 + 0} = 1500
2. 假如有吉他/音响/电脑, 验证公式:v[3][4]
(1). i = 3；j = 4
(2). w[i] = w[3] =3 j = 4
j = 4 >= w[i] = 3 => 4 >= 3
v[3][4] = max {v[2][4], v[3] + v[2][1]} = max{3000, 2000+1500} = 2000+1500
归纳：
从表格的右下角开始回溯，如果发现前n个物品的最佳组合的价值和前n-1个物品最佳组合的价值一样，说明第n个物品没有被装入；否则，第n个物品被装入。
问题：背包容量为4时，能装入物品的最大价值是多少？
参考代码：
#include<iostream>
using namespace std;
int main() {
int w[] = {1, 4, 3}; //物品重量
int v[] = {1500, 3000, 2000}; //物品的价值
int m = 4; //背包容量
int n = 3; //物品的个数
int dp[4][5];
//初始化dp数组
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= m; j++) {
dp[i][j] = 0;
}
}
//填表
for(int i=1; i<=n; i++) {
for(int j=1; j<=m; j++) {
if(j<w[i-1]) {
dp[i][j] = dp[i-1][j];
} else {
dp[i][j] = max(dp[i-1][j],dp[i-1][j-w[i-1]]+v[i-1]);
}
}
}
//输出dp数组
// for(int i=0; i<=n; i++) {
// for(int j=0; j<=m; j++) {
// cout<<dp[i][j]<<" ";
// }
// cout<<endl;
// }
//最大总价值
cout<<dp[n][m];
}
- 代码优化：
思考？
- 是否可以将二维数组压缩成一维数组
- 回答：可以，请看以下代码：
#include<iostream>
using namespace std;
int main() {
int w[] = {1, 4, 3}; //物品重量
int v[] = {1500, 3000, 2000}; //物品的价值
int m = 4; //背包容量
int n = 3; //物品的个数
int dp[5];
//初始化dp数组
for (int j = 0; j <= m; j++) {
dp[j] = 0;
}
//填表
for(int i=1; i<=n; i++) {
for(int j=m; j>=1; j--) {
if(j>=w[i-1])
dp[j] = max(dp[j],dp[j-w[i-1]]+v[i-1]);
}
//输出dp数组
// for(int j=0; j<=m; j++) {
// cout<<dp[j]<<" ";
// }
// cout<<endl;
}
//最大总价值
cout<<dp[m];
}
注意要点：
1、内层循环倒序遍历（且注意判断条件：j >= w[i - 1]）
- 原因：倒叙遍历是为了保证物品 i 只被放入一次！一旦正序遍历了，那么物品就会被重复加入多次！
2、为何能变为一维数组
- 原因：实际上是把dp[i - 1]那一层拷贝到dp[i]上。
- 小试牛刀
#include<iostream>
using namespace std;
int main() {
int m,n;
cin>>m>>n;
int w[n+1],v[n+1];
for(int i=0; i<=n; i++) {
if(i==0) {
w[0]=0;
v[0]=0;
continue;
}
cin>>w[i]>>v[i];
}
int dp[n+1][m+1];
//初始化dp数组
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= m; j++) {
dp[i][j] = 0;
}
}
//填表
for(int i=1; i<=n; i++) {
for(int j=1; j<=m; j++) {
if(j<w[i]) {
dp[i][j] = dp[i-1][j];
} else {
dp[i][j] = max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);
}
}
}
//输出dp数组
// for(int i=0; i<=n; i++) {
// for(int j=0; j<=m; j++) {
// cout<<dp[i][j]<<" ";
// }
// cout<<endl;
// }
//最大总价值
cout<<dp[n][m];
}
LeetCode中 “01背包” 题型汇总：
- 分割等和子集：转化后为0-1背包可行性问题。
- 目标和：转化问题以后为0-1背包方案数问题。
- 最后一块石头的重量 II：转化后为0-1背包最小值问题。
- 一和零：两个维度的01背包
（3）完全背包”问题
概念：有N件物品和一个最多能背重量为W的背包。第i件物品的重量是weight[i]，价值是value[i]。每件物品都有无限个（也就是可以放入背包多次），求解将哪些物品装入背包里物品价值总和最大。
完全背包和01背包问题唯一不同的地方就是，每种物品有无限件。
#include<iostream>
using namespace std;
int main() {
int w[] = {1, 4, 3}; //物品重量
int v[] = {1500, 3000, 2000}; //物品的价值
int m = 4; //背包容量
int n = 3; //物品的个数
int dp[5];
//初始化dp数组
for (int j = 0; j <= m; j++) {
dp[j] = 0;
}
//填表
for(int i=1; i<=n; i++) {
for(int j=1; j<=m; j++) {
if(j>=w[i-1])
dp[j] = max(dp[j],dp[j-w[i-1]]+v[i-1]);
}
//输出dp数组
// for(int j=0; j<=m; j++) {
// cout<<dp[j]<<" ";
// }
// cout<<endl;
}
//最大总价值
cout<<dp[m];
}
注意要点：
- 内层循环变为正向遍历
- 递推方程式与01完全背包一致
LeetCode中 “完全背包” 题型汇总：
（4） “打家劫舍”系列
（5）“股票”系列【大多可用“贪心”思维】
（6） “子序列”系列
- 最大子序和
- 最长连续递增序列
- 最长递增子序列【较难】
- 最长递增子序列的个数
【难】
以下标黄题目思路基本一致：
==最长重复子数组==【较难】
==最长公共子序列==【较难】
==不相交的线==【较难】
不同的子序列【困难】
编辑距离【困难】
回文子串【较难】
最长回文子串【较难】
（7）“跳跃游戏”系列【可用“贪心”思维】
13.分治算法
14.回溯算法
腾讯云面向开发者汇聚海量精品云计算使用和开发经验，营造开放的云计算技术生态圈。
更多推荐
32
0- 0
已为社区贡献4条内容
所有评论(0)