第5章 第7节 高级算法

推荐给朋友

● 说一下小顶堆的调整过程

参考回答:

堆排序的步骤分为三步:

1)建堆;2)交换数据;3)向下调整。

假设我们现在要对数组arr[]={8,5,0,3,7,1,2}进行排序(降序):

首先要先建小堆:

堆建好了下来就要开始排序了:

现在这个数组就已经是有序的了。

● 算法题:2sum,3sum

参考回答:

2sum:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int,vector<int>> mark;
for(int i=0;i<nums.size();i++)
mark[nums[i]].push_back(i);
for(int i = 0;i<nums.size();i++){
if(target-nums[i] == nums[i]){
if(mark[nums[i]].size() > 1){
vector<int> tmp{i,mark[nums[i]][1]};
return tmp;
}
}else{
if(mark.find(target-nums[i]) != mark.end()){
vector<int> tmp{i,mark[target-nums[i]][0]};
return tmp;
}
}
}
}
3sum:
void two_sum(vector<int>& nums,int i,int target,vector<vector<int>> &result){
int j = nums.size()-1;
int b = i-1;
while(i<j){
if(nums[i]+nums[j] == target){
result.push_back(vector<int>{nums[b],nums[i],nums[j]});
i++;
j--;
while(i<j && nums[i] == nums[i-1]) i++;
while(i<j && nums[j+1] == nums[j]) j--;
}else{
if(nums[i]+nums[j] < target)
i++;
else
j--;
}
}
return;
}
vector<vector<int>> threeSum(vector<int>& nums) {
set<vector<int>> result;
vector<vector<int>> result2;
sort(nums.begin(),nums.end());
for(int i=0;i<nums.size();i++)
if(i>0&&nums[i-1]== nums[i])
continue;
else
two_sum(nums,i+1,-nums[i],result2);
return result2;
}


● 手撕代码:以概率p生成1、概率1-p生成0的rand函数,得到0-1等概率的rand函数,计算新的rand函数中:调用一次,while循环的期望次数

参考回答:

function g(x)

{

int v = f(x) + f(x)>0?0:1;

if(v==0)

{

return 0;  //1.f(x),f'(x)同时为0

}

else if(v==2)

{

return 1;  //2.f(x),f'(x)同时为1

}

else

{

g(x);  //3.f(x),f'(x)一个为0一个为1,重新生成随机数

}

}

新的rand函数中:调用一次,while循环的期望次数是2。

● Kruskal算法的基本过程

参考回答:

Kruskal算法是以边为主导地位,始终选取当前可用的拥有最小权值的边,所选择的边不能构成回路。首先构造一个只有n个顶点没有边的非连通图,给所有的边按值以从小到大的顺序排序,选择一个最小权值边,若该边的两个顶点在不同的连通分量上,加入到有效边中,否则舍去这条边,重新选择权值最小的边,以此重复下去,直到所有顶点在同一连通分量上。

● BFS和DFS的实现思想

参考回答:

BFS:(1)顶点v入队列(2)当队列为非空时继续执行否则停止(3)从队列头取顶点v,查找顶点v的所有子节点并依次从队列尾插入(4)跳到步骤2

DFS:(1)访问顶点v并打印节点(2)遍历v的子节点w,若w存在递归的执行该节点。

● 关联规则具体有哪两种算法,它们之间的区别

参考回答:

标签:数据结构与算法

Apriori和FP-growth算法

Apriori多次扫描交易数据库,每次利用候选频繁集产生频繁集,而FP-growth则利用树形结构,无需产生候选频繁集而直接得到频繁集,减少了扫描交易数据库的次数,提高算法的效率但是Apriori有较好的扩展性可用于并行计算。一般使用Apriori算法进行关联分析,FP-growth算法来高效发现频繁项集。

● 贪婪算法

参考回答:

贪婪算法(贪心算法)是指在对问题进行求解时,在每一步选择中都采取最好或者最优(即最有利)的选择,从而希望能够导致结果是最好或者最优的算法。贪婪算法所得到的结果往往不是最优的结果(有时候会是最优解),但是都是相对近似(接近)最优解的结果。贪婪算法并没有固定的算法解决框架,算法的关键是贪婪策略的选择,根据不同的问题选择不同的策略。

必须注意的是策略的选择必须具备无后效性,即某个状态的选择不会影响到之前的状态,只与当前状态有关,所以对采用的贪婪的策略一定要仔细分析其是否满足无后效性。

其基本的解题思路为:1)建立数学模型来描述问题;2)把求解的问题分成若干个子问题;3)对每一子问题求解,得到子问题的局部最优解;4)把子问题对应的局部最优解合成原来整个问题的一个近似最优解。

● 模拟退火,蚁群对比

参考回答:

