题目是这样的:写程序判断是否字符串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。程序如下:
这样算法的空间复杂度为O(256),时间复杂度为O(strlen(A)+strlen(B))。 顺便说一下mbsxx.com收集有各个公司的面试题,挺不错的。想要去面试的朋友可以找上面的题目练习练习。