Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit3e79203

Browse files
committed
add new solution
1 parent8cdb2ed commit3e79203

8 files changed

+525
-2
lines changed
Lines changed: 100 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,100 @@
1+
# 实现一个二叉搜索树迭代器类BSTIterator ，表示一个按中序遍历二叉搜索树（BST）的迭代器：
2+
#
3+
#
4+
#
5+
# BSTIterator(TreeNode root) 初始化 BSTIterator 类的一个对象。BST 的根节点 root 会作为构造函数的一部分给出
6+
# 。指针应初始化为一个不存在于 BST 中的数字，且该数字小于 BST 中的任何元素。
7+
# boolean hasNext() 如果向指针右侧遍历存在数字，则返回 true ；否则返回 false 。
8+
# int next()将指针向右移动，然后返回指针处的数字。
9+
#
10+
#
11+
# 注意，指针初始化为一个不存在于 BST 中的数字，所以对 next() 的首次调用将返回 BST 中的最小元素。
12+
#
13+
#
14+
#
15+
# 你可以假设 next() 调用总是有效的，也就是说，当调用 next() 时，BST 的中序遍历中至少存在一个下一个数字。
16+
#
17+
#
18+
#
19+
# 示例：
20+
#
21+
#
22+
# 输入
23+
# ["BSTIterator", "next", "next", "hasNext", "next", "hasNext", "next", "hasNext
24+
# ", "next", "hasNext"]
25+
# [[[7, 3, 15, null, null, 9, 20]], [], [], [], [], [], [], [], [], []]
26+
# 输出
27+
# [null, 3, 7, true, 9, true, 15, true, 20, false]
28+
#
29+
# 解释
30+
# BSTIterator bSTIterator = new BSTIterator([7, 3, 15, null, null, 9, 20]);
31+
# bSTIterator.next(); // 返回 3
32+
# bSTIterator.next(); // 返回 7
33+
# bSTIterator.hasNext(); // 返回 True
34+
# bSTIterator.next(); // 返回 9
35+
# bSTIterator.hasNext(); // 返回 True
36+
# bSTIterator.next(); // 返回 15
37+
# bSTIterator.hasNext(); // 返回 True
38+
# bSTIterator.next(); // 返回 20
39+
# bSTIterator.hasNext(); // 返回 False
40+
#
41+
#
42+
#
43+
#
44+
# 提示：
45+
#
46+
#
47+
# 树中节点的数目在范围 [1, 105] 内
48+
# 0 <= Node.val <= 106
49+
# 最多调用 105 次 hasNext 和 next 操作
50+
#
51+
#
52+
#
53+
#
54+
# 进阶：
55+
#
56+
#
57+
# 你可以设计一个满足下述条件的解决方案吗？next() 和 hasNext() 操作均摊时间复杂度为 O(1) ，并使用 O(h) 内存。其中 h 是树的高
58+
# 度。
59+
#
60+
# Related Topics 栈 树 设计 二叉搜索树 二叉树 迭代器
61+
# 👍 620 👎 0
62+
63+
64+
# leetcode submit region begin(Prohibit modification and deletion)
65+
# Definition for a binary tree node.
66+
# class TreeNode:
67+
# def __init__(self, val=0, left=None, right=None):
68+
# self.val = val
69+
# self.left = left
70+
# self.right = right
71+
classBSTIterator:
72+
73+
def__init__(self,root:TreeNode):
74+
self.root=root
75+
self.stack= []
76+
whileself.root:
77+
self.stack.append(self.root)
78+
self.root=self.root.left
79+
80+
defnext(self)->int:
81+
node=self.stack.pop()
82+
root=node.right
83+
whileroot:
84+
self.stack.append(root)
85+
root=root.left
86+
returnnode.val
87+
88+
defhasNext(self)->bool:
89+
ifself.stack:
90+
returnTrue
91+
else:
92+
returnFalse
93+
94+
95+
96+
# Your BSTIterator object will be instantiated and called as such:
97+
# obj = BSTIterator(root)
98+
# param_1 = obj.next()
99+
# param_2 = obj.hasNext()
100+
# leetcode submit region end(Prohibit modification and deletion)

‎script/[437]路径总和 III.py

