yxCoding

I am a coder

看到一道Google的面试题

yxjoey posted @ 2008年4月06日 21:56 in C语言 with tags c 程序 , 1666 阅读

题目是这样的:写程序判断是否字符串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收集有各个公司的面试题,挺不错的。想要去面试的朋友可以找上面的题目练习练习。


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter