专栏首页MiningAlgorithmsPython3刷题系列(四)

Python3刷题系列(四)

一、哈希表:

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)   # 递归

本文分享自微信公众号 - MiningAlgorithms(gh_d0cc50d1ed34)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-04-18

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • JSONObject put,accumulate,element的区别

    public Object put (Object key, Object value) 将value映射到key下。如果此JSONObject对象之前存在一个...

    用户5640963
  • Json(Json-lib)中使用JSONObject.toBean(JSONObject jsonObject, Class beanClass)日期保存了当前时间

    1、问题:使用Json-lib,转换数据的方法JSONObject.toBean(JSONObject jsonObject, Class beanClass)...

    用户5640963
  • springmvc整合axis2 过程

    项目需要使用springmvc发布一个对外的服务,原来使用spring+cxf的结合,使用axis2的客户端调用,没有任何问题,但是使用pb9的客户端调用,一直...

    用户5640963
  • 【ionic+angularjs】angularjs ui-router路由简介($urlRouter、$state、$stateProvider、ui-sref....)

    之前有写过一篇关于Angular自带的路由:ngRoute。今天来说说Angular的第三方路由:ui-router。那么有人就会问:为什么Ang...

    用户5640963
  • 001.常见监控简介

    主动模式:客户端主动上报数据到服务器端,对服务器的开销较小,适合大规模的监控环境。

    木二
  • c# 利用AForge.NET组件操作摄像头

    private FilterInfoCollection videoDevices;

    用户5640963
  • linux应用之wget命令详解

    wget是linux最常用的下载命令, 一般的使用方法是: wget + 空格 + 要下载文件的url路径

    用户5640963
  • Liunx命令行:vi详解

    进入vi的命令 vi filename :打开或新建文件,并将光标置于第一行首 vi +n filename :打开文件,并将光标置于第n行首 vi + ...

    用户5640963
  • JSONObject.fromObject 转换JSON字符串Map及javabean时间处理的问题

    这几天的项目开发过程中遇到一个比较棘手的问题,主要是通用导出类中,使用了一个javabean转换成json字符串的问题,javabean中一个日期格式是“yyy...

    用户5640963
  • webuploader java版本

    网上一些webuploader上传的资料,有php版和java版本的,做了一下整合,现分享以下成果,可以讨论,不喜勿碰。说一下过程。

    用户5640963

扫码关注云+社区

领取腾讯云代金券