我会将需要用到的一些主要的知识点放在算法介绍的旁边，并且我是以解决一个问题来介绍一个算法的，而不是直接介绍；
第一个：找一个数组里的最值
擂台法：
const int inf=10e9;
int main(){
int n; scanf("%d",&n);
int min=inf,max=-inf;//将最大值和最小值设得足够小和足够大
while(n--){
int mid; scanf("%d",&mid);
if(mid>=max) max=mid;
if(mid<=min) min=mid;
}
printf("min=%d max=%d",min,max);
}
排序法：顾名思义就是排序，那么就只需要两个端点就是了；
先来一个容易但是效率低的算法：冒泡排序：【数组，循环】
#includeconst int N = 1000010; int st[N],n;//st用来存储数字，而n用来记录有多少个数 void swap(int &a, int &b) { int mid = a; a = b; b = mid; } int main() { scanf("%d", &n); for (int i = 0; i < n; i++) { scanf("%d", &st[i]); } int m=n;//这里为什么要记录一个m=n，希望大家可以思考一下 while (m--) { for (int i = 0; i < m; i++) { if (st[i] > st[i + 1]) swap(st[i], st[i + 1]);//我这边直接创建一个函数来实现交换，来使代码好看些，如果对函数不熟悉的可以用中间变量来交换； } } for (int i = 0; i < n; i++)//输出数组 printf("%d ", st[i]); }
这个排序很好理解，但是效率非常低，时间复杂度是o(n^2)，一般数据为10000个就跑不动了，那个时候就需要快排和归并了，而且c++里就自带一个快排sort，但是为了秉着理解万岁的原则，本菜鸟先放一下快排的代码，然后讲sort函数的用法；【函数，递归】
#includeusing namespace std; const int N = 100010; int st[N]; int n; int quick_sort(int min, int max) { if (min >= max) return 0; int l = min - 1, r = max + 1; int x = st[l + r >> 1];//l+r>>1等价于(l+r)/2 while (l < r) { do l++; while (st[l] < x); do r--; while (st[r] > x); if (l < r) { swap(st[l], st[r]); } } quick_sort(min, r); quick_sort(r+1, max); } int main(){ cin >> n; for (int i = 0; i < n; i++) { cin >> st[i]; } quick_sort(0, n - 1); for (int i = 0; i < n; i++) { cout << st[i] << ' '; } }
快排的时间复杂度是o(n*log n) 就是说数据越多，快排与冒泡的效率差别是非线性级的，但是理解快排的基础是递归，可能很多人对递归可能不是很熟悉，因为我相信点进来的人大部分是和本菜鸟一样的编程新手；
那么本菜鸟再来介绍c++里的sort排序函数；【指针，函数】
#include#include using namespace std; const int N = 100010; int st[N],n; int main() { scanf_s("%d", &n); for (int i = 0; i < n; i++) scanf_s("%d", &st[i]); sort(st, st + n); for (int i = 0; i < n; i++) printf("%d ", st[i]); }
sort函数要包含algorithm函数库，是不是很方便？？效率快，而且非常好写！
sort函数里的两个实参是数组中需要排序的范围的两端指针，sort(st,st+n); 的范围是整个数组；
要注意sort的功能不止于此，因为这边只是轻微地提一下，所以需要深入地了解的话可以去查一下别的跟详细的文章，也许某一天学成了，本菜鸟也会发一篇关于sort的文章；
那还有没有更快而且比上面两个更好写的排序算法呢？
有当然有，那就是宇宙最快的桶排了，你别看整个名字这么low，但是它的时间复杂度可是只有o(n)，已经是理论极限了，而且才寥寥数行；
那么先来看一下代码吧；
#include#include using namespace std; const int N = 100010; int st[N],sort1[N]; int main() { int n; cin >> n; int maxnum = -1; for (int i = 0; i < n; i++) { scanf_s("%d", &st[i]); maxnum = max(maxnum, st[i]); } for (int i = 0; i < n; i++) { sort1[st[i]]++; } for (int i = 0; i <= maxnum; i++) { while (sort1[i] != 0) { cout << i<<' '; sort1[i]--; } } }
桶排的核心思想呢，就是讲需要排序的数据映射成另外一个数组的下标，然后按另外一个数组的下标依次输出；
但是桶排有一个天大的缺陷，那就是如果数据太大，那么就会爆内存；
这个需要好好地想一想；
------------------------------
字符串和数字的回文判断
回文相信大家都知道是什么意思，那么我现在来介绍几个回文判断算法；
判断回文数：【循环，if】
#include#include #include using namespace std; const int N = 100010; int main() { int num; scanf_s("%d", &num); int mid = num,re=0; while (mid) { re = re * 10 + mid % 10; mid /= 10; } if (re == num) puts("Yes"); else puts("No"); }
这边的核心语句就算re = re * 10 + mid % 10;
我一直相信一句话，“学习最好的方法就是思考”
看不太懂的可以自己用笔来走一遍；
判断回文串：【循环，if】
#include#include #include using namespace std; const int N = 100010; int main() { char st[N]; scanf("%s",st); for (int i = 0; i <= strlen(st); i++) { if (st[i] != st[strlen(st) - i - 1]) { puts("No"); return 0; } } puts("Yes"); }
这边再来介绍一个c++的容器，string，可以非常方便地存储字符串和做到一些c语言里难以实现的 *** 作；
#include#include #include using namespace std; const int N = 100010; int main() { string a,b;//调用string得包含c++的string头文件； cin>>a;//string 的输入 a[i]//string支持随机访问 //string里的字符串可以按照字典序比较大小，如果不晓得什么的字典序，那么可以去百度查一下； if (a > b) { puts("Yes"); } //string支持运算符 *** 作 a += b; //如果a里存的是abc，b里是efg,那么a+=b后，a为abcdefg； //string支持sort函数 *** 作； sort(a.begin(), a.end());//用字典序来完成a字符串里的升序排序； //string支持访问字符串长度； int len = a.size();//a.size()会返回一个int类型的值，为a字符串的长度 //string支持一键清空 a.clear();//清空字符串 }
平时掌握以上 *** 作就够了；
那么我再来介绍一个c++里的利器函数；
reverse() 函数顾名思义，它可以让数组或者各种容器里的数据翻转过来，这样就很简单了，判断一个回文串看它翻转过来后是否还相同，如果相同，那么就是字符串了
#include#include #include using namespace std; const int N = 100010; int main() { char st[N]; scanf("%s", st); reverse(st, st + strlen(st)); puts(st); }
与sort一样，reverse函数里的两个实参是数组里需要翻转的范围的两个端点的指针；
string 也支持reverse函数
#include#include #include using namespace std; const int N = 100010; int main() { string a; cin>>a; reverse(a.begin(), a.end()); cout<
--------------------------
去重工作；
有的题目可能会给你一些有序或者无序的数字来叫你去掉一些重复的数字；
这个其实很好解决，如果是有序的数组，那么用桶排就可以了；
#include#include using namespace std; const int N = 100010; int st[N],sort1[N]; int main() { int n; cin >> n; int maxnum = -1; for (int i = 0; i < n; i++) { scanf_s("%d", &st[i]); maxnum = max(maxnum, st[i]); } for (int i = 0; i < n; i++) { sort1[st[i]]++; } for (int i = 0; i <= maxnum; i++) { if(sort1[i] != 0) { cout << i<<' '; } } }
只需要将第三个循环里的while改成if就行了；
但是还是有会那个天大的缺陷，数字不能太大；
然后还有一个更快而且速度更快而且不要额外空间，但是只能运用于有序数组的算法，双指针算法，这个算法有点难懂，我就直接抄我之前做的笔记了哈：）
#include#include using namespace std; const int N = 100010; int st[N]; int main() { int n; cin >> n; for (int i = 0; i < n; i++) { scanf_s("%d", &st[i]); } int j, i; for ( i = 0, j = 0; i < n; i++) { if (st[i + 1] != st[i]) { st[j] = st[i]; j++; } } for (int i = 0; i < j; i++) { printf("%d ", st[i]); } }
其原理是这样的：
输入n个数字，排序并去重：
这里的j和i可以形象化为两个走楼梯的人，而楼梯就是递增的数组，其中i会尽量使j每走的一部都会到达新的高度，这时聪明的i就想到一个办法，i让j与自己同时登上楼梯，并命令愚蠢的j，说“如果你前面的阶梯突然增高了，那么你就往前走”，说完自己往前走一步，然后他会往后面看一看，看自己是否在一个新高度，如果不是新高度，那么i就会往前走一步，然后再次重复刚才的过程，直到发现自己上了一个台阶，然后会魔法的i就施展自己的小魔法，让自己在的阶梯的高度不变的情况下，使j所在的阶梯前一个阶梯的高度与自己一样，接着接收到命令j就往前走一步，看见j的高度和自己一样后i又继续往前走....循环往复，直到i到达楼梯的尽头，这使i会发现j和自己在同一个高度...；
--------------
关于素数的问题：
平时我们写的素数筛选是这样的
#include#include #include using namespace std; const int N = 100010; long long st[N]; int main() { int n; cin>>n; int flag=1; for(int i=1;i<=n;i++){ for(int j=2;j*j<=i;j++){ if(i%j==0){ flag=0; break; } } if(flag) printf("%d ",i); flag=1; } }
这个的时间复杂度是o(n*n^1/2) 时间复杂度不算优秀，但不需要额外数组；
我来介绍一个需要额外数组，而且时间复杂度为o(n)的算法，素数筛；
#include#include using namespace std; const int N = 10000010; int st[N]; int main() { int n; cin >> n; for (int i = 2; i <= n; i++) { if (st[i] == 1)//如果这个数不可能是素数，那么我们就跳过它； continue; else { for (int j = 2 * i; j <= n; j += i) { st[j] = 1;//将所有不可能是素数的数给标记； } } } for (int i = 1; i <= n; i++) { if (st[i] == 0)//剩下的就都是素数了； cout << i<<' '; } }
这个素数筛其实是有数学证明的，其原理就是将除了x外的所有x的倍数否认，这样从2~n遍历一边x，剩下的没有被否认的就是素数了；
其实这个和桶排是有异曲同工之妙的，也都是基于对下标的 *** 作；
好了，差不多就这些了，以后还会更新一些初级算法和方便的数据结构，觉得还可以的话可以点个大拇指哦；
：）
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）