一.问题来源

  昨晚看微博,发现于梁斌penny,他在说现在的面试制度考不出来真功夫,也就是基本功,面试题千篇一律的算法,看过会,不看就不会。期间提到了快慢指针求中位数。

  查资料时我发现,这其实是计算机系统原理里的知识点。

二.快慢指针概念

  快慢指针中的快慢指的是移动的步长,即每次向前移动速度的快慢。例如可以让快指针每次沿链表向前移动2,慢指针每次向前移动1次。

三.快慢指针的应用

3.1 判断单链表是否为循环链表

  对于初学者来说,要解决这个问题,最可能采取的方法就是使用两个循环。当外层循环步进一个节点时,内层循环就遍历外层循环节点之后的所有节点,然后比较内外循环的两个节点。若有节点地址相等,则表明该单链表有循环,反之则不存在循环。这种方法无疑效率比较低。

  今天给大家介绍一个经典的方法,通过快慢指针来检查单链表是否存在循环。其思路很简单,大家可以想一下上体育课长跑的情景。当同学们绕着操场跑步的时候,速度快的同学会遥遥领先,最后甚至会超越其它同学一圈乃至n圈——这是绕圈跑。那么如果不是绕圈跑呢?速度快的同学则会一直领先直到终点,不会再次碰到后面的速度慢同学——不考虑地球是圆的这种情况。

  快慢指针的设计思想也是这样。快指针每次步进多个节点——这个视情况而定,慢指针每次只步进一个节点。那么如果该链表存在循环的话,快指针一定会再次碰到慢指针,反之则不存在循环。

让快慢指针从链表头开始遍历,快指针向前移动两个位置,慢指针向前移动一个位置;如果快指针到达NULL,说明链表以NULL为结尾,不是循环链表。如果 快指针追上慢指针,则表示出现了循环。

int isExitsLoop(LinkList L) {
    LinkList fast, slow;
    fast = slow = L;
	while (fast && fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast)
        {
            break;
        }
    }
    return ((fast == NULL) || (fast->next == NULL));
}

  注:不一定直接是一个环,可能说先共同走一段路,在尾部形成环。如果是第一种情况(长度为5,从1开始),看分解如下表。

1 3 5 2 4 1
1 2 3 4 5 1

3.2 在有序链表中寻找中位数

  该方法在不借助计数器变量实现寻找中位数的功能。原理是:快指针的移动速度是慢指针移动速度的2倍,因此当快指针到达链表尾时,慢指针到达中点。程序还要考虑链表结点个数的奇偶数因素,当快指针移动x次后到达表尾(1+2x),说明链表有奇数个结点,直接返回慢指针指向的数据即可。如果快指针是倒数第二个结点,说明链表结点个数是偶数,这时可以根据“规则”返回上中位数或下中位数或(上中位数+下中位数)的一半。

while (fast&&slow) 
{ 
  if (fast->next==NULL) 
      return slow ->data; 
  else if (fast->next!= NULL && fast->next->next== NULL) 
      return (slow ->data + slow ->next->data)/2; 
  else 
  { 
      fast= fast->next; 
      fast= fast->next; 
      slow = slow ->next; 
  } 
 }

3.3 如果链表为存在环,如果找到环的入口点?

  有一个单链表,其中可能有一个环,也就是某个节点的next指向的是链表中在它之前的节点,这样在链表的尾部形成一环。
  那么问题来了,如何判断一个链表是不是这类链表?如果链表为存在环,如果找到环的入口点?  当fast若与slow相遇时,slow肯定没有走遍历完链表(不是一整个环,有开头部分,如上图)或者恰好遍历一圈(未做验证,看我的表格例子,在1处相遇)。于是我们从链表头、与相遇点分别设一个指针,每次各走一步,两个指针必定相遇,且相遇第一点为环入口点(慢指针走了n步,第一次相遇在c点,对慢指针来说n=s+p,也就是说如果慢指针从c点再走n步,又会到c点,那么顺时针的CB距离是n-p=s,但是我们不知道s是几,那么当快指针此时在A点一步一步走,当快慢指针相遇时,相遇点恰好是圆环七点B(AB=CB=s))。

node* findLoopPort(node *head) {
    node *fast, *slow;
    fast = slow = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) {
            break;
        }
    }
    if ((fast == NULL) || (fast->next == NULL)) {
        return NULL;
    }
    slow = head;
    while (slow != fast) {
        slow = slow->next;
        fast = fast->next;
    }
    return slow;
}

3.4 扩展问题

  判断两个单链表是否相交,如果相交,给出相交的第一个点(两个链表都不存在环)。

  比较好的方法有两个:

  1.将其中一个链表首尾相连,检测另外一个链表是否存在环,如果存在,则两个链表相交,而检测出来的依赖环入口即为相交的第一个点。
  2.如果两个链表相交,那个两个链表从相交点到链表结束都是相同的节点,我们可以先遍历一个链表,直到尾部,再遍历另外一个链表,如果也可以走到同样的结尾点,则两个链表相交。
