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

Python3刷题系列(九)

二叉搜索树中序遍历,前缀树,二分图,二叉树前序遍历,并查集,拓扑排序

目录:

1,Leetcode-230

2,Leetcode-208

3,Leetcode-785

4,Leetcode-144

5,Leetcode-513

6,Leetcode-684

7,Leetcode-207

8,Leetcode-110

1,Leetcode-230:

 # leetcode-230:二叉搜索树,中序遍历,beats 56.14%

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def kthSmallest(self, root: TreeNode, k: int) -> int:
        self.cnt, self.val = 0, 0
        self.inOrder(root, k)
        return self.val
    
    def inOrder(self, root: TreeNode, k: int):
        if not root:
            return
        self.inOrder(root.left, k)
        self.cnt += 1
        if self.cnt == k:
            self.val = root.val
            return
        self.inOrder(root.right, k)

2,Leetcode-208:

# leetcode-208: 字典树,前缀树,beats 39.87% 
class Node:
    def __init__(self):
        self.children = {}
        self.is_leaf = False

class Trie:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.root = Node()

    def insert(self, word: str) -> None:
        """
        Inserts a word into the trie.
        """
        node = self.root
        for c in word:
            if c not in node.children:
                node.children[c] = Node()
            node = node.children[c]
        node.is_leaf = True

    def search(self, word: str) -> bool:
        """
        Returns if the word is in the trie.
        """
        node = self.root
        for c in word:
            if c not in node.children:
                return False
            node = node.children[c]
        return node.is_leaf

    def startsWith(self, prefix: str) -> bool:
        """
        Returns if there is any word in the trie that starts with the given prefix.
        """
        node = self.root
        for c in prefix:
            if c not in node.children:
                return False
            node = node.children[c]
        return True


# Your Trie object will be instantiated and called as such:
# obj = Trie()
# obj.insert(word)
# param_2 = obj.search(word)
# param_3 = obj.startsWith(prefix)

3,Leetcode-785:

# leetcode-785:二分图:beats 80.75%
class Solution:
    def isBipartite(self, graph: List[List[int]]) -> bool:
        colors = [-1] * len(graph)
        for i in range(len(graph)):
            if colors[i] == -1 and not self.dfs(i, 0, colors, graph):
                return False
        return True
    
    def dfs(self, cur_node, cur_color, colors, graph):
        if colors[cur_node] != -1:
            return colors[cur_node] == cur_color
        
        colors[cur_node] = cur_color
        for next_node in graph[cur_node]:
            if not self.dfs(next_node, 1-cur_color, colors, graph):
                return False
        return True

4,Leetcode-144:

# leetcode-144:二叉树前序遍历

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:  # 递归写法,beats 12.29%
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        result = []
        if not root:
            return result
        result.append(root.val)
        result += self.preorderTraversal(root.left)
        result += self.preorderTraversal(root.right)
        return result


class Solution:  # 非递归写法,beats 84.21%
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        result = []
        s = []
        if not root:
            return result
        s.append(root)
        while s:
            root = s.pop()
            result.append(root.val)
            if root.right:
                s.append(root.right)
            if root.left: 
                s.append(root.left) 
        return result

5,Leetcode-513:

# leetcode-513:查找树的左下角值,beats  88.92%
class Solution:
    def findBottomLeftValue(self, root: TreeNode) -> int:
     q = [root]
      while q:
        root = q.pop(0)
        if root.right:
          q.append(root.right)
        if root.left:
          q.append(root.left)
      return root.val

6,Leetcode-684------并查集

# leetcode-684:并查集,beats  5.42%
class UnionFind:
    def __init__(self, n):
        self.ids = []
        for i in range(n+1):
            self.ids.append(i)
            
    def union(self, u, v):
        u_id = self.find(u)
        v_id = self.find(v)
        if u_id == v_id:
            return
        for i in range(len(self.ids)):
            if self.ids[i] == u_id:
                self.ids[i] = v_id
    
    def find(self, p):
        return self.ids[p]
    
    def connect(self, u, v):
        return self.find(u) == self.find(v)
                
    
class Solution:    
    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:
        uf = UnionFind(len(edges))
        for e in edges:
            u, v = e[0], e[1]
            if uf.connect(u, v):
                return u, v
            uf.union(u, v)
        return -1, -1

7,Leetcode-207:

