学习笔记（一）

2017.03.17

（前言：由于是第一节讲座，所以讲的都是比较基础的东西）

算法复杂度

时间复杂度

时间复杂度是指执行算法所需要的计算工作量；（算法的复杂性体现在运行该算法时的计算机所需资源的多少上，计算机资源最重要的是时间和空间（即寄存器）资源，因此复杂度分为时间和空间复杂度）。

例子：如 for (i=1;i<=n;i++) --> O(n);

再加一层for循环，则O(n^2);

时间复杂度

空间复杂度是指执行这个算法所需要的内存空间。

例子：如 int a[n]; --> O(n);

冗余

冗余有两层含义，第一层含义是指多余的不需要的部分，第二层含义是指人为增加地重复部分。

例：给定一串序列 X1，X2，X3……Xn，求连续子序列和的最大值。

法一：暴力枚举解法

时间复杂度：O(n^3)

改进：sum[i][j]存储Xi-Xj的子序列和，则sum[i][j]=sum[i][j-1]+Xj;

时间复杂度：O(n^2)

再改进：若sum[i][j]<0，则break，因为后面不可能会出现最大值。

证：sum[i][j]<0,设sum[i][j+n]=max，则sum[j+1][j+n]=sum[i][j+n]-sum[i][j]>max，矛盾；

再再改进：若sum[i][j]<0,则i=j+1继续枚举；

法二：前缀和

算出每个数的前缀和C，则题目可变成求 C[R]-C[L] 的最大值，则给定任意R，求1-R的C最小值min，给定R+1的时候，可对比min与C[R+1]的大小即可，时间复杂度：O(n)

思维题：给定 n 只蚂蚁的起始位置，速度为 1 ，在长为 L的水平杆子上爬行，两只蚂蚁相遇时掉头，问所有蚂蚁都掉下杆子的时间

解："两只蚂蚁相遇时掉头" 这句话是唬人的，将两只蚂蚁灵魂互换就可以发现，其实可以当做没掉头。

贪心

在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的是在某种意义上的局部最优解。

例：1元，5元，10元的硬币，问求需要购买X元的物品最少需要多少个硬币？

则对10元贪心。

例：第I件工作开始的时间为Si，结束时间为Ti，求给定时间最多能做多少工作？

则对结束时间Ti贪心。

二分

二分查找的基本思想是将n个元素分成大致相等的两部分，取a[n/2]与x做比较，如果x=a[n/2],则找到x,算法中止；如果x<a[n/2],则只要在数组a的左半部分继续搜索x,如果x>a[n/2],则只要在数组a的右半部搜索x.

例：8 个硬币，1 个是假的，偏轻，有天平 x 1，哪个硬币是假的？

解：解法很简单了，直接四个四个称，再从轻的那一堆分半称，以此类推。

例：求a+b个数，a个2的倍数，b个3的倍数，各个数字互不重复，问最大数的最小值是多少？

好吧，等学长讲完了我才恍然大悟题目的意思，然后，就没然后了。

时间复杂度：O(log2n)

分治

分治算法的基本思想是将一个规模为N的问题分解为K个规模较小的子问题，这些子问题相互独立且与原问题性质相同。求出子问题的解，就可得到原问题的解。即一种分目标完成程序算法，简单问题可用二分法完成。

如需要处理[1,8]个数据，则可以先处理[1,4],[5,8]-->[1,2][3,4]，[5,6][7,8]

归并算法与逆序对

（例子忘了记，从百度上截取了一段）

如　设有数列{6，202，100，301，38，8，1}

初始状态：6,202,100,301,38,8，1

第一次归并后：{6,202},{100,301},{8,38},{1}，比较次数：3；

第二次归并后：{6,100,202,301}，{1,8,38}，比较次数：4；

第三次归并后：{1,6,8,38,100,202,301},比较次数：4；

时间复杂度：O(nlogn) 空间复杂度：O(n)

逆序对：在归并的过程中计算每个小区间的逆序对数，进而计算出大区间的逆序对数

倍增（ST算法解RMQ）

RMQ:Range Minimum/Maximum Query 即区间最值查询，是指这样一个问题：对于长度为n的数列A，回答若干询问RMQ（A,i,j）(i,j<=n)，返回数列A中下标在i，j之间的最小/大值。

ST:SparseTable 在O(nlogn)时间内进行预处理，然后在O(1)时间内回答每个查询,首先进行预处理，然后查询

预处理：先算出一个数的最小值，然后算两个数，然后算四个数，然后算八个数。其中四个数可以通过两个数的最小值互相比较得出，以此类推。

动规方程：F[i, j]=max（F[i，j-1], F[i + 2^(j-1)，j-1]）

查询：设有n个数，则找出2^i < n < 2^i + 1, 算前面2^i 个数的最小值，算后面2^i个数的最小值，二者相比即可得到

如：给数列{2,1,0,4,7,-1,5}

求2^0个数:2 1 0 4 7 -1 5

求2^1个数:1 0 0 4 -1 -1 5

