排序
选择排序（简单选择排序）
- 从1到n进行n趟操作
- 每趟从待排序部分（i到n）选择最小元素与待排序部分第一个元素（i）交换
- 复杂度O(n2)
for (int i = 0; i < n; i++) {
int k = i;
for (int j = i; j < n; j++) {
if (num[j] < num[k]) {
k = j;
}
}
swap(num[k], num[i]);
}
插入排序（直接插入排序）
- 从2到n进行(n-1)趟操作
- 将第i个元素插入有序的前(i-1)个元素中
- 插入后仍然保持有序
- 从后往前枚举已有序部分
for (int i = 1; i < n; i++) {
int temp = num[i], j = i;
while (j > 0 && temp < num[j - 1]) {
num[j] = num[j - 1];
j--;
}
num[j] = temp;
}
sort函数
使用前提
#include <algorithm>
using namespace std;
使用方式
sort(首元素地址, 尾元素地址的下一个地址, 比较函数（非必需）);
如果不写比较函数，默认对区间进行递增排序。
比较函数
- 基本数据类型。例如，从大到小排列：
bool cmp(int a, int b) {
return a > b;
}
- 结构体数组。例如，按x大小排列：
struct node {
int x, y;
} ssd[10];
bool cmp(node a, node b) {
return a.x > b.x;
}
或者，在x相等的情况下，按照y从小到大排序：
bool cmp(node a, node b) {
if (a.x != b.x) {
return a.x > b.x;
} else {
return a.y < b.y;
}
}
- STL容器排序
只有vector、string、deque可以用sort()排序。
例如vector：
#include <vector>
#include <algorithm>
using namespace std;
bool cmp(int a, int b) {
return a > b;
}
int main() {
vector<int> vi;
vi.push_back(3);
vi.push_back(1);
vi.push_back(2);
sort(vi.begin(), vi.end(), cmp);
return 0;
}
string：
string str[3] = {"bbbb", "cc", "aaa"};
sort(str, str + 3);
或者把string按长度从小到大排序：
bool cmp(string str1, string str2) {
return str1.length() < str2.length();
}
sort(str, str + 3, cmp);
排序题常用解题步骤
- 定义相关结构体
- 编写
cmp函数 - 实现排名
散列
- 用空间换时间
- 将元素通过一个函数（散列函数H）转换为整数，使得该整数可以尽量唯一地代表这个元素
常用的散列函数
- 直接定址法：恒等变换（H(key)=key）或线性变换（H(key)=a*key+b）
- 平方取中法：key的平方中间若干位作为hash（很少用）
- 除留余数法：H(key)=key%mod
取TSize是一个素数，mod取与TSize相等。mod为素数时能尽量覆盖每一个数。
解决散列冲突
- 线性探查法：检查下一个位置（循环），直到找到一个空闲位置，可能引发扎堆
- 平方探查法：H(key)+12、H(key)-12、H(key)+22、H(key)-22、H(key)+32...，超出范围取模
- 链地址法（拉链法）：把H(key)相同的key连接成单链表
- 可以用STL里的
map和unordered_map（C++11）
字符串hash初步
- 把字母当成0-25的26进制数
- 如果有小写字母就52进制
- 如果有数字可以选择变成62进制或者在末尾直接拼接个数确定的数字
递归
分治
将原问题划分成若干个规模较小而结构与原问题相同或相似的子问题，分别解决子问题，最后合并子问题的解，得到原问题的解。
分治法的三个步骤：
- 分解
- 解决
- 合并
子问题应当相互独立、没有交叉，如果有则不能用分治。
递归
- 递归的两个重要概念：递归边界、递归式（递归调用）
全排列
划分子问题：输出以1开头的全排列、输出以2开头的全排列、……、输出以n开头的全排列
#include <cstdio>
bool table[11]; // 记录数是否在排列中
int P[11], n; // P为当前排列
void generate(int index) {
if (index == n + 1) { // 递归边界
for (int i = 1; i <= n; i++) {
printf("%d", P[i]);
}
putchar('\n');
return;
}
for (int i = 1; i <= n; i++) { // 枚举1到n，给没排列的数找个地方
if (!table[i]) { // 如果i不在当前排列中
P[index] = i; // 把i加入当前排列
table[i] = true; // 标记i已经在排列中
generate(index + 1); // 递归式
table[i] = false; // 解决完子问题，恢复状态
}
}
}
int main() {
scanf("%d", &n);
generate(1);
return 0;
}
n皇后问题
在n*n的国际象棋棋盘上放n个皇后，使得n个皇后两两均不在同一行、同一列、同一对角线上。
-
方法1
考虑到每行只能放一个皇后，每列也只能放一个皇后，如果把n列皇后对应行号写出来，就是1-n的一个排列。只需要枚举1-n的所有排列，查看每个排列对应的放置方案是否合法。
可以在全排列代码基础上求解。到达递归边界时表示生成了一个排列，所以要在其内部判断是否为合法方案。遍历每两个皇后，判断它们是否在同一对角线上。
int count = 0; void generate(int index) { if (index == n + 1) { // 递归边界，生成一个排列 bool flag = true; // flag为true表示当前为合法方案 for (int i = 1; i <= n; i++) { // 遍历任意两个皇后 for (int j = i + 1; j <= n; j++) { if (abs(i - j) == abs(P[i] - P[j])) { // 如果在对角线上 flag = false; // 不合法 } } } if (flag) { count++; } return; } for (int i = 1; i <= n; i++) { if (!table[i]) { P[index] = i; table[i] = true; generate(index + 1); table[i] = false; } } } -
方法2
当已经放置一部分皇后时，剩下的无论怎么放都不行，就不用继续递归了，直接返回上层。
一般地，如果在到达递归边界前的某层，由于一些事实导致已经不需要向子问题递归，就可以直接返回上一层。这种方法叫做回溯法。
void generate(int index) { if (index == n + 1) { // 递归边界，生成一个合法方案 count++; // 如果能到这里一定合法 return; } for (int x = 1; x <= n; x++) { // 第x行 if (!table[x]) { // 第x行没有皇后 bool flag = true; // flag为true表示不会和之前的冲突 for (int pre = 1; pre < index; pre++) { // 遍历之前的皇后 if (abs(index - pre) == abs(x - P[pre])) { flag = false; break; } } if (flag) { P[index] = x; table[x] = true; generate(index + 1); table[x] = false; } } } }
贪心
简单贪心
在当前状态下局部最优，来达到全局最优。
区间贪心
区间不相交问题：给出N个开区间(x,y)，从中选择尽可能多的开区间，使得这些开区间两两没有交集。总是选择左端点最大的区间，或者总是选择右端点最小的区间。
二分
二分查找
- 在有序序列中找出给定的元素。时间复杂度为O(logn)。
步骤：
- 一开始令[left, right]为整个序列的下标区间（[0, n-1]），然后测试每次当前[left, right]的中间位置mid=(left+right)/2，判断A[mid]与欲查询元素的大小
- 如果A[mid]=x，说明查找成功，退出查询
- 如果A[mid]>x，说明x在mid位置的左边，往左子区间[left, mid-1]继续查找
- 如果A[mid]<x，说明x在mid位置的右边，往右子区间[mid+1, right]继续查找
- 如果left>right，查找失败
int binarySearch(int A[], int left, int right, int x) {
int mid;
while (left <= right) {
mid = (left + right) / 2;
if (x == A[mid]) {
return mid;
} else if (x < A[mid]) {
right = mid - 1;
} else {
left = mid + 1;
}
}
return -1;
}
如果序列是递减的，只需把x < A[mid]改为x > A[mid]。
- 如果递增序列中的元素可能重复，求序列中第一个大于等于元素的位置：
循环条件left<=right改为left<right，因为不是判断存不存在，而是找位置当left==right时刚好能夹出唯一位置。要查询的元素可能比所有元素都大，所以二分的初始区间应为[0, n]。
int solve(int left, int right) {
int mid;
while (left < right) {
mid = (left + right) / 2;
if (条件成立) { // 第一个满足条件的元素位置<=mid
right = mid;
} else {
left = mid + 1;
}
}
return left; // right也行
}
快速幂
给定三个正整数a、b、m（a<109，b<1018，1<m<109），求ab%m。
-
思想
- 如果b是奇数，那么ab=a*ab-1
- 如果b是偶数，那么ab=ab/2*ab/2
-
递归实现
递归边界：b=0时返回1
递归式：如上所述思想
代码实现：
long long binaryPow(long long a, long long b, long long m) { if (b == 0) { return 1; } if (b % 2 == 1) { return a * binaryPow(a, b - 1, m) % m; } else { long long mul = binaryPow(a, b / 2, m) % m; return mul * mul % m; } }时间复杂度O(logb)。
b为偶数时不能直接返回
binaryPow(a, b / 2, m) * binaryPow(a, b / 2, m)，会导致时间复杂度退化。这两个值是相等的，直接保存下来即可。另外：
- 如果初始时a>m，在进入函数前让a对m取模
- 如果m为1，可以直接在函数外特判为0，无需计算
-
迭代实现
把b写成二进制，ab就可以写成若干二次幂之和。
- 初始令ans=1，存放累积结果
- 判断b的二进制末尾是否为1，如果是，令ans乘a的值
- 令a平方，将b右移一位（除以2）
- 只要b>0，就回到第2步
代码实现：
long long binaryPow(long long a, long long b, long long m) { long long ans = 1; while (b > 0) { if (b & 1) { ans = ans * a % m; } a = a * a % m; b >>= 1; } return ans; }
实际递归和迭代效率差距不明显。
双指针
例1：给一个递增的正整数序列和正整数M，求序列中两个不同位置的数a和b，使得a+b=M，输出所有满足条件的方案。
令下标i的初值为0，下标n的初值为n-1，接下来根据a[i]+a[j]与M的大小关系进行选择，使i不断向右移动、j不断向左移动直到i>=j成立：
- 如果a[i]+a[j]==M，说明找到了一个方案。由于序列递增，a[i+1]+a[j]>M与a[i]+a[j-1]<M均成立，但a[i+1]+a[j-1]与M的关系未知，剩余的方案在[i+1, j-1]区间产生，令i右移，j左移。
- 如果a[i]+a[j]>M，则a[i+1]+a[j]>M成立，但a[i]+a[j-1]与M的关系未知，剩余方案在[i, j-1]产生，令j左移。
- 如果a[i]+a[j]<M，则a[i]+a[j-1]<M成立，但是a[i+1]+a[j]与M关系未知，剩余方案在[i+1, j]产生，令i右移。
while (i <= j) {
if (a[i] + a[j] == m) {
printf("%d %d\n", i, j);
i++;
j--;
} else if (a[i] + a[j] < m) {
i++;
} else {
j--;
}
}
例2：序列合并问题
假设有两个递增序列A和B，合并成递增序列C。
设置两个下标i和j，分别指向A和B的第一个元素，根据大小决定哪一个放入C：
- 若A[i]<B[j]，则A[i]加入C，i右移
- 若A[i]>B[i]，则B[i]加入C，j右移
- 若A[i]==B[i]，则选择任意一个加入C，让对应的下标右移
- 上述操作执行到i、j中的任意一个达到末端位置，然后把另一个序列的所有元素依次加入C
int merge(int A[], int B[], int C[], int n, int m) {
int i = 0, j = 0, index = 0;
while (i < n && j < m) {
if (A[i] <= B[i]) {
C[index++] = A[i++];
} else {
C[index++] = B[j++];
}
}
while (i < n) {
C[index++] = A[i++];
}
while (j < m) {
C[index++] = B[j++];
}
return index;
}
归并排序
将序列两两分组，组内单独排序；再归并，组内单独排序，一直到只剩一个组。时间复杂度为O(nlogn)。
-
递归实现
反复将当前区间分为两半，对两个子区间[left, mid]和[mid+1, right]分别递归进行归并排序，然后将两个已经有序的子区间合并为有序序列。
const int maxn = 100; void merge(int A[], int L1, int R1, int L2, int R2) { int i = L1, j = L2; int temp[maxn], index = 0; while (i <= R1 && j <= R2) { if (A[i] <= A[j]) { temp[index++] = A[i++]; } else { temp[index++] = A[j++]; } } while (i <= R1) { temp[index++] = A[i++]; } while (j <= R2) { temp[index++] = A[j++]; } for (i = 0; i < index; i++) { A[L1 + i] = temp[i]; } } void mergeSort(int A[], int left, int right) { if (left < right) { // 递归边界 int mid = (left + right) / 2; mergeSort(A, left, mid); mergeSort(A, mid + 1, right); merge(A, left, mid, mid + 1, right); } } -
非递归实现
令step初值为2，将数组中每step个元素分为左右两部分，两部分进行合并，再把step乘2，重复操作，直到step/2超过元素个数n。
void mergeSort(int A[]) { for (int step = 2; step / 2 <= n; step *= 2) { for (int i = 1; i <= n; i += step) { int mid = i + step / 2 - 1; if (mid + 1 <= n) { merge(A, i, mid, mid + 1, min(i + step - 1, n)); } } } }