Chinaunix首页 | 论坛 | 博客
  • 博客访问: 356229
  • 博文数量: 76
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 2363
  • 用 户 组: 普通用户
  • 注册时间: 2013-07-21 22:30
文章分类
文章存档

2014年(38)

2013年(38)

分类: IT职场

2014-01-02 17:42:19

因为白师兄的缘故,偶然看他做大众点评网网上的笔试题,总共有两个编程题。


第一个题目大意是:给定两个字符串,将凡是在第二个字符串出现过的字符从字符串一中删除,即删除字符串一和字符串二相同字符(只对字符串一执行删除操作)。

这个看到题目是觉得很简单,最常规的方法是依次遍历字符串一,然后用此时的字符与字符串二依次比较,相同则删除。这是大家最常想到的方法了。但是有没有更高效的算法呢,这样才能在笔试中脱颖而出,下面是我和师兄的想法:

第一步:开辟一个128(或者256)的字符标记数组flag,并将其初始化为为零,每个数组元素的索引值即为当前表示的字符(49表示字符‘1’)。

第二步:然后遍历字符串二,并将相应的flag对应的字符位置置一。遍历完成后,flag数组会将字符串二出现过的字符的相应位置置一。

第三步:遍历字符串一,检查flag数组的相应位置是否为一,如果是一则执行删除操作,不为一则继续执行,直到数组最后一个元素。

上边算法对比于最常想到的方法,对字符串二的遍历次数会明显减少(字符串一长度越长,节约的时间就越多)。不足之处就是借助了一个标记数组,在空间复杂度上不如常用算法。

注意:执行完删除操作后,要注意此时字符串长度已经发生改变,因此利用for循环使用的变量索引要做一定改变,才能正常完成功能。

至于程序代码,我就不给出了,大家自己可以实现试试。



第二个题目大意如下:现在的智能手机都是触屏,而且都有智能的锁屏软件,一般是如下的这个样子

095450856.jpg

然后将数字连接即可生成不同的密码。当然连接数字有一个约束条件:相连数字之间不能有第三个数字。即不能出现上图中直线的那种情况。

编程实现,找出符合约束条件的所有密码的(密码长度为3~9)组合。


解答:刚看到题目,有点晕,不知道如何下手。但是静下心,通过分析对比,可以发现,当相连的两个字符的水平距离为2(且在同一垂直线上)者垂直距离(且在同一个水平距离)为2,亦或水平距离和垂直距离都为2的时候会满足约束条件。

上边的约束条件其实就是密码长度为2时应该满足的要求,那么代码长度为3时,其实可以用密码长度为2的来模拟,先确定一个数字,然后寻找满足约束条件的数字,那么剩下就是密码长度为2的寻找,既然密码长度为3的找到了,密码长度为4的也就不在话下,利用相同方法…依次类推可以得到密码长度为9的密码。

这时是不是有点感觉了,这就是递归嘛。


第一步:开辟一个标记数组,用来标记不同密码长度时对应的长度,当为一时会终止递归。如果发现相应数字处已经有数字,则直接返回(即一个密码不能有两个相同数字)。

第二步:建立邻接矩阵,即将每个数字能够满足约束条件的数字放在该数字后边

比如对于数字1 。建立邻接矩阵后为1-> 2 -> 4 -> 5 ->6 ->8

第三步:对于不同的密码长度调用代码生成函数(递归函数)


下边是代码实现


#include

#include

#include

#defineNUM_NODE 9 //定义数字节点个数


typedefstruct LIST{

      int index;

      struct LIST * next;

}node,*pnode;//设立数字节点


intnode_num[10];//保存每个邻接矩阵的后边的节点个数,比如数字1它的邻接矩阵为1->2 -> 4 -> 5 ->6 ->8,所以个数为5

intflag[10];//标记数组,记录密码长度的迭代变化


int sum=0;

pnode code_node[NUM_NODE+1];//之所以定义为NUM_NODE+1是因为保持索引值和数字大小一致

voidgetxy(int num,int *x,int *y);//将数字转化成坐标,以进行判断是否满足约束标准


intcom_dist(int x1,int y1,int x2,int y2);//利用getxy得到的坐标,计算不同数字的距离


intinsert_node(pnode node,int num);//邻接矩阵的初始化过程,节点插入


voidcode_gen(pnode node,int len);//密码生成


FILE *f;


int main()