这时我们记下两个链表length,再遍历一次,长链表节点先出发前进(lengthMax-lengthMin)步,之后两个链表同时前进,每次一步,相遇的第一点即为两个链表相交的第一个点。

四.参考文献及结束语

4.1 问题1

  相差多少?才能保证相遇?如果从物理学的角度理解(s-t曲线),肯定相遇,那么问题是如何尽快相遇(也就是快慢指针相差几倍才能使A点尽可能靠近源点,也就是说相遇尽可能早,这样复杂度就低了)?看下图,自己研究吧,笔者未做详细探索。

 

4.2 问题2

  s=t,s=2t和s=3t,s=6t的效果一样吗?

4.3 感想

  指针可以相差倍数,那也可以相差固定位数啦?比如求链表的倒数第n位.

4.4 参考文献

  http://anyhu.blog.sohu.com/184515249.html
  http://www.nowamagic.net/librarys/veda/detail/1842

标签智能推荐:

音效资源下载网站大全

ADOBE:https://offers.adobe.com/en/na/audition/offers/audition_dlc.htmlfreesound:http://freesound.orgsound-effects-library:http://www.sound-effects-library.comJamendo:https://www.jamendo.comccMixter:ht

【Tools】常用专业软件汇总

lity_measure/vqmt_download.html#purchasehttps://blog.csdn.net/vn9PLgZvnPs1522s82g/article/details/79724162http://www.ultraedit.cn/http://www.interrasystems.com/vega-analyzer.phphttps://www.adobe.com/c

Adobe Audition 2020 v13.0.4.39 特别版本

dobeAudition,简称“AU”音频录制、编辑和混合软件。Audition是业界最佳的数字音频编辑软件,专业声音剪辑软件,强大的音轨处理软件。具有音频录制、音频编辑、音频混合、音频降噪、设计音效、多轨混音、母带处理、现场调音、编辑视频音轨、音频转码等功能,支持频谱编辑工具自动语音对齐、降噪工具和自动响度纠正,支持多音轨多声道音频及多种音频特效与音频格式,提高音频质量和音频编辑整体效率。新版变

【音视频系列3】音频MP3文件和PCM文件,分析PCM音频文件,及转换为WAV文件

音频声音文件MP3和PCM两者均是封装格式,为了分析PCM,先下载一个MP3文件,然后通过ffmpeg将MP3文件转成PCM文件进行分析,使用分析软件为audition音频软件。转换PCM文件ffmpeg-ihai.mp3-fs16leaudio1.pcm转换后可以使用此命令播放看转换是否成功:ffplay-ar44100-ac2-fs16le-iaudio1.pcm转换后的文件放到auditio

【转】音视频基础课程

ng》《SpeechCodingAlgorithms》4.其他类书籍--专门书籍,如《自适应信号处理》,因为音频编码也好其他音频技术也好,自适应技术是经常使用的。例如无损编码的Wavpack,MPEG4ALS,都使用了自适应技术。--滤波器设计的相关书籍。《多抽样率数字信号处理理论及其应用》:讲解Transform技术。HE-AAC和ATRAC3,使用的QMF;MP3使用的PQF;AAC,MP3使

6.用户、组权限管理

用户、组和权限管理:Multi-tasks(多用户),Multi-Users(多任务)每个使用者:用户标识,密码:3A认证:Authentication(认证)Authorizaton(授权)Audition(审计)用户组:用户容器用户类别:管理员普通用户系统用户登录用户用户标识:UserID,UID16bits二进制数字:0-65535管理员:0普通用户:1-35635系统用户:1-499(Ce

使用juce制作vst插件

成即可生成vst插件七,将生成的VST插件放入C:\ProgramFiles\CommonFiles\VST3目录,打开adobeaudition软件,点击效果->音频增效管理器->扫描增效工具,扫描结果见下图。如果不能显示插件,尝试重启或者更换audition版本,我使用的2020版本正常。 八,在audition软件中点击文件->新建 -->多轨道会

第二周(0830~0905)

'>/tmp/issue.out;cat/tmp/issue.out  Q4、请总结描述用户和组管理类命令的使用方法总结描述:(一)3A的含义Authentication:认证,验证用户身份Authorization:授权,不同的用户设置不同权限Accouting|Audition:审计 (二)UID,GID的规范Linux中每个用户是通过UserId(UID)

liunxzzl

ct:]:标点符号[:graph:]:图形字符[:cntrl:]:控制(非打印)字符[:xdigit:]:十六进制字符 catzzl|tr'a-z''A-Z'Authentication:认证,验证用户身份Authorization:授权,不同的用户设置不同权限Accouting|Audition:审计Linux中每个用户是通过UserId(UID)来唯一标识的。管理员:root,0普通