CWYAlpha

Just another WordPress.com site

Thought this was cool: C语言逻辑操作符的巧妙用法:an anagram of a palindrome

leave a comment »


   
这是网上看到的面试题。
    A string is
a palindrome if it has exactly the same sequence of characters when
read left-to-right as it has when read right-to-left. For example,
the following strings are palindromes:
   
“kayak”,
    “Rats live
on no evil star”,
    “Able was I
ere I saw Elba”.
    A string A
is an anagram of a string B if A can be obtained from B by
rearranging the characters. For example, in each of the following
pairs one string is an anagram of the other:
    “mary” and
“army”,
    “rocketboys”
and “octobersky”,

Write a function:
    class
Solution { public int isAnagramOfPalindrome(String S); }
    that, given
a non-empty string S consisting of N characters, returns 1 if S is
an anagram of some palindrome and returns 0 otherwise.
Assume that:
N is an integer within the range [1..100,000];
string S consists only of English lower-case letters (a-z).

For example, given S = “dooernedeevrvn”, the function should return
1, because “dooernedeevrvn” is an anagram of the palindrome
“neveroddoreven”. Given S = “aabcba”, the function should return
0.

Complexity:
    expected
worst-case time complexity is O(N);
    expected
worst-case space complexity is O(1) (not counting the storage
required for input arguments).

题目来源:
http://stackoverflow.com/questions/8447222/anagram-of-a-palindrome

回贴中给出了java的实现。这里提供两种C的实现代码,并加以分析。

   
题目应该不需要过多的解释了,很容易懂,就是一个回文的判断。如果一个由26个字母组成的字符串,经过重新字符串排列后所得的字符串是个回文,那么return
1,反之,return 0。其中输入的字符串S均为小写字符。
   
一个最normal的算法:具体说明见注释
int isAnagramOfPalindrome ( char *S ) {
    int
counts[26];//设置一个大小为26的int型数组
                  
//每位分别用于表示26个字母中,各字母在字符串S里的个数
    int i,
N;
    for (i=0;
i<26; ++i)
       
counts[i] = 0;
    N=0;
    while (S[N])
{//扫描S
       
++counts[S[N]-‘a’];//每遇到一个字母就在counts[]相应位置+1
       
++N;
    }
    int
oddcount=0;
    for (i=0;
i<26; ++i)
       
if (counts[i]%2)
           
++oddcount;//判断counts中个数为奇数的
    if ( (N%2)
&& (oddcount==1) )
//若字符串S的长度为奇数,且其中只有一个字母的个数为奇数,则返回1
       
return 1;
    else if
((!(N%2)) &&
(oddcount==0))//若字符串S的长度为偶数,且每个字母的个数均为偶数,也返回1
       
return 1;
   
//我觉得这里可以改成if(oddcount <= 0) return 1;
不知道有没有想错,脑子有点迷糊了@_@
   
//否则,返回0
    return
0;
}
   
这是一般人看到题目第一反应能想到的算法,当然其中的一些处理,还是需要注意,比如:++counts[S[N]-‘a’];一些代码细节都提高代码效率和可读性的关键。

   
当然,既然题目叫做逻辑操作符的巧妙应用,自然这道题有不同寻常的解法,一个Germany大牛提供的算法,仅三行搞定:
int isAnagramOfPalindrome ( char *S ) {
    int
m=0;
    while(*S) m
^= (1<<(*S++-‘S’));
    return
!(m&(m-1));
}
   
由于代码太短,不容易注释,这里慢慢说明吧。短短两句话,让我对逻辑操作符的用法突然有了一种顿悟…以前看代码一看到这类代码就头晕。暂且把此代码的可读性放到一边,此例仅仅用于说明这道题的一个新解法,拓宽自己的思路和相法。原来代码可以这么写~

    分步解释:
    1)
1<<(*S++-‘S’)
      
这一步将S中的每位字符都转成数字,作为数字1左移的位数
      
为了方便理解,定义一个int n =
1<<(*S++-‘S’);
    2)m ^=
(1<<(*S++-‘S’)); =>
简化为:m = m^n;
      
这一步将m与n作异或
   
3)不断循环1)2)两步过程
   
4)!(m&(m-1))
      
将m与m-1相与后取反,return
   
看完每个人看完我的解释都想把我打一顿,说了跟没说一样…完全不明白跟原题有几毛钱关系!OK,俺上面的目的只是会了复习一下逻辑操作符而已:P

   
首先,此代码的精华之一,在于,作者巧借了int是32位的特点来实现他所想要的功能~为什么这么说呢,参见算法一,我们需要一个26位的counts数组,而int型是32位,32>26,显然,用一个int,位数就足够了!可是每位只能用0/1来表示,而S中任意字母出现的个数最大的可能是100,000(题中:N
is an integer within the range [1..100,000])。
   
那么,怎么办呢?这便是2)步中异或的作用了。以前我一直对异或操作符特别不敏感,写了几年的代码了,除了找工作的笔试里遇到异或,真正工作中,根本不会想到。异或操作最经典的一道题:如何不引入第三个变量而实现两个整型变量的交换,这也是C++程序员面试宝典中版版都出现的例子。答案就是用异或,同时也不会出现溢出的问题:

                                 
a = a^b; b = a^b; a = a^b;
   
OK,大功告成!要理解这一步,最关键的就是理解异或的作用,不仅是表面作用,还有更深层次的涵义。异或,应该是初中数学里的知识?规则如下:

                               
1^1 = 0^0 = 0; 1^0 = 0^1 = 1;
   
即两位相同则为0,不同则为1。其实这三步异或可以这么理解:
    前两步可以等价于:b =
