算法笔记
《算法笔记》的笔记。
第一章 C/C++基础
1.基本数据类型
10^9以内使用int，以上则使用long long
如果long long赋大于2^32-1的初值，需要在初值后面加上LL。例如：long long bignum = 123456789012345LL
- 尽量不使用宏定义来做除了定义常量以外的事（存在陷阱）。定义常量推荐const写法。
2.顺序结构
- scanf的几种格式符：%d，%lld，%f，%lf（double），%c，%s。
- printf的格式符，double、float均为%f。
- %md不足m位右对齐（空格补齐），%0md用0补齐，%mf保留m位小数输出。
- 常用math函数：fabs()，floor()，ceil()，pow()，sqrt()，log()，asin()，sin()，round()。
- 如果数组大小较大（大概10^6级别），则需要定义在主函数外。主函数内申请的局部变量使用系统栈，允许的空间较小，全局变量来自静态存储区，允许申请的空间较大。
- memset(数组名，值，sizeof(数组名))，按字节赋值。用来赋0,1不容易出错。如果赋其他数字，使用fill函数。
- gets(数组名)用于输入一行字符串，以\n为结束，因此gets一行的字符串后，需要getchar()接收换行符。
- 常用字符数组函数：
- strlen(数组)
- strcmp(数组1，数组2)
- strcpy(数组1，数组2)，数组2复制到数组1
- strcat(数组1，数组2)，数组2接到数组1后面
- sscanf(str,”%d”,&n)，从左至右
- sprintf(str,”%d”,n)，从右至左
第二章 简单模拟
1.日期差值
1 |
|
2.进制转换
D进制的A+B
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int main(){
int a,b,d,sum;
int ans[40],num=0;
scanf("%d%d%d",&a,&b,&d);
sum = a+b;
do{
ans[num++] = sum%d;
sum/=d;
}while(sum!=0);
for(int i=num-1;i>=0;i--)
printf("%d",ans[i]);
return 0;
}
进行n次操作，每次选出待排序部分中最小的元素，与A[i]进行交换。复杂度为O(n^2)
1 | void SelectSort(){ |
1.2直接插入排序
直接插入排序是将带插入部分一个个插入初始已有序部分中的过程，具体做法为从后往前枚举已有序部分来确定插入位置。
1 | void InsertSort(){ |
1.3冒泡排序
每次将最大的数移动到最右侧，移动n-1次完成排序。
1
2
3
4
5
6
7
8
9
10
11void BubbleSort(){
for(int i=1;i<n;i++){ //n-1次排序
for(int j=0;j<n-i;j++){ //将最大的数移动至最右侧
if(A[j]>A[j+1]){
int temp = A[j];
A[j+1] = temp;
A[j] = A[j+1];
}
}
}
}
归并排序与快速排序在双指针一节中。 ## 2.散列 ### 2.1散列的定义及整数散列
将元素通过一个函数转换为整数，使得该整数可以尽量唯一的代表这个元素。其中把这个转换函数称为散列函数H，对于一个元素key，转换的结果为整数H(key)。
对于key为整数的情况来说，常用的散列函数有直接定址法（H(key)=key或H(key)=a*key+b），平方取中法（取key平方的中间若干位作为数组下标，很少使用），除留取余法（H(key)=key%mod）。
使用除留取余法时，可以把很大的数转换为小于mod的整数，数组TSize要大于mod。可能有key1和key2的H(key1)=H(key2)的冲突情况，这种情况有以下三种解决方法：
- 线性探查法：当H(key)被占用，检查H(key+1)是否被占用，不断检查直到找到可用的位置。使用这种方式可能导致扎堆。
- 平方探查法：当H(key)被占用，检查H(key)+1，H(key)-1，H(key)+2^2，H(key)-2^2……。如果H(key)+k^2超过了表长，就对表长取模，如果H(key)-k^2<0，就将(H(key)-k^2)%TSize+TSize)%TSize作为结果。也可以只使用正向的平方探查，如果在表长范围内没有找到位置，当k>=TSize时，也一定无法找到位置。
- 链地址法：将所有的H(key)相同的key链接成一条单链表。
*2.2字符串hash
字符串hash是将一个字符串映射为一个整数，使得该整数可以尽可能的唯一的代表字符串S。映射方式是将大小写字母映射到0-51，然后按照进制转换的方式将其转换为十进制数。如果字符串中有数字，可以增大进制为62，或者可以将末尾的确定个数的数字直接拼接上去。
给出N个字符（有恰好三位大写字母组成），再给出M个查询字符串，问每个查询字符串在N个字符串中出现的次数。
1 |
|
3.递归
3.1分治
分治法将原问题划分成若干个规模较小而结构与原问题相同或相似的子问题，然后分别解决这些子问题，最后合并子问题的解，即可得到原问题的解。分治法分解出的子问题应当是相互独立，没有交叉的。分治法作为一种算法思想，既可以使用递归的方法实现，也可以通过非递归的方法实现。
*3.2递归
递归是实现分治的一种方式。递归的核心在于解决以下两个问题： - 递归边界 - 递归式
以下是递归解决的全排列问题。本题也体现了回朔的思想。
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/*-------------------------------------------------------------------------------------------------
示例
输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
-------------------------------------------------------------------------------------------------*/
class Solution {
public:
vector<int> path;
vector<vector<int>> res;
vector<bool> used;
void traceback(vector<int>& nums){
if(path.size()==nums.size()){ //边界
res.push_back(path);
}
for(int i=0;i<nums.size();i++){
if(used[i])
continue;
used[i] = true;
path.push_back(nums[i]);
traceback(nums);
path.pop_back();
used[i] = false;
}
}
vector<vector<int>> permute(vector<int>& nums) {
int len = nums.size();
used.resize(len,false);
traceback(nums);
return res;
}
};
n皇后问题也是一个全排列问题，递归解法如下：
1 | class Solution { |
4.贪心
4.1简单贪心
贪心法是求解一类最优化问题的方法，总是考虑当前状态下局部最优的策略，使全局的结果达到最优。策略最优的证明通常使用反证法和数学归纳法，一般情况下，只要举不出反例就可以尝试使用贪心法求解问题。
*4.2区间贪心
区间不相交问题是另一个经典的贪心问题。给出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/*-------------------------------------------------------------------------------------------------
给定一个区间的集合 intervals ，其中 intervals[i] = [starti, endi] 。返回 需要移除区间的最小数量，使剩余区间互不重叠 。
-------------------------------------------------------------------------------------------------*/
class Solution {
public:
struct interval{
int left,right;
};
static bool cmp(interval a,interval b){ //按右边界从小到大排序
if(a.right==b.right)
return a.left<b.left;
return a.right<b.right;
}
int eraseOverlapIntervals(vector<vector<int>>& intervals) {
int ans = 1;
int num=intervals.size();
vector<interval> _intervals;
struct interval temp;
for(int i=0;i<num;i++){
temp.left = intervals[i][0];
temp.right = intervals[i][1];
_intervals.push_back(temp);
}
sort(_intervals.begin(),_intervals.end(),cmp);
temp = _intervals[0];
for(int i=1;i<num;i++){
if(temp.right<=_intervals[i].left){
ans++;
temp.right = _intervals[i].right; //更新已选的最大右边界
}
}
return num-ans;
}
};
类似的题还有最少的箭射气球、合并区间。这两个题也体现了贪心的思想，但是与区间不相交问题不同，这两个问题是尽可能让区间相交合并，因此在处理上和上题不同。例如最少的箭这道题，一种方式就是按左边界从小到大排序，从左往右选，尽量使相交区间更多，这和上题的顺序不同。在解决这类问题时，要仔细考虑按哪个边界排序，从哪一侧开始遍历。 ## *5.二分法 ### 5.1二分查找
二分查找是基于有序序列的查找算法，该算法从整体区间开始，每次测试当前区间的中间位置，通过判断中间元素与查找元素的大小进行进一步查找。二分查找的高效在于每次去除当前区间中的一半元素，时间复杂度只有O(logn)。以下是最基本的二分查找：
1 |
|
以上的这个查找，是在闭区间[left,right]进行的，最终终止的条件是left>right，这是因为left=right的情况要检查最终的唯一位置是否为符合要求的元素。如果是在[left,right)区间进行查找，没有left=right的情况，终止条件就是left<right了。
当问题转变为寻找有序序列中第一个满足条件的元素的位置时，终止条件又不同了。如果是闭区间，终止条件将变为left<right，当left=right时就已经找到唯一的位置，且不需要像查找元素一样，判断该元素是否符合要求了，直接返回位置就可以了。类似的，如果是(left,right]这样的区间，终止条件为left+1<right，当left+1=right，就找到唯一位置了。以下是解决有序序列的第一个满足某条件的元素的位置的固定解法：
1 | //[left,right] |
还有一点需要注意的是，mid=(left+right)/2可能发生溢出，因此常常用mid=left+(left-right)/2这条语句代替。下面是搜索插入位置的解，其中可以注意到，最后返回的是right+1，这是因为查找时取到了left=right，最后判断结束后，可能产生right=mid-1或left=mid+1，再结合可能插入的几种情况(在整个数组前，中，后)，最终返回right+1。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
int left = 0,right = nums.size()-1,mid = 0;
while(left<=right){
mid = left + (right-left)/2;
if(nums[mid]==target) return mid;
else if(nums[mid]>target){
right = mid-1;
}
else{
left = mid+1;
}
}
return right+1;
}
};
通过以上几题可以看出，while循环的终止条件，循环中最后对left和right的处理，最后返回的位置，都是要根据具体情况考虑的。直接记忆很可能出错，还是需要进行推导。
5.2二分法拓展
除了二分查找外，二分法也经常应用于其他问题。最经典的例子是求根号2的近似值，这个问题是一类问题的代表：在给定区间上有单调函数f(x)，求方程f(x)=0的根，用逐步逼近的方式求解答案。 ### 5.3快速幂
研究一个以下问题：给定三个正整数a、b、m，求a^b%m。其中a<10^9，b<10^18，1<m<10^9。
这个问题，使用循环是无法处理的，因为数量级非常大，必须采用其他的做法，即快速幂。快速幂基于二分的思想，如下： - 如果b是奇数，a^b = a * a^(b-1) - 如果b是偶数，a^b=a^(b/2) * a^(b/2)
b是奇数的情况总是可以转换为b是偶数的情况，b是偶数的情况总是可以转化为b/2的情况。以下是快速幂的迭代写法，递归写法同理：
1
2
3
4
5
6
7
8
9
10
11
12typedef long long LL;
LL binaryPow(LL a, LL b, LL m){
LL ans = 1;
while(b>0){
if(b&1){
ans = ans*a%m;
}
a=a*a%m;
b>>=1;
}
return ans;
}
双指针是利用问题本身与序列的特性，使用两个下标(或指针)对序列进行扫描，以较低的复杂度解决问题。双指针是一种重要的编程技巧。以下是双指针的一个例子：给定一个递增的整数序列和正整数M，求序列中两个位置a ，b的数使他们的和为M，输出所有方案。代码如下：
1 | while(i<j){ |
以上的解决方式充分利用了序列递增的性质。这种遍历方式不仅常用于数组，也应用于链表的相关问题。
6.2归并排序
归并排序是一种基于归并思想的排序方法。对于两路归并排序，原理是将序列两两分组，组内单独排序，再将这些组两两归并，组内再单独排序，直到只剩下一个组为止。以下是递归实现：
1 | const int maxn = 100; |
非递归实现的思路是在for循环中进行排序，实现如下:
1 | void mergeSort(int A[],int n){ |
快速排序是排序算法中平均时间复杂度为O(nlogn)的一种算法。快速排序的思路是： 1. 调整序列中的元素，使当前序列最左端的元素在调整后满足左侧所有元素均不超过该元素，右侧所有元素均大于该元素。 2. 对该元素的左侧和右侧分别递归进行1的调整，直到当前调整区间的长度不超过1。
首先实现步骤1，保证左侧元素小于第一个元素，右侧元素大于第一个元素。实现方式是把右边比该元素小的换到左边，再把左边元素大的换到右边，交替进行，当left与right重合时，调整完毕。
1
2
3
4
5
6
7
8
9
10
11int Partition(int A[],int left,int right){
int temp = A[left];
while(left<right){
while(left<right && A[right]>temp) right--;
A[left] = A[right];
while(left<right && A[left]<temp) left++;
A[right] = A[left];
}
A[left] = temp;
return left;
}
实现1后，快速排序只需要递归完成：
1
2
3
4
5
6
7void quickSort(int A[],int left,int right){
if(left<right){
int pos = Partition(A,left,right);
quickSort(A,left,pos-1);
quickSort(A,pos+1,right);
}
}
快速排序在序列中元素的排列比较随机时效率最高，但是当序列中元素接近有序时，会达到最坏的时间复杂度O(n^2)，产生这种情况的原因在于没有把当前区间划分为两个长度接近的自区间。解决方法是随机选择基准(放在中间的元素)，这样对任意输入数据的期望时间复杂度都能达到O(nlogn)。
1
2
3
4
5int randPartition(int A[], int left, int right){
int p = (round(1.0*rand()/RAND_MAX*(right-left)+left));
swap(A[p],A[left]);
//原Partition的划分过程，不需要任何改变......
}
PAT B1019 数字黑洞。这个题其实感觉不算数学问题，只是简单模拟。 ## 2.最大公约数与最小公倍数 **最大公约数**
求解最大公约数常使用辗转相除法。
1 | int gcd(int a,int b){ |
最小公倍数
在求得最大公约数的基础上求最小公倍数：
1 | int lcm(int a,b){ |
3.分数
分数的表示及化简
分数可以用结构体表示为假分数，注意由于分子分母的乘除法可能超出int范围，常使用long long型的分子分母。
1 | struct fraction{ |
分数输出
1 | void showresult(fraction r){ |
4.素数
素数是除了1和本身以外，不能被其他数整除的一类数。1既不是合数也不是素数。以下是关于素数的两个问题：如何判断给定的正整数是否是素数；如何较快的求出1-n以内的素数。
先看如何判断一个数是否是素数的问题。假设k是数n的约数，那么n/k也是n的约数，有n*n/k=n，这两个约数一个大于等于根号n，一个小于等于根号n。因此寻找约数只需要在根号n范围内寻找就可以了。
1 | bool isprime(int n){ |
能够判断素数，求素数表只要一个数一个数判断就可以了，但是这样判断时间复杂度为O(n*根号n)，对于10^5以上时就很慢了。有更高效的算法能够加快求素数表，以下是比较容易理解的埃氏筛法：
1 | const int manx = 101; |
5.质因子分解
能够求出质数表，质因子分解只需要一个一个判断是否是因子，不断除去因子就可以了。
1 |
|
6.大整数运算
对于超出存储精度范围的整数，可以用数组来存储每一位。将整数的高位存储在数组的高位，整数的低位存储在数组的低位。
1 | struct bign{ |
读入时注意高位存在数组高位，这样从低位开始遍历比较顺。
1 | bign change(char str[]){ |
四则运算基本上就是按照运算法则一位一位进行运算。
1 | //加法 |
第五章 C++标准模版库(STL)
1.vector常见用法
1 | //定义 |
2.set
1 | //定义 |
3.string
1 | //迭代器和vector一样，以下是常用函数 |
4.map
1 | //定义 |
5.queue
1 | //常用函数 |
6.priority_queue
1 | //常用函数 |