求2^2个数: [1,2]的2^1 最小值和[3,4]的2^1 最小值相比即可得到 [1,4] 的最小值 以此类推

求[1,7]的最小值可从预处理中得到前四个数最小值，以及后四个数最小值，二者相比即可

贴几个写笔记过程中的参考：

动态规划

下下节讲座的内容

先贴上参考博客：

后记：收获很大的一节讲座，感觉这是我一直渴望的学习，高中参加竞赛培训时一直很遗憾没能好好学习这些算法思想，而现在我大概找到了自己想要努力的方向。听讲座时讲到RMQ问题完全是一脸懵逼，结束后一群人围在讲台让学长重新讲了遍，还偶遇了师姐，这才是该有的学习的态度啊。感谢学长的精彩授课~笔记没有用很规范的语言写，通俗易懂就好。

笔记（二）

2017.03.24

暴力

暴力的工具——搜索

DFS（Depth-First-Search）深度优先搜索

基本思路（递归）：DFS它从某个状态开始，不断地向下一个状态转移,直到无法转移,然后才退回到前一步的状态，继续转移其他状态，如此不断重复，直到找到最终的解。

简单点说,bfs的搜索方式就是一次性搜索到底为止,然后回头一步,再继续按其他路搜索到底…重复这个过程

BFS（Breadth First Search）广度优先搜索

基本思路（队列）：宽度优先搜索总是先搜索距离离初始状态最近的状态,bfs与dfs不同之处在于搜索顺序,它是按照:

开始状态 - > 只需一次转移就可以达到的状态->只需两次转移就可以达到的状态->…..这样的顺序进行搜索.对于同一个状态,bfs只经过一次

暴力的技巧

直接枚举

思想：for循环+判断，把求解性问题转变为判断性问题

例：求abcde/fghij=n，a ~ j 是0 ~ 9的排列

解：可写出10个for循环语句判断是否为解，复杂度为O（10^10)

优化：n*fghij=abcde，枚举前六个字母，复杂度为10^6

递归

……不知道该记什么

递归之记忆化搜索

暴力的过程中可能会出现子问题重复计算,且无后效性。

针对这个问题我们依然是递归的，然后把结果保存在二维数组d中,初始化d为-1，如果在递归过程中发现某个子问题的结果已经计算过了。d[i][j]>=0.直接return d[i][j];

如 滑雪问题

回溯

dfs的方法，从根结点出发。当探索到某一结点时，要先判断该结点是否包含问题的解，如果包含，就从该结点出发继续探索下去，如果该结点不包含问题的解，则逐层向其祖先结点回溯。(dfs+剪枝).

例：在一个8X8的棋盘上放8个皇后，使得这8个皇后无法互相攻击(任意2个皇后不能处于同一行，同一列或是对角线上)，输出所有可能的摆放情况。

参考解法：

STL初步（C++标准模板库）

队列

include//头文件

queueque;//定义变量

que.push(x);//元素x入队

que.front();//查询队首元素

que.pop();//队首元素出队

que.size();//元素个数

que.empty();//判断是否为空

栈

include//头文件

stacksta;//定义变量

sta.push(x);//x元素入栈

sta.top();//查询队首元素

sta.pop();//出队

sta.size();//元素个数

sta.empty();//判断是否为空

简单粗暴直接上链接：

二分查找

时间复杂度:O(logn)

前提:有序

1.lower_bound();

返回值为大于等于key的最小的值

2.upper_bound();

返回值为大于key的最小的值

应用：upper_bound - lower_boud 可得到key的重复数

vector

头文件

include

定义变量

vectorv;

插入

v.push_back(13);

删除第i个元素

v.erase(v.begin()+i);

清空

v.clear();

遍历元素

(1)//迭代器

vector
    
     ::iterator it;for(it = v.begin();it!=v.end();++it)//支持it +=1  cout << *it << ' ';
    

(2)//.size()

for(int i = 0; i < v.size(); ++i)  cout << v[i] << endl;

查找

int k = lower_bound(v.begin(),v.end(),13) - v.begin();if(v[k] == 13) cout << “Find” << 13 << endl;else  cout << "Not find " << 13 << endl;

排序

vector
    
     v;sort(v.begin(),v.end());//默认从小到大排序
    

set

复杂度:log(n)

头文件

include

定义变量

setS；

插入

S.insert(13);

删除

S.erase(13);

清空

S.clear();

遍历元素

set
    
     ::iterator it1;// 迭代器for (it1 = S1.begin(); it1 != S1.end(); ++it1)     cout << *it1 << " ";
    

查找

it = S1.find(13);if (it1 != S1.end())   cout << "Find " << 13 << endl;else cout << "Not find " << 13 << endl;

map

头文件

include

定义变量

map<string,int>mp;

插入

mp[“a”] = 1;

mp.insert(map<string, int> :: value_type("b", 2));

复杂度：log(n)

C++11新特性介绍

……不知道讲了什么但记得一个很有用的万能头文件：#include<bits/stdc++11.h>

好，就这样吧，没有后记。因为这是一节我一脸懵逼的讲座，有空要翻出c++ primer了。