给大家一道题哈~~~俗话说有乐趣要分享，大家好才是真的好！

huntrsky

有一个长度为N的先入先出队列，其中每个元素包含两个int，找寻其中M个“连续”元素，记录有多少组元素满足要求。
其中连续的含义：举个例子（1，2）（3，1）（4，5）这3个元素就是连续的，首先要保证先后次序（（1，2）（4，5）（3，1）就不连续），然后是第一个元素中两int的和等于第二个元素的第一个int的值。
另：队列中的元素可以随意修改，但不能漏掉满足要求的情况
呵，看谁的效率最高哈~~~~最重要的是，have fun！！！

selfrun

这个一次遍历就好了吧，复杂度O(n)

cugb_cat

首先遍历建立一个连续表，以后再修改其中元素的值的时候就可以只看其前后节点了。

huntrsky

建立表分配释放内存，不是会拖慢效率么？
而且遍历的算法是怎样的呢？

pinyin

这个标题咋看咋怪，楼主是在练拐弯技巧吗？

cjaizss

遍历一遍不就行了吗？
“另：队列中的元素可以随意修改，但不能漏掉满足要求的情况”没搞懂........

wangqi0021

啥意思

zwhermes

不明白。（1，2），（3，1），（4，5）怎么就连续了？
既然可以随便改，那就整个队列都可以改成连续的了吧。

huntrsky

恐怕不是那么简单吧,比如队列为{1,1},{2,1},{3,2},{3,1},{12,3},{4,1},{8,1}要找3个连续数有几种情况,就不好写遍历了

huntrsky

这个是我做磁盘预读时的代码:其中第一个int代表磁盘偏移量,第二个int代表读取长度,如果找到有连续的数就说明要预读.没有就不管,因为本身是为了提高磁盘的读效率,所以这里的查找本身效率也要非常的高,我下面的算法就有缺陷,为了效率抛弃了一些满足要求的值,但是也没办法,所有想问问坛子里的各位兄弟有更好的想法没有~~~希望不吝赐教哈

1. #include <iostream>
   
2. using namespace std;
   
3. 
   
4. typedef struct _ReadAheadInf
   
5. {
   
6.         int QuadPart;
   
7.         int Length;
   
8. }ReadAheadInf, *P_ReadAheadInf;
   
9. 
   
10. const int ReadAheadInfArryNum=9;
    
11. const int SeriesNum=3;
    
12. 
    
13. ReadAheadInf pReadAheadInfArry[ReadAheadInfArryNum]={{1,1},{2,1},{3,2},{3,1},{12,3},{4,1},{8,1},{9,1},{11,1}};
    
14. P_ReadAheadInf pReadAheadInfArryEdit=pReadAheadInfArry+8; //指向队列的尾巴
    
15. int main(int argc, char *argv[])
    
16. {       
    
17.         int i=0,j=0,iCheckOk=1,len=0;
    
18.         P_ReadAheadInf pTempBase=NULL;
    
19.         P_ReadAheadInf pTempRun=NULL;
    
20. 
    
21.         while(1)
    
22.         {
    
23.                 pTempBase=(pReadAheadInfArryEdit-SeriesNum<pReadAheadInfArry)?        \
    
24.                         (pReadAheadInfArry+ReadAheadInfArryNum-(SeriesNum-(pReadAheadInfArryEdit-pReadAheadInfArry))):(pReadAheadInfArryEdit-SeriesNum);
    
25.                 for(i=0;i<ReadAheadInfArryNum-SeriesNum+1;++i)
    
26.                 {
    
27.                         pTempRun=pTempBase+1;
    
28.                         iCheckOk=1;
    
29.                         len=pTempBase->Length;
    
30.                         for(j=0;j<i+SeriesNum-1;++j)
    
31.                         {
    
32.                                 //判断越界
    
33.                                 if(pTempRun-pReadAheadInfArry>=ReadAheadInfArryNum)
    
34.                                         pTempRun=pReadAheadInfArry;
    
35.                                 //判断连续
    
36.                                 if(pTempBase->Length+pTempBase->QuadPart==pTempRun++->QuadPart)
    
37.                                 {
    
38.                                         pTempBase->Length+=(pTempRun-1)->Length;
    
39.                                         if(++iCheckOk==SeriesNum)
    
40.                                         {
    
41.                                                 (pTempRun-1)->QuadPart=-1;//找到
    
42.                                                 break;
    
43.                                         }
    
44.                                 }
    
45.                         }
    
46.                         pTempBase->Length=len;
    
47.                         //判断越界
    
48.                         if(--pTempBase<pReadAheadInfArry)
    
49.                                 pTempBase=pReadAheadInfArry+ReadAheadInfArryNum-1;
    
50.                 }
    
51.         }
    
52. }
    

复制代码