算法·入门篇『课堂随笔』

Ne0inhk

— 45 min read
算法·入门篇『课堂随笔』

Zero·前言

本文章需结合 B站教学视频 共同学习与观看。

一、O(n)

1.1 分析模型基础

在分析算法复杂度之前，我们必须知道的概念：

  1. 时间复杂度：算法执行所需的时间与输入规模的关系
    • 白话：大概执行了多少次宏观上、可概括的代码段
  2. 空间复杂度：算法执行所需的额外存储空间与输入规模的关系
    • 白话：开辟了多大的空间，这个容量与输入规模的比例

常用表示法：

  • 大O记号（Big-O）：表示算法的最坏情况或渐进上界
  • Ω记号（Omega）：表示算法的最好情况或渐进下界
  • Θ记号（Theta）：表示算法的紧确界

1.2 冒泡排序分析

voidbubble_sort(int arr[],int n){for(int i =0; i < n-1; i++){bool swapped =false;for(int j =0; j < n-i-1; j++){if(arr[j]> arr[j+1]){swap(arr[j], arr[j+1]); swapped =true;}}if(!swapped)break;}}

时间复杂度分析

  1. 最好情况（已有序数组）：
    • 第一轮遍历后立即退出（借助swapped标志）
    • 比较次数 = n-1
    • 时间复杂度：O(n)
  2. 最坏情况（逆序数组）：
    • 完全执行所有循环
    • 比较次数 = (n-1)+(n-2)+…+1 = n(n-1)/2
    • 时间复杂度：O(n²)
  3. 平均情况：
    • 仍需进行大量比较和交换
    • 时间复杂度：O(n²)
  4. 稳定性分析：
    • 只有相邻元素比较交换
    • 稳定排序

空间复杂度分析

  • 仅使用常数级别的额外空间（i,j和swapped变量）
  • 空间复杂度：O(1)（原地排序）

二、排序算法（入门级别）

排序是很实用的、常用的（几乎是必需品，只不过现在封装的很好，让你感觉不到）

排序的学习可以让你了解一些 算法的基本思想与操作技巧（暴力、比较、交换、分治、减治、空间换时间等）

  • 排序算法也是 分析 时间/空间复杂度的理想模型
  • 排序也是计算机科学早期研究的核心问题（如1956年希尔排序的提出）

2.1 选择排序

排序算法中最简单直观的。

思路：不断缩小范围确定当前范围内的最小/最大值，随后将最小/最大值与目标位置进行交换。那么每一趟筛选的行为就是选出第n个最小/最大值！

举例： 从小到大排序下方数字

  • 18、1、5、27、12（下标范围 0 ~ 4，最小值 1 与 下标 0 的 18 交换）
  • 1、18、5、27、12（下标范围 1 ~ 4，最小值 5 与 下标 1 的 18 交换）
  • 1、5、18、27、12（下标范围 2 ~ 4，最小值 12 与 下标 2 的 18 交换）
  • 1、5、12、27、18（下标范围 3 ~ 4，最小值 18 与 下标 3 的 27 交换）
  • 1、5、12、27、18（下标范围 4 ~ 4，单个元素自然有序）
#include<iostream>usingnamespace std;constint maxN =1e5+10;int arr[maxN];voidselect_sort(int*arr,int n){for(int i =0; i < n -1; i++){int pos = i;// 假设认为当前范围最小值 pos 就是 当前范围的第一个数for(int j = i +1; j < n; j++){if(arr[pos]> arr[j]){// 发现当前范围更小的数 pos = j;// 记录这个数的下标}}// 交换这俩数int t = arr[i]; arr[i]= arr[pos]; arr[pos]= t;}}intmain(void){int n ; cin >> n;for(int i =0; i < n; i++){scanf("%d",&arr[i]);}select_sort(arr, n);for(int i =0; i < n; i++){printf("%d ", arr[i]);}return0;}

2.2 冒泡排序

见名知意，冒泡就是说将目前第n个最大/最小的数，冒泡到顶端。如果顶端有了k个泡，那么就要排在k个泡之后成为第k+1个泡。

思路：由于每次冒泡都需要排在之前泡泡的后面，并且之前冒泡的数值肯定是合理的。所以缩小冒泡范围并把当前范围最小/最大的值，通过相邻元素两两交换最后冒泡到范围顶端。

举例： 从小到大排序下方数字

  • 18、1、5、27、12

（下标范围 0 ~ 4， 18 > 1 交换）1、18、5、27、12

（下标范围 0 ~ 4， 18 > 5 交换）1、5、18、27、12

（下标范围 0 ~ 4， 18 < 5 不交换）1、5、18、27、12

（下标范围 0 ~ 4， 27 > 12 交换）1、5、18、12、27（第一个泡泡）

  • 1、5、18、12、27

（下标范围 0 ~ 3， 1 < 5 不交换）1、5、18、12、27

（下标范围 0 ~ 3， 5 < 18 不交换）1、5、18、12、27

（下标范围 0 ~ 3， 18 > 12 交换）1、5、12、18、27

  • 1、5、12、18、27

（下标范围 0 ~ 2， 1 < 5 不交换）1、5、12、18、27

（下标范围 0 ~ 2， 5 < 12 不交换）1、5、12、18、27

  • 1、5、12、27、18

（下标范围 0 ~ 1， 1 < 5 不交换）1、5、12、18、27

  • 1、5、12、18、27（下标范围 0 ~ 0，单个元素自然有序）
#include<iostream>usingnamespace std;constint maxN =1e5+10;int arr[maxN];voidbuttle_sort(int*arr,int n){for(int i =0; i < n -1; i++){for(int j =0; j < n - i -1; j++){if(arr[j]> arr[j +1]){int temp = arr[j]; arr[j]= arr[j +1]; arr[j +1]= temp;}}}}intmain(void){int n ; cin >> n;for(int i =0; i < n; i++){scanf("%d",&arr[i]);}buttle_sort(arr, n);for(int i =0; i < n; i++){printf("%d ", arr[i]);}return0;}

2.2.1 稳定/不稳定排序的说法

如果一个排序算法在排序后能够保持相等元素的原始相对顺序，那么这个算法就是稳定的。

[("Alice",90),("Bob",85),("Chris",90),("Dave",80)]// 稳定排序的升序（Alice和Chris都是90分，Alice原本在Chris前面，排序后仍然在前面。）[("Dave",80),("Bob",85),("Alice",90),("Chris",90)].// 不稳定排序的升序（可能 Alice 就在 Chris 的后面）[("Dave",80),("Bob",85),("Chris",90),("Alice",90)]

2.3 插入排序

插入排序类似于两堆扑克牌，从无序列扑克牌堆里面选牌插入到有序扑克牌堆。

思路 ：将数组分为已排序和未排序两部分，每次从未排序部分取出第一个元素，在已排序部分找到合适的位置插入。

举例 ：从小到大排序下方数字

  • 18、1、5、27、12（初始状态，第一个元素18视为已排序）
  • 1、18、5、27、12（将1插入到18前面）
  • 1、5、18、27、12（将5插入到1和18之间）
  • 1、5、18、27、12（27已经在正确位置）
  • 1、5、12、18、27（将12插入到5和18之间）
#include<iostream>usingnamespace std;int arr[50];intmain(void){int n; cin >> n;for(int i =0; i < n;++i){ cin >> arr[i];}for(int i =1; i < n;++i){// 要插入的元素int t = arr[i];// 存起来int j = i -1;// 18 1 5 27 12// 1 5 18 27 12for(; j >=0;--j){if(arr[j]> t){ arr[j +1]= arr[j];}else{break;}} arr[j +1]= t;}for(int i =0; i < n;++i){ cout << arr[i]<<" ";}return0;}

2.4 希尔排序

希尔排序是插入排序的改进版，通过分组（分治思想）让插入排序提高了效率。

