找好工作，快人一步经典算法面试题解答(三)----- 最短路径、最长路径
1、最长字符连接
有n个长为m+1的字符串，如果某个字符串的最后m个字符与某个字符串的前m个字符匹配，则两个字符串可以联接，问这n个字符串最多可以连成一个多长的字符串，如果出现循环，则返回错误。
将各个字符串作为一个节点，首尾链接就好比是一条边，将两个节点连接起来，于是问题就变成一个有关图的路径长度的问题。链接所得的字符串最长长度即为从图的某个节点出发所能得到的最长路径问题，与最短路径类似，可以应用弗洛伊德算法求解。对于循环，即可认为各个节点通过其他节点又回到自己，反应在路径长度上，就表示某个节点到自己节点的路径大于零（注：初始化个节点到自己的长度为零）。
弗洛伊德算法介绍
Floyd-Warshall算法（Floyd-Warshall algorithm）是解决任意两点间的的一种，可以正确处理或负权的最短路径问题，同时也被用于计算有向图的传递闭包。Floyd-Warshall算法的为，为。
Floyd-Warshall算法的原理是。
设为从到的只以集合中的节点为中间节点的最短路径的长度。
若最短路径经过点k，则；若最短路径不经过点k，则。
算法如下：
const int MAX = ;
int floyd(int matrix[5][5],int n)
&int dist[5][5];
&int path[5][5];
&for(int i=0; i&n; i++)
&&for(int j=0; j&n; j++)
&&&dist[i][j] = matrix[i][j],path[i][j] = -1;
&for(int k=0; k&n; k++)
&&for(int i=0; i&n; i++)
&&&for(int j=0; j&n; j++)
&&&&if(dist[i][j]&dist[i][k]+dist[k][j])
&&&&&dist[i][j] = dist[i][k]+dist[k][j],path[i][j] =
&for(int i=0; i&n; i++)
&&for(int j=0; j&n; j++)
&&&if(i!=j&&dist[i][j] != MAX)
&&&&cout&&i&&&到&&&j&&&最短距离为&&&dist[i][j]&&
&&&&cout&&&路径逆序为:&&&j&&&-&&;
&&&&int mid = path[i][j];
&&&&while(mid!=-1)
&&&&&cout&&mid&&&-&&,mid = path[i][mid];
&&&&cout&&i&&endl&&
&return 0;&&&
int _tmain(int argc, _TCHAR* argv[])
&int matrix[5][5] = {0,MAX,1,4,MAX,
&&MAX,0,MAX,MAX,MAX,
&&MAX,MAX,0,MAX,2,
&&MAX,3,MAX,0,MAX,
&&MAX,3,MAX,MAX,0};
&floyd(matrix,5);
&return 0;
运行如下：
问题代码如下：
void maxLengthInStrings(string text[],int nSize)
int dist[100][100];
int path[100][100];
memset(path,-1,sizeof(int)*100*100);
memset(dist,0,sizeof(int)*100*100);
int m = text[0].size()-1;
for(int i=0; i&nS i++)
string iText = text[i].substr(1,m);
for(int j=0; j&nS j++)
string jText = text[j].substr(0,m);
if(iText == jText)
dist[i][j] = 1;
dist[i][j] = 0;
for( int k=0; k&nS k++)
for( int i=0; i&nS i++)
for( int j=0; j&nS j++)
if(dist[i][k]&&dist[k][j])
if(dist[i][j]&dist[i][k]+dist[k][j])
dist[i][j] = dist[i][k]+dist[k][j];
path[i][j] =
int max_from,max_to,max = 0;
for(int i=0; i&nS i++)
for(int j=0; j&nS j++)
if(max&dist[i][j])
max = dist[i][j],max_from = i,max_to =
cout&&&最长串逆序如下&&&text[max_to]&&& &;
int mid = path[max_from][max_to];
while(mid&=0)
cout&&text[mid]&&& &,mid = path[max_from][mid];
cout&&text[max_from]&&
int _tmain(int argc, _TCHAR* argv[])
string text[] = { &abcd&, &
& & & & & & & & & &bcde&, &
& & & & & & & & & &&cdea&, &
& & & & & & & & & & &deab&, &
& & & & & & & & & & &&eaba&, &
& & & & & & & & & & & &abab&, &
& & & & & & & & & & &deac&, &
& & & & & & & & & &&cdei&, &
& & & & & & & & & &bcdf&, &
& & & & & & & & & &&cdfi&, &
& & & & & & & & & & &dfic&, &
& & & & & & & & & &&cdfk&, &
& & & & & & & & & &bcdg&, &
maxLengthInStrings(text,sizeof(text)/sizeof(text[0]));
&运行结果如下：
&2、.用天平（只能比较，不能称重）从一堆小球中找出其中唯一一个较轻的，
使用x 次天平，最多可以从y 个小球中找出较轻的那个，求y 与x 的关系式
&三叉树，每次分为三等分，y = 3^x
3、随机数问题
随机取样问题，在《计算机程序设计艺术》(volume 2 chapter 3)中得到了详细的讲解，关于该问题的详细探讨可以翻阅该书相应章节。
随机取样问题可以分为：
1、&确定数目元素的随机取样，可以表述为：从N个元素中获得K个相异且随机的元素。
2、&不确定数目元素的随机取样，可以表述为：从一个数据流中获得k个相异且随机的元素。
其实第二个问题包含着第一个问题，我们只要探讨第二个问题即可，我直接给出下面的算法吧，首先要注意取样问题的描述：“k个”“相异”“随机”，代码如下：
T* random_sample(stream s,intk)
&&&&&T* rand_list=newT[k];
&&&&&inti=k;
&&&&&s.open();
&&&&&/*store first k elements in stream*/
&&&&&while(k--&=0)
&&&&&&&&&&&rand_list[i]=s.next();
&&&&&while(!s.end())
&&&&&&&&&&&i++;
&&&&&&&&&&&intidx=rand(0, i-1);//create random number [0, i-1]
&&&&&&&&&&&if(idx&=k-1)//[0,k-1]
&&&&&&&&&&&&&&&&rand_list[idx]=s.next();
下面对其正确性进行证明，正确性应该保证“k个”“相异”“随机”，前两个条件显然成立，开始状态前两个状态就成立，函数执行过程中，每次替换的元素都不相同（我们认为在stream中不同位置的元素不同），对于“随机”的证明可以使用数学归纳法进行：
待证明问题，对于任意n&=k，经过上述方法后，得到的结果中任何一个元素出现的概率均为k/n。
1、当n=k时，rand_list[]中存储前k个元素，p=k/n=k/k=1成立。
2、假设当n=i时，命题成立：i个元素出现在rand_list[]中的概率为k/i。
当n=i+1时，执行上述算法，我们只关注最后一步：对于第i+1个元素的操作。
对第i+1个元素执行上述算法之前，对于前i个元素中任意一个元素，它们在rand_list[]中出现的概率为k/i，我们以k/(i+1)的概率去替换rand_list[]中的元素，前i个元素中任意一个元素被替换的概率为：
&&&&&&&k(1/i)* ( 1/(i+1))
前i个元素中任意一个元素最终被取到的概率：
&&&&&&&k/i - k(1/i)* ( 1/(i+1)) = k/(i+1)
对于第i+1个元素，它被取到的概率可以直接计算得到：
&&&&&&&P(i+1)=k/(i+1)
所以当n=i+1时，上述命题也成立。
下面给两个相关的题目：
1、给定一个未知长度的整数流，如何随机选取一个数
2、给定一个数据流，其中包含无穷尽的搜索关键字（比如，人们在谷歌搜索时不断输入的关键字）。如何才能从这个无穷尽的流中随机的选取1000个关键字？
看过本文的人也看了：
我要留言技术领域：
你已经自动关注本知识库了哦！
确定要取消收藏吗？
删除图谱提示
你保存在该图谱下的知识内容也会被删除，建议你先将内容移到其他图谱中。你确定要删除知识图谱及其内容吗？
删除节点提示
无法删除该知识节点，因该节点下仍保存有相关知识内容！
删除节点提示
你确定要删除该知识节点吗？温馨提示！由于新浪微博认证机制调整，您的新浪微博帐号绑定已过期，请重新绑定！&&|&&
LOFTER精选
网易考拉推荐
用微信&&“扫一扫”
将文章分享到朋友圈。
用易信&&“扫一扫”
将文章分享到朋友圈。
阅读(2741)|
用微信&&“扫一扫”
将文章分享到朋友圈。
用易信&&“扫一扫”
将文章分享到朋友圈。
历史上的今天
loftPermalink:'',
id:'fks_',
blogTitle:'计算机常见算法面试/笔试题集',
blogAbstract:'1.用最简单的方法判断一个LONG整形的数A是2^n（2的n次方）
若a为2的N次方，则a最高位为1，其他位为0，那么(a-1)正好相反，只有最高位为0，其他位为1，然后做a和（a-1）的 位与就行了，结果为0则a为2的N次方。&
return (N-1)&N? FALSE : TRUE;
2.判断单链表是否存在环,判断两个链表是否相交：'
{list a as x}
{if x.moveFrom=='wap'}
{elseif x.moveFrom=='iphone'}
{elseif x.moveFrom=='android'}
{elseif x.moveFrom=='mobile'}
${a.selfIntro|escape}{if great260}${suplement}{/if}
{list a as x}
推荐过这篇日志的人：
{list a as x}
{if !!b&&b.length>0}
他们还推荐了：
{list b as y}
转载记录：
{list d as x}
{list a as x}
{list a as x}
{list a as x}
{list a as x}
{if x_index>4}{break}{/if}
${fn2(x.publishTime,'yyyy-MM-dd HH:mm:ss')}
{list a as x}
{if !!(blogDetail.preBlogPermalink)}
{if !!(blogDetail.nextBlogPermalink)}
{list a as x}
{if defined('newslist')&&newslist.length>0}
{list newslist as x}
{if x_index>7}{break}{/if}
{list a as x}
{var first_option =}
{list x.voteDetailList as voteToOption}
{if voteToOption==1}
{if first_option==false},{/if}&&“${b[voteToOption_index]}”&&
{if (x.role!="-1") },“我是${c[x.role]}”&&{/if}
&&&&&&&&${fn1(x.voteTime)}
{if x.userName==''}{/if}
网易公司版权所有&&
{list x.l as y}
{if defined('wl')}
{list wl as x}{/list}