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/
