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

Commit7119b6c

Browse files
authored
Merge branch 'youngyangyang04:master' into master
2 parentsf539571 +feb42c6 commit7119b6c

File tree

3 files changed

+107
-3
lines changed

3 files changed

+107
-3
lines changed

‎problems/0108.将有序数组转换为二叉搜索树.md

Lines changed: 71 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -209,6 +209,8 @@ public:
209209

210210

211211
Java：
212+
213+
递归: 左闭右开[left,right)
212214
```Java
213215
classSolution {
214216
publicTreeNodesortedArrayToBST(int[]nums) {
@@ -232,6 +234,75 @@ class Solution {
232234

233235
```
234236

237+
递归: 左闭右闭[left,right]
238+
```java
239+
classSolution {
240+
publicTreeNodesortedArrayToBST(int[]nums) {
241+
TreeNode root= traversal(nums,0, nums.length-1);
242+
return root;
243+
}
244+
245+
// 左闭右闭区间[left, right)
246+
privateTreeNodetraversal(int[]nums,intleft,intright) {
247+
if (left> right)returnnull;
248+
249+
int mid= left+ ((right- left)>>1);
250+
TreeNode root=newTreeNode(nums[mid]);
251+
root.left= traversal(nums, left, mid-1);
252+
root.right= traversal(nums, mid+1, right);
253+
return root;
254+
}
255+
}
256+
```
257+
迭代: 左闭右闭[left,right]
258+
```java
259+
classSolution {
260+
publicTreeNodesortedArrayToBST(int[]nums) {
261+
if (nums.length==0)returnnull;
262+
263+
//根节点初始化
264+
TreeNode root=newTreeNode(-1);
265+
Queue<TreeNode> nodeQueue=newLinkedList<>();
266+
Queue<Integer> leftQueue=newLinkedList<>();
267+
Queue<Integer> rightQueue=newLinkedList<>();
268+
269+
// 根节点入队列
270+
nodeQueue.offer(root);
271+
// 0为左区间下表初始位置
272+
leftQueue.offer(0);
273+
// nums.size() - 1为右区间下表初始位置
274+
rightQueue.offer(nums.length-1);
275+
276+
while (!nodeQueue.isEmpty()) {
277+
TreeNode currNode= nodeQueue.poll();
278+
int left= leftQueue.poll();
279+
int right= rightQueue.poll();
280+
int mid= left+ ((right- left)>>1);
281+
282+
// 将mid对应的元素给中间节点
283+
currNode.val= nums[mid];
284+
285+
// 处理左区间
286+
if (left<= mid-1) {
287+
currNode.left=newTreeNode(-1);
288+
nodeQueue.offer(currNode.left);
289+
leftQueue.offer(left);
290+
rightQueue.offer(mid-1);
291+
}
292+
293+
// 处理右区间
294+
if (right>= mid+1) {
295+
currNode.right=newTreeNode(-1);
296+
nodeQueue.offer(currNode.right);
297+
leftQueue.offer(mid+1);
298+
rightQueue.offer(right);
299+
}
300+
}
301+
return root;
302+
}
303+
}
304+
```
305+
235306
Python：
236307
```python3
237308
# Definition for a binary tree node.

‎problems/0115.不同的子序列.md

Lines changed: 34 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -186,6 +186,40 @@ class Solution:
186186
return dp[-1][-1]
187187
```
188188

189+
Python3:
190+
```python
191+
classSolutionDP2:
192+
"""
193+
既然dp[i]只用到dp[i - 1]的状态，
194+
我们可以通过缓存dp[i - 1]的状态来对dp进行压缩，
195+
减少空间复杂度。
196+
（原理等同同于滚动数组）
197+
"""
198+
199+
defnumDistinct(self,s:str,t:str) ->int:
200+
n1, n2=len(s),len(t)
201+
if n1< n2:
202+
return0
203+
204+
dp= [0for _inrange(n2+1)]
205+
dp[0]=1
206+
207+
for iinrange(1, n1+1):
208+
# 必须深拷贝
209+
# 不然prev[i]和dp[i]是同一个地址的引用
210+
prev= dp.copy()
211+
# 剪枝，保证s的长度大于等于t
212+
# 因为对于任意i，i > n1, dp[i] = 0
213+
# 没必要跟新状态。
214+
end= iif i< n2else n2
215+
for jinrange(1, end+1):
216+
if s[i-1]== t[j-1]:
217+
dp[j]= prev[j-1]+ prev[j]
218+
else:
219+
dp[j]= prev[j]
220+
return dp[-1]
221+
```
222+
189223
Go：
190224

191225

‎problems/周总结/20201003二叉树周末总结.md

Lines changed: 2 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -40,9 +40,8 @@ public:
4040
return isSame;
4141

4242
}
43-
boolisSymmetric(TreeNode* root) {
44-
if (root == NULL) return true;
45-
return compare(root->left, root->right);
43+
boolisSymmetric(TreeNode* p, TreeNode* q) {
44+
return compare(p, q);
4645
}
4746
};
4847
```

0 commit comments

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