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

谁借莪１个温暖的怀抱￠ 2022-06-13 05:44 78阅读 0赞

# Hamming Distance #

## 题目大意 ##

两个整数的汉明距离是指其二进制不相等的位的个数。  
给定两个整数x和y，计算汉明距离。  
注意：  
0 ≤ x, y < 2^31.

## 解题思路 ##

异或运算

## 代码 ##

class Solution(object):
        def hammingDistance(self, x, y):
            """
            :type x: int
            :type y: int
            :rtype: int
            """
            return bin(x ^ y).count('1')

## 我提交的 ##

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中一般使用列表，广度优先（横向）一般使用迭代

## 代码 ##

# 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类是怎么用的，看了答案才明白。  
后来尝试了：

t1.right.val
    >> 2
    t1.left.left.val
    >> 5

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