477.汉明距离总和
https://leetcode-cn.com/problems/total-hamming-distance/
难度：中等
题目：
两个整数的 汉明距离 指的是这两个数字的二进制数对应位不同的数量。
计算一个数组中，任意两个数之间汉明距离的总和。
注意:
- 数组中元素的范围为从 0到 10^9。
- 数组的长度不超过 10^4。
示例：
输入: 4, 14, 2 输出: 6 解释: 在二进制表示中，4表示为0100，14表示为1110，2表示为0010。 所以答案为： HammingDistance(4, 14) + HammingDistance(4, 2) + HammingDistance(14, 2) = 2 + 2 + 2 = 6.
分析
如果看过我昨天的解题： 461.汉明距离
那么相信今天的题目，只需要简单思考下，就能解决。 昨天是计算两个数的汉明距离，今天无非多几个。
来一个打一个，来两个打一双，来多少都不够塞牙缝的。
2 (0 0 1 0) 4 (0 1 0 0) 14 (1 1 1 0) ↑ ↑ ↑
查看上图，末尾尾数都是0，不存在汉明距离，其他三位都分别存在0和1，那么这个多位该如何算？
让我们把相同的数放在一起 先这样[1] *[0,0]，然后在看看一共有几种排列？
1的个数 * 0的个数 = 1的个数 * 总数 - 1的个数 = 2 3 * 2 = 6 用例通过。
好了，算法知道了，下来我们来构造矩阵，由于数组元素范围在0 ~ 10 ** 9,10 ** 9 < 2 ** 30.
所以我们构造一个最大1000行的列表，然后计算每一列汉明距离n * (length - n)。
矩阵转置怎么快？zip(*matrix)，转换为31 * 1000的矩阵在进行计算。
解题1 二维矩阵：
class Solution: def totalHammingDistance(self, nums): ret, ln = 0, len(nums) matrix = [bin(num)[2:].zfill(31) for num in nums] for row in zip(*matrix): n = row.count('1') ret += n * (ln - n) return ret
上面的方法我们最大可能会构造一个31 * 1000的矩阵，那么有没有拿空间换时间的方法呢？
答案是有的，我们维护一个长度为31的全零数组，然后将二进制的字符串进行倒序后，
判断每一位的结果追加至计数列表。最终循环计算列表的总和即可。
解题2 列表计数器：
class Solution: def totalHammingDistance(self, nums): count_list = [0] * 31 ret, ln = 0, len(nums) for num in nums: for index, s in enumerate(bin(num)[2:][::-1]): if s == '1': count_list[index] += 1 for count in count_list: ret += count * (ln - count) return ret
