461. Hamming Distance and 477. Total Hamming Distance in Python

题目：

The Hamming distance between two integers is the number of positions at which the corresponding bits are different.

Given two integers x and y, calculate the Hamming distance.

Note:
0 ≤ x, y < 231.

Example:

Input: x = 1, y = 4
Output: 2
Explanation:
1   (0 0 0 1)
4   (0 1 0 0)
       ↑   ↑
The above arrows point to positions where the corresponding bits are different.

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

代码：

这两周比较慢，都没有做题，赶紧做两道。这两个题目比较像，就放在一起吧。汉明距离，就是把数字变成二进制，看有多少为不一样，不一样的个数就是汉明距离。

所以，第一题，仅仅比较两个数字，我就用了常人都能想到的方法，转换成二进制字符串，遍历比较。唯一注意的就是将较短的字符串前面加0补足和长的相同位数。

   def hammingDistance(self, x, y):
        """
        :type x: int
        :type y: int
        :rtype: int
        """
        str1 = bin(x)[2:]
        str2 = bin(y)[2:]
        if len(str1) < len(str2):
            str1 = '0'*(abs(len(str2)-len(str1)))+str1
        else:
            str2 = '0' * (abs(len(str2) - len(str1))) + str2

        res = 0
        for i in range(0,len(str1)):
            if not str1[i:i+1] == str2[i:i+1]:
                res += 1
        return res

这个题通过了，但第二个题目要求给出一个字符串，两两求出汉明距离，然后相加。于是，我接着上题的函数，增加了一个遍历，O(n^2):

 def totalHammingDistance(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if not nums:
            return 0
        res = 0
        new_nums = sorted(nums)
        print sorted(set(nums))
        for i in range(len(new_nums)):
            for j in new_nums[i+1:]:
                print new_nums[i],j
                print self.hammingDistance(new_nums[i],j)
                res += self.hammingDistance(new_nums[i],j)
        return res

逻辑是没错，但不用想，leetcode中当然超时，会有一个包含1000个7、8位数字的列表去测试。唉，没办法，想不出来，百度了一下。这个汉明距离，其实可以通过每个bit位上面数字0的个数和1的个数相乘的结果，相加求得。等于逐一遍历列表中每个数字的每个bit位，所有bit位遍历一遍。

    def totalHammingDistance2(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if not nums:
            return 0
        res = 0
        lists = []
        nums.sort()
        for i in nums:
            temp = list(bin(i)[2:])
            temp.reverse()
            lists.append(temp)

        for i in range(len(lists[-1])):
            count_0, count_1 = 0, 0
            for element in lists:
                # print element
                if len(element)-1 < i:
                    count_0 += 1
                elif element[i] == '0':
                    count_0 += 1
                elif element[i] == '1':
                    count_1 += 1
                # print count_0,count_1
            res += count_0 * count_1
        return res

试了下，果然没问题！：）