首页 > 代码库 > 华为历年试题(数组8)

华为历年试题(数组8)

有一个数组a[N]如a[10]={0,1,2,3,4,5,6,7,8,9}

每隔两个数删除一个数,如0,1,2(删除),3,4,5(删除),6,7,8(删除),9,

到数组尾部回到数组头部继续删除,要求编写一个函数实现实现上述操作,

返回最后一个数的数组下标。

函数接口:int getLast(int iLen)

参数:数组初始元素个数iLen

#include<iostream>using namespace std; struct LinkP{  int val;  LinkP *next;  LinkP(int a):val(a),next(NULL){}};LinkP *cycLinkP(int iLen){  if(iLen<=1)       return 0;        LinkP *p1 = new LinkP(0);    LinkP *h = p1;   int i = 1;   while(i<iLen)   {      LinkP *p = new LinkP(i);      p1->next = p;      p1 = p;      i++;   }   p1->next = h;   return h;}int getLast(int iLen){    LinkP *h = cycLinkP(iLen);    int num = iLen-1;    LinkP *p = h;    LinkP *p1 = h;    while(num)    {       num--;       p = p->next;       p1 = p->next->next;       p->next = p1;       p = p1;    }        return p->val;}void main(){    int iLen = 2;    cout<<getLast(iLen)<<endl;    }

 如果不用上面的循环链表,而用数组的话,如下编码:

 特别注意用数组做时,出现往前两步越界的问题,往往只能想到越来一次界,还有一种情况可能越两次界,所以要用while循环,直到不越界为止。

int getLast(int iLen){    int i,len;    int *s=(int *)malloc(sizeof(int)*iLen);    for(i=0;i<iLen;i++)        s[i]=i;    len=iLen;    int j=0,k;    while(len>1)    {        if(j+2>=len)//防止要循环2圈的情况        {            j=j+2-len;            while(j>=len)                j -= len;        }        else            j=j+2;        for(k=j;k<len-1;k++)        {            s[k]=s[k+1];        }        len--;    }    return *s;}