Lines changed: 68 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,68 @@
1+
# 给定一个二叉树的根节点 root ，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的 路径 的数目。
2+
#
3+
# 路径 不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。
4+
#
5+
#
6+
#
7+
# 示例 1：
8+
#
9+
#
10+
#
11+
#
12+
# 输入：root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8
13+
# 输出：3
14+
# 解释：和等于 8 的路径有 3 条，如图所示。
15+
#
16+
#
17+
# 示例 2：
18+
#
19+
#
20+
# 输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
21+
# 输出：3
22+
#
23+
#
24+
#
25+
#
26+
# 提示:
27+
#
28+
#
29+
# 二叉树的节点个数的范围是 [0,1000]
30+
# -109 <= Node.val <= 109
31+
# -1000 <= targetSum <= 1000
32+
#
33+
# Related Topics 树 深度优先搜索 二叉树
34+
# 👍 1398 👎 0
35+
36+
37+
# leetcode submit region begin(Prohibit modification and deletion)
38+
# Definition for a binary tree node.
39+
# class TreeNode:
40+
# def __init__(self, val=0, left=None, right=None):
41+
# self.val = val
42+
# self.left = left
43+
# self.right = right
44+
classSolution:
45+
defpathSum(self,root:Optional[TreeNode],targetSum:int)->int:
46+
defhelper(root,targetSum):
47+
ifnotroot:
48+
return0
49+
# 注意这里不要返回因为在node.val可能<0
50+
iftargetSum==root.val:
51+
mid=1
52+
else:
53+
mid=0
54+
left=helper(root.left,targetSum-root.val)
55+
right=helper(root.right,targetSum-root.val)
56+
returnleft+right+mid
57+
58+
defdfs(root,target):
59+
ifnotroot:
60+
return0
61+
left=dfs(root.left,target)
62+
right=dfs(root.right,target)
63+
mid=helper(root,target)
64+
returnleft+right+mid
65+
returndfs(root,targetSum)
66+
67+
68+
# leetcode submit region end(Prohibit modification and deletion)
Lines changed: 79 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,79 @@
1+
# 给定一个二叉树的根 root 和两个整数 val 和 depth ，在给定的深度 depth 处添加一个值为 val 的节点行。
2+
#
3+
# 注意，根节点 root 位于深度 1 。
4+
#
5+
# 加法规则如下:
6+
#
7+
#
8+
# 给定整数 depth，对于深度为 depth - 1 的每个非空树节点 cur ，创建两个值为 val 的树节点作为 cur 的左子树根和右子树根。
9+
# cur 原来的左子树应该是新的左子树根的左子树。
10+
# cur 原来的右子树应该是新的右子树根的右子树。
11+
# 如果 depth == 1 意味着 depth - 1 根本没有深度，那么创建一个树节点，值 val 作为整个原始树的新根，而原始树就是新根的左子树。
12+
#
13+
#
14+
#
15+
#
16+
# 示例 1:
17+
#
18+
#
19+
#
20+
#
21+
# 输入: root = [4,2,6,3,1,5], val = 1,
22+
#
23+
# depth = 2
24+
# 输出: [4,1,1,2,null,null,6,3,1,5]
25+
#
26+
# 示例 2:
27+
#
28+
#
29+
#
30+
#
31+
# 输入: root = [4,2,null,3,1], val = 1, depth = 3
32+
# 输出: [4,2,null,1,1,3,null,null,1]
33+
#
34+
#
35+
#
36+
#
37+
# 提示:
38+
#
39+
#
40+
# 节点数在 [1, 104] 范围内
41+
# 树的深度在 [1, 104]范围内
42+
# -100 <= Node.val <= 100
43+
# -105 <= val <= 105
44+
# 1 <= depth <= the depth of tree + 1
45+
#
46+
# Related Topics 树 深度优先搜索 广度优先搜索 二叉树
47+
# 👍 122 👎 0
48+
49+
50+
# leetcode submit region begin(Prohibit modification and deletion)
51+
# Definition for a binary tree node.
52+
# class TreeNode:
53+
# def __init__(self, val=0, left=None, right=None):
54+
# self.val = val
55+
# self.left = left
56+
# self.right = right
57+
classSolution:
58+
defaddOneRow(self,root:TreeNode,val:int,depth:int)->TreeNode:
59+
defdfs(root,depth):
60+
ifnotroot:
61+
returnNone
62+
ifdepth==1:
63+
node=TreeNode(val)
64+
node.left=root
65+
returnnode
66+
ifdepth==2:
67+
left=TreeNode(val)
68+
right=TreeNode(val)
69+
left.left=root.left
70+
right.right=root.right
71+
root.left=left
72+
root.right=right
73+
returnroot
74+
root.left=dfs(root.left,depth-1)
75+
root.right=dfs(root.right,depth-1)
76+
returnroot
77+
returndfs(root,depth )
78+
79+
# leetcode submit region end(Prohibit modification and deletion)