思路 ：

  1. 选择一个增量序列（通常为n/2, n/4, …, 1）
  2. 依据每个增量去分组，然后将每组都进行插入排序
  3. 到最后增量为1，也就是要进行一次完整的插入排序

希尔排序会有一种假象：让初学者误认为嵌套循环多就是速度慢的、进而忽略了有序序列堆插入排序具体实现过程的影响。

举例 ：从小到大排序下方数字 [18, 1, 5, 27, 12, 9, 6, 15]

  1. 初始增量=4（数组长度8/2）：
    • 分组：[18,12], [1,9], [5,6], [27,15]
    • 排序后：[12,18], [1,9], [5,6], [15,27]
    • 数组变为：[12, 1, 5, 15, 18, 9, 6, 27]
  2. 增量=2：
    • 分组：[12,5,18,6], [1,15,9,27]
    • 排序后：[5,6,12,18], [1,9,15,27]
    • 数组变为：[5, 1, 6, 9, 12, 15, 18, 27]
  3. 增量=1（标准插入排序）：
    • 最终排序结果：[1, 5, 6, 9, 12, 15, 18, 27]
#include<iostream>usingnamespace std;constint maxN =1e5+10;int arr[maxN];voidshell_sort(int*arr,int n){for(int gap = n /2; gap >0; gap /=2){// 增量序列for(int i = gap; i < n; i++){// 对每个分组进行插入排序int temp = arr[i];int j;for(j = i; j >= gap && arr[j - gap]> temp; j -= gap){ arr[j]= arr[j - gap];} arr[j]= temp;}}}intmain(void){int n; cin >> n;for(int i =0; i < n; i++){scanf("%d",&arr[i]);}shell_sort(arr, n);for(int i =0; i < n; i++){printf("%d ", arr[i]);}return0;}

2.5 计数排序

核心思想 ：统计每个元素出现的次数，然后按顺序输出

特点 ：

  • 非比较排序，时间复杂度O(n+k)，k为数据范围
  • 适用于整数且范围不大的情况
  • 稳定排序