(a^b)^b = a^(b^b) = a^0 =
a;原因很简单,google一下异或满足结合律即可明白,证明么,运用高中数学知识自行解决~~最后一步也可以等价于:a =
(a^b)^a = a^b^a = a^a^b = 0^b = b;这一步用到了异或满足交换律的知识。
   
OK,理解了异或的含义,就可以来解释算法二的第二步了。首次进入循环时,m=m^n,此时m的初值为0,因为m=n。此后每次循环,m都与上一次进行异或,从前面这个两次交换的例子我们可以发现,由于26个字符中每个字母都在int
m的二进制表示中独占一位,事实上我们并不需要知道它们分别都占的哪一位,也就是说步骤1的1<<(*S++-‘S’)中的’S’可以是任意一个ASCII码,目的就是把字符转换成二进制数值。我们也可以写成*S++-‘a’等等~——这是插播,重新回到正题,由于26个字符中每个字母都在int
m的二进制表示中独占一位,并且每个字母所占的位置显然是不变的。因此每做一次异或,就有可能变化一次。以字符串kakay为例,当k第一次出现时,m中k所在位的二进制值为1,当k第二次出现时,此位经过异或会变成1,所以可以推出,我们就可以巧妙地用异或来使得k位中,1表示k出现了奇数次,0表示k出现了偶数次,这不正是算法一中,第二个循环完成的工作么?多巧妙啊~~因此,当算法二的循环体执行完毕后,m的二进制形式用于表示26个字母中每一位出现次数的奇偶性了。

   
解释到这里,相信大部分人都已经明白接下来需要做什么了,按照算法一的normal思想,我们只需要保证m的二进制形式中,要么只有一个1,要么没有1,我们甚至不需要知道S的长度。那么,怎么判断m中有几个1呢?最后一步:!(m&(m-1)),相信很多人都知道m&(m-1)语句的作用,面试宝典里也有这个题,我当时理解绝对没有分析完这道题来得深刻~这个语句的作用就是判断m是否是2的N次方。例如m=(4)10=(0100)2,m-1=(3)10=(0011)2,因此,若m&(m-1)=0则说明m是2的N次方,也进一步说明m中只有一个1!这里作者又用了一个巧妙的办法,即我们不需要知道m中具体有多少个1,只需要知道m中是有一个1,0个1,还是大于1个1。这个判断简单的用m&(m-1)即可解决。当m&(m-1)=0,m里有一个1,或者没有1,此时返回1,反之,m里有大于1个1,则返回0。算法完毕。这里插播一个小细节,即没有1时,m=0,m-1=-1,注意0和-1如何按位与?就是负数的二进制表示问题,即补码,请各位看官google之吧~

   
分析完毕。下面总结陈词:今天写这篇代码分析的目的,第一在于希望自己知其然,还要知其所以然,因此把代码的内在分析了一遍,加深印象。第二,分析代码不在于会这一道题目,也不在于这个算法是否最优,当然,某些情况是这个目的,但此前对我来说,不是~我的目的是希望自己通过这样一个经典而巧妙的解法,学到其中的思想,毕意思想才是最重要的,通过整个的分析,反推出别人的思考过程,从而学会举一反三,这里的举,举的是思想,是方法~~例如从这个例子可以知道,以后再遇上此类需要用一个数组来记录每一位出现的次数时,可以考虑用int型来代替,当然,这有限制,限制性前文也有提及~~~希望自己通过这个例子,明白c语言中逻辑运算没有那么可怕,慢慢地学习快速读懂这样的代码,也学着在资源有限的情况下,用这种方法提高程序效率。但逻辑运算的代码一般都不太容易理解,用于解决这类问题,也有其精妙之处,因此今后如果自己用到这样的方法,一定要记得写清注释,加强代码的可读性。

   
在本文结束前,再罗嗦两句俺的近况吧。好久没写日志了,赫赫~~一是俺娘又在催我找对象了,越催越勤,唉,咋办呢…她听说我新公司基本都是有孩子的同事,立马大叫:你怎么找了个这样的工作!——我瀑布汗啊!!!!!再说工作,从换工作至今一直懒得更新blog,要学的知识实在太多,感触也太多。刚刚看邮件,看到组里一个同事给我回了我下午遇到的一个问题——我只是想通过这个小事说明,新公司里真的不缺牛人和好人,而这一点,最大的好处在于,我总能找到帮助我解决问题的人,当然,前提是我经过了自己的努力,但还是没法解决~入职一个多月,每天的进步似乎比以前一年多的收获还多(当然也许夸张了一点),但的确有这样的感受——这有点像那个“拥有者获得更多的理论”——每当遇到学习瓶颈时,学着多与周围的人沟通,总会遇到一个能指点迷津的人,他们不需要告诉我太多,给我一个指导方向,足矣,能让我不走岔,或者说少走了点岔路,也避免了我学习上的停滞不前,这一点是我上一个工作所不能及之处~正应了那句话:别人的成功经历也许不能教会你成功,但别人的失败经历却能让你避免一些失败~——至于如何辩证理智的看待这一切,我无需多言~辩证理智么,姐的拿手好“菜”啦~~
  青春就应该这样绽放  游戏测试:三国时期谁是你最好的兄弟!!  你不得不信的星座秘密
from 小胖妞妞,一个人的旅程: http://blog.sina.com.cn/s/blog_4b687eac01013svx.html

Written by cwyalpha

六月 14, 2012 在 5:25 下午

发表在 Uncategorized

发表评论

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / 更改 )

Twitter picture

You are commenting using your Twitter account. Log Out / 更改 )

Facebook photo

You are commenting using your Facebook account. Log Out / 更改 )

Google+ photo

You are commenting using your Google+ account. Log Out / 更改 )

Connecting to %s

%d 博主赞过: