Algorithm Design 学习记录

待补充……

1-1 General Problem Solving Techniques

1、位运算

1
2
3
i = (i - 1) & s; //枚举子集
i &= (i - 1); //去掉最低位
i & (-i); //取最低位

2、scanf类正则表达式

1
2
3
"%[a-z]" //表示匹配a到z中任意字符
"%[abc]" //匹配abc中一员
"%[^a]" //匹配非a的任意字符

3、next_permutation函数

函数返回值为bool类型,当排序后的序列为升序时,返回false;其他时候,返回true。可以通过如下方式枚举全排列。

1
2
3
4
sort(a.begin(), a.end());
do {
func();
} while (next_permutation(a.begin(), a.end()));

4、set.rbegin()反向迭代器

set.rbegin()是反向迭代器(reverse_iterator),不能用于set.erase()。需要加*取值删除或只是用set.base()获取对应的正向迭代器。

1
2
s.erase(*s.rbegin()); //取值后删除
s.erase((++rit).base()); //转化为正向迭代器后删除

1-2 Designing Efficient Algorithms

1-3 Dynamic Programming

支付宝扫码领红包