Leetcode 算法面试冲刺 热题 HOT 100 刷题（85 94 96 98 101）（五十九）

news/2024/7/8 10:04:02 标签: 算法, leetcode, 面试

文章目录

  • 85. 最大矩形
  • 94. 二叉树的中序遍历
  • 96. 不同的二叉搜索树
  • 98. 验证二叉搜索树
  • 101. 对称二叉树

85. 最大矩形

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

94. 二叉树的中序遍历

在这里插入图片描述
在这里插入图片描述
简单题

def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        if not root: return []
        res = []
        def dfs(root, res):
            if not root: return 
            if root.left:
                dfs(root.left, res)
            res.append(root.val)
            if root.right:
                dfs(root.right, res)
        dfs(root, res)
        return res

在这里插入图片描述

96. 不同的二叉搜索树

在这里插入图片描述
不会
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

const numTrees = (n) => {
  const dp = new Array(n + 1).fill(0);
  dp[0] = 1;
  dp[1] = 1;
  for (let i = 2; i <= n; i++) {
    for (let j = 0; j <= i - 1; j++) {
      dp[i] += dp[j] * dp[i - j - 1];
    }
  }
  return dp[n];
};

照着答案写的：

class Solution:
    def numTrees(self, n: int) -> int:
        dp = [0] * (n + 1)
        dp[0] = 1
        dp[1] = 1
        for i in range(2, n + 1):
            for j in range(i):
                if j <= i - 1:
                    dp[i] += dp[j] * dp[i - 1 - j]
        return dp[n]

在这里插入图片描述
第二遍：
在这里插入图片描述
写出来了，我觉得要把边界情况想明白并不容易。

class Solution:
    def numTrees(self, n: int):
        dp = [0] * (n + 1)
        dp[0] = dp[1] = 1
        for i in range(2, n + 1):
            for j in range(0, i):
                dp[i] += dp[j] * dp[i - 1 - j]
        return dp[-1]

在这里插入图片描述

98. 验证二叉搜索树

在这里插入图片描述
在这里插入图片描述
最简单的想法就是dfs遍历，然后如果是升序的数组，就是BST。但是遇到了[2, 2, 2]然后发现过不了，加了一个set就过了。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        if not root: return
        res = []
        def dfs(root):
            if not root:
                return
            if root.left:
                dfs(root.left)
            res.append(root.val)
            if root.right:
                dfs(root.right)
        dfs(root)
        return res == sorted(set(res))

在这里插入图片描述
答案：
在这里插入图片描述

class Solution:
    def isValidBST(self, root: TreeNode) -> bool:
        stack, inorder = [], float('-inf')
        
        while stack or root:
            while root:
                stack.append(root)
                root = root.left
            root = stack.pop()
            # 如果中序遍历得到的节点的值小于等于前一个 inorder，说明不是二叉搜索树
            if root.val <= inorder:
                return False
            inorder = root.val
            root = root.right

        return True

第二遍：还是没写对

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isValidBST(self, root) -> bool:
        def dfs(root):
            if not root:
                return True
            if root.left:
                if root.left.val > root.val:
                    return False
                return dfs(root.left)
            if root.right:
                if root.right.val < root.val:
                    return False
                return dfs(root.right)
            return True
        if root.left:
            if root.left.val >= root.val:
                return False
        if root.right:
            if root.right.val <= root.val:
                return False
        return dfs(root.left) and dfs(root.right)

看到了一个答案：
在这里插入图片描述
官方答案：
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
按照答案写出来的，来需要在看。。。。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isValidBST(self, root):
        def dfs(root, lower, upper):
            if not root:
                return True
            val = root.val
            if lower != None and root.val <= lower:
                return False
            if upper != None and root.val >= upper:
                return False
            if not dfs(root.left, lower, val): return False
            if not dfs(root.right, val, upper): return False
            return True
        return dfs(root, None, None)

101. 对称二叉树

在这里插入图片描述
在这里插入图片描述
尝试写了一下，没写对。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isSymmetric(self, root: Optional[TreeNode]) -> bool:
        def helper(root):
            if not root.left and not root.right:
                return
            if root.left and root.right:
                if root.left.val == root.right.val:
                    return helper(root.left) and helper(root.right)
                else:
                    return False
            else:
                return False
        return helper(root)

下面是答案：
在这里插入图片描述
在这里插入图片描述

class Solution {
public:
    bool check(TreeNode *p, TreeNode *q) {
        if (!p && !q) return true;
        if (!p || !q) return false;
        return p->val == q->val && check(p->left, q->right) && check(p->right, q->left);
    }

    bool isSymmetric(TreeNode* root) {
        return check(root, root);
    }
};

根据答案写的：

def isSymmetric(self, root: Optional[TreeNode]) -> bool:
        if not root: return True

        def dfs(root1, root2):
            if not root1 and not root2:
                return True
            if not root1 or not root2:
                return False
            return root1.val == root2.val and dfs(root1.left, root2.right) and dfs(root1.right, root2.left)
        return dfs(root.left, root.right)

