【Leetcode】【python】Hamming Distance, Merge Two Binary Trees
【Leetcode】【python】Hamming Distance, Merge Two Binary Trees
蛮三刀酱
发布于 2019-03-26 17:07:36
发布于 2019-03-26 17:07:36
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该答案应该是广度优先的迭代方法。
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2017年06月29日，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录