目录
1. 路径总和 II 🌟🌟
2. 两数相除 🌟🌟
3. 不同的二叉搜索树 II 🌟🌟
🌟 每日一练刷题专栏 🌟
Golang每日一练 专栏
Python每日一练 专栏
C/C++每日一练 专栏
Java每日一练 专栏
1. 路径总和 II
给你二叉树的根节点 root
和一个整数目标和 targetSum
,找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。
叶子节点 是指没有子节点的节点。
示例 1:
输入:root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22 输出:[[5,4,11,2],[5,8,4,5]]
示例 2:
输入:root = [1,2,3], targetSum = 5 输出:[]
示例 3:
输入:root = [1,2], targetSum = 0 输出:[]
提示:
- 树中节点总数在范围
[0, 5000]
内 -1000 <= Node.val <= 1000
-1000 <= targetSum <= 1000
出处:
https://edu.csdn.net/practice/25658336
代码:
from typing import List
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution:
def pathSum(self, root: TreeNode, sum: int) -> List[List[int]]:
pathvalue = 0
path = []
result = []
def preorder(node, pathvalue, sum, path, result):
if node == None:
return
pathvalue += node.val
path.append(node.val)
if pathvalue == sum and node.left == None and node.right == None:
result.append(list(path)) # 注意加list
preorder(node.left, pathvalue, sum, path, result)
preorder(node.right, pathvalue, sum, path, result)
pathvalue -= node.val
path.pop()
preorder(root, pathvalue, sum, path, result)
return result
def listToTree(lst: List[int]) -> TreeNode:
if not lst:
return None
root = TreeNode(lst[0])
queue = [root]
i = 1
while i < len(lst):
node = queue.pop(0)
if lst[i] is not None:
node.left = TreeNode(lst[i])
queue.append(node.left)
i += 1
if i < len(lst) and lst[i] is not None:
node.right = TreeNode(lst[i])
queue.append(node.right)
i += 1
return root
#%%
s = Solution()
null = None
nums = [5,4,8,11,null,13,4,7,2,null,null,5,1]
root = listToTree(nums)
targetSum = 22
print(s.pathSum(root, targetSum))
输出:
[[5, 4, 11, 2], [5, 8, 4, 5]]
2. 两数相除
给定两个整数,被除数 dividend
和除数 divisor
。将两数相除,要求不使用乘法、除法和 mod 运算符。
返回被除数 dividend
除以除数 divisor
得到的商。
整数除法的结果应当截去(truncate
)其小数部分,例如:truncate(8.345) = 8
以及 truncate(-2.7335) = -2
示例 1:
输入: dividend = 10, divisor = 3 输出: 3 解释: 10/3 = truncate(3.33333..) = truncate(3) = 3
示例 2:
输入: dividend = 7, divisor = -3 输出: -2 解释: 7/-3 = truncate(-2.33333..) = -2
提示:
- 被除数和除数均为 32 位有符号整数。
- 除数不为 0。
- 假设我们的环境只能存储 32 位有符号整数,其数值范围是 [−2^31, 2^31 − 1]。本题中,如果除法结果溢出,则返回 231 − 1。
出处:
https://edu.csdn.net/practice/25658337
代码:
import math
class Solution(object):
def divide(self, dividend, divisor):
if divisor == 0:
return math.inf #MAX_INT
if dividend == 0:
return 0
isPositive = (dividend < 0) == (divisor < 0)
m = abs(dividend)
n = abs(divisor)
res = math.log(m) - math.log(n)
res = int(math.exp(res))
if isPositive:
return min(res, 2147483647)
return max(0 - res, -2147483648)
if __name__ == '__main__':
s = Solution()
print(s.divide(10, 3))
print(s.divide(7, -3))
print(s.divide(1, 0))
输出:
3
-2
inf
3. 不同的二叉搜索树 II
给你一个整数 n
,请你生成并返回所有由 n
个节点组成且节点值从 1
到 n
互不相同的不同 二叉搜索树 。可以按 任意顺序 返回答案。
示例 1:
输入:n = 3 输出:[[1,null,2,null,3],[1,null,3,2],[2,1,3],[3,1,null,null,2],[3,2,null,1]]
示例 2:
输入:n = 1 输出:[[1]]
提示:
1 <= n <= 8
出处:
https://edu.csdn.net/practice/25658338
代码:
class TreeNode(object):
def __init__(self, x):
self.val = x
self.left = None
self.right = None
def to_list(self, count):
queue = []
queue.append(self)
result = []
while len(queue) > 0:
if count == 0:
break
node = queue.pop(0)
if node is None:
result.append('null')
else:
count -= 1
result.append(node.val)
queue.append(node.left)
queue.append(node.right)
return result
class Solution(object):
def generateTrees(self, n):
"""
:type n: int
:rtype: List[TreeNode]
"""
if n == 0:
return []
return self.get_trees(1, n)
def get_trees_impl(self, start, end):
trees = []
if start > end:
trees.append(None)
return trees
for i in range(start, end + 1):
lefts = self.get_trees_impl(start, i - 1)
rights = self.get_trees_impl(i + 1, end)
for j in range(len(lefts)):
for k in range(len(rights)):
root = TreeNode(i)
root.left = lefts[j]
root.right = rights[k]
trees.append(root)
return trees
def get_trees(self, start, end):
trees = self.get_trees_impl(start, end)
results = []
for tree in trees:
if tree is None:
results.append([])
else:
results.append(tree.to_list(end))
return results
# %%
s = Solution()
print(s.generateTrees(n=3))
输出:
[[1, 'null', 2, 'null', 3], [1, 'null', 3, 2], [2, 1, 3], [3, 1, 'null', 'null', 2], [3, 2, 'null', 1]]
🌟 每日一练刷题专栏 🌟
✨ 持续,努力奋斗做强刷题搬运工!
👍 点赞,你的认可是我坚持的动力!
🌟 收藏,你的青睐是我努力的方向!
✎ 评论,你的意见是我进步的财富! 文章来源:https://www.toymoban.com/news/detail-414808.html
☸ 主页:https://hannyang.blog.csdn.net/文章来源地址https://www.toymoban.com/news/detail-414808.html
Golang每日一练 专栏 |
|
Python每日一练 专栏 |
|
C/C++每日一练 专栏 |
|
Java每日一练 专栏 |
到了这里,关于Python每日一练(20230415)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!