在这里插入图片描述
想了BFS是可以实现的，DFS，还是不会写。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isSymmetric(self, root):
        def preorder(root, flag, pth):
            if not root:
                return pth[:]
            pth.append(root.val)
            if flag:
                if root.left:
                    preorder(root.left, flag, pth)
                if root.right:
                    preorder(root.right, flag, pth)
            else:
                if root.right:
                    preorder(root.right, flag, pth)
                if root.left:
                    preorder(root.left, flag, pth)

        pth1 = preorder(root.left, True, [])
        pth2 = preorder(root.right, False, [])
        print(pth1)
        print(pth2)

看答案写了一遍，是觉得真简单，但是自己想不到。。。。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isSymmetric(self, root):
        def dfs(root1, root2):
            if not root1 and not root2:
                return True
            if not root1 or not root2:
                return False
            if root1.val != root2.val:
                return False
            return dfs(root1.left, root2.right) and dfs(root1.right, root2.left)
        return dfs(root.left, root.right)

在这里插入图片描述


http://www.niftyadmin.cn/n/1207620.html

相关文章

ifcfg、ip、ss，配置文件

ifcfg、ip、ss，配置文件

ifcfg、ip、ss&#xff0c;配置文件一、ifcfg1、ifconfig命令&#xff1a;命令使用格式&#xff1a;ifonfig [INTERFACE]#ifconfig -a :显示所有接口&#xff0c;包括inactive状态的接口ifconfig interface [aftype] options | address..#ifconfig IFACE IP/MASK [up|down]例&a…
阅读更多...
Leetcode 算法面试冲刺 热题 HOT 100 刷题（102 104 105 114 121）（六十）

Leetcode 算法面试冲刺 热题 HOT 100 刷题（102 104 105 114 121）（六十）

文章目录102. 二叉树的层序遍历104. 二叉树的最大深度105. 从前序与中序遍历序列构造二叉树114. 二叉树展开为链表121. 买卖股票的最佳时机102. 二叉树的层序遍历 # Definition for a binary tree node. # class TreeNode: # def __init__(self, val0, leftNone, rightNone…
阅读更多...
二维码显示要求

二维码显示要求

1&#xff1a;鼠标挪到二维码时能正常显示 2&#xff1a;显示的速度 3&#xff1a;抽象出一个方法转载于:https://www.cnblogs.com/lxq0924/p/5082619.html
阅读更多...
Leetcode 算法面试冲刺 热题 HOT 100 刷题（124 128 136 139 141）（六十一）

Leetcode 算法面试冲刺 热题 HOT 100 刷题（124 128 136 139 141）（六十一）

文章目录124. 二叉树中的最大路径和128. 最长连续序列136. 只出现一次的数字139. 单词拆分141. 环形链表124. 二叉树中的最大路径和 困难题&#xff0c;我先跳过。 128. 最长连续序列 不会。 class Solution {public int longestConsecutive(int[] nums) {Set<Integer&…
阅读更多...
自定义颜色清屏

自定义颜色清屏

openGL默认情况下清屏将RGB分量清零&#xff0c;所以屏幕变成黑色。采用如下的函数&#xff1a;glClear(GL_COLOR_BUFFER_BIT)。当然可以自定义清屏的颜色&#xff0c;采用如下的函数&#xff1a;glClearColor(1.0f, 0.0f, 0.0f, 0.0f)&#xff0c; 将屏幕渲染成红色void myDis…
阅读更多...
目标检测 Chapter1 传统目标检测方法

目标检测 Chapter1 传统目标检测方法

文章目录目标检测问题定义介绍目标检测和图像分类、图像分割的区别目标检测问题方法传统目标检测深度学习目标检测传统 Vs 深度学习传统目标检测综述Viola-JonesHOGSVMDPMNMS 非极大值抑制目标检测问题定义 介绍 目标种类与数量问题&#xff1a;种类不同。种类越多&#xff0c…
阅读更多...
maven ClassNotFoundException: org.springframework.web.context.ContextLoader

maven ClassNotFoundException: org.springframework.web.context.ContextLoader

信息: Starting Servlet Engine: Apache Tomcat/6.0.32 2012-3-31 9:39:40 org.apache.catalina.core.StandardContext listenerStart 严重: Error configuring application listener of class org.springframework.web.context.ContextLoaderListener java.lang.ClassNotFound…
阅读更多...
目标检测 CenterNet 模型原理与论文精读（一）

目标检测 CenterNet 模型原理与论文精读（一）

文章目录简介Backbone如何制作数据集的Ground TruthCenter的设置如何计算Loss总结简介 Faster R-CNN和RetinaNet都是基于Anchor机制的。 Faster R-CNN是需要RPN进行预选框的筛选&#xff0c;300个框左右。 RetinaNet是one-stage的方法&#xff0c;没有RPN&#xff0c;直接暴力枚…
阅读更多...
最新文章

Copyright @ 2022~2023