voidcountingSort(int arr[],int n){// 假设数据范围在0到100之间int count[101]={0};// 统计每个元素出现的次数for(int i =0; i < n; i++) count[arr[i]]++;// 按顺序填充原数组int index =0;for(int i =0; i <=100; i++){while(count[i]--){ arr[index++]= i;}}}

2.6 归并排序（前置知识：双指针）

归并排序：应用快慢指针与递归去解决排序问题的算法。

#include<iostream>usingnamespace std;// 5 4 3 2 1voidmerge_sort(int*arr,int l,int r){if(l >= r)return;int mid =(l + r)/2;merge_sort(arr, l, mid);merge_sort(arr, mid +1, r);int tmp[10];int i = l, j = mid +1, k =0;while(i <= mid && j <= r){if(arr[i]< arr[j]) tmp[k++]= arr[i++];else tmp[k++]= arr[j++];}while(i <= mid) tmp[k++]= arr[i++];while(j <= r) tmp[k++]= arr[j++];for(i = l, k =0; i <= r;++i,++k){ arr[i]= tmp[k];}}intmain(void){int n;int arr[10]; cin >> n;for(int i =0; i < n;++i){ cin >> arr[i];}merge_sort(arr,0, n -1);for(int i =0; i < n;++i){ cout << arr[i]<<" ";}return0;}

2.7 快速排序（前置知识：双指针）

快速排序：应用左右指针与递归去解决排序问题的算法。

#include<iostream>usingnamespace std;// 5 4 3 2 1voidquick_sort(int*arr,int l,int r){if(l >= r)return;int x = arr[(l + r)/2];int i = l -1, j = r +1;while(i < j){do i++;while(arr[i]< x);do j--;while(arr[j]> x);if(i < j){int temp = arr[i]; arr[i]= arr[j]; arr[j]= temp;}}quick_sort(arr, l, j);quick_sort(arr, j +1, r);}intmain(void){int n;int arr[10]; cin >> n;for(int i =0; i < n;++i){ cin >> arr[i];}quick_sort(arr,0, n -1);for(int i =0; i < n;++i){ cout << arr[i]<<" ";}return0;}

三、大整数四则运算

接下来，我带着大家继续锻炼模拟思维。

何为大整数：通常指的是非常大的整数，其值远超常规数据类型（如32位或64位整数）能直接表示的范围。

意义：

  • 现代加密算法（如 RSA、ECC）依赖大质数或大整数运算，防止暴力破解。例如：RSA-2048 使用两个 1024 位的质数相乘，生成密钥。
  • 精确计算极大数值（如天文数字、阶乘、斐波那契数列等）。

3.1 加法

大整数加法应该算是四个运算法则里，最好理解的了。

#include<iostream>#include<string>#include<vector>usingnamespace std;intmain(void){ string a,b; cin >> a >> b; vector<int> A; vector<int> B;// 做倒置存入到 vector 中（倒置是因为比较好处理，可以不倒置）for(int i = a.size()-1; i >=0;--i){ A.push_back(a[i]-'0');}for(int i = b.size()-1; i >=0;--i){ B.push_back(b[i]-'0');}/* 4321 765 */int t =0;// 维护进位值 vector<int> C;// 存储最后结果for(int i =0; i < A.size()|| i < B.size();++i){if(i < A.size()) t += A[i];// 有就加，该位没数就不加if(i < B.size()) t += B[i]; C.push_back(t %10);// 存储的是某个位的数 t /=10;// 更新进位值}if(t >0) C.push_back(t);// 若最后进位值还有，那么就属于进多了一位for(int i = C.size()-1; i >=0;--i){ cout << C[i];}return0;}

3.2 减法

大整数减法会遇到负数问题的处理，还有前置0。关键点在于这里~

#include<iostream>#include<string>#include<vector>usingnamespace std;// 必须要判断出 A、B 两个数谁更大boolisMax(vector<int> A, vector<int> B){if(A.size()== B.size()){for(int i = A.size()-1; i >=0;--i){if(A[i]== B[i]){continue;}return A[i]> B[i];}returntrue;}else{return A.size()> B.size();}}intmain(void){ string a, b; cin >> a >> b; vector<int> A; vector<int> B;for(int i = a.size()-1; i >=0;--i){ A.push_back(a[i]-'0');}for(int i = b.size()-1; i >=0;--i){ B.push_back(b[i]-'0');}bool flag =isMax(A, B);if(!flag)// 如果 B 比 A 大则将他们交换，因为我们要默认 A - B 进行模拟运算{ vector<int> temp = A; A = B; B = temp;}int t =0;// 借位 vector<int> C;for(int i =0; i < A.size()|| i < B.size();++i){int num =-t;if(i < A.size()) num += A[i];if(i < B.size()) num -= B[i];if(num <0){ t =1; num +=10;}else{ t =0;} C.push_back(num %10);}while(C.size()>1&& C[C.size()-1]==0){ C.pop_back();}if(C.size()==1&& C[0]==0){ cout <<0<< endl;return0;}if(!flag) cout <<"-";for(int i = C.size()-1; i >=0;--i){ cout << C[i];}return0;}

3.3 乘法

#include<iostream>#include<string>#include<vector>#include<algorithm>usingnamespace std;intmain(void){ string a, b; cin >> a >> b; vector<int> A; vector<int> B;for(int i = a.size()-1; i >=0;--i){ A.push_back(a[i]-'0');}for(int i = b.size()-1; i >=0;--i){ B.push_back(b[i]-'0');}/* 4321 765 */ vector<int>C(1000005);if(A.size()< B.size())swap(A, B);for(int i =0; i < B.size();++i){int j =0;int t =0;for(; j < A.size();++j){int num = A[j]* B[i]+ t;int ret = num %10; t = num /10; C[i + j]+= ret; C[i + j +1]+= C[i + j]/10; C[i + j]= C[i + j]%10;}if(t >0) C[i + j]+= t;}bool flag =true;for(int i = A.size()+ B.size(); i >=0;--i){if(i >0&& flag && C[i]==0){continue;}if(flag && C[i]!=0){ flag =false;} cout << C[i];}return0;}

3.4 除法

除法这里用到了大整数减法。

#include<iostream>#include<vector>#include<string>#include<algorithm>usingnamespace std;// 比较两个大整数boolisGreaterOrEqual(vector<int> A, vector<int> B){if(A.size()!= B.size())return A.size()> B.size();for(int i = A.size()-1; i >=0;--i){if(A[i]!= B[i])return A[i]> B[i];}returntrue;}// 减法函数 vector<int>subtractBigInt(vector<int> A, vector<int> B){ vector<int> C;int t =0;for(int i =0; i < A.size()|| i < B.size();++i){int num =-t;if(i < A.size()) num += A[i];if(i < B.size()) num -= B[i];if(num <0){ t =1; num +=10;}else{ t =0;} C.push_back(num %10);}while(C.size()>1&& C.back()==0) C.pop_back();return C;}// 除法函数 pair<vector<int>, vector<int>>divideBigInt(vector<int> dividend, vector<int> divisor){ vector<int> quotient; vector<int> remainder = dividend;if(!isGreaterOrEqual(remainder, divisor)){return{ vector<int>{0}, remainder };} vector<int> current;for(int i = remainder.size()-1; i >=0;--i){ current.insert(current.begin(), remainder[i]);while(current.size()>1&& current.back()==0) current.pop_back();int q =0;while(isGreaterOrEqual(current, divisor)){ current =subtractBigInt(current, divisor); q++;} quotient.push_back(q);}reverse(quotient.begin(), quotient.end());while(quotient.size()>1&& quotient.back()==0) quotient.pop_back();return{ quotient, current };}intmain(){ string a, b; cin >> a >> b; vector<int> A, B;for(int i = a.size()-1; i >=0;--i) A.push_back(a[i]-'0');for(int i = b.size()-1; i >=0;--i) B.push_back(b[i]-'0');auto[quotient, remainder]=divideBigInt(A, B); cout <<"Quotient: ";for(int i = quotient.size()-1; i >=0;--i) cout << quotient[i]; cout <<"\nRemainder: ";for(int i = remainder.size()-1; i >=0;--i) cout << remainder[i];return0;}

四、数组基本操作

4.1 增删改查

  • 增
int arr[50];// 开辟足够大的数组int arr[2]=5;// 比如现在有两个元素了，我们增加一个元素。那就是 为下标2 赋值
  • 删
// 通过覆盖元素实现删除int arr[50]={1,2,3,4,5};// 起始位置为待删除元素位置 终止位置为最后元素位置for(int i =0; i < n;++i){ arr[i]= arr[i+1];}// 由于删掉一个元素 所以长度 从 n => n - 1for(int i =0; i < n -1;++i){ cout << arr[i]<<" ";}
  • 改
arr[5]=18;// 改就是重新赋值
  • 查
cout << arr[5]<< endl;// 直接访问即可

4.2 数组元素交换与自身插入

  • 数组元素交换
// 其实就是依赖于下标找到 A 和 B 然后进行 交换操作int temp = arr[2]; arr[2]= arr[3]; arr[3]= temp;
  • 自身插入：在一个数组中，A元素要插入到B元素的前面或后面
// 这个主要用的是 与删除操作 元素覆盖逆着来的写法。// 比如我们要把下标3的元素 插入到目前下标为1的前面int t = arr[3];for(int i =3-1; i >=1;--i){ arr[i +1]= arr[i];// 这个元素覆盖就是从左往右覆盖的(由于会覆盖掉待移动的元素，所以我们提前用 变量t 存储起来了)} arr[1]= t;// 从下标1 开始都整体往右移动了一位，所以我们只需要将 下标1位置重新赋值为t 即可完成需求// 比如我们要把下标3的元素 插入到目前下标为1的后面int t = arr[3];for(int i =3-1; i >1;--i){ arr[i +1]= arr[i];// 这个元素覆盖就是从左往右覆盖的(由于会覆盖掉待移动的元素，所以我们提前用 变量t 存储起来了)} arr[1+1]= t;

4.3 实现动态数组

动态数组是普通数组的增强版，我记忆非常尤新。大一上学期的大作业，我写的就是动态数组的基本实现。

主要它是要实现以下几个扩展功能：

  • 自动扩容
  • 增删改查方法
  • size方法
#include<iostream>#include<cstring>usingnamespace std;template<typenameT>classDynamicArray{private: T*data; size_t size; size_t capacity;// 扩容voidreserve(size_t new_capacity){if(new_capacity <= capacity)return; T* new_data =new T[new_capacity];// 分配新内存for(size_t i =0; i < size; i++){ new_data[i]= data[i];}delete[] data;// 释放旧内存 data = new_data; capacity = new_capacity;}public:DynamicArray(size_t init_capacity =4):size(0),capacity(init_capacity >0? init_capacity :4){ data =new T[capacity];// 分配初始内存}// 析构函数（释放内存）~DynamicArray(){delete[] data;}voidpush_back(const T& elem){if(size >= capacity){reserve(capacity *2);} data[size++]= elem;// size 就是下标 size++ 就是数量}voidremove(size_t index){if(index >= size){throwout_of_range("index out of bounds");return;}for(int i = index; i < size -1;++i){ data[i]= data[i +1];} data[size -1].~T();// 调用析构函数 size--;// 数量少了一个！} T&operator[](size_t index){if(index >= size){throwout_of_range("index out of bounds");}return data[index];} size_t get_size()const{return size;} size_t get_capacity()const{return capacity;}};intmain(void){ DynamicArray<int> arr; arr.push_back(12);for(int i=0;i<arr.get_size();i++){ cout << arr[i]<<" ";}return0;}

五、双指针

双指针严格来说不能是算法，它更像是一种技巧或思想。到后面的学习里，我们还会讲到贪心，它也是一种思想。双指针常被用于线性有单调性趋势遍历的优化之中！使其从 O(n^2) => O(n)

5.1 快慢指针（龟兔指针）

概念：通过使用两个指针以不同的速度遍历数据结构（线性结构）。 —— 滑动窗口与快慢指针的思想就很类似

检测链表是否有环

找链表中间节点

删除倒数第N个节点

判断是否为回文链表

寻找数组中重复元素
  • 快指针：先行一步满足前置条件（探索者）快速遍历并检测符合条件的数据
  • 慢指针：配合快指针解决需求（建造者）维护已处理数据的正确边界

利用两者之间的速度差，可以在某个时刻根据特殊规则，获得或处理某些数据。

大白话：根据需求，当发现只需要用一个变量，先行一步拿到前置条件，再用另一个变量配合该前置条件，就可以完成需求时，那么你应该尝试下快慢指针。

5.1.1 有序数组去重

#include<iostream>usingnamespace std;int arr[50];intmain(void){int n; cin >> n;for(int i =0; i < n;++i){ cin >> arr[i];}if(n ==0)return0;// 边界检查int i =0;// 慢指针（为了配合快指针的）for(int j =1; j < n;++j){// 快指针的目的是找到非重复项if(arr[j]!= arr[i]){// 找到之后，用非重复项覆盖掉重复项 i++;// 慢指针前进 arr[i]= arr[j];// 覆盖重复项}}// 输出去重后的数组（前 i+1 个元素）for(int k =0; k <= i;++k){ cout << arr[k]<<" ";} cout << endl;return0;}

5.1.2 数组的原地删除

原地删除某元素：比如数组 1,2,3,4,5,6,6,2,1,2,3,2 你就想把 里面的 2 全部删掉。逆向思维去看，其实就是只保留不是2的元素。

#include<iostream>usingnamespace std;voidremove_element(arr, n, val){int slow =0;for(int fast =0; fast < n;++fast){// 快指针去遍历if(arr[fast]!= val){// 进行筛选 arr[slow++]= arr[fast];// 慢指针给数组重新赋值符合条件的 arr[fast]}}}

5.1.3 最长连续不重复子序列（经典例题）

在这里插入图片描述
#include<iostream>usingnamespace std;constint maxN =1e5+10;int arr[maxN];intmain(void){int n; cin >> n;for(int i =0; i < n;++i){ cin >> arr[i];}int maxLen =0;// 记录最长长度// n^3// n^2// 计数排序// nint cnt[maxN]={0};int i =0;// 慢指针for(int j =0; j < n;++j){ cnt[arr[j]]++;while(cnt[arr[j]]>1){ cnt[arr[i]]--; i++;}if(maxLen < j - i +1) maxLen = j - i +1;} cout << maxLen << endl;return0;}

5.2 左右指针

左右指针是一种强大的算法技巧，其归属于双指针。特别适合处理数组和字符串问题。与快慢指针不同，左右指针同时从序列的两端向中间移动，形成 对称扫描！

在这里插入图片描述


左右指针最直接的应用就是（唐突）：二分查找、二分法答案

5.2.1 基础模板

voidtwo_pointers(int* arr,int n){int l =0, r = n -1;// r 是最后元素的下标while(l < r){// 只要 l < r 就继续扫描if 左侧条件满足 { l++;}if 右侧条件满足 { r--;}// 当然可能同时满足（这个所谓的条件，都是人为定的）}}

5.2.2 两数之和 II - 输入有序数组 (LeetCode 167)

题目：给定一个已按非递减顺序排列的整数数组 numbers，请你从数组中找出两个数，它们的和等于目标数 target。假设每个输入只对应唯一的答案，并且不能使用相同的元素两次。

那么这道题。如果暴力去做，怎么样也得 O(n^2)。但由于题目说提供的数据是有序的，就可以利用左右指针优化到 O(n)

voidtwo_sum(int*arr,int n,int target){// 若升序，肯定遵循左小右大int l =0, r = n -1;while(l < r){int total = arr[l]+ arr[r];if(total == target){ cout << l <<" "<< r << endl;break;}elseif(total < target){// 证明左边的太小了 l++;}else{// 证明右边的太大了 r--;}} couit <<""<< endl;}

5.2.3 反转字符串 (洛谷 P5705 【深基2.例7】数字反转)

题目：编写一个函数，将输入的字符串反转过来。

#include<iostream>usingnamespace std;intmain(void){ string a; cin >> a;int i =0, j = a.size()-1;while(i < j){char t = a[i]; a[i]= a[j]; a[j]= t; i++; j--;} cout << a << endl;return0;}

六、二分法

6.1 二分查找

  • while(l < r)
#include<iostream>usingnamespace std;constint maxN =1e5+10;int arr[maxN];intmain(void){int n,x;s cin >> n >> x;for(int i =0; i < n;++i){ cin >> arr[i];}int l =0, r = n -1;while(l < r){int mid =(l + r)/2;if(arr[mid]> x){ r = mid -1;}elseif(arr[mid]< x){ l = mid +1;}else{ cout << mid << endl;return0;}}if(arr[l]== x) cout << l << endl;else cout <<-1<< endl;return0;}
  • while(l <= r)
#include<iostream>usingnamespace std;constint maxN =1e5+10;int arr[maxN];intmain(void){int n,x; cin >> n >> x;for(int i =0; i < n;++i){ cin >> arr[i];}int l =0, r = n -1;while(l <= r){int mid =(l + r)/2;if(arr[mid]> x){ r = mid -1;}elseif(arr[mid]< x){ l = mid +1;}else{ cout << mid << endl;return0;}} cout <<-1<< endl;return0;}

6.2 左右边界

  • while(l < r)
#include<iostream>usingnamespace std;constint maxN =1e5+10;int arr[maxN];intmain(void){int n,x; cin >> n >> x;for(int i =0; i < n;++i){ cin >> arr[i];}int l =0, r = n -1;// 1 2 2 2 3 while(l < r){int mid =(l + r)/2;if(arr[mid]>= x){ r = mid;}else{ l = mid +1;}}if(arr[l]== x) cout << l << endl;else cout <<-1<< endl; l =0, r = n -1;// 1 2 2 2 3 while(l < r){int mid =(l + r +1)/2;if(arr[mid]<= x){ l = mid;}else{ r = mid -1;}}if(arr[r]== x) cout << r << endl;else cout <<-1<< endl;return0;}
  • while(l <= r)
#include<iostream>usingnamespace std;constint maxN =1e5+10;int arr[maxN];intmain(void){int n,x; cin >> n >> x;for(int i =0; i < n;++i){ cin >> arr[i];}int l =0, r = n -1;// 1 2 2 2 3 while(l <= r){int mid =(l + r)/2;if(arr[mid]< x){ l = mid +1;}else{ r = mid -1;}}if(arr[l]== x) cout << l << endl;else cout <<-1<< endl; l =0, r = n -1;// 1 2 2 2 3 while(l <= r){int mid =(l + r)/2;if(arr[mid]> x){ r = mid -1;}else{ l = mid +1;}}if(arr[r]== x) cout << r << endl;else cout <<-1<< endl;return0;}

七、筛质数

质数：只能被1 与 自身整除的数。

7.1 朴素法 O(nlogn)

#include<iostream>usingnamespace std;constint maxN =1e5+10;int arr[maxN];boolisPrime(int x){if(x <=1)returnfalse;for(int i =2; i < x;++i){if( x % i ==0&& x !=2){returnfalse;}}returntrue;}intmain(void){int n; cin >> n;for(int i =2; i <= n;++i){if(isPrime(i)){ cout << i << endl;}}return0;}

这里还会有个数学证明，优化了遍历条件。提高了效率，使其 i < x 化为 i * i <= x

  • 首先我们要知道，x = a * b，x / a = b。那么此时比如 i = a，则 x / i = b，也就是说如果一旦它有个因子是a，肯定会有个b的，我们的i就是帮他试试有没有这样的因子a。这个是前提！那么问题了，如果 x 可以被平方根，是不是就直接能确定因子 sqrt(x)，那么就不难发现，其它因子无非就是比 sqrt(x) 大或者小，如果 a是比 sqrt(x) 大，那么 b 就比 sqrt(x) 小，这是肯定的。此时我们其实就可以给 i 规定最大范围，即 i <= sqrt(x) 这是没毛病的，因为只要我在 小于等于 sqrt(x) 范围内尝试是否有一个因子，那么另外一个因子也就被确定了。合乎数学逻辑。
#include<iostream>usingnamespace std;constint maxN =1e5+10;int arr[maxN];boolisPrime(int x){if(x <=1)returnfalse;for(int i =2; i * i <= x;++i){if( x % i ==0&& x !=2){returnfalse;}}returntrue;}intmain(void){int n; cin >> n;for(int i =2; i <= n;++i){if(isPrime(i)){ cout << i << endl;}}return0;}

7.2 埃氏筛 O(nloglogn)

朴素筛的时候，我们就知道用数学所谓的 平方根，因子相关知识进行优化。那么也不难想到，任何数的倍数其实都不可能是质数的！所以我们只需要筛出不是质数的，剩下的就是质数喽。

#include<iostream>#include<string.h>usingnamespace std;constint maxN =1e5+10;bool primeArr[maxN];intmain(void){int n; cin >> n;memset(primeArr,true,sizeof(bool)* maxN); primeArr[0]=false; primeArr[1]=false;for(int i =2; i * i <= n;++i){for(int j =2* i; j < n; j += i){ primeArr[j]=false;}}for(int i =0; i < n;++i){if(primeArr[i]){ cout << i << endl;}}return0;}

7.3 欧拉筛 O(n)

其实朴素筛、埃氏筛 速度已经不错了，但有些时候可能需要最好的性能。此时就需要 使用 欧拉筛，它主要是优化了埃氏筛的缺点。

埃氏筛中，有这样一种情况，会导致多筛！比如 6 = 2 * 3，那么 对于2来说会有 * 3的时候，而对于 3 来说又会有*2的时候，但其实只需要筛一次就够，如果能保证筛一次的话，时间复杂度就可以 O(n)

  • 基本观察：每个非质数（合数）都会有唯一的 最小质因子
  • 关键机制：如果我们可以确保每个合数只在它 最小质因子与对应因数相乘时才被标记为 合数，那么就只筛了一次，不会多筛。就比如说 6 只在 最小质因子 2 乘以 3 的时候，才会被标记，其余情况不会被标记。
#include<iostream>#include<string.h>usingnamespace std;constint maxN =1e5+10;int primes[maxN];// 升序bool vis[maxN];intmain(void){int n; cin >> n;memset(vis,false,sizeof(bool)* maxN);// 假设都没被标记为合数int pos =0;for(int i =2; i <= n;++i){if(!vis[i])// 先判断是不是合数{ primes[pos++]= i;// i 是质数// 当前这个质数 * 其它已经确认的质数 = 合数for(int j =0;j < pos && i * primes[j]<= n;++j){ vis[i * primes[j]]=true;// 这个是合数}}else{// 当前这个合数 * 已经确认的质数（从最小的开始） = 合数// 但当前这个合数很可能是 某个最小质数的倍数，所以如果用它继续筛就筛多了// 必须判断出它是哪个最小质数的倍数for(int j =0;j < pos && i * primes[j]<= n;++j){ vis[i * primes[j]]=true;// 这个是合数if(i % primes[j]==0){// 看下当前这个 i 是不是最小质数break;// 证明不是最小质数了，可以是 primes[j] 的倍数，那么这个 primes[j] 在后续就可以帮他继续筛完// 即 当前的 i 就不用去做没意义的筛了。}}}}for(int i =0; i <pos;++i){ cout << primes[i]<< endl;}return0;}

八、前缀和与差分

  • 前缀和：快速求某个区间中所有元素的累加和。（所以这些数肯定是要 反复使用进行累加的）
  • 差分：对多个区间进行加数，快速得到操作后的数组集合（需要学习前缀和）

8.1 一维前缀和

  • 朴素写法
#include<iostream>usingnamespace std;constint maxN =1e5+10;int arr[maxN];intmain(){int n; cin >> n;for(int i =0; i < n;++i){ cin >> arr[i];}int p,q; cin >> p >> q;int sum =0;for(int i = p; i <= q;++i){ sum += arr[i];} cout << sum << endl;return0;}
  • 前缀和写法
#include<iostream>usingnamespace std;constint maxN =1e5+10;int arr[maxN];int sum[maxN]={0};intmain(){int n; cin >> n;for(int i =0; i < n;++i){ cin >> arr[i];} sum[1]= arr[0];for(int i =2; i <= n;++i){ sum[i]= sum[i -1]+ arr[i -1];}// 1 2 3 4 5// 1 3 6 10 15for(int i =0; i < n +1;++i){ cout << sum[i]<<" ";}int p,q; cin >> p >> q; cout << endl; cout << sum[q +1]- sum[p -1]<< endl;return0;}

8.2 二维前缀和

核心思想还是 前缀和，只不过是从 一维数组拓展到了二维矩阵。所以我们要探索有哪些变化，总结出通式，解决二维前缀和问题。

#include<iostream>usingnamespace std;constint maxN =1005;int arr[maxN][maxN]={0};int sum[maxN][maxN]={0};intmain(){int n,m; cin >> n >> m;for(int i =1; i <= n; i++){for(int j =1; j <= m; j++){ cin >> arr[i][j];}}for(int i =1; i <= n; i++){for(int j =1; j <= m; j++){ sum[i][j]= sum[i -1][j]+ sum[i][j -1]- sum[i -1][j -1]+ arr[i][j]; cout << sum[i][j]<<" ";} cout << endl;}int q; cin >> q;while(q--){int x1, y1, x2, y2; cin >> x1 >> y1; cin >> x2 >> y2; cout << sum[x2][y2]- sum[x1 -1][y2]- sum[x2][y1 -1]+ sum[x1 -1][y1 -1]<< endl;}return0;}

8.3 一维差分

原理：构建差分数组，将其当作新的原数组。然后进行前缀和操作，意外发现由差分数组还原成了真正的原数组。所以，只要我们在差分数组里进行区域内的加数操作，得到普遍规律可循，最后进行前缀和就可以得到我们的目标数组。

#include<iostream>usingnamespace std;constint maxN =1e5+10;int arr[maxN]={0};int d[maxN]={0};intmain(){int n,q; cin >> n >> q;for(int i =1; i <= n; i++){ cin >> arr[i];}for(int i =1; i <= n; i++){ d[i]= arr[i]- arr[ i -1];}while(q--){int l, r, c; cin >> l >> r >> c; d[l]+= c;if(r +1< n){ d[r +1]-= c;}}for(int i =1; i <= n; i++){ arr[i]= d[i]+ arr[i -1]; cout << arr[i]<<" ";}return0;}

8.4 二维差分

#include<iostream>usingnamespace std;constint maxN =1005;int arr[maxN][maxN]={0};int d[maxN][maxN]={0};// 差分数组int sum[maxN][maxN]={0};// 前缀和数组intmain(){int n, m, q; cin >> n >> m >> q;// 输入原始数组并初始化差分数组for(int i =1; i <= n; i++){for(int j =1; j <= m; j++){ cin >> arr[i][j];// 计算差分数组 d[i][j]= arr[i][j]- arr[i-1][j]- arr[i][j-1]+ arr[i-1][j-1];}}// 处理查询while(q--){int x1, y1, x2, y2, c; cin >> x1 >> y1 >> x2 >> y2 >> c;// 更新差分数组 d[x1][y1]+= c;if(y2 +1<= m) d[x1][y2+1]-= c;if(x2 +1<= n) d[x2+1][y1]-= c;if(x2 +1<= n && y2 +1<= m) d[x2+1][y2+1]+= c;}// 通过差分数组计算前缀和数组for(int i =1; i <= n; i++){for(int j =1; j <= m; j++){ sum[i][j]= d[i][j]+ sum[i-1][j]+ sum[i][j-1]- sum[i-1][j-1]; cout << sum[i][j]<<" ";} cout << endl;}return0;}

九、链表、队列、栈

9.1 单链表

#include<iostream>usingnamespace std;structNode{ Node* next;int data;};intmain(){ Node* A =newNode(); Node* B =newNode(); A -> data =1; B -> data =2; A -> next = B; B -> next =NULL; Node* currentNode = A;// 1. 遍历// Node* currentNode = A;// while (currentNode != NULL) {// cout << currentNode -> data << endl;// currentNode = currentNode -> next;// }// 2. 通关下标找到目标节点// int pos;// cin >> pos;// for (int i = 0; i < pos; i++) {// if (i == 0) {// currentNode = A;// }else {// currentNode = currentNode -> next;// }// if (currentNode == NULL) {// break;// }// }// if (currentNode == NULL) cout << A->data << endl;// else cout << currentNode->data << endl;// 3. 通过下标删除目标节点// int pos;// cin >> pos;// Node* preNode = A;// currentNode = preNode -> next;// if (pos == 0) {// A = currentNode;// delete preNode;// }else if (pos > 0) {// for (int i = 2; i <= pos; i++) {// preNode = currentNode;// currentNode = preNode -> next;// if (currentNode == NULL) {// break;// }// }// if (currentNode == NULL) {cout << "删除失败" << endl;}// else {// preNode -> next = currentNode->next;// delete currentNode;// }// }//// currentNode = A;// while (currentNode != NULL) {// cout << currentNode -> data << endl;// currentNode = currentNode -> next;// }// 4. 在下标后面插入一个节点int pos; cin >> pos;int data; cin >> data;for(int i =0; i <= pos; i++){if(i ==0){ currentNode = A;}else{ currentNode = currentNode -> next;}if(currentNode ==NULL){break;}}if(currentNode ==NULL) cout <<-1<< endl;else{ Node* newNode =newNode(); newNode -> data = data; newNode -> next = currentNode ->next; currentNode -> next = newNode;} currentNode = A;while(currentNode !=NULL){ cout << currentNode -> data << endl; currentNode = currentNode -> next;}return0;}

9.2 双链表

#include<iostream>usingnamespace std;structNode{ Node* pre; Node* next;int data;};intmain(){ Node* head =newNode(); Node* A =newNode(); Node* B =newNode(); head -> next = A; A -> data =1; B -> data =2; A -> pre = head; A -> next = B; B -> pre = A; B -> next =NULL; Node* cNode = head -> next;while(cNode !=NULL){ cout << cNode -> data << endl; cNode = cNode -> next;}// 删除int pos; cin >> pos;int t = pos +1;// 第 pos + 1 个 cNode = head;for(int i =1; i <= t; i++){ cNode = cNode -> next;if(cNode ==NULL){ cout <<"删除失败"<< endl;return0;}} Node* preNode = cNode -> pre; preNode -> next = cNode->next;delete cNode; cNode = head -> next;while(cNode !=NULL){ cout << cNode -> data << endl; cNode = cNode -> next;}return0;}

9.3 栈

#include<iostream>usingnamespace std;structNode{ Node* pre; Node* next;int data;}; Node* tail =NULL;voidpush(int data){ Node* newNode =newNode(); newNode->data = data; newNode->next =NULL; newNode->pre = tail; tail->next = newNode; tail = newNode;}intpop(){ Node* preNode = tail->pre; preNode -> next =NULL;int ret = tail -> data;delete tail; tail = preNode;return ret;}intmain(){ Node* head =newNode(); Node* A =newNode(); Node* B =newNode(); head -> next = A; A -> data =1; B -> data =2; A -> pre = head; A -> next = B; B -> pre = A; B -> next =NULL; tail = B; Node* cNode = head -> next;while(cNode !=NULL){ cout << cNode -> data << endl; cNode = cNode -> next;}push(3);push(4); cNode = head->next;while(cNode !=NULL){ cout << cNode->data << endl; cNode = cNode -> next;}pop(); cNode = head->next;while(cNode !=NULL){ cout << cNode->data << endl; cNode = cNode -> next;}return0;}

9.4 队列

#include<iostream>usingnamespace std;structNode{ Node* pre; Node* next;int data;}; Node* tail =NULL;voidpush(int data){ Node* newNode =newNode(); newNode->data = data; newNode->next =NULL; newNode->pre = tail; tail->next = newNode; tail = newNode;}intpop(){ Node* preNode = tail->pre; preNode -> next =NULL;int ret = tail -> data;delete tail; tail = preNode;return ret;} Node* head =newNode();intoutQue(){ Node* firstNode = head->next;if(firstNode ==NULL)return-1; head -> next = firstNode -> next;int ret = firstNode -> data;delete firstNode;return ret;}intmain(){ Node* A =newNode(); Node* B =newNode(); head -> next = A; A -> data =1; B -> data =2; A -> pre = head; A -> next = B; B -> pre = A; B -> next =NULL; tail = B; Node* cNode = head -> next;while(cNode !=NULL){ cout << cNode -> data << endl; cNode = cNode -> next;}push(3);push(4); cNode = head->next;while(cNode !=NULL){ cout << cNode->data << endl; cNode = cNode -> next;}outQue(); cNode = head->next;while(cNode !=NULL){ cout << cNode->data << endl; cNode = cNode -> next;}return0;}

9.5 数组模拟链表、栈、队列

链表既然能够实现栈和队列，那么自然 数组就也可以实现 栈和队列，甚至可以 模拟链表的逻辑。我们来看下。

  • 模拟链表
    链表结构的核心就在于 “链”，它可以直接找到对应的节点。那么我们可以通过 数组构建一个映射表，该数组的下标就相当于某个节点，然后存储的数据就是 链接的节点下标。这样我们就构建出了单链表的逻辑结构。
#include<iostream>usingnamespace std;constint maxN =1e5+10;int nodeArr [maxN];int linkArr [maxN];intmain(){ linkArr[0]=1;// 0号 指向 1号节点 nodeArr[1]=1;// 1号 节点 nodeArr[2]=2;// 2号 节点 linkArr[1]=2;// 1号 指向 2号节点 linkArr[2]=-1;// 定义 -1 是下个节点无 NULLint nextPos = linkArr[0];int cNode = nodeArr[nextPos];while(nextPos !=-1){ cout << cNode << endl; nextPos = linkArr[cNode]; cNode = nodeArr[nextPos];}return0;}
  • 模拟栈
#include<iostream>usingnamespace std;constint maxN =1e5+10;int stack [maxN];int tail =0;// 当前要入栈位置voidpush(int data){if(tail >= maxN){ cout <<"满了"<<endl;return;} stack[tail++]= data;}intpop(){if(tail ==0)return-1;return stack[--tail];}intmain(){push(1);push(2);for(int i =0; i < tail;++i){ cout << stack[i]<< endl;}pop();for(int i =0; i < tail;++i){ cout << stack[i]<< endl;}return0;}
  • 模拟队列
#include<iostream>usingnamespace std;constint maxN =1e5+10;int q[maxN];int top =0;int tail =-1;voidpush(int x){ q[++tail]= x;}intpop(){return q[top++];}intmain(){push(2);if(tail < top){ cout <<"空的"<< endl;} cout <<"数量"<< tail +1- top << endl; cout <<pop()<< endl;return0;}
  • 模拟循环队列
#include<iostream>usingnamespace std;constint maxN =1e5+10;int q[maxN];int top =0;// 头元素下标int tail =0;// 待插入节点的下标（即队尾的下一个下标）boolisFull(){return(tail +1)% maxN == top;}voidpush(int data){if(isFull()){ cout <<"队列满了"<< endl;return;} q[tail]= data; tail =(tail +1)% maxN;}intoutQ(){if(top == tail){ cout <<"队列空的"<< endl;return-1;}int ret = q[top]; top =(top +1)% maxN;return ret;}intmain(){push(1);push(2); cout <<outQ()<< endl;return0;}

十、DFS、BFS

讲DFS与BFS 这就不得不说一个典故 （迷宫）

想象一下，你进入了一个巨大的迷宫，你的目标是从起点 S 找到终点 T。 迷宫的结构如下，其中 # 代表墙，不能走；. 代表路代表路，可以走。
S . . # . . . . # . . . # . . # . . . . . . . # # . . . # . # T . . .

现在有两个问题被提出：

  • 走到终点的方案有多少种，分别都打印出来（DFS）
  • 走到终点最近的方案是什么路径，打印出来（BFS）

10.1 DFS

DFS：深度优先搜索，被戏称为一路走到黑。随便选一条路，死磕到底，碰壁后再倒回来换条路去走。

  • 你的行动方式：
    • 从起点 S 开始，开始，你标记“我已经来过这里了”。
    • 你面前有多个岔路口，你随机选一个（比如总是先向右），然后一直走下去。
    • 每到一个新地方，你都继续沿用这个规则（比如先向右），完全不管其他还没走的岔路。
    • 如果有一天你发现前面是墙或者已经走过的地方（死胡同），你就原路返回，回到上一个有未探索岔路口的地方，换另一条路继续深入。
    • 直到你在某条路的尽头发现了终点 T。
  • 辅助容器：栈
    • 为了管理这种“一路到底，然后回溯”的过程，你需要另一个工具——栈。
    • 把起点 S 压入栈。
    • 只要栈不为空，就取出栈顶的那个位置（比如 B）。注意，拿的是最新的那个！
    • 检查 B 是不是终点？如果是，胜利！
    • 如果不是，就把 B 周围所有能走且没走过的邻居，按顺序压入栈。
    • 重复步骤2。（这样，下一次就会先探索刚压进去的其中一个邻居，从而不断深入）
  • 非递归版本
#include<iostream>usingnamespace std;// 我们是 节点，二维数组，所以最好是 建立 x,y // 题目要求我们 用 x,y 下标 去确定一个节点的话，那么我们就要定义 这样的结构typedefstruct{int x, y;}Node;typedefstruct{ Node point;int dir;// 下次探索的方向 0 1 2 3}SNode;constint maxN =105; Node d[4]={{-1,0},{0,1},{1,0},{0,-1}};bool vis[maxN][maxN];// 为走过的节点打标记 Node path[maxN * maxN];int pathLen =0;char arr[maxN][maxN]; SNode s[maxN * maxN];int top =-1;intmain(void){int n,m; cin >> n >> m;for(int i =0; i < n;++i){for(int j =0; j < m;++j){ cin >> arr[i][j]; vis[i][j]=false;if(arr[i][j]=='S'){ s[++top]={i,j,0}; vis[i][j]=true; pathLen =1; path[0]={i,j};}}}while(top >=0){// 只有栈为空的时候，才不去探索 SNode* cNode =&s[top];if(cNode->dir >3){ vis[cNode->point.x][cNode->point.y]=false; pathLen--; top--;continue;}int nx = cNode->point.x + d[cNode->dir].x;int ny = cNode->point.y + d[cNode->dir].y; cNode->dir++;if(nx >=0&& nx < n && ny >=0&& ny < m &&!vis[nx][ny]&& arr[nx][ny]!='#'){ vis[nx][ny]=true; path[pathLen++]={nx,ny};if(arr[nx][ny]=='T'){for(int i =0; i < pathLen;++i){ cout << path[i].x <<","<< path[i].y <<" ";} cout << endl; vis[nx][ny]=false; pathLen--;}else{ s[++top]={nx,ny,0};}}}return0;}
  • 递归版本
#include<iostream>usingnamespace std;constint maxN =1005;typedefstruct{int x, y;} Point;typedefstruct{ Point p;int nextDir;// 下一步尝试的方向 (0~3)} StackNode;// 方向：上下左右 Point d[4]={{-1,0},{0,1},{1,0},{0,-1}};bool vis[maxN][maxN];// 是否走过了 Point path[maxN];int pathLen =0;int totalPaths =0;// 记录多少种路径方案char arr[maxN][maxN];int n, m;;// 5,7voiddfs(int x,int y){ vis[x][y]=true; path[pathLen++]={x, y};if(arr[x][y]=='T'){printf("Path %d:\n",++totalPaths);for(int i =0; i < pathLen; i++){printf("(%d,%d) ", path[i].x, path[i].y);}printf("\n\n");return;}for(int i =0; i <4; i++){int nx = x + d[i].x;int ny = y + d[i].y;if(nx >=0&& nx < n && ny >=0&& ny < m &&!vis[nx][ny]&& arr[nx][ny]!='#'){// 没有访问过dfs(nx, ny); vis[nx][ny]=false; pathLen--;}}}intmain(void){ cin >> n >> m;for(int i =0; i < n;++i){for(int j =0; j < m;++j){ cin >> arr[i][j];}}int startX =-1, startY =-1;// 从 -1 开始for(int i =0; i < n;++i){for(int j =0; j < m;++j){if(arr[i][j]=='S'){ startX = i; startY = j;break;}}if(startX !=-1)break;}if(startX ==-1){printf("没有起始点\n");return1;}for(int i =0; i < n; i++)for(int j =0; j < m; j++) vis[i][j]=false;dfs(startX, startY);if(totalPaths ==0){printf("No path found!\n");}else{printf("Total paths: %d\n", totalPaths);}return0;}

10.2 BFS

DFS：广度优先搜索，又称为地毯式搜索。先探索所有最近的地方（层次感），再探索更远的地方。

  • 你的行动方式：
    • 从起点 S 开始，你标记 “我已经来过这里了”。
    • 你站在 S，向四周（上、下、左、右）可通行的方向看，把所有能直接到达的点都记录下来。这些是你的 “第一层” 邻居。
    • 然后，你不再自己往前走，而是召唤出几个分身。每个分身去一个“第一层”邻居点。
    • 所有这些分身在各自的位置上，再次重复你的动作：记录他们周围还未被探索的、“第二层第二层”的邻居点。
    • 这个过程一层一层地展开，就像，就像在水里扔下一块石头，涟漪一圈一圈地扩散出去，直到某个分身找到了终点 T。
  • 辅助容器：队列
    • 为了管理这个“分层探索”的过程，你需要一个强大的工具——队列。
    • 队列的特点：先进先出 (FIFO)，就像现实生活中的排队。先进去的人先出来。
    • 如何使用：
      • 把起点 S 放进队列。
      • 只要队列不为空，就拿出队首的那个位置（比如 A）。
      • 检查 A 是不是终点？如果是，胜利！ ！
      • 如果不是，就把 A 周围所有能走且没走过的邻居，按顺序（比如上、下、左、右）依次放入队列的末尾。
      • 重复步骤2。
#include<algorithm>#include<iostream>#include<ranges>#include<vector>usingnamespace std;constint maxN =1005;structPoint{int x;int y;}; Point q[maxN];int top =0;int tail =0;boolifFull(){return(tail +1)% maxN == top;}voidpush(Point data){if(ifFull()){return;} q[tail]= data; tail =(tail +1)% maxN;} Point outQ(){if(top == tail){ cout <<"队列空的"<< endl;return{-1,-1};} Point ret = q[top]; top =(top +1)% maxN;return ret;} Point d[4]={{-1,0},{0,1},{1,0},{0,-1}};char arr[maxN][maxN];bool vis[maxN][maxN]; Point pre[maxN][maxN];// 记录当前节点的上一个节点intmain(){int n,m;int startX, startY;int endX, endY; cin >> n >> m;for(int i =0; i < n; i++){for(int j =0; j < m; j++){ cin >> arr[i][j]; vis[i][j]=false;if(arr[i][j]=='S'){ startX = i; startY = j;}if(arr[i][j]=='T'){ endX = i; endY = j;}}}push({startX, startY}); vis[startX][startY]=true; pre[startX][startY]={-1,-1};bool flag =false;// 默认没找到 Twhile(top != tail){ Point cNode =outQ();if(cNode.x == endX && cNode.y == endY){ flag =true;break;}for(int i =0; i <4; i++){int nx = cNode.x + d[i].x;int ny = cNode.y + d[i].y;if(nx <0|| nx >= n || ny <0|| ny >= m)continue;if(arr[nx][ny]=='#'|| vis[nx][ny])continue; vis[nx][ny]=true; pre[nx][ny]= cNode;push({nx, ny});}}if(!flag){ cout <<"根本没终点"<<endl;}else{ vector<Point> path;int x = endX, y = endY;while(x !=-1|| y !=-1){ path.push_back({x,y}); Point p = pre[x][y]; x = p.x; y = p.y;}reverse(path.begin(), path.end()); cout << endl;for(int i =0; i < path.size(); i++){ cout << path[i].x <<" "<< path[i].y;if(i != path.size()-1) cout <<" -> ";}}return0;}

十一、贪心思想（完结）

贪心思想的核心是：每一步都做出当前看起来“最好”的选择，希望通过局部最优解最终达到全局最优解。

注意：贪心算法并不总能得到全局最优解，但在某些特定问题上，它是有效的，并且效率很高！
  • 贪心选择性质：每一步都做当前看起来最好的选择，不考虑未来。
  • 最优子结构：问题的最优解包含其子问题的最优解。
  • 无后效性：一旦做出选择，就不会再改变，也不会影响之前的选择。

11.1 找零钱问题

问题：假设你有面值为 1元、5元、10元 的硬币，要找给顾客 36 元，要求用最少数量的硬币。

贪心：每次都尽可能用最大面值的硬币就行了。

#include<stdio.h>intmain(){// 定义硬币面值（按从大到小排序）int coins[]={10,5,1};int numCoins =3;// sizeof(coins) / sizeof(coins[0]); 这个写法是计算数组元素个数的技巧写法int amount;printf("请输入要找零的金额（元）: ");scanf("%d",&amount);if(amount <0){printf("金额不能为负数！\n");return1;}int totalCoins =0;printf("找零方案：\n");for(int i =0; i < numCoins; i++){int count = amount / coins[i];// 当前面值能用多少个if(count >0){printf("%d元硬币：%d枚\n", coins[i], count); totalCoins += count; amount -= coins[i]* count;}}printf("总共需要硬币：%d枚\n", totalCoins);return0;}

11.2 活动选择问题（区间调度）

问题：有 n 个活动，每个活动有开始时间和结束时间。你一次只能参加一个活动，如何选择最多的活动？

  • 贪心：优先选择结束时间最早的活动。因为结束得早，留给后面的时间就多，能安排更多活动。
#include<stdio.h>#include<stdlib.h>// 定义活动结构体typedefstruct{int start;int finish;int id;// 活动编号（可选，用于输出原始顺序）} Activity;// 比较函数：用于 qsort，按结束时间升序排序intcompare(constvoid*a,constvoid*b){ Activity *actA =(Activity *)a; Activity *actB =(Activity *)b;return actA->finish - actB->finish;}intmain(){int n;printf("请输入活动数量: ");scanf("%d",&n);if(n <=0){printf("活动数量必须大于0。\n");return1;} Activity activities[n];printf("请输入每个活动的开始时间和结束时间（格式：start finish）:\n");for(int i =0; i < n; i++){scanf("%d %d",&activities[i].start,&activities[i].finish); activities[i].id = i +1;// 编号从1开始// 简单校验if(activities[i].start >= activities[i].finish){printf("警告：活动%d的开始时间应小于结束时间！\n", i +1);}}// 按结束时间升序排序qsort(activities, n,sizeof(Activity), compare);// 贪心选择printf("\n最多可参加的活动如下（按结束时间排序）:\n");int count =1;int lastFinish = activities[0].finish;printf("活动%d: [%d, %d]\n", activities[0].id, activities[0].start, activities[0].finish);for(int i =1; i < n; i++){if(activities[i].start >= lastFinish){printf("活动%d: [%d, %d]\n", activities[i].id, activities[i].start, activities[i].finish); count++; lastFinish = activities[i].finish;}}printf("\n最多可参加 %d 个活动。\n", count);return0;}

Read more

鸿蒙金融理财全栈项目——生态合作、用户运营、数据变现

鸿蒙金融理财全栈项目——生态合作、用户运营、数据变现

《鸿蒙APP开发从入门到精通》第19篇：鸿蒙金融理财全栈项目——生态合作、用户运营、数据变现 📊🌍💰 内容承接与核心价值 这是《鸿蒙APP开发从入门到精通》的第19篇——生态合作、用户运营、数据变现篇，100%承接第18篇的风险控制、合规审计、产品创新架构，并基于金融场景的生态合作、用户运营、数据变现要求，设计并实现鸿蒙金融理财全栈项目的生态合作、用户运营、数据变现功能。 学习目标： * 掌握鸿蒙金融理财项目的生态合作设计与实现； * 实现金融机构合作、支付渠道合作、数据分析合作； * 理解用户运营在金融场景的核心设计与实现； * 实现用户增长、用户留存、用户转化； * 掌握数据变现在金融场景的设计与实现； * 实现数据服务、数据产品、数据变现； * 优化金融理财项目的用户体验（生态合作、用户运营、数据变现）。 学习重点： * 鸿蒙金融理财项目的生态合作设计原则； * 用户运营在金融场景的应用； * 数据变现在金融场景的设计要点。 一、 生态合作基础 🎯 1.1 生态合作定义 生态合作是指金融理财项目与其他金融机构、

By Ne0inhk

Flutter 三方库 at_server_status 的鸿蒙化适配指南 - 在鸿蒙系统上构建极致、透明、实时的 @protocol 去中心化身份服务器状态感知与鉴权监控引擎

欢迎加入开源鸿蒙跨平台社区：https://openharmonycrossplatform.ZEEKLOG.net Flutter 三方库 at_server_status 的鸿蒙化适配指南 - 在鸿蒙系统上构建极致、透明、实时的 @protocol 去中心化身份服务器状态感知与鉴权监控引擎 在鸿蒙（OpenHarmony）系统的隐私保护应用、去中心化身份管理工具（基于 @protocol 协议）或需要实时监控全球分布式节点健康状况的场景中，如何判定一个 @sign（电子签名标识）背后的 Root 服务器或 Secondary 服务器是否在线、配置是否由于由于由于由于已就绪？at_server_status 为开发者提供了一套工业级的、基于协议栈的状态审计与自检方案。本文将深入实战其在鸿蒙 Web3 身份安全底座中的应用。 前言 什么是 atServer Status？它是 @protocol（一种旨在让用户完全掌控数据的去中心化协议）官方生态的核心组件。

By Ne0inhk
HarmonyOS6 组件复用 reuseId 官方使用文档

HarmonyOS6 组件复用 reuseId 官方使用文档

文章目录 * 一、核心 API 定义 * 1. reuseId 通用属性 * 2. 核心装饰器 * 3. 组件复用生命周期 * 二、核心使用规则 * 三、完整可运行示例代码 * 四、示例执行流程与日志说明 * 1. 页面初始化 * 2. 点击「显示/隐藏组件」 * 3. 点击「切换复用ID」 * 4. 再次切换回原ID * 总结 本文档基于 HarmonyOS 官方 reuseId 通用属性规范编写，配套可直接运行、无语法报错的完整示例，适用于 API 12+ 稳定版 DevEco Studio，严格遵循 ArkTS 语法检查规则。 reuseId 是 HarmonyOS ArkUI

By Ne0inhk
Flutter 三方库 http_client_interceptor 的鸿蒙化适配指南 - 实现原生 HttpClient 的全量请求拦截、支持端侧动态 Headers 注入与网络流量审计实战

Flutter 三方库 http_client_interceptor 的鸿蒙化适配指南 - 实现原生 HttpClient 的全量请求拦截、支持端侧动态 Headers 注入与网络流量审计实战

欢迎加入开源鸿蒙跨平台社区：https://openharmonycrossplatform.ZEEKLOG.net Flutter 三方库 http_client_interceptor 的鸿蒙化适配指南 - 实现原生 HttpClient 的全量请求拦截、支持端侧动态 Headers 注入与网络流量审计实战 前言 在进行 Flutter for OpenHarmony 开发时，虽然我们常使用 dio 等高阶库，但仍有大量底层插件或遗留系统直接使用 Dart 原生的 HttpClient。如何在中途“截获”这些原生请求，以便统一添加鉴权 Token、日志审计或处理特定区域的网关重定向？http_client_interceptor 是一款专为原生 IO 库设计的拦截器插件。本文将探讨如何在鸿蒙端构建极致透明的网络治理层。 一、原直观解析 / 概念介绍 1.1 基础原理

By Ne0inhk