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.length
1 <= n <= 500
0 <= 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/