LeetCode 六月每日一题
*1 你能在你最喜欢的那天吃到你最喜欢的糖果吗(Mid)
解法:前缀和+区间交集
原理:
favoriteDay内吃糖的总数区间 X = [favoriteDay + 1, (favoriteDay + 1) * dailyCap],即左边界为每天只吃一个,右边界为每天吃到最大
可以吃到favoriteType的区间 Y = [sum[favoriteType - 1] + 1, sum[favoriteType]],即最少只吃到一个,最多吃到最后一个(吃完)
只要两区间有交集,总有吃法使得在favoriteDay当天吃到favoriteType类的糖。
边界情况:当favoriteType == 0时,Y的左边界为1,即只要吃一个糖就能吃到第0类
LeetCode 五月每日一题
28 汉明距离综合(Mid)
477. 汉明距离总和(Middle)
思路:用乘法法则,计算所有数字在每一位上的汉明距离差,再求总和
乘法法则:集合A有n种选择,集合B有m种选择,从A、B各选一个有nm种可能,在此处,因为在第i位上为1的数字和为0的数字汉明距离为1,因此组合后所有可能性即为第i位上的汉明距离数
C++trick_methods
lambda表达式
lambda表达式
参考:http://c.biancheng.net/view/3741.html
背景
lambda 表达式是 C++11 最重要也最常用的一个特性之一,C# 3.5 和 Java 8 中就引入了 lambda 表达式。
lambda表达式有如下优点:
- 声明式编程风格:就地匿名定义目标函数或函数对象,不需要额外写一个命名函数或者函数对象。以更直接的方式去写程序,好的可读性和可维护性。
- 简洁:不需要额外再写一个函数或者函数对象,避免了代码膨胀和功能分散,让开发者更加集中精力在手边的问题,同时也获取了更高的生产率。
- 在需要的时间和地点实现功能闭包,使程序更灵活。
《算法笔记》总结
[TOC]
0 起步
基本数据类型:变量,强制转换,符号常量(define),const
顺序结构:赋值,scanf/printf,getchar/putchar,typedef,math函数
区分double型的scanf和printf
常用math函数
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#include <math.h>
// 规范
double fabs(double x); // 取绝对值
double round(double x); // 四舍五入,返回的double需用(int)取整
double floor(double x); // 向下取整
double ceil(double x); // 向上取整
// 以上两个函数对负数也有效,如floor(-5.2) = -6
// 计算
double pow(double r, double p); // 返回r^p
double sqrt(double x); // 返回x的算术平方根
double log(double x); // 返回以e为底的对数
// 换底公式处理任何底的对数: log_a(b) = log(b) / log(a)
// 三角函数
double sin(double x);
double cos(double x);
double tan(double x);
// 参数要求弧度制 如1/3 * pi
// 反三角函数
double asin(double x);
double acos(double x);
double atan(double x);
选择结构:if,switch
循环结构:while,do while,for,break/continue
数组:memset,字符数组,string.h头文件,
1 | #include <cstring> |
sscanf/sprintf(字符串格式转换)
1 | // 将数据输入到字符串 |
函数:嵌套、递归
指针:指针与数组、引用&
- 引用不产生副本,而是给原变量起别名
- 指针引用(如
int* &r
),在需要改指针存储的unsigned int
型地址本身时使用
结构体:访问元素.
/->
,构造函数
输入字符串汇总:
1 | char str[MAXN]; |
文件输入
1 | #include <stdio.h> |
C语言字符判断函数
1 | #include <ctype.h> |
1 算法初步
1.1 排序
c++ sort
1 | #include <algorithm> |
c qsort
1 | #include <stdlib.h> |
写cmp函数的原则:
- 希望元素按什么顺序排列,就直接按照大小次序返回即可;
1.2 递归
典例:全排列
1 | // dfs(0) |
n皇后问题
1 | // 核心思想:排列 + 判断方案是否合法 |
1.3 贪心
局部最优推得全局最优
- 简单贪心:分布背包
- 区间贪心
- 活动选择、区间选点问题
1.4二分
查找序列是否存在满足条件的元素(常规二分
1
2
3
4
5
6
7
8
9
10
11
12
13// 严格递增序列
int solve(int left, int right, int x)
{
int mid;
while (left <= right)
{
mid = (left + right) / 2;
if (A[mid] == x) return mid
else if (A[mid] > x) right = mid - 1;
else left = mid + 1; // A[mid] < x
}
return -1; // 查找失败
}
查找序列第一个满足条件的元素
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16// 序列从左到右先不满足,后满足
// 若存在,返回的是元素的位置
// 若不存在,返回的是“假设存在,它应在的位置”
int solve(int left, int right)
{
int mid;
while (left < right) // 此时才有区间
{
mid = (left + right) / 2;
if (条件成立) // 满足条件,则第一个满足的在[left, mid]之间
right = mid // 因为mid也满足,所以不是mid-1
else
left = mid + 1;
}
return left; // left==right时退出循环
}对于左开右闭的区间
(left, right]
,二分条件就是while ((left + 1 < right)
对于左闭右开
[left, right)
,二分条件是while (left < right - 1)
二分拓展
计算单调函数
f(x)=0
的根(近似)1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19const double eps = 1e-5
// f(x)递增
double f(double x)
{
return ...; // 函数值
}
double solve(double left, double right)
{
double mid;
while (right - left > eps)
{
mid = (left + right) / 2;
if (f(mid) > 0) // 若递减,把>改为<
right = mid; // 往[left, mid]逼近
else
left = mid; // 往[mid, right]逼近
}
}快速幂(求$a^b\%m$,O(logb))
递归写法
- 如果b是奇数($b \& 1$),$a^b = a * a^{b - 1}$
- 如果b是偶数,$a^b = a^{b/2} * a^{b / 2}$
1
2
3
4
5
6
7
8
9
10
11
12
13
14typedef long long LL;
// O(logb)
LL binaryPow(LL a, LL b, LL m)
{
if (b == 0) return 1;
if (b & 1) // 奇数
return a * binaryPow(a, b - 1, m) % m;
else
{
LL mul = binaryPow(a, b / 2, m);
return mul * mul % m;
}
}迭代写法:
b可以写成若干二次幂的和,如$2^{13} = 2^{(1101)_2} = 2^8 2^4 2^1$
当二次幂$i$号位被选中(中间的式子),那么$a^{2i}$就被选中(右边的式子)
- 判断b的二进制末尾是否为1,是则令ans*a
- a自乘,相当于进入下一位的判断和计算
- b右移一位,和2的作用类似
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15LL binaryPow(LL a, LL b, LL m)
{
LL ans = 1;
while (b)
{
if (b & 1) // b的二进制末尾为1
{
ans = ans * a % m; // 用b的二进制计算幂
}
a = a * a % m;
b >>= 1; // b右移一位
}
return ans;
}
注:任何正整数对1取模一定为0
1.5 Two Pointer
Two Pointer即双指针,用两个指针(或下标)一同访问一个序列,加快速度
1.5.1 归并排序
two pointer思想:merge中,两个数组两个指针
2-路归并排序的核心是将两个有序的数组合并为一个
1 | // 合并数组 |
1.5.2快排
two pointer思想:partition中,一个数组、首尾双指针
1 | #include <stdlib.h> |
1.6 其他高效技巧
打表
递推(有时思考一下递推式比简单暴力高效很多)
“有几个PAT”:计算一个给定字符串包含多少个PAT暴力计算会超时,但利用组合的思想,计算A左边的P数,乘以A右边的T数,就能得到一个A形成的PAT个数
例如 APPAPT,中间的A左边2个P,右边1个T,总共能形成2*1=2个PAT,将所有A的结果相加得到最终结果
随机选择算法(求第K大的数)
此处有文字游戏:如1 2 3 4 5 6,有两种理解:1)第一大 1,第二大 2;2)第一大 6,第二大 51
2
3
4
5
6
7
8
9
10
11
12
13// 期望时间O(n)
void randSelect(int A[], int left, int right, int K)
{
int p = randPartition(left, right); // 使用快排的randPartition
int M = p - left + 1; // 位置p在[left,right]中排在第M位
if (K == M)
return A[p]; // 找到第K大元素
else if (K < M)
return randSelect(A, left, p - 1, K); // 在左子区间
else
return randSelect(A, p + 1, right, K - M); // 在右子区间的第K-M位
}
2 数学问题
简单数学
- 数字黑洞
最大公约数和最小公倍数
1 | // 最大公约数 |
1 | //最小公倍数 |
分数四则运算
素数
素数:不能被其他数整除的数(n%i!=0
)
求素数表
遍历1-sqrt(n),复杂度为O(n * sqrt(n))
质数筛
埃氏(O(nloglogn)):对每个质数,筛去其倍数
1
2
3
4
5
6
7
8
9
10
11
12
13void prime()
{
// i既可能是待存质数,同时也作为筛
for (int i = 2; i <= MAXN; i++)
{
if (!vis[i])
{
p[++p[0]] = i; // p[0]为cnt
for (int j = i + i; j <= MAXN; j += i)
vis[j] = true;
}
}
}欧拉筛(O(n)):在埃氏筛的基础上,每个合数只被其最小质因子筛去,避免重复
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17void prime()
{
for (int i = 2; i <= MAXN; i++)
{
// 存质数
if (!vis[i])
p[++p[0]] = i;
// 筛:筛去i * p[j]
for (int j = 1; j <= p[0] && i * p[j] <= MAXN; j++)
{
vis[i * p[j]] = true;
if (i % p[j] == 0) // 以后会由质因子筛到,避免重复
break;
}
}
}关键语句
if ((i % p[j]) == 0) break;
的理解:- 当$i \% p[j]$时,令$i = k \times p[j]$,继续往下执行,即筛$i \times p[j+1]$,而此时有$i \times p[j+1] = p[j] \times k \times p[j+1]$,即$i \times p[j+1]$会在$i’=k \times p[j+1]$时由$p[j]$筛掉,此时属于重复操作,违背由最小质因子筛去的法则。对于$p[j+2], … p[j+m]$类同,因而中断循环
注意!!!
i % p[j]
== 0
才表示p[j]
整除i
!!!
大整数运算
由于大整数运算从低位开始,而字符串读入从高位,因此在转换时要记得反置
大整数结构体
1
2
3
4
5
6
7
8
9
10
11
12struct BigN
{
int num[MAXN];
int len;
// 初始化函数
BigN()
{
memset(num, 0, sizeof(d));
len = 0;
}
};加法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21BigN add(BigN a, BigN b)
{
BigN c;
int carry = 0; // 进位
int res;
for (int i = 0; i < a.len || i < b.len; i++)
{
res = a.num[i] + b.num[i] + carry;
c.num[c.len++] = res % 10;
carry = res / 10;
}
// 末尾进位
if (carry != 0)
{
c.num[c.len++] = carry;
}
return c;
}减法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18// 假设a > b,如果a < b需交换a、b并在前面加-号
BigN sub(BigN a, BigN b)
{
BigN c;
for (int i = 0; i < a.len || i < b.len; i++)
{
if (a.num[i] < b.num[i])
{
a.num[i] += 10;
a.num[i+1] -= 1; // 由于a > b,if不会在i=len时成立,所以不会越界
}
c.num[c.len++] = a.num[i] - b.num[i];
}
while (c.len > 1 && c.num[c.len-1] == 0) // 去除高位0但保留至少1位数
c.len--;
return c;
}高精度与低精度的乘法
- 从低位遍历大整数,每位与低精度相乘,并加上已有进位
- 取个位数为结果,多位
- 循环直至遍历所有位,记得考虑最后的进位
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18BigN mult(BigN a, int b)
{
BigN c;
int carry = 0;
for (int i = 0; i < a.len; i++)
{
int temp = a.num[i] * b + carry; // 每位与低精度相乘,并加上已有进位
c.num[c.len++] = temp % 10; // 取个位数为结果
carry = temp / 10; // 高位为进位
}
while (carry != 0) // 最后的多位进位
{
c.num[c.len++] = carry % 10;
carry /= 10;
}
}高精度与低精度除法
注意:唯一从字符串反置后的高位开始遍历的计算(加减乘都是从低位),实际就是直接按输入的序- 商的位数和被除数(左边)的位数一一对应
- 遍历被除数的每一位,余数(初始化为0)和每次选取的位组成新的临时被除数
- 若除不了(小于除数),结果为0,进入下一位;若能除,记录商,更新余数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20BigN divide(BigN a, int b, int& r)
{
BigN c;
c.len = a.len; // 商和被除数每一位一一对应
int temp = 0;
for (int i = a.len - 1; i >= 0; i--) // 从高位开始遍历
{
temp = temp * 10 + a.num[i]; // 本次选择的位与上一位遗留的余数组合
if (temp < b) c.num[i] = 0; // 不够除,该位为0
else // 够除
{
c.num[i] = temp / b; // 商
temp = temp % b; // 该位遗留的余数
}
}
r = temp; // 最终余数
while (c.len > 1 && c.num[c.len - 1] == 0) c.len--; // 去除高位0但至少保留1位
}
组合数
求
n!
中有多少个质因子p
O(logn)
结论:n!
中有$\frac{n}{p}+\frac{n}{p^2}+\frac{n}{p^3}+…$个质因子p
1
2
3
4
5
6
7
8
9int cal(int n, int p)
{
int ans = 0;
while (n)
{
ans += n / p;
n /= p;
}
}可用于计算
n!
末尾有多少个0:计算质因子5的个数求组合数$C_{n}^{m}$
定义计算(阶乘)(long long也只能承受n<20的数据)递推公式:$Cn^m = C{n-1}^m + C_{n-1}^{m-1}$,$C_n^0 = C_n^n = 1$
1
2
3
4
5long long C(long long n, long long m)
{
if (m == 0 || n == m) return 1;
else return C(n-1, m) + C(n-1, m-1); // 可以储存计算结果防止重复计算
}用定义,边除边乘,$C_{n+m-i}^{i}=\frac{(n-m+1)(n-m+2)…(n-m+i)}{12…i}$一定是整数
1
2
3
4
5
6
7
8
9long long C(long long n, long long m)
{
long long ans = 1;
for (long long i = 1; i <= m; i++)
{
ans = ans * (n - m + i) / i;
}
return ans;
}
C++标准模板库STL
注1:
无特殊说明,一般1
2#include <[STL名字]>
using namespace std;即可使用
注2:
STL嵌套,如果出现>>
,记得在中间加空格:> >
,否则c++11会将其识别为移位注3:
STL的find()
一般用if (stl.find(x) != stl.end())
进行判断,string
特殊,可以用string::npos
注4: 计算value在stl中的个数
1
count(stl.begin(), stl.end(), value);
注5:C++11新特性!
引入emlace_front、empace 和 emplace_back进行构造插入
1
2
3
4
5
6//push_back()创建一个临时对象,然后将临时对象拷贝到容器中
d.push_back(Date(“2016”,”05”,”26”));
// 直接进行构造插入,省去构造临时对象的开销
// 前提是元素需要有相应的构造函数
d.emplace_back(“2016”,”05”,”26”);
vector
定义
1
2
3vector<typename> name; // 一维变长
vector<vector<typename>> name; // 二维变长
vector<typename> arrName[arrSize]; // 第一维定长,第二维变长元素访问
- 使用下标:
v[i]
- 迭代器:
vector<typename>::iterator it
:类似指针,用*it
访问元素vi.begin()
,vi.end()
:左闭右开。(只有vector和string可以使用vi.begin()+i
的写法
- 使用下标:
常用函数
1
2
3
4
5
6
7vi.push_back(x); // O(1)
vi.pop_back(); // O(1), 删除尾元素
vi.size(); // O(1), 返回unsigned类型
vi.clear(); // O(n), 清除vector中所有元素
vi.insert(it, x); // O(n), 向it处插入一个元素
vi.erase(it); // O(n), 删除it处的元素
vi.erase(first, last) // O(n), 删除[first, last)内的所有元素, first, last为迭代器
set
内部自动有序且不含重复元素的集合
定义:和vector类似
元素访问
只能通过迭代器:set<typename>::iterator it
1
2
3
4
5// 只能按以下方式枚举,不支持*(it+i)
for (set<int>::iterator it = st.begin(); it != st.end(); it++)
{
printf("%d", *it);
}常用函数
1
2
3
4
5
6
7
8st.insert(x); // O(logn), 自动递增排序和去重
st.find(value); // O(logn), 返回值为value的迭代器it
st.count(value); // 如果value在集合中,返回1,否则返回0
st.erase(it); // O(1), 删除元素
st.erase(value); // O(logn), 删除元素
st.erase(first, last); /// O(n)
st.size(); // O(1)
st.clear(); // O(n)- 拓展:
multiset
,unordered_set
string
定义
1
2
3
4
5
6
7
8// 使用字符串常量初始化
string str = "abcd";
// 使用字符数组初始化
char c[MAXN];
...
string str(c);
string str1 = c;元素访问
直接像字符数组一样访问
直接输入输出,只能用
cin
和cout
1
2
3string str;
cin >> str;
cout << str;使用printf输出
1
printf("%s\n", str.c_str());
迭代器访问
1
2
3
4for (string::iterator it = str.begin(); it != str.end(); it++)
{
printf("%c", *it);
}
常用函数
operator+=(字符串拼接)
1
string str3 = str1 + str2;
compare operator,按字典序比较
1
2
3
4if (str1 >= str2)
{
// do something...
}其他
1
2
3
4
5
6
7
8
9
10
11
12
13str.length(); str.size(); // O(1), 二者基本相同
str.insert(pos, str2); // O(N), 在pos下标处插入str2
str.insert(it, first, last); // O(N), 在原字符串it处插入串[first, last)
str.erase(it); // O(N), 删除it指向的元素
str.erase(first, last);
str.erase(pos, length); // 从pos处删除length个字符(含本身)
str.clear(); // O(1), 清空
str.substr(pos, len); // O(len), 返回从pos开始、长度为len的子串
str.find(str2); // O(nm), 如果str2是字串, 返回其在str第一次出现的位置, 否则返回string::npos(unsigned_int型, 值为-1)
str.find(str2, pos); // 从pos处开始匹配str2
// 常用写法:if (str.find(str2) != string::npos) 如果能找到, 则...
str.replace(pos, len, str2); // O(n), 把str从pos处开始、长度为len的子串替换为str2
str.replace(first, last, str2); // 把str的[first, last)子串替换为str2
map
map内的键会按从小到大顺序自动排序(因为是基于红黑树实现),键唯一
注:
map无法按value排序,只能将pair
放进vector
里,对vector
排序
定义
1
map<type1, type2> mp;
访问
直接使用下标(新值会覆盖旧值)
1
mp['c'] = 20;
通过迭代器访问
1
2
3map<type1, type2>::iterator it;
it->first; // 访问键
it->second; // 访问值
常用函数
1
2
3
4
5
6
7it = mp.find(key); // O(logN), 返回键为key的迭代器it
mp.insert(make_pair(value1, value2));
mp.erase(it); // O(1), 删除元素
mp.erase(key); // O(logN), 根据键删除
mp.erase(first, last); // 删除一个区间的元素
mp.size(); // O(1)
mp.clear(); // O(N)拓展
multimap
:一个键对多个值unordered_map
:只映射不排序,比纯map
快很多
其他
- hashmap可当作bool数组使用
- map会自动初始化
queue
先进先出
定义
1
queue<type> q;
元素访问
只能用q.front()
或q.back()
访问队首或队尾元素
(ps:访问前先使用empty()
判断队是否空)常用函数
1
2
3
4
5q.push(); // O(1)
q.front(); q.back(); // O(1)
q.pop(); // O(1) 队首出队
q.empty(); // O(1) 队列是否空
q.size();拓展
- 双端队列
deque
:首尾皆可插入和删除 - 优先队列
priority_queue
:堆实现,最大元素置于队首
- 双端队列
其他
- 通常通过重新定义一个队列来完成清空
O(1)
- 通常通过重新定义一个队列来完成清空
priority_queue
用堆实现,队首元素是当前队列中优先级最高的一个
定义
1
2#include <queue>
priority_queue<type> name;元素访问
只能通过top()
来访问队首元素(优先级最高)
(ps:使用top()
前要用empty()
判断队是否空)常用函数
1
2
3
4
5pq.push(x); // O(logN), 入队
pq.top(); // O(1)
pq.pop(); // O(logN), 令队首元素出队
pq.empty(); // O(1), 队是否空
pq.size(); // O(1)优先级设置
基本数据类型
默认为大顶堆。小顶堆写法为:1
priority_queue< [type], vector<[type]>, greater<[type]> > pq;
vector<[type]
:承载堆的容器;greater<[type]>
:小于对应大优先级结构体优先级
写在结构体内:
1
2
3
4
5
6
7
8
9
10
11
12
13struct fruit
{
string name;
int price;
// 重载小于号
friend bool operator < (const fruit& f1, const fruit& f2)
{
return f1.price < f2.price; // 价格大的优先级大, 相当大顶堆
// return f1.price > f2.price // 价格小的优先级大,即小顶堆
}
};
priority_queue<fruit> pq;(
friend
友元允许非成员函数访问类/结构体的所有成员)写在结构体外:
1
2
3
4
5
6
7
8
9struct cmp
{
bool operator() (const fruit& f1, const fruit& f2)
{
return f1.price > f2.price; // 小顶堆
}
};
priority_queue<fruit, vector<fruit>, cmp> pq;注意:结构体指针的比较需另写struct cmp
1
2
3
4
5
6
7
8struct cmp
{
bool operator() (const Node* n1, const Node* n2) const
{
return n1->v > n2->v;
}
};
priority_queue<Node*, vector<Node*>, cmp> pq;
stack
后进先出
定义
1
stack<type> name
元素访问
st.top()
常用函数
1
2
3
4st.push(x); // O(1)
st.top(); // O(1)
st.pop(); // O(1)
st.empty(); // O(1)其他
- 通常通过重新定义一个栈来完成栈的清空
O(1)
- 通常通过重新定义一个栈来完成栈的清空
pair
将两个元素合成为一个
定义
1
2
3
4
5
6
7
8
9
10#include <utility>
using namespace std;
// 声明
pair<type1, type2> name;
//初始化
pair<type1, type2> p(value1, value2);
//临时构建
pair<type1, type2>(value1, value2); // 方法一
make_pair(value1, value2); // 方法二元素访问
只有两个元素:
p.first
,p.second
常用函数
- 比较操作
直接使用比较符号如>=, !=
。首先比较first
,只有当first
相等时才去比较second
(可类似priority_queue
重写<
号)
- 比较操作
常见用途
作为map的键值对插入1
mp.insert(make_pair(value1, value2));s
algorithm头文件下的常用函数
1 | #include <algorithm> |
数据结构专题
链表
定义
1
2
3
4
5
6
7
8
9
10
11
12
13// 动态
struct node
{
typename data; // 数据域
node* next; // 指针域
};
// 静态
struct node
{
typename data;
int next; // 用数组下标表示指针域
};空间分配
1
2
3
4
5
6// C malloc
#include <stdlib.h>
node* p = (node*)malloc(sizeof(node));
// c++ new
node* p = new node;(申请较大动态数组时可能会失败)
内存泄漏:使用
malloc
或new
分配的空间,使用后没有释放,直到程序结束前一直占据。内存泄漏会导致内存消耗过快而最终五内存可使用
1
2
3
4
5// C free
free(p); // p为指针变量,free释放p指向的空间,并将p指向NULL
// C++
delete(p);malloc
与free
成对出现;new
与delete
成对出现创建与增删
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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51// 创建
node* create(vector<typename> arr)
{
node *p, *head;
head = new node; // 使用头节点,相当于数组的下标0
for (int i = 0; i < arr.length(); i++)
{
p = new node;
p->val = arr[i];
p->next = head->next;
head->next = p;
}
return head;
}
// 增
void insert(node* head, int pos, int val)
{
node* p = head;
// p移动到pos的前一个元素位置
// (p从head开始,i从0开始,i到达pos-1时,p也到达第pos-1个元素)
// 使用头节点即可不用讨论在链表头插入的情况
int i;
for (i = 0; i < pos - 1 && p != NULL; i++, p = p->next);
if (p == NULL || i > pos - 1) // i小于1或大于表长
return;
node* q = new node;
q->val = val;
q->next = p->next;
p->next = q;
}
// 删(删除某一位置上的元素)
void deleteNode(node* head, int pos)
{
node* p = head;
node* q = NULL;
// 同insert寻找前元
for (int i = 0; i < pos - 1; i++, p = p->next);
if (p == NULL || p->next == NULL)
return;
q = p->next; // 要删除q
p->next = q->next;
delete(q); // 与new成对
}静态链表排序
将有效结点前置,按升序排序。之后即可用数组下标访问链表,数组序即为排序后的链表序1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23// 定义有效位
struct node
{
int data, addr;
int next;
int valid; // 为true表示在链表上
}ls[maxn];
// 定义比较函数
bool cmp(const node& n1, const node& n2)
{
if (n1.valid && n2.valid) // 都是有效结点
{
return n1.data < n2.data;
}
else
{
return n1.valid > n2.valid;
}
}
// sort需要排所有元素(包括无效的)
sort(ls, ls+maxn, cmp);
搜索专题
DFS
找“岔路口”与“死胡同”
比如背包问题,对每个物品,有选或不选两种选择即“岔路口”;物品重量总和超过V或已完成n个物品选择,就到达“死胡同”
用递归即可写出
1 | void dfs(int index, int sumW, int sumC) |
BFS
访问完所有邻接点,再往下层
一般用队列实现
1 | void bfs(int s) |
迷宫问题
1 | // 增量数组 |
- 注
inq[x][y]
的含义是判断结点是否入过队,而非结点是否已被访问。如果使用后者定义会导致重复入队,进而造成重复访问 迷宫问题考虑的重点是:检查下一次可以走到的位置以及它们是否合法
8数码难题的启发
- 将数字排列的矩阵,转换为一串整型数字,当作状态,用于剪枝。已到过该状态就无需再入队
sprintf
和sscanf
处理字符串和数字间的转换
树
一些定义与概念
- 结点、根结点、叶子结点、子树、边
- 层次:根节点为第1层,往下增;
- 深度:即层数
- 高度:从最底层叶子结点(高度为1)向上逐层累加至该结点
- 度
- 结点的度:该结点子树的棵数,叶子结点的度为0
- 树的度:树中结点的最大的度
- 祖先、子孙:自己既是自己的祖先结点,也是自己的子孙结点
二叉树
概念
- 递归定义:要么没有根节点,是一棵空树;要么由根节点、左子树、右子树组成,子树都是二叉树
(与度为2的树的区别:不能随意交换左右子树的位置) - 满二叉树:每层结点个数都达到最大
- 完全二叉树:除最后一层,其余层节点数都达到最大
定义与增删改查
1 | // 定义 |
完全二叉树的递归创建
1 | Node* create(int x) |
遍历
1 | // 先序 中-左-右 |
二叉树静态实现
1 | // 用数组下标代表指针,-1表示NULL |
注:
- 有些题按层序标了号,要求计算一些特性,此时可能无需建树(只需假想一棵树),利用下标计算:
当前结点: x,左子: 2x,右子: 2x+1,
判断超出范围:2x > n
一般的树
尽量考虑静态写法,maxn为结点数上限
1 | sreuct node |
从树的遍历看DFS与BFS
- DFS:合法的DFS都能画出树的形式,“死胡同”等价于叶子结点;“岔路口”等价于非叶子结点,DFS遍历过程即树的先序遍历过程
从树的角度引入对状态的剪枝 - BFS:即对树的层序遍历
需要再看看的题目
- codeup_611_b 子结点计算
- codeup_611_d 树重建(主要看指针方式存储树的创建)
二叉查找树 BST
也叫二叉排序树
递归定义:
- 要么是一棵空树
- 要么由根节点、左右子树构成,左子树上的结点小于根结点,右子树上的结点大于根节点
性质:
- 对二叉查找树进行中序遍历,遍历结果是有序的
编码
1 | // 查找 O(h) |
删除比较难,单独记录一下:
删除结点v的基本思路是:使v的前驱(左子树的最大结点,即左子树最右结点)或后继(右子树的最小结点,即右子树的最左结点)覆盖v,然后递归删除前驱或后继
编码
1 | node* findMax(node* root) |
注:一直删除前驱或后继会导致树退化成一条链,解决办法有:
- 交替删除前驱或后继
- 记录高度,总是优先在高度较高的一棵子树里删除结点
平衡二叉树 AVL树
使树高在每次插入后保持O(logn)级别
平衡因子
平衡因子:左子树与右子树的高度差(ps:高度从叶子开始计算,叶子为1)
为记录平衡因子,需要在树的结构中增加变量height:
1 | struct Node |
AVL树的重点是插入,需要考虑平衡的调整:
旋转
左旋:
- 使B的左子树♦成为A的右子树
- 使A成为B的左子树、更新高度
- 根节点设置为B
1
2
3
4
5
6
7
8
9
10void leftRotation(Node* &root)
{
Node* temp = root->rch;
root->rch = temp->lch; // 步骤1
temp->lch = root; // 步骤2
updateHeight(root); // 顺序别反,root此时是temp的子树
updateHeight(temp);
root = temp; // 步骤3
}右旋
- 使A的右子树成为B的左子树
- 使B成为A的右子树、更新高度
- 根节点设置为A
1
2
3
4
5
6
7
8
9
10
11// 实际上就是把左旋的lch和rch颠倒
void rightRotation(Node* &root)
{
Node* temp = root->lch;
root->lch = temp->rch; // 步骤1
temp->rch = root; // 步骤2
updateHeight(root);
updateHeight(temp);
root = temp; // 步骤3
}
插入
AVL插入即BST插入+平衡调整
平衡调整:将最靠近插入结点的失衡结点调整到正常
四种情况(左插LL、LR,右插RR、RL):
树形 | 判定条件 | 调整方法 | 示图 |
---|---|---|---|
LL | BF(root) = 2, BF(root->lch) = 1 |
对root右旋 | |
LR | BF(root) = 2, BF(root->lch) = -1 |
对root->lch左旋,再对root右旋 | |
RR | BF(root) = -2, BF(root->rch) = -1 |
对root左旋 | |
RL | BF(root) = -2, BF(root->rch) = 1 |
对root->rch右旋,再对root左旋 |
编码
1 | void insert(Node* root, int x) |
知道如何插入后,AVL树的建立与查找就和BST无异了:
1 | Node* create(int data[], int n) |
注意易错点:
search
不要想复杂了,查找树按照大小选择子树查找,如果找不到,就是查找失败,无需考虑其他树上有没有该结点- 涉及对root本身的修改要记得用指针引用
Node* &root
,这里有leftRotation
,rightRotation
和insert
insert
之后要记得updateHeight
哈夫曼树
结点的路径长度:从根结点到该结点所经过的边数
叶子的带权路径长度:叶子的权值乘以路径长度
树的带权路径长度:所有叶子结点的带权路径长度之和
哈夫曼树:树的带权路径最小的二叉树(最优二叉树)
构建过程:
- 初始n个结点,视为n棵只有1个结点的树
- 合并其中权值最小的两棵树,生成两棵子树的父结点,权值为两个根结点之和
- 重复步骤2,直到只剩下一棵树为止,这棵树即哈夫曼树,根结点的权值为最小带权路径长度
哈夫曼树的构建思想核心为:反复选择两个最小的元素,合并,直到剩下一个元素。有时无需构建树,只需通过合并,得到最终带权路径长度即可。
哈夫曼编码:
- 对任何一个叶子结点,其编号一定不会成为其他任何结点编号的前缀
- 左0右1
- 按频次作为权值,字符串编码为01串的长度即树的带权路径长度
并查集
定义
并(Union):合并两个集合;
查(Find):查找,判断两个元素是否在同一集合;
集(Set):集合
性质:
- 并查集产生的每个集合都是一棵树(因为只对不同集合进行合并,集合内不会有环)
实现:
- 用数组
father[i]
记录结点i的父节点;若i=father[i]
,说明i是根节点。一个集合只有一个根结点,其是集合的标志
编码:
1 | // 初始化 |
补充路径压缩的示意图:
并查集模型的应用:
- 输入一条边的两个点(双向边),使用
union
就能将两个点并在一个集合下,进而计数集合的个数或集合内元素个数
堆
定义
堆是一棵完全二叉树
大顶堆:树中每个结点的值都不小于孩子
小顶堆:不大于
实现方式:用数组来存储完全二叉树,这样结点就按层序存储在数组中。第一个结点存于下标1,第i号的左孩子是2i,右孩子是2i+1,父亲是i/2
1 | int heap[MAXN]; |
ps:如果不是强调自己实现堆,在可用STL的情况下,尽量用优先队列,不要造轮子
1 | #include <queue> |
向下调整
- 当前结点与其孩子比较,将其中权值大的孩子与V交换
- 继续让V与孩子比较,直到孩子的权值都比V小或没有孩子结点
1 | // O(logn) |
建堆
完全二叉树的叶子结点个数为$\lceil \frac{n}{2} \rceil$,因此在$[1, \lfloor \frac{n}{2} \rfloor]$范围内的都是非叶子结点,
n个结点的完全二叉树有性质
1)n0+n1+n2=n(其中n0表示度为0的结点)
2)n0=n2+13)n1 = 0 或 1
综上可得n0 = $\lceil \frac{n}{2} \rceil$
从$\lfloor \frac{n}{2} \rfloor$倒着枚举,对遍历到的结点$i$进行$[i, n]$范围的调整。
倒着调整是因为,每次调整一个结点后,当前子树中权值最大的结点就会处于子树的根结点位置(这正是向下调整的逻辑),轮到父节点调整时,又可以直接使用这一结果,保证了每个结点都是以其为根结点的子树的权值最大点
记住结论即可:
1 | // O(n) |
删除堆顶
思路:用最后一个结点覆盖堆顶结点(根结点),然后对根结点向下调整
1 | // O(logn) |
增添元素
思路:把要添加的元素放在数组最后,然后向上调整
向上调整:与父结点比较,如果比父节点大就交换,直到到达堆顶或父节点权值大为止
1 | // O(logn) |
堆排序
思路:取出堆顶元素,然后将堆的最后一个元素替换至堆顶,然后对堆顶向下调整
实际上为了节省空间,用原来存储heap的数组来存排序后的序列,所以用倒着遍历heap数组实现堆排序
- i从n开始遍历,直到堆只1个元素
- 访问到i,将i与堆顶交换
- 在[1, i-1]范围对堆顶进行向下调整
1 | // O(nlogn) |
总结一下
- 倒着遍历:
- 建堆:数组中已有数据,从$\lceil \frac{n}{2} \rceil$开始倒着遍历,对每个结点向下调整,建立起堆结构
- 堆排序:从结点n开始倒着遍历,和堆顶交换,对堆顶向下遍历,已访问的结点固定不再动
- 调整
- 向下调整:用于建堆、删除堆顶、堆排序。后二者是对堆顶向下调整,调整后,子树根结点就存放着最大元素
- 向上调整:用于插入时,将尾巴插入的结点调整到它的位置
图
定义:
图由顶点和边组成:G(V, E)
有向图与无向图
度:和顶点相连的边的条数;
入度:入边条数;出度:出边条数- 权值:点权、边权
图的存储
邻接矩阵:
G[i][j]=1代表结点i和j之间有边,G[i][j]=0或-1表示无边
G[i][j]存放边权,对于不存在的边可设为0、-1或一个很大的数
一般适用于顶点数目不大(不超过1000)的题目
邻接表
Adj\[i\]
存放顶点i
的所有出边组成的列表
1 | struct Node |
使用构造函数实现加边
1 | Adj[i].push_back(Node(3, 4)); // i和3之间的边,结点3的权值为4 |
图的遍历
对无向图:
- 连通:两个顶点之间相互可达
- 连通图:图G(V, E)中任意两个顶点连通
- 连通分量:非连通图中的极大连通子图
对有向图:
- 强连通:两个顶点各有一条有向路径通向另一个顶点(即可达)
- 强连通图:图G(V, E)中任意两个顶点强连通
- 强连通分量:非强连通图中的极大强连通子图
DFS
邻接表版:
1 | vector<int> adj[MAXV]; |
无向图、邻接矩阵存储,涉及边权的累计:
1 | void DFS(int u, int& totalW) |
BFS
之前介绍过了,这里只放图的代码
1 | // 邻接矩阵版 |
注意:清空inq
数组时,要对整个MAXV长度清空,否则后面来的如果访问顶点数大于前者
最短路径
Dijkstra
算法流程:
- 从未访问过的点集(V-S)中找到一个与起点距离最小的点u
- u作为中介点,对起点s 与 所有从u能到达的未访问顶点 进行relaxing(松弛)操作
1 | const int INF = 1e9; |
三种可能的第二标尺(多条最短路径时的其他衡量标准):
只需在relaxing操作中进行修改
新增边权(如花费)
初始化合数组d相同1
2
3
4
5
6
7
8
9
10
11
12
13for (int v = 0; v < n; v++)
{
if (!vis[v] && G[u][v] != INF)
{
if (d[u] + G[u][v] < d[v])
{
d[v] = d[u] + G[u][v];
c[v] = c[u] + cost[u][v];
}
else if (d[u] + G[u][v] == d[v] && c[u] + cost[u][v] < c[v]) // 多条
c[v] = c[u] + cost[u][v];
}
}新增点权(如每个点的资源)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15// w[u]记录从起点s到点u收集的最大资源数(前提为路径最短)
// 初始化w[s]=weight[s],其余w[u]=0
for (int v = 0; v < n; v++)
{
if (!vis[v] && G[u][v] != INF)
{
if (d[u] + G[u][v] < d[v])
{
d[v] = d[u] + G[u][v];
w[v] = w[u] + weight[v];
}
else if (d[u] + G[u][v] == d[v] && w[u] + weight[v] > w[v]) // 多条
w[v] = w[u] + weight[v];
}
}求最短路径条数
1
2
3
4
5
6
7
8
9
10
11
12
13for (int v = 0; v < n; v++)
{
if (!vis[v] && G[u][v] != INF)
{
if (d[u] + G[u][v] < d[v])
{
d[v] = d[u] + G[u][v];
num[v] = num[u]; // 仅一条时,遵循上个结点
}
else if (d[u] + G[u][v] == d[v])
num[v] += num[u]; // 有多条不同的最短路通往v
}
}
使用Dij+dfs简化逻辑:
使用dij记录下所有最短路径
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17vector<int> pre[MAXV];
// 在relaxing操作中
for (int v = 0; v < n; v++)
{
if (!vis[v] && G[u][v] != INF)
{
if (d[u] + G[u][v] < d[v])
{
d[v] = d[u] + G[u][v];
pre[v].clear(); // 因为最短路已换,前驱需清空
pre[v].push_back(u); // 添加新的前驱
}
else if (d[u] + G[u][v] == d[v])
pre[v].push_back(u); // 记录多个前驱
}
}遍历所有最短路径,找出第二标尺最优的路径
遍历过程相当于对终点为根结点,起点为叶子结点(可重复)的递归树的搜索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
26vector<int> pre[MAXV];
vector<int> path, tempPath;
int optValue;
void dfs(int v, int curValue)
{
if (v == st) // 到达起点,形成一条倒着的完整最短路
{
if (curValue 优于 optValue) // 更新
{
optValue = curValue;
path = tempPath;
path.push_back(v); // 别忘了添加起点
}
return;
}
tempPath.push_back(v); // 加入临时的最短路径
for (int i = 0; i < pre[v].size(); i++)
{
int u = pre[v][i];
dfs(u, curValue + value[u][v]); // 递归访问前驱结点,累计第二标尺的权值
}
tempPath.pop_back(); // 删除结点v,因为要记录其他最短路
}
注意:
- INF要用
const int INF = 1e9
定义,不要用#define
,后者值为0,原因不明 - 所有的min都要记得初始化
Bellman-Ford与SPFA
Bellman-Ford:
邻接表实现为$O(VE)$,思路如下:
进行V-1轮操作,每轮对所有边松弛
最后一轮再对所有边松弛,如果仍能松弛,说明有原点可达的负环,返回false;否则返回true;
1 | d[s] = 0; // 起点为0 |
SPFA:
邻接表实现为$O(kE)$,从B-F算法优化而来,思路如下:
只有当某个顶点d[u]的值改变时,从它出发的邻接点v的d[v]才有可能改变
因此建立一个队列,每次松弛后,如果顶点不在队中,将其入队。若入队次数超过V-1次,则存在负环
1 | vector<Node> adj[MAXV]; |
可以使用优先队列priority_queue
进行优化
Floyd
全源最短路径算法,$O(n^3)$,n应限制在200以内
基本思想:枚举中介点k,使用k任意两个顶点进行松弛操作
1 | int dis[MAXV][MAXV]; |
最小生成树MST
MST(Minimum Spanning Tree)
在给定无向图G中求一棵树T,T包含G中所有顶点,且边都来自G,满足整棵树边权之和最小
- 作为树,MST有:边数=顶点数-1
- MST不唯一,但边权之和一定为1
- 一般给定一个根结点求最小生成树
Prim
复杂度$O(V^2)$,优先队列优化能达到$O(VlogV)$
基本思想:
集合S存放已访问结点,每次从V-S中选择与S距离最小的点u,将该距离最小的边加入MST,并将u加入S
令顶点u为中介,优化 所有u的邻接点 与 集合S 之间的最短距离
循环n次后,即得到MST
(Prim与Dij的思想几乎相同,区别只有:Prim松弛的是邻接点到集合S的距离,Dij松弛的是邻接点到起点之间的距离;在代码中体现为数组d[i]的意义)
1 | int G[MAXV][MAXV]; |
Kruskal
复杂度$O(ElogE)$,开销来自于边排序
基本思想:边贪心策略
每次选择图中最小边权的边,如果加入不成环(边两端顶点在不同连通块中),就把边加入MST中
实现:使用并查集判断是否成环
1 | // 边结构 |
总结
- prim和dij思想相近,都是不断优化
d[]
,复杂度与顶点数有关,适用于稠密图(边多点少) - kruskal使用边贪心策略,并查集判断是否成环,复杂度与边数有关,适用于稀疏图(边少点多)
拓扑排序
有向无环图(Directed Acyclic Graph, DAG):有向、无环(任意点都无法通过边回到自身)
拓扑排序:将DAG图的所有顶点排成一个序列,如果存在边u->v,则序列中u一定在v之前
算法步骤:
- 定义队列Q,将所有入度为0的结点入队
- 取队首结点输出,删去所有从它出发的边,并令边到达的结点入度-1
- 重复直到队空。如果入过队的结点数目为N,则排序成功;否则图中有环
1 | // 邻接表实现 |
关键路径
AOV(Activity On Vertex)网:顶点活动网,用顶点表示活动,边集表示活动间优先关系的有向图
AOE(Activity On Edge)网:边活动网,带权边集表示活动,顶点表示事件的有向图。边权表示活动所需时间
源点:入度为0的点,表示起始事件;
汇点:出度为0的点,表示终止事件
关键路径:AOE网中的最长路径,关键路径上的活动称为关键活动,关键路径的长度等于工程最短完成时间
- 最长?从路径长度上看,选择不能拖延的活动,组成的就是最长的路径,比较对象是选择其他路径的方案
- 最短?从时间角度看,不能拖延的活动按照时间完成就是最短的时间,比较对象是活动中有拖延的方案
AOE网实际是DAG图
求解关键路径的问题即 求解DAG图中最长路径
四个关键的数组:
数据 | 定义 | 计算 | 图示 |
---|---|---|---|
e[r] |
活动$a_r$的最早开始时间 | e[r] = ve[i] | |
l[r] |
活动$a_r$的最迟开始时间 | l[r] = vl[j] - length[r] | (活动r最迟开始时间+活动时间=事件j最迟发生时间) |
ve[i] |
事件$i$的最早发生时间 | ve[j] = max{ve[ip] + length[rp]} | (所有前驱事件发生、活动完成之后,Vj才能被激活,最后完成的是max) |
vl[i] |
事件$i$的最迟发生时间 | vl[i] = min{vl[jk] - length[rk]} | (图中用了逆拓扑展示) (事件i的最迟发生,加上活动时间,不能影响到任何后继事件,最先影响到的是min) |
编码:
1 | // 拓扑排序,并计算ve |
动态规划 DP
- 状态:记录当前信息;状态转移方程:根据之前的状态计算当前状态值
如何设计二者是DP的核心 - 最优子结构:问题最优解可以由子问题的最优解构造出来
- 状态的无后效性:当前状态一旦确定,不再改变。只有当前状态能影响下一状态,历史信息只能通过已有状态影响决策,而不直接参与决策
分治与DP
- 同:都分解为子问题
- 异:分治的子问题不重叠,DP的重叠
贪心与DP
- 同:都要求最优子结构
- 异:贪心壮士断腕,直接选择一个子问题往下求解;DP总会考虑所有子问题,选择继承能得到最优解的一个
最大连续子序列
给定数字序列$A_1, …, A_n$,求$i, j$使$A_1 + … + A_j$最大,输出这个和
暴力:$O(n^2)$,DP:$O(n)$
状态:dp[i]
表示以A[i]为结尾的连续序列最大和
状态转移方程:dp[i] = max(A[i], dp[i-1] + A[i])
- 一个元素:A[i]
- 多个元素:前面最大和dp[i-1]加上当前A[i]
1 | dp[0] = A[0]; |
最长不下降子序列 LIS
LIS(Longest Increasing Sequence)
给定一个数字序列,子u最长的非下降子序列长度(可以不连续)
暴力:$O(2^n)$, DP:$O(n^2)$
状态:dp[i]
表示以A[i]结尾的LIS长度
状态转移方程:dp[i] = max{1, dp[j] + 1}
(j=1, 2,…, i-1 && A[j] <= A[i])
- A[i]跟在A[j]后面,LIS长度+1
- A[i]自己成为一条新的LIS,长度为1
1 | for (int i = 0; i < n; i++) |
最长公共子序列 LCS
给定两个字符串A和B,求字符串s,使s使A和B的最长公共部分(可以不连续)
复杂度:$O(nm)$
状态:dp[i][j]
表示A的i
号位和B的j
号位之前的LCS长度
状态转移方程:
- 如果A[i]==B[i],LCS长度为增加1位
- 否则,继承
dp[i-1][j]
和dp[i][j-1]
中较大的一个
1 | char A[MAXN], B[MAXN]; |
最长回文串
复杂度:$O(n^2)$
状态:dp[i][j]
表示S[i]到S[j]是否是回文串,是为1,不是为2
状态转移方程:
- 若
S[i]==S[j]
,则只要S[i+1]
至S[j-1]
是回文串,S[i]
至S[j]
就是,因此继承dp[i+1][j-1]
- 若
S[i]!=S[j]
,肯定不是回文串,dp[i][j]=0
采用区间dp实现,即两层循环,外层枚举子串长度L,内层枚举初始位置(左端点)i,右端点=i+L-1
1 | int ans = 0; // 最大长度 |
DAG最长路
也即求关键路径,两个问题:
- 整个DAG中的最长路径
- 固定终点,求DAG的最长路径
整个DAG中的最长路径
状态:dp[i]
表示从i号结点出发能获得的最长路径长度
状态转换方程:dp[i] = max{dp[j] + length[i->j]} (i,j)∈E
- 因为是用后继结点
j
更新结点i
,使用递归,代替逆拓扑序列求解
1 | int DP(int i) |
上述代码还自动实现了取字典序最小的路径(因为是按结点从小到大遍历)
固定终点的DAG最长路径
状态:dp[i]
表示从i
出发到终点T的最长路径长度
状态转移方程:dp[i] = max{dp[j] + length[i->j]} (i,j)∈E
- 与前一个问题的方程相同,区别在对边界的定义:初始化所有dp[i]=-INF来表达不可达,dp[T]=0
1 | int DP(int i) |
path选择以及最小字典序方案和上一个问题相同
总结:
- 不规定终点的DAG关键路径,dp[i]=0有两层意思:
1)如果是出度为0的点,从它出发的关键路径长度为0
2)出度不为0的点,表示未更新dp[i],因此进入邻接点的遍历 - 规定终点的关键路径问题,不能初始化所有dp[i]=0,因为并非所有点都可达T,所以初始化未-INF,并利用vis数组记录dp[i]是否更新
不关心起点,因为dp[i]已经具有这层意思。
对于规定起点S的问题,返回DP(S)即可,
对于未规定起点的问题,取dp[i]最大的结果返回用DAG的思路解决矩形嵌套问题:每个矩形看成一个顶点,嵌套关系视为有向边,边权为1,于是就能转换为DAG最长路问题
背包问题
多阶段动态规划问题::arrow_right:问题可以描述成若干有序阶段,每个阶段(多个状态)只与上个阶段的状态有关
01背包就是多阶段DP问题
01背包
DP:$O(nV)$
n件物品,容量V的背包,每件物品重w[i],价值c[i],问如何选取物品使背包内物品总价值最大(每个物品1件)
- 状态与最优子结构
dp[i][v]
表示选择前i项物品装入容量v的背包的最大价值- 不放第i件物品:
dp[i][v]=dp[i-1][v]
- 放第i件物品:
dp[i][v] = dp[i-1][v-w[i]]+c[i]
- 不放第i件物品:
状态转移方程
自底向上
边界dp[0][v]=0
(0件物品放入任何背包容量的价值都为0)
枚举i<-1 to n
,v<-w[i] to V
编码:
1 | for (int i = 1; i <= n; i++) |
优化空间复杂度:
上一阶段的状态,用于计算当前阶段的状态后,就不再使用,因此可以用滚动数组,化为一阶数组表示当前状态
注意,自底向上的遍历必须逆序,因为如果正序遍历,dp[v]
使用的dp[v-w[i]]
是i-1
阶段的状态,会造成错误。逆序保证了计算第i
阶段的状态时使用的都是i-1
阶段的状态
1 | for (int i = 1; i <= n; i++) |
总结:
- 如果能划分阶段,可以尝试将阶段作为状态,将数组降一维
- 如果设计的状态不满足无后效性,可以尝试将状态升维(多个阶段,每个阶段多个状态)来表达相应信息
完全背包问题
与01背包的区别在于,每个物品有无穷件(可选择多次)
状态与最优子结构
dp[i][v]
表示选择前i项物品装入容量v的背包的最大价值- 不放第i件物品:
dp[i][v]=dp[i-1][v]
- 放第i件物品:
dp[i][v] = dp[i][v-w[i]]+c[i]
注意此处转移到了第i
阶段而非i-1
阶段,因为放了第i件物品后还可以继续放
- 不放第i件物品:
状态转移方程
|
优化版:- 自底向上
对于优化版:边界:初始化所有dp[v]为0(即表示dp[0][v]=0
)
正向枚举v<-w[i] to V
,因为求解dp[i][v]
总是需要它左边的dp[i][v-w[i]]
,而上方的dp[i-1][v]
在计算完后才会覆盖
1 | for (int i = 1; i <= n; i++) |
总结
- 当题目与序列或字符串
A
有关时,可以考虑状态设计:- 令
dp[i]
表示以A[i]
结尾(或开头)的xxx - 令
dp[i]
表示以A[i]
至A[j]
区间的xxx
- 令
当题目包含某种”方向“的意思时,状态需要几个维度来表示,对每一维用以下描述
- 恰好为
i
- 前
i
令
dp
数组表示恰好为i
(或前i
)的xxx- 恰好为
大多数情况都可以把DP问题看作一个有向无环图(DAG),结点是状态,边是状态转移方向,辅助理解
KMP算法
给出两个字符串text
和pattern
,判断pattern
是否是text
的子串
暴力法枚举起始点$O(nm)$,使用KMP能达到$O(n+m)$
求解next数组
next[i]
定义:
使子串s[0...i]
的前缀s[0...k]
和后缀s[i-k...i]
相等的最大的k(前后缀长度为k+1),也即最长相等前后缀的前缀最后一位的下标
上框下划线画出匹配的前后缀,下框的第一行为前缀,第二行为后缀递推求解next[i]:
令j=next[i-1]
若
s[i] == s[j+1]
,最长相等前后缀可以扩展,长度+1,即next[i]=j+1
若
s[i] != s[j+1]
,前后缀匹配失败,相等前后缀无法达到那么长,因此需要缩短一点。需要找出一个j'
,使得- 1)
s[i] == s[j'+1]
成立 - 2)
s[0...j']
(下图3的~)是s[i-j-1...i-1]
(下图3和~在一个框的上方的子串)的后缀
因为s[i-j-1..i-1] == s[0..j]
(由j=next[i-1]
的意义决定,j
是s[0..i-1]
的最长前后缀匹配的前缀最后一位下标),所以只需满足s[0..j']
是s[0..j]
的后缀
从下面图片来理解就是:j=next[4]=2,需要找一个串s[0..j']
,使得它是s[2..4]="aba"
的后缀(这样才能匹配成功),因为s[2..4] == s[0..2]
(因为next[4]=2
),所以也即s[0..j']
需满足是s[0..2]
后缀 - 3)
s[0...j']
是s[0...j]
的前缀(自动满足,因为是在0..j
里找j'
) - 4)
j'
尽可能大
上面的要求2)3)4),正好就是
next[j]
的定义:s[0..j]
最长相等前后缀的前缀下标j'
,因此只需让j'=next[j]
,判断s[i]==s[j'+1]
是否成立,不成立继续回退,直到j'=-1
- 1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18// 求解长度为len的字符串s的next数组
void getNext(char s[], int len)
{
int j = -1;
next[0] = -1;
// 1. 让i在1~len-1范围内遍历
for (int i = 1; i < len; i++)
{
// 2.不断令j=next[j],直到j回退到-1,或满足s[i]==s[i+1]
while (j != -1 && s[i] != s[j+1])
j = next[j];
// 3. 若s[i]==s[j+1],则next[i]=j+1,否则next[i]=j
if (s[i] == s[j+1])
j++;
next[i] = j;
}
}
KMP算法
令i指向text的欲比较位,j指向pattern已被比较的最后一位
若
text[i] == pattern[j+1]
,说明匹配成功,i、j自增,继续比较若
text[i] != pattern[j+1]
,匹配失败,需要考虑j
回退到哪,位置要满足以下条件:- 1)
text[i] == pattern[j' + 1]
成立 - 2)
pattern[0..j']
仍然与text
相应位置处于匹配状态,即pattern[0..j']
是text[i-1-j..i-1]
的后缀,由于之前匹配的结果有text[i-1-j..i-1] == pattern[0..j]
,因此只需满足pattern[0..j']
是pattern[0..j]
的后缀 - 3)
pattern[0..j']
是pattern[0..j]
的前缀(自动满足,因为是回退) - 4)
j'
尽可能大
条件2)3)4)正是数组
next[j]
的定义,因此只需不断令j'=next[j]
,直到满足条件1)或j'=-1
为止。(逻辑与next
数组的求解几乎一致)从这个角度来看,
next
数组的含义就是当j+1
位失配时,j
应该回到的位置- 1)
1 | bool KMP(char text[], char pattern[]) |
统计文本串text
中pattern
的出现次数(不是子串个数,如text=”ababab”中,pattern=”abab”出现了2次)
思路:
完全匹配一次pattern后,j
需回退一定距离,使得不漏解且效率最高。由于next[j]
的定义是最长前后缀匹配的前缀最后一位,完全匹配时text[i-j..i] == pattern[0..j], j=m-1
,所以令j=next[j]
,在next[j]
之前的位置都已完成匹配,省去了许多无意义的比较
1 | int KMP(char text[], char pattern[]) |
总结
- 计算
next
数组实际上是pattern
自我匹配的过程 - KMP的关键是
j
回退的位置j=next[j]
,实质就是回到一个已知匹配的长度,从而省去从头开始比较的开销。容易模糊的地方是如何证明这个回去的位置是有效而且最优的,可以多看看上面的解释,思路就是递推求解代替逐项匹配 - $O(n+m)$的开销:i和j的变化是$O(n)$的,计算next数组的开销是$O(m)$
其他
中缀表达式计算
1)中缀转换为逆波兰(后缀表达式):
(使用队列存储)
如果是数字,直接入队
如果是运算符op:如果运算符栈空,压入运算符栈,否则与栈顶比较优先级(用
map
记录优先级):
只有在遇到” ) “的情况下我们才弹出” ( “,其他情况我们都不会弹出” ( “1
2
3
4
5
6while(栈非空 && 栈顶 != '(' && op小于或等于栈顶)
{
// 栈顶入队
// 弹栈
}
// 表达式中的op压栈如果遇到一个右括号,则将栈元素弹出(入队),将弹出的操作符输出直到遇到左括号为止。注意,左括号只弹出并不输出。
表达式扫描结束后,若运算符栈非空,从栈顶依次入队
2)逆波兰表达式运算:
(由队首依次出队)
- 如果是数字,压栈
- 如果是运算符,取栈顶两个数字,运算,将结果压栈
- 队列扫描结束后,栈顶数字即最终结果
3)中缀表达式直接计算:
(使用数字栈和运算符栈)
- 如果是数字,压栈
- 如果是运算符,同1),不过弹栈时,取数字栈顶两个元素运算后压栈,而非入队
- 同1),弹栈时运算而非入队
C语言变长参数函数写法
使用头文件<stdarg.h>
实现,下面为用到的四个宏:
va_list
:声明指向变长参数的指针apva_start(ap, arg)
:用于初始化变长参数指针ap的位置,arg为最后一个固定参数va_arg(ap, type)
:ap传入变长参数指针,type为参数类型。函数返回ap当前指向的类型为type的参数,并将ap指向参数列表的下一个参数va_end(ap)
:置ap为空指针
变长参数函数的参数中,先填写若干个固定参数,然后在最后一个固定参数的逗号后方添加3个点,表示变长参数
1 | #include <stdarg.h> |
Debug思路
- 注意考虑边界情况,如0、有质数的题考虑1
- 没有编码错误的情况下,找逻辑错误(代码是否和题目逻辑一致),着重检查循环里的数组下标
i,j,k
- 注意浮点数精度:
float
能保证6位,double
能保证到15位。有时float错了可能double能过 - 可能没有考虑多组输入
- 格式问题,有些题目可能输出点个数为0时需输出空行
- 无法调试可能的原因:
- 内存爆了,减小MAXN
- 添加查看了STL容器
- 声明
const char []
型数据时,一定要检查后面有没有添加'\0'
,否则可能会出现本地没问题但交上去WA的情况。比如:const char ONE[2] = {'1', '\0'};
能过,但const char ONE[1] = {'1'};
在Linux环境下会出现怪数,但windows下结果正常 - 同阶时间复杂度的算法,实际表现可能有很大差异。比如
O(nlogn)
和O(2nlog(2n))
。当RE时,可能其他同阶算法能过 - sort的cmp函数中如果使用
return a >= b
可能会有段错误(原因不明),改用return a > b
,不影响语义 - 多组输入,记得对每个用到的数据结构进行初始化
杂
字符转数字
1
2
3num = 0;
for (int i = 0; i < len; i++)
num = num * 10 + str[i] - '0';注意先找规律,n很大的不要一上来就递归DP,很容易超时。有时可能往简单想能做出来
int的范围[-2147483648, 2147483647],10个0就无法支持了,一般取INF=1e9
ceil()
:向上取整;floor()
:向下取整;round()
:四舍五入;三者都返回double
值万能库:
include <bits/stdc++.h>
long
和int
都是4字节,long long
才是8字节21!就超过了
long long
的范围cin
和cout
远比scanf
和printf
花费时间多,能不用尽量不用运行时限为1s,算法复杂度不能超过百万级,也即不能超过一千万
比如$O(n^2)$,n应<=3000cin
的多组输入:while(cin >> x)
,cin
在读入EOF时返回0浮点数比较,在经过大量计算后应考虑误差
1
2
3
4#include <math.h>
const double eps = 1e-8
#define Equ(a, b) (fabs((a)-(b))<(eps))大于、小于、大于等于,以及sqrt、asin、cos等也需要考虑
C的空指针为
NULL
,c++11引入nullptr
scanf("%c")
会可以读入空格,需要考虑下标的计算(i、j的加加减减之类的)从实体加减考虑,不要考虑加减位置
C语言中整型最大值和最小值的宏
1
2
3
4#include <limits.h>
printf("%d ", INT_MAX); //2147483647
printf("%d ", INT_MIN); //-2147483648命令行输入
1
2
3
4
5
6int main( int argc, char *argv[ ])
{
int i;
for(i=1; i<argc; i++)
printf(“%s%c”, argv[i], (i< argc-1)? ' ': '\n');
}
ettercap+driftnet抓取同一无线网段中设备阅览的图片
环境
OS:Ubuntu 16.04LTS
软件:ettercap, driftnet
1 | $ sudo apt-get install ettercap-graphical |
ps:使用虚拟机vmware+kali体验更好
抓包
$sudo ettercap -G
打开ettercap图形化界面- Sniff->Unified sniffing->wlp2s0(无线网卡)
- Host->scan for hosts,扫描连接在同一网段上的设备
- 设备IP地址Add to Target 1;路由器IP(通常是最后一位为1)Add to Target 2(注意不要反了,否则可能导致宽带认证错误,上不了网,只能打电话找运营商清除一下之前的缓存)
- Mitm(中间人攻击)->Arp poisoning->Sniff remote connections->ok,至此,设备与路由器的通信会经过本主机,因此可以截获报文
- Start->Start sniffing开始监听,View->View Connections查看截获的报文
图片监视
监听无线网卡:1
$ sudo driftnet -i wlp2s0
会弹出一个图片预览框,截取设备访问的图片
driftnet其他参数:
- -i 监听网卡
- -b 声音提醒
- -a 保存图片(这样的话图片不会显示在窗口)
- -d 图片保存目录,例:driftnet -i wlan0 -b -a -d /pic
总结
经过本人的实验,可以抓取到微信朋友圈的视频帧、图片(很少),以及公众号中浏览的一些图片,原因可能是大部分图片还是经过加密传输的。但即使如此,还是见识到了连接在同一wifi上造成的信息泄露。
参考
LeetCode 820.单词的压缩编码
题目描述
约瑟夫环问题
标准做法 递归 $O(n)$
由于问题是求0到n-1里最后剩下的数字,所以问题也可以转换为安全数字的序号。对问题建模,令f(n, m)
为问题的答案,即最终安全位置的序号。最开始,我们要删除的是第m%n
个元素,之后,序列长度变为n-1,然后从第m%n
位开始往后数。剩下的n-1长度的序列从第m%n
位开始,只要往后数f(n-1, m)
位就能达到安全位置,所以(m%n+f(n-1,m))%n
即为所求。(m%n+f(n-1,m))%n = (m+f(n-1, m)%n
1 | class Solution { |
标准做法 迭代/DP $O(n)$
由上面的递归式,就可以得到DP所需的状态转移方程
只有一个状态转换量,所以可以用简单变量替代
在i=1
时,也就是长度为1的序列,安全位置就是0,即f1 = 0
1
2
3
4
5
6
7
8
9class Solution {
public:
int lastRemaining(int n, int m) {
int f = 0;
for (int i = 2; i != n + 1; ++i)
f = (m + f) % i;
return f;
}
};
总结
- 模拟约瑟夫环的删除过程会超时
- 这种类似归纳法解决问题的逻辑很巧妙,希望能掌握下来