‎script/[62]不同路径.py

Lines changed: 64 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,64 @@
1+
# 一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
2+
#
3+
# 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
4+
#
5+
# 问总共有多少条不同的路径？
6+
#
7+
#
8+
#
9+
# 示例 1：
10+
#
11+
#
12+
# 输入：m = 3, n = 7
13+
# 输出：28
14+
#
15+
# 示例 2：
16+
#
17+
#
18+
# 输入：m = 3, n = 2
19+
# 输出：3
20+
# 解释：
21+
# 从左上角开始，总共有 3 条路径可以到达右下角。
22+
# 1. 向右 -> 向下 -> 向下
23+
# 2. 向下 -> 向下 -> 向右
24+
# 3. 向下 -> 向右 -> 向下
25+
#
26+
#
27+
# 示例 3：
28+
#
29+
#
30+
# 输入：m = 7, n = 3
31+
# 输出：28
32+
#
33+
#
34+
# 示例 4：
35+
#
36+
#
37+
# 输入：m = 3, n = 3
38+
# 输出：6
39+
#
40+
#
41+
#
42+
# 提示：
43+
#
44+
#
45+
# 1 <= m, n <= 100
46+
# 题目数据保证答案小于等于 2 * 109
47+
#
48+
# Related Topics 数学 动态规划 组合数学
49+
# 👍 1468 👎 0
50+
51+
52+
# leetcode submit region begin(Prohibit modification and deletion)
53+
classSolution:
54+
defuniquePaths(self,m:int,n:int)->int:
55+
dp= [[0]*nforiinrange(m)]
56+
foriinrange(n):
57+
dp[0][i]=1
58+
foriinrange(m):
59+
dp[i][0]=1
60+
foriinrange(1,m):
61+
forjinrange(1,n):
62+
dp[i][j]=dp[i-1][j]+dp[i][j-1]
63+
returndp[-1][-1]
64+
# leetcode submit region end(Prohibit modification and deletion)

‎script/[63]不同路径 II.py

Lines changed: 63 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,63 @@
1+
# 一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
2+
#
3+
# 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish”）。
4+
#
5+
# 现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？
6+
#
7+
# 网格中的障碍物和空位置分别用 1 和 0 来表示。
8+
#
9+
#
10+
#
11+
# 示例 1：
12+
#
13+
#
14+
# 输入：obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
15+
# 输出：2
16+
# 解释：3x3 网格的正中间有一个障碍物。
17+
# 从左上角到右下角一共有 2 条不同的路径：
18+
# 1. 向右 -> 向右 -> 向下 -> 向下
19+
# 2. 向下 -> 向下 -> 向右 -> 向右
20+
#
21+
#
22+
# 示例 2：
23+
#
24+
#
25+
# 输入：obstacleGrid = [[0,1],[0,0]]
26+
# 输出：1
27+
#
28+
#
29+
#
30+
#
31+
# 提示：
32+
#
33+
#
34+
# m == obstacleGrid.length
35+
# n == obstacleGrid[i].length
36+
# 1 <= m, n <= 100
37+
# obstacleGrid[i][j] 为 0 或 1
38+
#
39+
# Related Topics 数组 动态规划 矩阵
40+
# 👍 838 👎 0
41+
42+
43+
# leetcode submit region begin(Prohibit modification and deletion)
44+
classSolution:
45+
defuniquePathsWithObstacles(self,obstacleGrid:List[List[int]])->int:
46+
m=len(obstacleGrid)
47+
n=len(obstacleGrid[0])
48+
dp= [[0]*nforiinrange(m)]
49+
foriinrange(n):
50+
ifobstacleGrid[0][i]==1:
51+
break
52+
dp[0][i]=1
53+
foriinrange(m):
54+
ifobstacleGrid[i][0]==1:
55+
break
56+
dp[i][0]=1
57+
foriinrange(1,m):
58+
forjinrange(1,n):
59+
ifobstacleGrid[i][j]==1:
60+
continue
61+
dp[i][j]=dp[i-1][j]+dp[i][j-1]
62+
returndp[-1][-1]
63+
# leetcode submit region end(Prohibit modification and deletion)

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp