今天写到了leetcode第477道题目的时候表示十分激动，一方面觉得刷leetcode很久没有刷到这么有趣的题目了，第二方面也是想记录一下刷leetcode的过程中的体会。
刷leetcode从一开始觉得很枯燥乏味,到现在几乎每天刷一道leetcode，似乎成为了饭后散步一样习以为常的事情了。这其中主要有亮点是我觉得刷leetcode带给我的好处。
- 刷leetcode的过程中逼着我去看一些绕口的英文句子。 在不知不觉中训练了我边看英文边思考的能力。
- 越来越掌握一门语言其实只要刷一遍leetcode就能懂个八九十了。
对于第一点当然是不言自明的了，对于第二点，我刚开始的时候没有这种感觉，不过后期刷了一页leetcode之后，体会颇深。我用的是python，所以每次做完题我都会去discussion里面找大神们的神操作，慢慢的竟然爱上了python哲学一般简洁的编程思想，很多技巧真的是只要一行就能实现java十几行的操作。这点让我每次对比完大神的操作和我自己的笨操作之后，总有一种what shit am I writing的感觉，然后就是试着模仿大神们的操作，重现一次implementation。我相信不只是python，java、scala或者golang都可以在里面找到对应的解释，我认为这是我目前发现的学习语言的捷径。
好了，言归正传，477这道题真的很棒，不会很复杂，但是也不是一开始就能想到的。以下是题目的description： ’’’ The Hamming distance between two integers is the number of positions at which the corresponding bits are different.
Now your job is to find the total Hamming distance between all pairs of the given numbers.
Example: Input: 4, 14, 2
Output: 6
Explanation: In binary representation, the 4 is 0100, 14 is 1110, and 2 is 0010 (just showing the four bits relevant in this case). So the answer will be: HammingDistance(4, 14) + HammingDistance(4, 2) + HammingDistance(14, 2) = 2 + 2 + 2 = 6.
Note: Elements of the given array are in the range of 0 to 10^9 Length of the array will not exceed 10^4. ’''
第一眼看上去就觉得要来一个二次遍历，时间复杂度当然会是O(N^2)，下面是我的一个实现：
def totalHammingDistance(self, nums):
res = 0
for i1,v1 in enumerate(nums):
for i2, v2 in enumerate(nums[i1+1:]):
res += bin(v1^v2).count('1')
return res
但是这种算法直接被leetcode否决了，其实也正常，一旦想到要遍历两次数组的时候，就应该预想到时间复杂度一定会很高，很大可能是不可取的。经验告诉我，这时候条件肯定是有用的，但是想破头脑也想不到怎么用。于是google之，发现大神们的做法真的很巧妙，顿时茅塞顿开，醍醐灌顶，头顶佛（lv）光，整个人都不好了。好了，吹得有点过了，下面我就来看图说话。
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | |
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | |
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | |
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | |
...
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | |
相信看了上面的图很多人就已经懂了吧。开玩笑的，不懂继续看我的笨解释。
我们的目标实际上是要找到同一个bit位上面，这n个数两两不同的个数，而考虑到bit位上面其实只有2种可能值，0和1。也就是说，在同一个bit位上面的值，每一个是1的数应该和剩余的0的数不相同，从而对总的hamming distance（hamming distance是两个数的二进制表达式中不相同的个数）产生贡献，而这个贡献是多少呢？如果该bit位上面的值是1的个数是count的话，那么0的个数就是n-count，因此这个位置上面最终也将使结果增加count*(n-count)的hanmming distance。复杂度瞬间从O(n^2) 降低到 O(32*n)。这是一个巨大的飞跃啊，题目的假设是每个元素是0<=x<=10^9，元素个数是0<n<=10^4，那么最坏的情况我们就要遍历10^13，而现在，我们最差也就只要遍历32*10^4，差距高低立判。下面是大概的解决方案：
class Solution(object):
def totalHammingDistance(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
res=0
n=len(nums)
for i in range(33):
bit_count = 0
for num in nums:
# calculate the number of bits
bit_count+=(num>>i)&1
res+=bit_count*(n-bit_count)
return res
事后不禁感叹,大神毕竟是大神啊，此等旁门左道都能想到。
之所以觉得这道题目很好，一方面觉得他训练了提高对题目条件的重视程度，第二方面他加深了我对bit操作的概念，包括位运算符等。然后再联想最近写leetcode的经历，感触颇深，因此专门拎出来写一篇博客记录（zhuangbi）一下。
最后照例总结一下最近的工作生活，最近有个大项目一直在赶，写leetcode也是忙中偷闲，一点一点攒，越来越觉得，leetcode虽然操作的是小的数据集，可能就一个4个数字的数组，但是放到上千万条的数据集来看，其实也是一个道理，很多大数据集问题可以按照这些训练的方法进行解析，有时候会在工作中突然用到的时候有种莫名的兴奋。这也是最近在做数据搬运工过程中的体会。然后side project也还要忙，如何平衡公司的project和自己的side project是一个很艰苦的过程，希望自己能够更加专注，做好每一个向这个community 贡献的产品。说到这里，想起了人生中第一次在开源社区的贡献被merge了，yeah!!!!
虽然只是一个小小的静态网站生成器的主题，但也算是走出了开源的第一步，可喜可贺。那就以这个逼作为结尾结束本文吧。Feel free to leave a comment below, and until then see you next time!