蛮三刀酱的博客

技术公众号:后端技术漫谈

【Leetcode】【python】Hamming Distance, Merge Two Binary Trees

发表于 更新于 分类于 阅读次数： Valine：

Hamming Distance

题目大意

两个整数的汉明距离是指其二进制不相等的位的个数。

给定两个整数x和y，计算汉明距离。
注意：
0 ≤ x, y < 2^31.

解题思路

异或运算

代码

1
2
3
4
5
6
7
8
class Solution(object):
    def hammingDistance(self, x, y):
        """
        :type x: int
        :type y: int
        :rtype: int
        """
        return bin(x ^ y).count('1')

我提交的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution(object):
    def hammingDistance(self, x, y):
        """
        :type x: int
        :type y: int
        :rtype: int
        """
        x_bin = list(bin(x))
        y_bin = list(bin(y))
        x_bin.reverse()
        y_bin.reverse()
        x_judge = []
        y_judge = []
        for x in x_bin:
            if x == 'b':
                break    
            x_judge.append(x)
        for y in y_bin:
            if y == 'b':
                break    
            y_judge.append(y)
        list_distance = abs(len(x_judge) - len(y_judge))
        if len(x_judge) < len(y_judge):
            for i in range(list_distance):
                x_judge.append('0')
        else:
            for i in range(list_distance):
                y_judge.append('0')
        distance = 0
        for i in range(len(x_judge)):
            if x_judge[i] != y_judge[i]:
                distance += 1
        return distance

总结

以后谁和我说二进制异或运算我和谁急

Merge Two Binary Trees

题目大意

给两个二叉树想要合并，有一些结点会重叠而有一些不会，现在想把重叠的结点值变为两者值相加，不重叠的直接用，构建出新的树

解题思路

考察的就是二叉树的遍历，遍历每个结点然后如果重叠（两个二叉树结点都不为空）新结点值便为两者和，不重叠（只有一个结点为空）新结点值为不为空的值，全为空到达底部返跳出。按照这个逻辑进行迭代

联想：二叉树遍历方式有深度优先和广度优先，深度（纵向）优先在Python中一般使用列表，广度优先（横向）一般使用迭代

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def mergeTrees(self, t1, t2):
        """
        :type t1: TreeNode
        :type t2: TreeNode
        :rtype: TreeNode
        """
        if t1 is None and t2 is None:
            return
        if t1 is None:
            return t2
        if t2 is None:
            return t1
        t1.val += t2.val
        t1.right = self.mergeTrees(t1.right, t2.right)
        t1.left = self.mergeTrees(t1.left, t2.left)
        return t1

总结

此题做时没有理解这个TreeNode类是怎么用的，看了答案才明白。
后来尝试了：

1
2
3
4
t1.right.val
>> 2
t1.left.left.val
>> 5

该答案应该是广度优先的迭代方法。