C++学习记录算法篇-快读与快写

发表于2022-02-27|更新于2025-07-13|数据结构与算法

|浏览量:

C++学习记录算法篇-快读与快写

快读

int read() {
    int x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}
    while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
    return x*f;
}

快写

void write(int x) {
     if(x<0) putchar('-'),x=-x;
     if(x>9) write(x/10);
     putchar(x%10+'0');
}

文章作者: 星辰微光

文章链接: http://example.com/2022/02/27/C++-%E5%AD%A6%E4%B9%A0%E8%AE%B0%E5%BD%95%E7%AE%97%E6%B3%95%E7%AF%87-%E5%BF%AB%E8%AF%BB%E4%B8%8E%E5%BF%AB%E5%86%99/

版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源星辰微光的博客！

相关推荐

C++学习记录算法篇-埃氏筛质数

C++学习记录算法篇埃氏筛质数埃氏筛质数法原理：质数的倍数都不是质数，因此将质数的倍数都筛除，剩下的都是质数。示例：假设要筛选从1到a(a>=2)内的所有质数： 1.先设所有数均为质数(利用布尔) 2.将1设为不是质数 3.从2开始，2的倍数均不是质数；再从3开始，3的倍数均不是质数 4.此时遇到4，4在筛除2的倍数时已经被筛除，则跳过4，从5开始，以此类推筛除所有非质数 5.3，4流程重复至根号内a即可代码示例： 123456789101112131415161718192021//以a=100为例bool is_prime[101];for(int i=1;i<=100;i++){ is_prime[i]=true;}//先假设所有的数都是质数is_prime[1]=false;//1不是质数//开始筛选for(int i=2;i<=pow(100,0.5);i++){ if(is_prime[i]==true) { for(int j=2;j*i<=100;j++) ...

C++学习记录算法篇—归并排序

C++学习记录算法篇—归并排序一、归并排序：归并排序利用了分治思想，即把大问题先拆分为小问题，对小问题进行求解，最后合并成大问题的解。在归并排序中体现为：先把数组拆分为许多小数组，对小数组进行排序，再把有序的小数组合并成有序的大数组。二、归并排序的实现：首先是归并排序的入口，在这个入口创建临时数组，并进行划分，最后在排序完成后删除临时数组 12345678910void merge_sort(int arr[],int n){ //首先分配辅助数组 int* tempArr = new int[n]; //分配完，进行数组的划分 msort(arr, tempArr, 0, n - 1); //排序完后，删除临时数组 delete tempArr; return;} 接下来是数组的划分，传入的参数为：欲划分的数组临时数组划分的起点（最开始是0）划分的终点（最开始是n-1）首先一直划分数组，直到每个小数组只有一个元素，这是一个递归的过程划分数组后，进入合并阶段 123456789101112131415void...

C++学习记录算法篇-堆排序

C++学习记录算法篇-堆排序一、堆堆是一颗完全二叉树如果堆的每一个节点（叶子节点除外）都大于他的子节点，这样的堆称为大根堆如果堆的每一个节点（叶子节点除外）都小于他的子节点，这样的堆称为小根堆对于用数组储存的堆，有以下运算性质：某个节点i的父节点下标为：（i-1）/2 （整数除法）某个节点i的左孩子节点下标为： i*2+1 某个节点i的右孩子节点下标为： i*2+2 二、堆排序（以从小到大为例）利用堆的性质进行排序：从小到大使用大根堆，从大到小使用小根堆大根堆的根节点的值最大，因此不断地把根节点放到数组的最末端，放完再维护堆，就可以实现从小到大排序三、代码实现：首先实现堆的维护：对于某个待维护的下标，我们要维护其子节点，子节点的子节点…直到叶子节点，这是一个递归的过程 12345678910111213141516171819202122//维护堆的性质，以大根堆为例：//所需要的参数：数组，数组的长度，待维护的下标void heapify(int arr[], int n, int...

C++学习记录算法篇—快速排序

C++学习记录算法篇—快速排序一、快速排序的过程（从小到大排为例）：首先，假设基准数为最左边的数。然后，让两个“哨兵”从最左边和最右边向中间探测，从左边出发的哨兵找比基准数大的数，从右边出发的哨兵找比基准数小的数注意，因为是从小到大排，所以右边的哨兵要先出发两个哨兵都“停下”（即找到了符合要求的数），交换两个“哨兵”的值，接着继续探测，继续交换，直到两个哨兵相遇为止两个哨兵相遇后，交换基准数与相遇时所指示的数。此时，基准数左边都小于基准数，基准数右边都大于基准数，这也是为什么要右边哨兵先动的原因至此，基准数归位，接着对基准数的两边再次进行快速排序，这是一个递归的过程。可以看到，快速排序就是不断地把基准数归位的过程下面是代码： 12345678910111213141516171819202122232425262728293031323334353637//快速排序函数void quicksort(int l, int r)//接受最左边数字的下标left，和最右边数字的下标right{ int i, j, t, temp; if (l >=...

C++学习记录算法篇：深度优先搜索1-n的全排列

C++学习记录算法篇：深度优先搜索1-n的全排列深度优先搜索的核心思想是**“不撞南墙不回头”，即对每一个路径进行深入直到不能深入为止**，之后再退回上一步，继续尝试新的路径，直到把每一条路径都尝试一遍。核心代码如下： 1234567891011121314void dfs(int step){ 判断边界//判断边界，step是否已经到最后一步，是的话返回 //尝试每一种可能 for(int i=1;i<=n;i++) { //尝试 dfs(step+1);//继续下一步,这是一个递归的过程 } return;//返回} 案例：求n的全排列：这里通过将手上标有1~n的牌放到n个箱子里，来模拟全排列的过程，代码如下： 12345678910111213141516171819202122232425262728293031323334353637383940414243#include<iostream>using...

C++学习记录-STL-list

C++学习记录-STL-list C++中的list是一个双向链表 list常用API 构造函数 1234list<T> 名称;//默认构造方式list(开始位置迭代器,结束位置迭代器);//将区间中的元素拷贝给该容器list(数量，元素);//将n个元素拷贝给该容器list(另一个容器);//拷贝构造函数插入删除操作 1234.push_back(元素);//尾部加入一个元素.pop_back(元素);//尾部弹出一个元素.push_front(元素);//头部插入一个元素.pop_front(元素);//头部弹出一个元素判断修改大小操作 123.size();//返回大小.empty();//判断是否为空.resize(num，elem);//重新指定容器长度为num，如果变长，则用默认元素填充，变短则删除多余元素数据获取 12.front();//获取第一个元素.back();//获取最后一个元素容器反转 12.reverse();//反转.sort();//默认从大到小排序

数据加载中