A-A+

《挑战程序设计竞赛》读书笔记(五)尺取法

2014年05月22日 算法 暂无评论 阅读 1,200 次
摘要:

《挑战程序设计竞赛》读书笔记(五)尺取法。本文介绍了尺取法。针对尺取法的思想,扩展介绍了双指针这种比较通用的方法,并给出了几个例子和对应的解法。

3.2节讲了一个很通用的方法,叫尺取法。

尺取法通常设定前后两个指针,不断地按照某种策略移动前后指针,考察前后指针所限定的区间。two_pointer

例如例题3.2.1:给定长度为n的整数序列,求出总和不小于S的连续子序列的长度的最小值。按照尺取法,设定前后指针s=0,t=0,然后将s向前移动,判断t~s之间的区间是否满足要求,如果小于S,s继续移动,直到和大于等于S为止。此时将t向前移动。反复进行该过程,期间记录长度,并更新长度的最小值。复杂度为O(N)。

 

事实上,前后指针,或者叫双指针的方法适用于更广的问题。这里列举几个例子。

Case 1:判断数组a[0…n-1]中是否存在两个数其和为S。

Solution:先排序,然后设定首尾指针head=0, tail=n-1,两个指针向中间移动。当a[head] + a[tail] < S时,head++,否则tail--。

 

Case 2:单链表中,如何在O(N)时间复杂度和O(1)的空间复杂度找到倒数第k个节点?

Solution:除了先遍历一遍求得长度外,另一种有趣的方法是设定两个指针s和t,让s先向前移动k个节点,然后s和t同时移动,当s到链表尾时,t正好在倒数第k个。

 

Case 3:判断链表是否有环。

Solution:这是经典的面试问题了。设定两个指针,quick和slow,均初始化为链表头,quick每次移动两个节点,slow每次移动一个节点。当quick和slow相遇时,说明有环,如果指针遇到链表尾,说明无环(有环链表不会出现尾)。

 

Case 4:两个单链表相交成Y型,求交点,要求仅遍历一遍,空间复杂度O(1)。

Solution:这道题比较tricky。在给定的复杂度限定下,可以从一个链表头开始,将该链表所有的节点的next指针置为NULL,然后从另一个链表头开始,遍历,遇到NULL指针表示走到了交点。

(该方法破坏了链表结构,所以实践中应该不会用到这种方法,写在这里权当开拓思路了)

如果不是复杂度限定,我们有多种方法找到交点。这里我们提供几种比较容易想到的方法:方法1:先分别遍历一遍,求出两个链表的长度L1、L2(设L1 > L2),长的先移动L1-L2个节点,然后两个链表的指针同时走并进行比较,指针相等则说明是交点。

方法2:遍历其中一条链表,将该链表的所有节点地址存入map,然后遍历另一条链表,如果节点地址出现在了map中,说明这个节点是交点。

 

给我留言