二分查找
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
|
#include <iostream>
#include <vector>
using namespace std;
// 二分查找函数/红绿灯标记法
bool isGreen(vector<int>arr,int mid,int target) {
return arr[mid] >= target;
}
int findMinGreenIndex(vector<int>arr,int len,int target) {
int left = -1;
int right = len;
while (left + 1 < right) {
int mid = (left + right ) / 2;
if (isGreen(arr,mid,target)) {
right = mid;
} else {
left = mid;
}
}
if (right == len ||right == 0 && arr[right] > target || left>-1&&right<len&&arr[right] != target) {
return -1;
}
return right;
}
int main() {
vector<int>arr = {1,3,5,7,9,11,13,15,17,19};
int target;
while(cin>>target)
{
if(target == -1)
break;
int len = arr.size();
int result = findMinGreenIndex(arr,len,target);
if(result == -1)
cout << "Not Found" << endl;
else
cout << result << endl;
}
return 0;
}
|
这段代码实现了一个二分查找算法，用于在一个有序数组中查找目标值。具体来说，它使用了一种称为“红绿灯标记法”的技术来确定目标值的位置。
代码的主要部分如下：
线性枚举
- 线性枚举特点
- 暴力算法
- 简单有效
- 用于开拓思路
- 没有数据结构基础也能学
线性枚举是一种基本的算法策略，它通过顺序遍历数据结构（如数组、列表等）中的每个元素来查找或处理特定的元素或满足特定条件的元素。这种方法通常被称为“暴力算法”，因为它不依赖于任何特定的数据结构或算法优化，而是简单地逐个检查每个元素。
假设我们有一个整数数组，我们想要找到数组中的最大值。我们可以使用线性枚举来实现这个目标。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
#include <iostream>
#include <vector>
using namespace std;
int findMax(vector<int>& arr) {
int maxVal = arr[0]; // 假设第一个元素是最大值
for (int i = 1; i < arr.size(); i++) {
if (arr[i] > maxVal) {
maxVal = arr[i]; // 如果找到更大的值，更新最大值
}
}
return maxVal;
}
int main() {
vector<int> arr = {3, 7, 1, 9, 4, 6, 8, 2, 5};
int maxValue = findMax(arr);
cout << "最大值是: " << maxValue << endl;
return 0;
}
|
在这个例子中，findMax函数接受一个整数向量arr作为参数，并返回数组中的最大值。函数首先假设第一个元素是最大值，然后遍历数组中的每个元素。如果找到一个比当前最大值更大的元素，就更新最大值。最后，函数返回最大值。 在main函数中，我们创建了一个包含一些整数的向量arr，然后调用findMax函数来找到数组中的最大值，并将结果输出到控制台。
模拟算法
模拟算法是一种通过模拟实际问题的过程来解决问题的算法。它通常用于解决那些难以用数学公式或其他精确方法解决的问题。模拟算法的基本思想是通过构建一个模型来模拟实际问题的过程，然后通过对模型的操作和分析来得到问题的解。
假设我们要模拟一个简单的银行排队系统，其中顾客随机到达银行并排队等待服务。我们可以使用模拟算法来模拟这个过程，并计算出顾客的平均等待时间。
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
|
#include <iostream>
#include <queue>
#include <cstdlib>
#include <ctime>
// 顾客类
class Customer {
public:
int arrivalTime; // 到达时间
int serviceTime; // 服务时间
Customer(int arrival, int service) : arrivalTime(arrival), serviceTime(service) {}
};
// 模拟银行排队系统
void simulateBankQueue(int totalCustomers, int maxServiceTime) {
std::queue<Customer> queue; // 顾客队列
int currentTime = 0; // 当前时间
int totalWaitTime = 0; // 总等待时间
// 模拟每个顾客的到达和服务过程
for (int i = 0; i < totalCustomers; i++) {
int arrivalTime = currentTime + rand() % 10; // 随机生成到达时间
int serviceTime = rand() % maxServiceTime + 1; // 随机生成服务时间
Customer customer(arrivalTime, serviceTime);
queue.push(customer);
// 如果当前顾客到达时间大于当前时间，更新当前时间
if (arrivalTime > currentTime) {
currentTime = arrivalTime;
}
// 计算当前顾客的等待时间
int waitTime = currentTime - arrivalTime;
totalWaitTime += waitTime;
// 更新当前时间，加上当前顾客的服务时间
currentTime += serviceTime;
}
// 计算平均等待时间
double averageWaitTime = static_cast<double>(totalWaitTime) / totalCustomers;
std::cout << "平均等待时间: " << averageWaitTime << " 分钟" << std::endl;
}
int main() {
srand(static_cast<unsigned int>(time(0))); // 设置随机种子
int totalCustomers = 100; // 总顾客数
int maxServiceTime = 10; // 最大服务时间
simulateBankQueue(totalCustomers, maxServiceTime);
return 0;
}
|
在这个例子中，我们定义了一个Customer类来表示顾客，其中包含到达时间和服务时间。然后，我们定义了一个simulateBankQueue函数来模拟银行排队系统。在函数中，我们使用一个队列来存储顾客，并模拟每个顾客的到达和服务过程。最后，我们计算出顾客的平均等待时间并输出。
在main函数中，我们设置了随机种子，并调用simulateBankQueue函数来模拟银行排队系统。
这个例子展示了模拟算法的基本思想：通过模拟实际问题的过程来解决问题。在这个例子中，我们模拟了银行排队系统的过程，并计算出了顾客的平均等待时间。
交换数字
编写一个函数，不使用临时变量，交换两个数字的值。
输入number=[1,2],输出[2,1]
1
2
3
4
5
6
|
vector<int> swapNumbers(vector<int> &number) {
number[0] = number[0] ^ number[1];
number[1] = number[0] ^ number[1];
number[0] = number[0] ^ number[1];
return number;
}
|
递推算法
递推算法是一种通过已知条件逐步推导出后续结果的算法。它通常用于解决那些可以通过已知的初始条件和递推关系来求解的问题。递推算法的基本思想是将一个复杂的问题分解为一系列简单的子问题，然后通过逐步求解这些子问题来得到最终的解。
- 递推算法的特点：
- 基于已知条件：递推算法依赖于已知的初始条件和递推关系来求解问题。通过已知的初始条件，可以逐步推导出后续的结果。
- 逐步求解：递推算法通过逐步求解子问题来得到最终的解。在每一步中，根据已知的条件和递推关系，计算出当前的结果，并将其作为下一步的输入。
- 高效性：递推算法通常具有较高的效率，因为它避免了重复计算。通过保存已经计算过的结果，可以在后续的计算中直接使用，从而减少了计算量。
- 应用场景：
- 斐波那契数列：递推算法常用于求解斐波那契数列。斐波那契数列是一个由0和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
|
#include <iostream>
int fibonacciSum(int n) {
if (n <= 0) {
return 0;
} else if (n == 1) {
return 1;
}
int a = 0, b = 1, sum = 1;
for (int i = 2; i <= n; i++) {
int temp = a + b;
a = b;
b = temp;
sum += b;
}
return sum;
}
int main() {
int n = 30;
int result = fibonacciSum(n);
std::cout << "斐波那契数列前 " << n << " 项的和为: " << result << std::endl;
return 0;
}
|
在这个代码中，fibonacciSum函数接受一个整数n作为参数，表示要计算斐波那契数列的前n项和。函数使用两个变量a和b来存储斐波那契数列的前两项，初始值分别为0和1。然后，通过一个循环从第3项开始计算斐波那契数列的每一项，并将其累加到变量sum中。最后，函数返回sum作为结果。 在main函数中，我们调用fibonacciSum函数并传入参数30，然后将结果输出到控制台。
选择排序
选择排序是一种简单直观的排序算法，它的基本思想是在未排序的序列中找到最小（或最大）元素，然后将其放到已排序序列的末尾。重复这个过程，直到所有元素都已排序。
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
|
#include <iostream>
#include <vector>
void selectionSort(std::vector<int>& arr) {
int n = arr.size();
for (int i = 0; i < n ; i++) {
int minIndex = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
int temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
}
int main() {
std::vector<int> arr = {64, 25, 12, 22, 11};
selectionSort(arr);
std::cout << "排序后的数组: ";
for (int i = 0; i < arr.size(); i++) {
std::cout << arr[i] << " ";
}
std::cout << std::endl;
return 0;
}
|
在这个代码中，selectionSort 函数接受一个整数向量 arr 作为参数，并对其进行排序。函数使用两个嵌套的循环来实现选择排序。外层循环控制排序的轮数，内层循环用于找到未排序部分的最小元素。如果找到的最小元素的索引不等于当前轮数的索引，则交换这两个元素。 在 main 函数中，我们创建了一个包含一些整数的向量 arr，然后调用 selectionSort 函数对其进行排序。最后，我们输出排序后的数组。
选择排序的时间复杂度为 O(n^2)，其中 n 是数组的长度。这是因为它需要进行 n-1 轮比较，每轮比较需要遍历未排序部分的所有元素。尽管选择排序的时间复杂度较高，但它的实现简单，适用于小规模数据的排序。
冒泡排序
冒泡排序是一种简单的排序算法，它重复地遍历要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。遍历数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
#include <iostream>
#include <vector>
void bubbleSort(std::vector<int>& arr) {
int n = arr.size();
for (int i = n - 1 ; i >= 0 ; i--) {
for (int j = 0; j < i; j++) {
if (arr[j] > arr[j + 1]) {
std::swap(arr[j], arr[j + 1]);
}
}
}
}
int main() {
std::vector<int> arr = {64, 34, 25, 12, 22, 11, 90};
bubbleSort(arr);
std::cout << "排序后的数组: ";
for (int i = 0; i < arr.size(); i++) {
std::cout << arr[i] << " ";
}
std::cout << std::endl;
return 0;
}
|
在这个代码中，bubbleSort 函数接受一个整数向量 arr 作为参数，并对其进行排序。函数使用两个嵌套的循环来实现冒泡排序。外层循环控制排序的轮数，内层循环用于比较相邻的元素并进行交换。
在 main 函数中，我们创建了一个包含一些整数的向量 arr，然后调用 bubbleSort 函数对其进行排序。最后，我们输出排序后的数组。
冒泡排序的时间复杂度为 O(n^2)，其中 n 是数组的长度。这是因为它需要进行 n-1 轮比较，每轮比较需要遍历未排序部分的所有元素。尽管冒泡排序的时间复杂度较高，但它的实现简单，适用于小规模数据的排序。
插入排序
插入排序是一种简单直观的排序算法，它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到O(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
|
#include <iostream>
#include <vector>
void insertionSort(std::vector<int>& arr) {
int n = arr.size();
for (int i = 1; i < n; ++i) {
int key = arr[i];
int j = i - 1;
// 将比key大的元素向后移动
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
--j;
}
arr[j + 1] = key;
}
}
int main() {
std::vector<int> arr = {12, 11, 13, 5, 6};
insertionSort(arr);
std::cout << "排序后的数组: ";
for (int i = 0; i < arr.size(); ++i) {
std::cout << arr[i] << " ";
}
std::cout << std::endl;
return 0;
}
|
在这个代码中，insertionSort 函数接受一个整数向量 arr 作为参数，并对其进行插入排序。函数首先遍历数组，从第二个元素开始，将当前元素存储在变量 key 中。然后，使用一个内部循环将比 key 大的元素向后移动，直到找到 key 的正确位置。最后，将 key 插入到正确的位置。 在 main 函数中，我们创建了一个包含一些整数的向量 arr，然后调用 insertionSort 函数对其进行排序。最后，我们输出排序后的数组。
插入排序的时间复杂度为 O(n^2)，其中 n 是数组的长度。这是因为它需要进行 n-1 轮比较，每轮比较需要遍历已排序部分的所有元素。尽管插入排序的时间复杂度较高，但它的实现简单，适用于小规模数据的排序。
计数排序
计数排序是一种非比较型整数排序算法，它的工作原理是通过统计数组中每个元素出现的次数，然后根据这些统计信息将元素放回原数组中，从而实现排序。计数排序适用于一定范围内的整数排序，并且在这个范围内的整数数量不是特别大的情况下，它的时间复杂度可以达到线性级别，即 O(n + k)，其中 n 是数组的长度，k 是数组中元素的最大值。
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
|
#include <iostream>
#include <vector>
#include <algorithm>
void countingSort(std::vector<int>& arr) {
if (arr.empty()) return;
// 找到数组中的最大值
int max_value = *std::max_element(arr.begin(), arr.end());
// 创建计数数组，大小为最大值加1
std::vector<int> count(max_value + 1, 0);
// 统计每个元素出现的次数
for (int num : arr) {
count[num]++;
}
// 根据计数数组将元素放回原数组
int index = 0;
for (int i = 0; i <= max_value; ++i) {
while (count[i] > 0) {
arr[index++] = i;
count[i]--;
}
}
}
int main() {
std::vector<int> arr = {4, 2, 2, 8, 3, 3, 1};
countingSort(arr);
std::cout << "排序后的数组: ";
for (int num : arr) {
std::cout << num << " ";
}
std::cout << std::endl;
return 0;
}
|
在这个代码中，countingSort 函数接受一个整数向量 arr 作为参数，并对其进行计数排序。函数首先找到数组中的最大值，然后创建一个大小为最大值加1的计数数组 count。接着，统计每个元素在原数组中出现的次数，并将这些次数存储在计数数组中。最后，根据计数数组将元素放回原数组，从而实现排序。 在 main 函数中，我们创建了一个包含一些整数的向量 arr，然后调用 countingSort 函数对其进行排序。最后，我们输出排序后的数组。
计数排序的时间复杂度为 O(n + k)，其中 n 是数组的长度，k 是数组中元素的最大值。这使得它在一定范围内的整数排序中非常高效。然而，计数排序需要额外的空间来存储计数数组，因此它的空间复杂度为 O(k)。如果数组中的元素范围很大，计数排序可能会消耗大量的内存。
并归排序
归并排序是一种分治算法，它将一个数组分成两个子数组，分别对这两个子数组进行排序，然后将它们合并成一个有序的数组。归并排序的时间复杂度为 O(n log n)，其中 n 是数组的长度。
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
|
#include <iostream>
#include <vector>
void merge(std::vector<int>& arr, int left, int mid, int right) {
int n1 = mid - left + 1;
int n2 = right - mid;
std::vector<int> L(n1), R(n2);
for (int i = 0; i < n1; i++)
L[i] = arr[left + i];
for (int j = 0; j < n2; j++)
R[j] = arr[mid + 1 + j];
int i = 0, j = 0, k = left;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
} else {
arr[k] = R[j];
j++;
}
k++;
}
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}
void mergeSort(std::vector<int>& arr, int left, int right) {
if (left < right) {
int mid = left + (right - left) / 2;
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
merge(arr, left, mid, right);
}
}
int main() {
std::vector<int> arr = {12, 11, 13, 5, 6, 7};
int arr_size = arr.size();
mergeSort(arr, 0, arr_size - 1);
std::cout << "排序后的数组: ";
for (int i = 0; i < arr_size; i++)
std::cout << arr[i] << " ";
std::cout << std::endl;
return 0;
}
|
在这个代码中，merge 函数用于合并两个子数组，mergeSort 函数用于递归地对数组进行排序。在 main 函数中，我们创建了一个包含一些整数的向量 arr，然后调用 mergeSort 函数对其进行排序。最后，我们输出排序后的数组。
归并排序的时间复杂度为 O(n log n)，其中 n 是数组的长度。这是因为它将数组分成两个子数组，每个子数组的长度为 n/2，然后对这两个子数组进行排序，最后将它们合并成一个有序的数组。由于每次合并操作的时间复杂度为 O(n)，因此归并排序的总时间复杂度为 O(n log n)。
快速排序
快速排序是一种高效的排序算法，它采用分治的策略来对数组进行排序。快速排序的基本思想是选择一个基准元素，将数组分为两部分，一部分的所有元素都小于基准元素，另一部分的所有元素都大于基准元素。然后对这两部分分别进行快速排序，最终整个数组就会变得有序。
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
|
#include <iostream>
#include <vector>
int partition(std::vector<int>& arr, int low, int high) {
int pivot = arr[high];
int i = (low - 1);
for (int j = low; j <= high - 1; j++) {
if (arr[j] < pivot) {
i++;
std::swap(arr[i], arr[j]);
}
}
std::swap(arr[i + 1], arr[high]);
return (i + 1);
}
void quickSort(std::vector<int>& arr, int low, int high) {
if (low < high) {
int pi = partition(arr, low, high);
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
int main() {
std::vector<int> arr = {10, 7, 8, 9, 1, 5};
int n = arr.size();
quickSort(arr, 0, n - 1);
std::cout << "排序后的数组: ";
for (int i = 0; i < n; i++)
std::cout << arr[i] << " ";
std::cout << std::endl;
return 0;
}
|
在这个代码中，partition 函数用于选择一个基准元素，并将数组分为两部分。quickSort 函数用于递归地对数组进行排序。在 main 函数中，我们创建了一个包含一些整数的向量 arr，然后调用 quickSort 函数对其进行排序。最后，我们输出排序后的数组。
快速排序的时间复杂度为 O(n log n)，其中 n 是数组的长度。这是因为它将数组分成两部分，每个部分的长度为 n/2，然后对这两部分分别进行排序，最后将它们合并成一个有序的数组。由于每次划分操作的时间复杂度为 O(n)，因此快速排序的总时间复杂度为 O(n log n)。
快速排序是一种非常高效的排序算法，适用于大规模数据的排序。它的实现相对简单，并且在大多数情况下都能提供较好的性能。
桶排序
桶排序是一种分布式排序算法，它将数组分到有限数量的桶子里。每个桶子再个别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序）。桶排序是鸽巢排序的一种归纳结果。当要被排序的数组内的数值是均匀分配的时候，桶排序使用线性时间（Θ(n)）。但桶排序并不是比较排序，他不受到 O(n log n) 下限的影响。
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
|
#include <iostream>
#include <vector>
#include <algorithm>
void bucketSort(std::vector<int>& arr, int bucketSize = 5) {
if (arr.empty()) return;
// 找到数组中的最大值和最小值
int min_value = *std::min_element(arr.begin(), arr.end());
int max_value = *std::max_element(arr.begin(), arr.end());
// 计算桶的数量
int bucket_count = (max_value - min_value) / bucketSize + 1;
std::vector<std::vector<int>> buckets(bucket_count);
// 将数组中的元素分配到桶中
for (int num : arr) {
int bucket_index = (num - min_value) / bucketSize;
buckets[bucket_index].push_back(num);
}
// 对每个桶中的元素进行排序，并将排序后的元素放回原数组
int index = 0;
for (auto& bucket : buckets) {
std::sort(bucket.begin(), bucket.end());
for (int num : bucket) {
arr[index++] = num;
}
}
}
int main() {
std::vector<int> arr = {4, 2, 2, 8, 3, 3, 1};
bucketSort(arr);
std::cout << "排序后的数组: ";
for (int num : arr) {
std::cout << num << " ";
}
std::cout << std::endl;
return 0;
}
|
在这个代码中，bucketSort 函数接受一个整数向量 arr 和一个可选的桶大小 bucketSize 作为参数，并对其进行桶排序。函数首先找到数组中的最大值和最小值，然后计算桶的数量。接着，将数组中的元素分配到桶中。最后，对每个桶中的元素进行排序，并将排序后的元素放回原数组。 在 main 函数中，我们创建了一个包含一些整数的向量 arr，然后调用 bucketSort 函数对其进行排序。最后，我们输出排序后的数组。
桶排序的时间复杂度取决于桶的数量和每个桶中元素的数量。在最坏情况下，所有元素都被分配到同一个桶中，此时桶排序的时间复杂度为 O(n^2)。在最好情况下，每个桶中的元素数量大致相同，此时桶排序的时间复杂度为 O(n)。桶排序的空间复杂度为 O(n + k)，其中 n 是数组的长度，k 是桶的数量。
基数排序
基数排序是一种非比较型整数排序算法，它的工作原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。基数排序的时间复杂度为 O(d * (n + k))，其中 d 是数字的最大位数，n 是数组的长度，k 是基数（通常为 10）。
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
|
#include <iostream>
#include <vector>
#include <algorithm>
void countingSort(std::vector<int>& arr, int exp) {
int n = arr.size();
std::vector<int> output(n);
std::vector<int> count(10, 0);
// 统计每个数字出现的次数
for (int i = 0; i < n; i++)
count[(arr[i] / exp) % 10]++;
// 计算每个数字的累计次数
for (int i = 1; i < 10; i++)
count[i] += count[i - 1];
// 将元素放到正确的位置上
for (int i = n - 1; i >= 0; i--) {
output[count[(arr[i] / exp) % 10] - 1] = arr[i];
count[(arr[i] / exp) % 10]--;
}
// 将排序后的元素复制回原数组
for (int i = 0; i < n; i++)
arr[i] = output[i];
}
void radixSort(std::vector<int>& arr) {
if (arr.empty()) return;
// 找到数组中的最大值
int max_value = *std::max_element(arr.begin(), arr.end());
// 对每一位进行计数排序
for (int exp = 1; max_value / exp > 0; exp *= 10)
countingSort(arr, exp);
}
int main() {
std::vector<int> arr = {170, 45, 75, 90, 802, 24, 2, 66};
radixSort(arr);
std::cout << "排序后的数组: ";
for (int num : arr)
std::cout << num << " ";
std::cout << std::endl;
return 0;
}
|
在这个代码中，countingSort 函数用于对数组中的元素按指定的位数进行计数排序。radixSort 函数用于对数组进行基数排序，它通过多次调用 countingSort 函数，每次按不同的位数进行排序，最终实现整个数组的排序。 在 main 函数中，我们创建了一个包含一些整数的向量 arr，然后调用 radixSort 函数对其进行排序。最后，我们输出排序后的数组。
基数排序的时间复杂度为 O(d * (n + k))，其中 d 是数字的最大位数，n 是数组的长度，k 是基数（通常为 10）。这使得它在一定范围内的整数排序中非常高效。然而，基数排序需要额外的空间来存储临时数组，因此它的空间复杂度为 O(n + k)。如果数组中的元素范围很大，基数排序可能会消耗大量的内存。
堆排序
堆排序是一种基于二叉堆数据结构的排序算法。它的基本思想是将数组构建成一个最大堆（或最小堆），然后依次将堆顶元素与堆的最后一个元素交换，并对剩余的元素进行堆调整，直到整个数组有序。
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
|
#include <iostream>
#include <vector>
void heapify(std::vector<int>& arr, int n, int i) {
int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < n && arr[left] > arr[largest])
largest = left;
if (right < n && arr[right] > arr[largest])
largest = right;
if (largest != i) {
std::swap(arr[i], arr[largest]);
heapify(arr, n, largest);
}
}
void heapSort(std::vector<int>& arr) {
int n = arr.size();
// 构建最大堆
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);
// 依次将堆顶元素与堆的最后一个元素交换，并对剩余的元素进行堆调整
for (int i = n - 1; i > 0; i--) {
std::swap(arr[0], arr[i]);
heapify(arr, i, 0);
}
}
int main() {
std::vector<int> arr = {12, 11, 13, 5, 6, 7};
heapSort(arr);
std::cout << "排序后的数组: ";
for (int num : arr)
std::cout << num << " ";
std::cout << std::endl;
return 0;
}
|
在这个代码中，heapify 函数用于维护最大堆的性质，即父节点的值大于等于其子节点的值。heapSort 函数用于对数组进行堆排序，它首先构建一个最大堆，然后依次将堆顶元素与堆的最后一个元素交换，并对剩余的元素进行堆调整，直到整个数组有序。 在 main 函数中，我们创建了一个包含一些整数的向量 arr，然后调用 heapSort 函数对其进行排序。最后，我们输出排序后的数组。
堆排序的时间复杂度为 O(n log n)，其中 n 是数组的长度。这是因为构建最大堆的时间复杂度为 O(n)，每次调整堆的时间复杂度为 O(log n)，而需要进行 n-1 次调整。堆排序的空间复杂度为 O(1)，因为它只需要常数级别的额外空间来存储临时变量。
哈希算法
哈希算法（Hash Algorithm）是一种将任意长度的输入数据映射为固定长度的哈希值的算法。哈希算法的主要特点是：
- 确定性：对于相同的输入数据，哈希算法始终会生成相同的哈希值。
- 快速计算：哈希值的计算速度非常快。
- 雪崩效应：输入数据的微小变化会导致哈希值的巨大变化。
- 哈希冲突：不同的输入可能会产生相同的哈希值，但好的哈希算法应该尽量减少冲突的发生。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
#include <iostream>
#include <string>
// 简单的哈希函数，将字符串转换为整数哈希值
unsigned int hash(const std::string& str) {
unsigned int hash = 0;
for (char c : str) {
hash = hash * 31 + c;
}
return hash;
}
int main() {
std::string input = "Hello, World!";
unsigned int hashValue = hash(input);
std::cout << "Input: " << input << std::endl;
std::cout << "Hash Value: " << hashValue << std::endl;
return 0;
}
|
在这个示例中，我们定义了一个简单的哈希函数hash，它将输入的字符串转换为一个整数哈希值。哈希函数使用了一个简单的乘法和加法操作，将字符串中的每个字符转换为一个整数，并将它们相加得到最终的哈希值。
贪心算法
贪心算法是一种在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望导致结果是全局最好或最优的算法。贪心算法在有最优子结构的问题中尤为有效。最优子结构的意思是局部最优解能决定全局最优解。简单地说，问题能够分解成子问题来解决，子问题的最优解能递推到最终问题的最优解。
假设游戏规则是：有一排硬币，正面朝上为 1，反面朝上为 0，每次可以选择连续的 k 个硬币进行翻转，目标是用最少的翻转次数让所有硬币都正面朝上。
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
|
#include <iostream>
#include <vector>
// 翻硬币游戏的贪心算法
int minFlips(std::vector<int>& coins, int k) {
int n = coins.size();
int flips = 0;
std::vector<int> isFlipped(n, 0); // 记录每个位置是否被翻转过
int currentFlip = 0; // 当前位置的翻转次数
for (int i = 0; i <= n - k; ++i) {
// 更新当前位置的翻转次数
if (i >= k) {
currentFlip ^= isFlipped[i - k];
}
// 如果当前硬币需要翻转
if ((coins[i] + currentFlip) % 2 == 0) {
isFlipped[i] = 1;
currentFlip ^= 1;
flips++;
}
}
// 检查剩余的硬币是否都正面朝上
for (int i = n - k + 1; i < n; ++i) {
if (i >= k) {
currentFlip ^= isFlipped[i - k];
}
if ((coins[i] + currentFlip) % 2 == 0) {
return -1; // 无法全部翻转为正面
}
}
return flips;
}
int main() {
std::vector<int> coins = {0, 1, 0, 1, 0};
int k = 2;
int result = minFlips(coins, k);
if (result != -1) {
std::cout << "最少需要翻转 " << result << " 次。" << std::endl;
} else {
std::cout << "无法将所有硬币翻转为正面。" << std::endl;
}
return 0;
}
|
- minFlips 函数：
- isFlipped 数组用于记录每个位置是否被翻转过。
- currentFlip 变量用于记录当前位置的翻转次数。
- 遍历前 n - k + 1 个硬币，如果当前硬币需要翻转，则进行翻转并更新 isFlipped 数组和 currentFlip 变量。
- 最后检查剩余的硬币是否都正面朝上，如果有硬币需要翻转但无法翻转，则返回 -1。
- main 函数：
- 定义一个硬币数组 coins 和每次翻转的硬币数量 k。
- 调用 minFlips 函数计算最少的翻转次数，并输出结果。
前缀和
前缀和是一种重要的预处理技术，能有效降低查询数组区间和的时间复杂度。
前缀和是一种预处理技术，用于快速计算数组中任意区间的和。对于一个长度为 n 的数组 arr，其前缀和数组 prefixSum 的第 i 个元素 prefixSum[i] 表示原数组中从下标 0 到下标 i 的所有元素的和。
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
|
#include <iostream>
#include <vector>
// 构建前缀和数组
std::vector<int> buildPrefixSum(const std::vector<int>& arr) {
int n = arr.size();
std::vector<int> prefixSum(n);
prefixSum[0] = arr[0];
for (int i = 1; i < n; ++i) {
prefixSum[i] = prefixSum[i - 1] + arr[i];
}
return prefixSum;
}
// 计算区间 [left, right] 的和
int queryRangeSum(const std::vector<int>& prefixSum, int left, int right) {
if (left == 0) {
return prefixSum[right];
}
return prefixSum[right] - prefixSum[left - 1];
}
int main() {
std::vector<int> arr = {1, 3, 5, 7, 9};
std::vector<int> prefixSum = buildPrefixSum(arr);
// 查询区间 [1, 3] 的和
int left = 1, right = 3;
int sum = queryRangeSum(prefixSum, left, right);
std::cout << "区间 [" << left << ", " << right << "] 的和为: " << sum << std::endl;
return 0;
}
|
- buildPrefixSum 函数：
该函数接收一个整数向量 arr，返回其前缀和数组。通过遍历原数组，累加元素得到前缀和数组。
- queryRangeSum 函数：
此函数接收前缀和数组 prefixSum 以及查询区间的左右边界 left 和 right，返回该区间的和。若 left 为 0，直接返回 prefixSum[right]；否则，返回 prefixSum[right] - prefixSum[left - 1]。
- main 函数：
创建一个示例数组 arr，调用 buildPrefixSum 函数构建前缀和数组，然后调用 queryRangeSum 函数查询区间 [1, 3] 的和并输出结果。
双指针
双指针是一种通过维护两个指针变量来高效处理线性数据结构的算法技巧。常见于数组、链表等场景，通过同步或异步移动两个指针来优化时间复杂度。
- 快慢指针（链表环路检测）
- 对撞指针
- 分离双指针
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
|
#include <iostream>
using namespace std;
struct ListNode {
int val;
ListNode* next;
ListNode(int x) : val(x), next(nullptr) {}
};
bool hasCycle(ListNode* head) {
ListNode* slow = head;
ListNode* fast = head;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast) return true;
}
return false;
}
int main() {
// 创建带环链表测试用例
ListNode* node1 = new ListNode(3);
ListNode* node2 = new ListNode(2);
ListNode* node3 = new ListNode(0);
ListNode* node4 = new ListNode(-4);
node1->next = node2;
node2->next = node3;
node3->next = node4;
node4->next = node2; // 形成环
cout << boolalpha << hasCycle(node1) << endl; // 输出 true
return 0;
}
|
左右指针示例：有序数组两数之和:
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
|
#include <iostream>
#include <vector>
using namespace std;
vector<int> twoSum(vector<int>& nums, int target) {
int left = 0;
int right = nums.size() - 1;
while (left < right) {
int sum = nums[left] + nums[right];
if (sum == target) {
return {left + 1, right + 1}; // 返回1-based索引
} else if (sum < target) {
left++;
} else {
right--;
}
}
return {};
}
int main() {
vector<int> nums = {2, 7, 11, 15};
auto res = twoSum(nums, 9);
cout << "[" << res[0] << ", " << res[1] << "]" << endl; // 输出 [1, 2]
return 0;
}
|
算法特点
- 时间复杂度优化：通常将O(n²)暴力解优化至O(n)
- 空间复杂度优势：多数情况只需常数级额外空间
- 实现简洁：逻辑清晰且代码量少
滑动窗口
别名“双指针”，“尺取法”
滑动窗口是一种通过维护窗口边界来高效处理连续区间问题的算法。常用于字符串、数组等线性结构，通过调节窗口大小/位置来优化暴力解法。
滑动窗口特点:
- 时间复杂度:通常将O(n²)优化至O(n)
- 固定大小窗口:窗口长度固定
- 可变大小窗口:根据条件动态调整窗口边界
-
- 简单 直观 易懂
-
- 时间 空间效率高
-
- 大部分题目只需要了解数组即可
-
- 部分题目需要哈希表的数据结构基础
示例：最长无重复字符子串
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
|
#include <iostream>
#include <unordered_set>
using namespace std;
int lengthOfLongestSubstring(string s) {
unordered_set<char> window; // 用于存储窗口内的字符
int max_len = 0;
int left = 0; // 窗口左边界
for (int right = 0; right < s.size(); right++) {
// 当遇到重复字符时收缩左边界
while (window.count(s[right])) {
window.erase(s[left]);
left++;
}
window.insert(s[right]);
max_len = max(max_len, right - left + 1);
}
return max_len;
}
int main() {
string test = "abcabcbb";
cout << "最长无重复子串长度: "
<< lengthOfLongestSubstring(test) << endl; // 输出 3
return 0;
}
|
- 变量初始化：
- unordered_set window;：使用 unordered_set 来存储当前窗口内的字符，unordered_set 可以快速判断一个字符是否已经存在于窗口中。
- int max_len = 0;：用于记录最长无重复字符子串的长度。
- int left = 0;：窗口的左边界，初始化为 0。
- 遍历字符串：
- for (int right = 0; right < s.size(); right++)：使用 right 指针从左到右遍历字符串。
- 处理重复字符：
- while (window.count(s[right]))：当 window 中已经存在当前字符 s[right] 时，说明出现了重复字符，需要收缩窗口。
- window.erase(s[left]);：从 window 中移除窗口左边界的字符。
- left++;：将窗口左边界右移一位。
- 更新窗口和最大长度：
- window.insert(s[right]);：将当前字符插入到 window 中。
- max_len = max(max_len, right - left + 1);：更新最长无重复字符子串的长度。
- 函数 main（该函数用于测试 lengthOfLongestSubstring 函数）
- 定义测试字符串：
- string test = “abcabcbb”;：定义一个测试字符串。
- 调用函数并输出结果：
- cout « “最长无重复子串长度: " « lengthOfLongestSubstring(test) « endl;：调用 lengthOfLongestSubstring 函数计算最长无重复字符子串的长度，并输出结果。
- 复杂度分析
- 时间复杂度：$O(n)$，其中 $n$ 是字符串的长度。每个字符最多被访问两次，一次是 right 指针右移时，一次是 left 指针右移时。
- 空间复杂度：$O(k)$，其中 $k$ 是字符集的大小。在本题中，字符集是 ASCII 字符集，因此 $k$ 是一个常数。
最短路径(dijkstra算法)
特点
- 非负边权
- 单源最短路
- 顶点数最好小于1000
- 少量数据结构知识和一点点的算法基础
Dijkstra算法是一种用于计算带权有向图或无向图中单个源节点到所有其他节点的最短路径的贪心算法。
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
|
#include <iostream>
#include <vector>
#include <queue>
#include <limits>
using namespace std;
// 定义无穷大
const int INF = numeric_limits<int>::max();
// Dijkstra算法实现
vector<int> dijkstra(const vector<vector<pair<int, int>>>& graph, int start) {
int n = graph.size();
vector<int> dist(n, INF); // 存储最短距离
dist[start] = 0;
// 优先队列，存储 (距离, 节点)
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
pq.push({0, start});
while (!pq.empty()) {
int u = pq.top().second;
int d = pq.top().first;
pq.pop();
// 如果当前距离大于已记录的最短距离，跳过
if (d > dist[u]) continue;
// 遍历当前节点的所有邻接节点
for (const auto& edge : graph[u]) {
int v = edge.first;
int weight = edge.second;
// 松弛操作
if (dist[u] + weight < dist[v]) {
dist[v] = dist[u] + weight;
pq.push({dist[v], v});
}
}
}
return dist;
}
int main() {
int n = 5; // 节点数
vector<vector<pair<int, int>>> graph(n);
// 添加边
graph[0].emplace_back(1, 4);
graph[0].emplace_back(2, 1);
graph[1].emplace_back(2, 2);
graph[1].emplace_back(3, 5);
graph[2].emplace_back(1, 2);
graph[2].emplace_back(3, 8);
graph[2].emplace_back(4, 10);
graph[3].emplace_back(4, 2);
graph[4].emplace_back(3, 2);
int start = 0; // 起始节点
vector<int> dist = dijkstra(graph, start);
// 输出最短距离
for (int i = 0; i < n; ++i) {
cout << "从节点 " << start << " 到节点 " << i << " 的最短距离是: ";
if (dist[i] == INF) {
cout << "无穷大" << endl;
} else {
cout << dist[i] << endl;
}
}
return 0;
}
|
在这个代码中，dijkstra 函数实现了Dijkstra算法，它接受一个邻接表表示的图和一个起始节点作为参数，返回一个包含从起始节点到所有其他节点的最短距离的向量。在 main 函数中，我们创建了一个示例图，并调用 dijkstra 函数计算最短路径，最后输出结果。