模拟退火算法:退火是一个物理过程,粒子可以从高能状态转换为低能状态,而从低能转换为高能则有一定的随机性,且温度越低越难从低能转换为高能。就是在物体冷却的过程中,物体内部的粒子并不是同时冷却下来的。因为在外围粒子降温的时候,里边的粒子还会将热量传给外围粒子,就可能导致局部粒子温度上升,当然,最终物体的温度还是会下降到环境温度的。

先给出一种求最优解的方法,在寻找一个最优解的过程中采取分段检索的方式,在可行解中随机找出来一个,然后在这个解附近进行检索,找到更加优化的解,放弃原来的,在新得到的解附近继续检索,当无法继续找到一个更优解的时候就认为算法收敛,最终得到的是一个局部最优解。

蚁群算法:很显然,就是模仿蚂蚁寻找食物而发明的算法,主要用途就是寻找最佳路径。先讲一下蚂蚁是怎么寻找食物,并且在寻找到了食物后怎么逐渐确定最佳路径的。

事实上,蚂蚁的目光很短,它只会检索它附近的很小一部分空间,但是它在寻路过程中不会去重复它留下信息素的空间,也就是它不会往回走。当一群蚂蚁遇到障碍物了之后,它们会随机分为两拨,一波往左一波往右,但是因为环境会挥发掉它们的信息素,于是,较短的路留下的信息素多,而较长的路因为挥发较多,也就留下得少了。接下来,蚁群就会趋向于行走信息素较多的路径,于是大部分蚂蚁就走了较短的路了。但是蚁群中又有一些特别的蚂蚁,它们并不会走大家走的路,而是以一定概率寻找新路,如果新路更短,信息素挥发更少,渐渐得蚁群就会走向更短的路径。

以上就是蚂蚁寻路的具体过程。把这个过程映射到计算机算法上,计算机在单次迭代过程中,会在路径的节点上留下信息素(可以使用数据变量来表示)。每次迭代都做信息素蒸发处理,多次迭代后聚集信息素较多的路径即可认为是较优路径。

● 算法题:名人问题,给出最优解法

参考回答:

问题描述:

有n个人他们之间认识与否用邻接矩阵表示(1表示认识,0表示不认识),并A认识B并不意味着B认识A,也就意味着是个有向图。如果一个人是名人,他必须满足两个条件,一个是他不认识任何人,另一个是所有人必须都认识他。

解决问题:

用一个数组保存所有没检查的人的编号,遍历数组中的两个人i,j。如果i认识j,则i必定不是名人,删除i,如果i不认识j,则j必定不是名人,删除j,最终会只剩下一个人,我们检查一下这个人是否是名人即可,如果是,返回这个人,如果不是,那么这n个人中并无名人。

代码:

//初始化数组编号

for(int i=a;i<n;i++){
a[i]=i;
}
while(n>1){
if(known[a[0]][a[1]]){

//如果a[0]号认识a[1]号

//删除a[0],删除操作用a[n]替换掉a[0]即可,再将n下标减1

a[0]=a[--n];
}else{

//如果a[0]号不认识a[1]号

//删除a[1]

a[1]=a[--n];
}
}

//最终检查a[0]是否为名人

for(int i=0;i<n;++i){

//不考虑自身,并且检查他是否认识某个人,如果认识,那么不是名人

//检查其他人是否认识他,如果有人不认识他,那么他也不是名人

if((a[0]!=i)&&(known[a[0]][i]||!known[i][a[0]]))
return -1;
}
return a[0];
}

算法优化:

以上算法需要用一个数组来保存没有检查的人的编号,意味着空间复杂度为O(n),是否可以让空间复杂度降低到O(1)呢,答案是肯定的,解决方法就是用一头扫的方法

这里我们就不需要用一个数组来保存没有检查的人的编号了,我们直接对n个人进行遍历

遍历的方式是定义两个下标,用两个下标一起往后扫,对于两个下标i,j而言,保证[o~i-1]没有名人,并且[i~j-1]也没有名人,如果i认识j,那么i不是名人,删掉i,删除的方法就是i=j,j++,如果i不认识j,删除j,删除的方式是j++,遍历的时候让j一直加就可以了。

int i=0;j=1;
for(;j<n;++j){
if(known[a[i]a[j]])
i=j;
}
for(j=0;j<n;j++){
if((i!=j)&&(known[i][j]||!known[j][i]))
return -1;
}
return i;
}

算法优化2:

除了一头扫的优化方式,也可以用两头扫的方式优化以上的算法,保证0~i-1没有名人,并且j+1~n也没有名人,如果i认识j,删除i,如果i不认识j,删除j

i=0;j=n-1;
while(i<j){
if(known[i][j]){
++i;
}else{
--j;
}
}
for(j=0;j<n;++j){
if(i!=j&&(known[i][j]||!known[j][i]))
return -1
}
return i;
}