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

Commit 1db81e1

Browse files
author
robot
committed
2 parents 304f7ea + a3e9d5c commit 1db81e1

File tree

4 files changed

+124
-7
lines changed

4 files changed

+124
-7
lines changed

‎problems/236.lowest-common-ancestor-of-a-binary-tree.md

Lines changed: 3 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -137,8 +137,10 @@ class Solution:
137137

138138
**复杂度分析**
139139

140+
令 h 为树的高度。
141+
140142
- 时间复杂度:$O(N)$
141-
- 空间复杂度:$O(N)$
143+
- 空间复杂度:$O(h)$
142144

143145
## 扩展
144146

‎problems/516.longest-palindromic-subsequence.md

Lines changed: 41 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -85,6 +85,11 @@ base case 就是一个字符(轴对称点是本身)
8585

8686
## 代码
8787

88+
代码支持:JS,Python3
89+
90+
91+
JS Code:
92+
8893
```js
8994
/*
9095
* @lc app=leetcode id=516 lang=javascript
@@ -116,10 +121,44 @@ var longestPalindromeSubseq = function (s) {
116121
};
117122
```
118123

124+
Python3 Code(记忆化递归):
125+
126+
```py
127+
class Solution:
128+
def longestPalindromeSubseq(self, s: str) -> int:
129+
@cache
130+
def dp(l,r):
131+
if l >= r: return int(l == r)
132+
if s[l] == s[r]:
133+
return 2 + dp(l+1,r-1)
134+
return max(dp(l+1, r), dp(l, r-1))
135+
return dp(0, len(s)-1)
136+
```
137+
138+
Python3 Code(普通 dp)
139+
140+
```py
141+
class Solution:
142+
def longestPalindromeSubseq(self, s: str) -> int:
143+
n = len(s)
144+
dp = [[0]*n for _ in range(n)]
145+
146+
for i in range(n-1, -1, -1):
147+
for j in range(i, n):
148+
if i == j:
149+
dp[i][j] = 1
150+
elif s[i] == s[j]:
151+
dp[i][j] = dp[i+1][j-1]+2
152+
else:
153+
dp[i][j] = max(dp[i+1][j], dp[i][j-1])
154+
return dp[0][-1]
155+
156+
```
157+
119158
**复杂度分析**
120159

121-
- 时间复杂度:$O(N^2)$
122-
- 空间复杂度:$O(N^2)$
160+
- 时间复杂度:枚举所有的状态需要 n^2 时间,状态转移需要常数的时间,因此总的时间复杂度为 $O(n^2)$
161+
- 空间复杂度:我们使用二维 dp 存储所有状态,因此空间复杂度为 $O(n^2)$
123162

124163
## 相关题目
125164

‎problems/785.is-graph-bipartite.md

Lines changed: 79 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -109,7 +109,7 @@ class Solution:
109109
令 v 和 e 为图中的顶点数和边数。
110110

111111
- 时间复杂度:$O(v+e)$
112-
- 空间复杂度:$O(v+e)$
112+
- 空间复杂度:$O(v),ドル stack depth = $O(v),ドル and colors array.length = $O(v)$
113113

114114

115115
如上代码并不优雅,之所以这么写只是为了体现和 886 题一致性。一个更加优雅的方式是不建立 grid,而是利用题目给的 graph(邻接矩阵)。
@@ -137,6 +137,10 @@ class Solution:
137137

138138
### 代码
139139

140+
代码支持:Python3,Java
141+
142+
Python3 Code:
143+
140144
```py
141145
class UF:
142146
def __init__(self, n):
@@ -163,13 +167,85 @@ class Solution:
163167
return True
164168
```
165169

170+
Java Code:
171+
172+
```java
173+
// weighted quick-union with path compression
174+
class Solution {
175+
class UF {
176+
int numOfUnions; // number of unions
177+
int[] parent;
178+
int[] size;
179+
180+
UF(int numOfElements) {
181+
numOfUnions = numOfElements;
182+
parent = new int[numOfElements];
183+
size = new int[numOfElements];
184+
for (int i = 0; i < numOfElements; i++) {
185+
parent[i] = i;
186+
size[i] = 1;
187+
}
188+
}
189+
190+
// find the head/representative of x
191+
int find(int x) {
192+
while (x != parent[x]) {
193+
parent[x] = parent[parent[x]];
194+
x = parent[x];
195+
}
196+
return x;
197+
}
198+
199+
void union(int p, int q) {
200+
int headOfP = find(p);
201+
int headOfQ = find(q);
202+
if (headOfP == headOfQ) {
203+
return;
204+
}
205+
// connect the small tree to the larger tree
206+
if (size[headOfP] < size[headOfQ]) {
207+
parent[headOfP] = headOfQ; // set headOfP's parent to be headOfQ
208+
size[headOfQ] += size[headOfP];
209+
} else {
210+
parent[headOfQ] = headOfP;
211+
size[headOfP] += size[headOfQ];
212+
}
213+
numOfUnions -= 1;
214+
}
215+
216+
boolean connected(int p, int q) {
217+
return find(p) == find(q);
218+
}
219+
}
220+
221+
public boolean isBipartite(int[][] graph) {
222+
int n = graph.length;
223+
UF unionfind = new UF(n);
224+
// i is what node each adjacent list is for
225+
for (int i = 0; i < n; i++) {
226+
// i's neighbors
227+
for (int neighbor : graph[i]) {
228+
// i should not be in the union of its neighbors
229+
if (unionfind.connected(i, neighbor)) {
230+
return false;
231+
}
232+
// add into unions
233+
unionfind.union(graph[i][0], neighbor);
234+
}
235+
}
236+
237+
return true;
238+
}
239+
240+
```
241+
166242

167243
**复杂度分析**
168244

169245
令 v 和 e 为图中的顶点数和边数。
170246

171-
- 时间复杂度:$O(v+e)$
172-
- 空间复杂度:$O(v+e)$
247+
- 时间复杂度:$O(v+e)$, using weighted quick-union with path compression, where union, find and connected are $O(1),ドル constructing unions takes $O(v)$
248+
- 空间复杂度:$O(v)$ for auxiliary union-find space int[] parent, int[] space
173249

174250
## 相关问题
175251

‎thinkings/tree.md

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -580,7 +580,7 @@ class Solution:
580580
# 叶子节点
581581
if cur and not cur.left and not cur.right:
582582
if remain == cur.val:
583-
res.append((path + [cur.val]).copy())
583+
nodes.append((path + [cur.val]).copy())
584584
return
585585
# 选择
586586
path.append(cur.val)

0 commit comments

Comments
(0)

AltStyle によって変換されたページ (->オリジナル) /