[6-10]leetcode 461. 汉明距离 leetcod

461. 汉明距离

时间：2019年5月25日10:15:16
难度：简单
编号：6
进度：6/5 20/52
语言：python3

---

思路：先将两个数亦或，然后求得到的数字中有多少个1
代码：

class Solution:
    def hammingDistance(self, x: int, y: int) -> int:
        return bin(x^y).count('1')

执行用时 : 52 ms, 在Hamming Distance的Python3提交中击败了84.71% 的用户
内存消耗 : 13.2 MB, 在Hamming Distance的Python3提交中击败了57.90% 的用户

226. 翻转二叉树

时间：2019年5月25日16:27:13
难度：简单
编号：7
进度：7/5 20/52
语言：python3

---

思路：直接利用递归，可以利用python的小trick节约一行代码

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def invertTree(self, root: TreeNode) -> TreeNode:
        if root == None:
            return 
        root.left,root.right = self.invertTree(root.right), self.invertTree(root.left)
        return root

执行用时 : 52 ms, 在Invert Binary Tree的Python3提交中击败了89.89% 的用户
内存消耗 : 12.7 MB, 在Invert Binary Tree的Python3提交中击败了99.58% 的用户

617. 合并二叉树

时间：2019年5月25日16:53:08
难度：简单
编号：8
进度：8/5 20/52
语言：python3

---

思路：最简单的递归

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def mergeTrees(self, t1: TreeNode, t2: TreeNode) -> TreeNode:
        if t1 == None and t2 == None:
            return
        root = TreeNode(0)
        if t1 == None:
            return t2
        elif t2 == None:
            return  t1
        else:
            root.val = t1.val  + t2.val
            
            root.left = self.mergeTrees(t1.left,t2.left)        
            root.right = self.mergeTrees(t1.right,t2.right)
        return root

104. 二叉树的最大深度

时间：2019年5月25日17:07:49
难度：简单
编号：9
进度：9/5 20/52
语言：python3
类型：二叉树

---

思路：二叉树递归

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        if root == None:
            return 0
        if root.left ==None and root.right == None:
            return 1
        return max(0,self.maxDepth(root.left)+1,self.maxDepth(root.right)+1)
        

执行用时 : 72 ms, 在Maximum Depth of Binary Tree的Python3提交中击败了56.32% 的用户
内存消耗 : 14.9 MB, 在Maximum Depth of Binary Tree的Python3提交中击败了86.22% 的用户

942. 增减字符串匹配

时间：2019年05月27日16:18:37
难度：简单
编号：10
进度：1/5 21/52
语言：python3
类型：字符串

---

思路：双指针

class Solution:
    def diStringMatch(self, S: str) -> List[int]:
        start = 0
        end = len(S)
        ans = []
        for each in S:
            if each == 'I':
                ans.append(start)
                start +=1
            else:
                ans.append(end)
                end -=1
        ans.append(end)
        return ans

执行用时 : 112 ms, 在DI String Match的Python3提交中击败了80.57% 的用户
内存消耗 : 14.3 MB, 在DI String Match的Python3提交中击败了21.85% 的用户