# leetcode-207:拓扑排序,beats 90.89%
class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        graphic = [[] for i in range(numCourses)]
        for pre in prerequisites:
            graphic[pre[0]].append(pre[1])
        visited = [0]*numCourses
        for i in range(numCourses):
            if self.exist_cycle(visited, graphic, i):
                return False
        return True
    
    def exist_cycle(self, visited, graphic, cur_node):
        if visited[cur_node] == 1:
            return True
        if visited[cur_node] == 2:
            return False
        visited[cur_node] = 1
        for next_node in graphic[cur_node]:
            if self.exist_cycle(visited, graphic, next_node):
                return True
        visited[cur_node] = 2
        return False

8,Leetcode-110:

# leetcode-110:平衡二叉树
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:  # beats 19.84%
    def isBalanced(self, root: TreeNode) -> bool:
        if root is None:
            return True
        left_height = self.getHeight(root.left)
        right_height = self.getHeight(root.right)
        if abs(left_height - right_height) > 1:
            return False
        return self.isBalanced(root.left) and self.isBalanced(root.right)
    
    def getHeight(self, root: TreeNode) -> int:
        if root is None:
            return 0
        left_height = self.getHeight(root.left)
        right_height = self.getHeight(root.right)
        return max(left_height, right_height) +1


class Solution:  # 这个解决方案的逻辑错误点在哪?
    def _maxDepth(self, node: TreeNode) -> int:
        if (not node):
            return 0
        left_depth = self._maxDepth(node.left)
        right_depth = self._maxDepth(node.right)
        return max(left_depth, right_depth) + 1

    def _minDepth(self, node: TreeNode) -> int:
        if (not node):
            return 0
        left_depth = self._minDepth(node.left)
        right_depth = self._minDepth(node.right)
        return min(left_depth, right_depth) + 1
    
    def isBalanced(self, root: TreeNode) -> bool:
        return (self._maxDepth(root) - self._minDepth(root)) <= 1

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

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

原始发表时间:2019-05-13

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 【算法基础】java 排序算法

    思路:依次比较相邻的两个数,将小数放在前面,大数放在后面。即在第一趟:首先比较第1个和第2个数,将小数放前,大数放后。然后比较第2个数和第3个数,将小数放前,大...

    用户5640963
  • Nginx proxy_set_header 理解

    用户认证接口:根据客户端IP和port,进行IP反查和端口范围确认,如符合则用户认证通过。 当前使用的是Nginx负载均衡,从客户端到Nginx端 ip和po...

    用户5640963
  • 安卓求职者的秋招总结,感谢牛客网,感谢牛友们

    楼主秋招投的是安卓岗,今年安卓确实比较好找工作,就我来说吧,给了面试机会的基本都拿到offer了(可见面的不多),知名一点的是网易,美团,头条,还有两个是贝壳,...

    牛客网
  • handler模块(100%)

    相信大家在看了前一章的模块概述以后,都对nginx的模块有了一个基本的认识。基本上作为第三方开发者最可能开发的就是三种类型的模块,即handler,filter...

    用户5640963
  • nginx proxy_set_header设置、自定义header

    允许重新定义或者添加发往后端服务器的请求头。value可以包含文本、变量或者它们的组合。 当且仅当当前配置级别中没有定义proxy_set_header指令时,...

    用户5640963
  • NGINX 配置文件 fastcgi_pass

    语法:fastcgi_pass fastcgi-server 默认值:none 使用字段:http, server, location 指定FastCGI...

    用户5640963
  • 002.SMB安装与端口

    木二
  • 面试官:mybatis你只写了接口为啥就能执行sql啊?

    又是一年毕业季,很多小伙伴开始去大城市打拼。来大城市第一件事就是租房,免不了和中介打交道,因为很多房东很忙,你根本找不到他。从这个场景中就可以抽象出来代理模式

    纯洁的微笑
  • Java:前程似锦的 NIO 2.0

    Java 之所以能够霸占编程语言的榜首,其强大、丰富的类库功不可没,几乎所有的编程问题都能在其中找到解决方案。但在早期的版本当中,输入输出(I/O)流并不那么令...

    纯洁的微笑
  • 001.RAID简介

    独立磁盘冗余数组(RAID, Redundant Array of Independent Disks),旧称廉价磁盘冗余数组(RAID,Redundant A...

    木二

扫码关注云+社区

领取腾讯云代金券