yxCoding

I am a coder


Crazy Faint

看到一道Google的面试题

yxjoey posted @ 2008-04-06 01:56PM in C语言 with tags c 程序
连接两个头尾重合的字符串（KMP算法应用）

题目是这样的：写程序判断是否字符串A里每个字符在A中出现的次数都大于在字符串B中出现的次数。

我的想法是
1. 首先我们可以发现，如果判断成立的话，A的长度必定要比B的长度长。
2. 因为字符char的大小有限，所以可以建立一个对应所有字符的数组，一般情况下应该是char chars[2^8], 初始化为0，然后先统计A串中所有出现的字符的个数。对于A的字符c，我们可以用chars[c]++来进行统计。在统计完毕之后，对于B的每个字符进行反向统计，即对于B中的字符c', 计算chars[c']--。若在对B的统计过程中，有某一chars[c']<=0,这说明对于字符c'，它在B中出现的次数不比A中少，由此返回0， 若所有chars[c']均满足chars[c']>0，则返回1。程序如下:

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>
  4. int Compare(char *A, char *B){
  5.         if(strlen(B)>strlen(A)) //若B比A长，则返回0
  6.                 return 0;
  7.         int c[256];
  8.         int i;
  9.         for(i=0; i<256; i++)
  10.                 c[i] = 0;
  11.         char *p = A;
  12.         while(*p!='\0'){
  13.                 c[*p++]++;
  14.         } //统计A中的字符
  15.         p = B;
  16.         while(*p!='\0'){
  17.                         c[*p]--; //反向统计B中的字符
  18.                         if(c[*p++]<=0) //若成立，说明此字符在B中不比A中少
  19.                                 return 0;
  20.         }
  21.         return 1;
  22. }
  23.  
  24. int main(int argc, char *argv[]){
  25.         char A[] = "ABCACB";
  26.         char B[] = "ABD";
  27.         printf("%d \n", Compare(A, B));
  28. }


这样算法的空间复杂度为O(256),时间复杂度为O(strlen(A)+strlen(B))。 顺便说一下mbsxx.com收集有各个公司的面试题，挺不错的。想要去面试的朋友可以找上面的题目练习练习。

Comments Feed


* Login
*