目录
1. 不同路径 🌟🌟
2. 戳气球 🌟🌟🌟
3. 验证二叉搜索树 🌟🌟
1. 不同路径
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
问总共有多少条不同的路径？
示例 1：
输入：m = 3, n = 7 输出：28
示例 2：
输入：m = 3, n = 2 输出：3 解释：从左上角开始，总共有 3 条路径可以到达右下角。 1. 向右 -> 向下 -> 向下 2. 向下 -> 向下 -> 向右 3. 向下 -> 向右 -> 向下
示例 3：
输入：m = 7, n = 3 输出：28
示例 4：
输入：m = 3, n = 3 输出：6
提示：
1 <= m, n <= 100- 题目数据保证答案小于等于
2 * 10^9
出处：
https://edu.csdn.net/practice/25223644
代码：
class Solution:
def uniquePaths(self, m, n):
"""
:type m: int
:type n: int
:rtype: int
"""
dmap = [[0] * n for _ in range(m)]
for i in range(m):
dmap[i][0] = 1
for j in range(n):
dmap[0][j] = 1
for i in range(1, m):
for j in range(1, n):
l = u = 0
if i-1 >= 0:
u = dmap[i-1][j]
if j-1>= 0:
l = dmap[i][j-1]
dmap[i][j] = l + u
return dmap[m-1][n-1]
# %%
s = Solution()
print(s.uniquePaths(m = 3, n = 7))
print(s.uniquePaths(m = 3, n = 2))
print(s.uniquePaths(m = 7, n = 3))
print(s.uniquePaths(m = 3, n = 3))
输出：
28
3
28
6
2. 戳气球
有 n 个气球，编号为0 到 n - 1，每个气球上都标有一个数字，这些数字存在数组 nums 中。
现在要求你戳破所有的气球。戳破第 i 个气球，你可以获得 nums[i - 1] * nums[i] * nums[i + 1] 枚硬币。 这里的 i - 1 和 i + 1 代表和 i 相邻的两个气球的序号。如果 i - 1或 i + 1 超出了数组的边界，那么就当它是一个数字为 1 的气球。
求所能获得硬币的最大数量。
示例 1：
输入：nums = [3,1,5,8] 输出：167 解释： nums = [3,1,5,8] --> [3,5,8] --> [3,8] --> [8] --> [] coins = 3*1*5 + 3*5*8 + 1*3*8 + 1*8*1 = 167
示例 2：
输入：nums = [1,5] 输出：10
提示：
n == nums.length1 <= n <= 5000 <= nums[i] <= 100
出处：
https://edu.csdn.net/practice/25223645
代码：
from typing import List
class Solution:
def maxCoins(self, nums: List[int]) -> int:
n=len(nums)+2
nums=[1]+nums+[1]
dp=[[0]*n for _ in range(n)]
for i in range(n-1,-1,-1):
for j in range(i,n):
if j-i>1:
for k in range(i+1,j):
dp[i][j]=max(dp[i][j],dp[i][k]+dp[k][j]+nums[i]*nums[k]*nums[j])
return dp[0][n-1]
# %%
s = Solution()
nums = [3,1,5,8]
print(s.maxCoins(nums))
nums = [1,5]
print(s.maxCoins(nums))输出：
167
10
3. 验证二叉搜索树
给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。
有效 二叉搜索树定义如下：
- 节点的左子树只包含 小于 当前节点的数。
- 节点的右子树只包含 大于 当前节点的数。
- 所有左子树和右子树自身必须也是二叉搜索树。
示例 1：
输入：root = [2,1,3] 输出：true
示例 2：
输入：root = [5,1,4,null,null,3,6] 输出：false 解释：根节点的值是 5 ，但是右子节点的值是 4 。
提示：
- 树中节点数目范围在
[1, 10^4]内 -2^31 <= Node.val <= 2^31 - 1
出处：
https://edu.csdn.net/practice/25223646
代码：
import sys
class TreeNode(object):
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class List2Tree(object):
def __init__(self, nums: list):
self.nums = nums
self.queue = []
if len(nums) == 1:
self.root = TreeNode(self.nums.pop(0))
else:
a = self.nums.pop(0)
b = self.nums.pop(0)
c = self.nums.pop(0)
self.root = TreeNode(a)
if b is not None:
self.root.left = TreeNode(b)
else:
self.root.left = b
if c is not None:
self.root.right = TreeNode(c)
else:
self.root.right = c
self.queue.append(self.root.left)
self.queue.append(self.root.right)
def convert(self):
while len(self.nums) > 0 and len(self.queue)> 0:
node = self.queue.pop(0)
if node is not None:
num= self.nums.pop(0)
if num is not None:
node.left = TreeNode(num)
else:
node.left = num
if len(self.nums) > 0:
num = self.nums.pop(0)
else:
num = None
if num is not None:
node.right = TreeNode(num)
else:
node.right = num
self.queue.append(node.left)
self.queue.append(node.right)
return self.root
class Solution(object):
def isValidBST(self, root):
root = List2Tree(root).convert()
return self.isVaild_helper(root, -sys.maxsize - 1, sys.maxsize)
def isVaild_helper(self, root, minVal, maxVal):
if root is None:
return True
if root.val >= maxVal or root.val <= minVal:
return False
return self.isVaild_helper(root.left, minVal, root.val) and self.isVaild_helper(root.right, root.val, maxVal)
# %%
s = Solution()
print(s.isValidBST([2,1,3]))
print(s.isValidBST([5,1,4,None,None,3,6]))
输出：
True
False
🌟 每日一练刷题专栏 🌟
✨ 持续，努力奋斗做强刷题搬运工！
👍 点赞，你的认可是我坚持的动力！
🌟 收藏，你的青睐是我努力的方向！
✎ 评论，你的意见是我进步的财富！
☸ 主页：https://hannyang.blog.csdn.net/