Python3刷题系列（四）

用户5473628

发布于 2019-08-08 14:53:25

3850

发布于 2019-08-08 14:53:25

文章被收录于专栏：MiningAlgorithmsMiningAlgorithms

一、哈希表：

1.Two Sum：

https://leetcode.com/problems/two-sum/

# python字典实现哈希表：
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        dict = {}
        for i in range(len(nums)):
            if nums[i] in dict:
                return [dict[nums[i]], i]
            dict[target - nums[i]] = i

2，Happy Number：

https://leetcode.com/problems/happy-number/

# 哈希表：
class Solution:
    def isHappy(self, n: int) -> bool:
        dict = {}
        while n != 1:
            n = sum(int(i) ** 2 for i in str(n))
            if n in dict:
                return False
            dict[n] = 1
        return True

二、二叉树：

1，Invert Binary Tree（翻转二叉树）

英文版：https://leetcode.com/problems/invert-binary-tree/

中文版：https://leetcode-cn.com/problems/invert-binary-tree/

# 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 not root:
            return root
        root.left, root.right = self.invertTree(root.right), self.invertTree(root.left)   # 递归
        return root

2，Maximum Depth of Binary Tree（二叉树的最大深度）

英文版：https://leetcode.com/problems/maximum-depth-of-binary-tree/

中文版：https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/

# 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 not root:
            return 0
        else:
            l = 1 + self.maxDepth(root.left)   # 递归
            r = 1 + self.maxDepth(root.right)
            return max(l, r)

3，Validate Binary Search Tree（验证二叉查找树）

英文版：https://leetcode.com/problems/validate-binary-search-tree/

中文版：https://leetcode-cn.com/problems/validate-binary-search-tree/

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

class Solution:
    def isValidBST(self, root: TreeNode) -> bool:
        if not root:
            return True
        
        pre = None
        stack = list()
        while root or stack:
            if root:
                stack.append(root)
                root = root.left
            else:
                root = stack.pop()
                if pre and root.val <= pre.val:
                    return False
                
                pre = root
                root = root.right
        return True

# reference:https://blog.csdn.net/qq_17550379/article/details/82315830

4，Path Sum（路径总和）

英文版：https://leetcode.com/problems/path-sum/

中文版：https://leetcode-cn.com/problems/path-sum/

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

class Solution:
    def hasPathSum(self, root: TreeNode, sum: int) -> bool:
        if root is None:
            return False
        if sum == root.val and root.left is None and root.right is None:
            return True
        return self.hasPathSum(root.left, sum - root.val) or self.hasPathSum(root.right, sum - root.val)   # 递归

本文参与腾讯云自媒体分享计划，分享自微信公众号。

原始发表：2019-04-18，如有侵权请联系 cloudcommunity@tencent.com 删除

https