{

      int begin_x,begin_y;

      int end_x,end_y;

      int i,j;

      int num;

      clock_t start,end;

      for(i=0;i<=NUM_NODE;i++)// 标记数组初始化

      {

             flag[i]=0;

      }

      for(i=0;i<=NUM_NODE;i++)//邻接矩阵的头结点初始化

      {

             code_node[i]=(pnode)malloc(sizeof(node)*1);

             code_node[i]->index=i;

             code_node[i]->next=NULL;

      }

      for(i=1;i<=NUM_NODE;i++)//邻接矩阵的生成

      {

             num=0;

             printf("%d->",i);

             getxy(i,&begin_x,&begin_y);

             for(j=1;j<=NUM_NODE;j++)

             {      

                    getxy(j,&end_x,&end_y);

                    if(begin_x==end_x&& begin_y==end_y)

                    {

                           continue;

                    }

                    if(1==com_dist(begin_x,begin_y,end_x,end_y))

                    {

                           insert_node(code_node[i],j);

                           printf("%d->",j);

                           num++;

                    }                    

             }

             node_num[i]=num;

             printf("\n");

      }


//     f=fopen("result.txt","w");

      start=clock();

      for(i=3;i<=9;i++)//密码长度的变化

      {


             for(j=1;j<=NUM_NODE;j++)//选取不同密码起始数字时的密码情况

             {

                    flag[j]=i;

//                   printf("%d->",code_node[j]->index);

                    code_gen(code_node[j],i);

                    flag[j]=0;

             }

      }

      end=clock();

      printf("%d",end-start);

//     fclose(f);

      return 0;

}

//获取不同数字的坐标

voidgetxy(int num,int *x,int *y)

{


      if(num>=1 && num<=3)

      {

             x[0]=1;

             y[0]=num%4;

      }

      if(num>=4 && num<=6)

      {

             x[0]=2;

             y[0]=(num-3)%4;

      }

      if(num>=7 && num<=9)

      {

             x[0]=3;

             y[0]=(num-6)%4;

      }

}

//计算不同数字的距离,水平和垂直距离

intcom_dist(int x1,int y1,int x2,int y2)

{


      int absx=abs(x1-x2);

      int absy=abs(y1-y2);

      if((absx==2 && absy==0) ||(absy==2 && absx==0) || (absx==2 && absy==2))

      {

             return -1;

      }

      else

      {

             return 1;

      }

}

//邻接矩阵初始化,使用的插入函数

intinsert_node(pnode node,int num)

{

      pnode new_node;

      pnode temp=node;

      new_node=(pnode)malloc(sizeof(node)*1);


      if(new_node==NULL)

      {

             return 0;

      }


      while(temp->next != NULL)

      {

             temp=temp->next;

      }

      new_node->index=num;

      new_node->next=NULL;

      temp->next=new_node;

      return 1;

}

//打印密码

voidprint_code()

{

      int i=0;

      int j;

      int max=0;


      for(i=0;i<=NUM_NODE;i++)

      {

             if (max
                    max=flag[i];

      }

      for(i=max;i>0;i--)

      {

             for(j=0;j<=NUM_NODE;j++)

             {

                    if(i==flag[j])

                    {

                           fprintf(f,"%d->",j);

                           printf("%d->",j);

                    }

             }

      }

      fprintf(f,"\n");

}

//密码生成

voidcode_gen(pnode node,int len)

{

      int num;

      int i,j;

      pnode temp;



      if(len==1) // 迭代终止条件,当长度为一时,进行输出和sum自增

      {      

//            print_code();

//            printf("\n");

             sum++;

             return;

      }

      else

      {

             num=node->index;

             for(i=0;i
             {

                    temp=node;

                    for(j=0;j<=i;j++)//邻接矩阵

                    {

                           temp=temp->next;

                    }

                    if(flag[temp->index]==0)

                    {

//                          printf("%d->",temp->index);

                           flag[temp->index]=len-1;

                    }

                    else

                    {

                           continue;

                    }

                    code_gen(code_node[temp->index],len-1);//密码长度为len-1

                    flag[temp->index]=0;

             }

      }

}




上边注释掉的语句为输出语句(包括命令行输出和文件输出),如果要观察输出,可以去掉注释,但是运行时间会较长。(因为命令行输出很占时间)


还有一个问题是,主函数中没有添加邻接矩阵的释放函数,可以自己添加。



其实,要想验证这一方法的正确性,可以使用实现全排列(网上代码多),然后利用约束条件进行判断,然后将满足的条件的加一。对比与上边的结果是否一致。由于时间问题,我就没有实现了比较了,谁如果比较了发现不对,请留言。
阅读(2242) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~