Skip to content

Commit 253d688

Browse files
yanglbmeyanglbme
committed
feat: add solutions to lc problem: No.0096. Unique Binary Search Trees
1 parent b98eb25 commit 253d688

File tree

15 files changed

+333
-51
lines changed

15 files changed

+333
-51
lines changed

‎README.md

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -181,6 +181,7 @@
181181
- [接雨水](./solution/0000-0099/0042.Trapping%20Rain%20Water/README.md)
182182
- [等差数列划分](./solution/0400-0499/0413.Arithmetic%20Slices/README.md)
183183
- [解码方法](./solution/0000-0099/0091.Decode%20Ways/README.md)
184+
- [不同的二叉搜索树](./solution/0000-0099/0096.Unique%20Binary%20Search%20Trees/README.md)
184185
- [礼物的最大价值](./lcof/面试题47.%20礼物的最大价值/README.md)
185186
- [最小路径和](./solution/0000-0099/0064.Minimum%20Path%20Sum/README.md)
186187
- [最长上升子序列](./solution/0300-0399/0300.Longest%20Increasing%20Subsequence/README.md)

‎README_EN.md

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -175,6 +175,7 @@ Complete solutions to [LeetCode](https://leetcode.com/problemset/all/), [LCOF](h
175175
- [Trapping Rain Water](./solution/0000-0099/0042.Trapping%20Rain%20Water/README_EN.md)
176176
- [Arithmetic Slices](./solution/0400-0499/0413.Arithmetic%20Slices/README_EN.md)
177177
- [Decode Ways](./solution/0000-0099/0091.Decode%20Ways/README_EN.md)
178+
- [Unique Binary Search Trees](./solution/0000-0099/0096.Unique%20Binary%20Search%20Trees/README_EN.md)
178179
- [Minimum Path Sum](./solution/0000-0099/0064.Minimum%20Path%20Sum/README_EN.md)
179180
- [Longest Increasing Subsequence](./solution/0300-0399/0300.Longest%20Increasing%20Subsequence/README_EN.md)
180181
- [Russian Doll Envelopes](./solution/0300-0399/0354.Russian%20Doll%20Envelopes/README_EN.md)

‎solution/0000-0099/0096.Unique Binary Search Trees/README.md

Lines changed: 54 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -21,27 +21,79 @@
2121
/ / \ \
2222
2 1 2 3</pre>
2323

24-
2524
## 解法
2625

2726
<!-- 这里可写通用的实现逻辑 -->
2827

28+
假设 n 个节点存在二叉搜索树的个数是 `G(n)`，1 为根节点，2 为根节点，...，n 为根节点，当 1 为根节点时，其左子树节点个数为 0，右子树节点个数为 n-1，同理当 2 为根节点时，其左子树节点个数为 1，右子树节点为 n-2，所以可得 `G(n) = G(0) * G(n-1) + G(1) * (n-2) + ... + G(n-1) * G(0)`。
29+
2930
<!-- tabs:start -->
3031

3132
### **Python3**
3233

3334
<!-- 这里可写当前语言的特殊实现逻辑 -->
3435

3536
```python
36-
37+
class Solution:
38+
def numTrees(self, n: int) -> int:
39+
dp = [0] * (n + 1)
40+
dp[0] = 1
41+
for i in range(1, n + 1):
42+
for j in range(i):
43+
dp[i] += dp[j] * dp[i - j - 1]
44+
return dp[-1]
3745
```
3846

3947
### **Java**
4048

4149
<!-- 这里可写当前语言的特殊实现逻辑 -->
4250

4351
```java
52+
class Solution {
53+
public int numTrees(int n) {
54+
int[] dp = new int[n + 1];
55+
dp[0] = 1;
56+
for (int i = 1; i <= n; ++i) {
57+
for (int j = 0; j < i; ++j) {
58+
dp[i] += dp[j] * dp[i - j - 1];
59+
}
60+
}
61+
return dp[n];
62+
}
63+
}
64+
```
65+
66+
### **C++**
67+
68+
```cpp
69+
class Solution {
70+
public:
71+
int numTrees(int n) {
72+
vector<int> dp(n + 1);
73+
dp[0] = 1;
74+
for (int i = 1; i <= n; ++i) {
75+
for (int j = 0; j < i; ++j) {
76+
dp[i] += dp[j] * dp[i - j - 1];
77+
}
78+
}
79+
return dp[n];
80+
}
81+
};
82+
```
4483
84+
### **Go**
85+
86+
```go
87+
func numTrees(n int) int {
88+
dp := make([]int, n+1)
89+
dp[0] = 1
90+
for i := 1; i <= n; i++ {
91+
for j := 0; j < i; j++ {
92+
dp[i] += dp[j] * dp[i-j-1]
93+
}
94+
}
95+
return dp[n]
96+
}
4597
```
4698

4799
### **...**

‎solution/0000-0099/0096.Unique Binary Search Trees/README_EN.md

Lines changed: 52 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -36,13 +36,64 @@
3636
### **Python3**
3737

3838
```python
39-
39+
class Solution:
40+
def numTrees(self, n: int) -> int:
41+
dp = [0] * (n + 1)
42+
dp[0] = 1
43+
for i in range(1, n + 1):
44+
for j in range(i):
45+
dp[i] += dp[j] * dp[i - j - 1]
46+
return dp[-1]
4047
```
4148

4249
### **Java**
4350

4451
```java
52+
class Solution {
53+
public int numTrees(int n) {
54+
int[] dp = new int[n + 1];
55+
dp[0] = 1;
56+
for (int i = 1; i <= n; ++i) {
57+
for (int j = 0; j < i; ++j) {
58+
dp[i] += dp[j] * dp[i - j - 1];
59+
}
60+
}
61+
return dp[n];
62+
}
63+
}
64+
```
65+
66+
### **C++**
67+
68+
```cpp
69+
class Solution {
70+
public:
71+
int numTrees(int n) {
72+
vector<int> dp(n + 1);
73+
dp[0] = 1;
74+
for (int i = 1; i <= n; ++i) {
75+
for (int j = 0; j < i; ++j) {
76+
dp[i] += dp[j] * dp[i - j - 1];
77+
}
78+
}
79+
return dp[n];
80+
}
81+
};
82+
```
4583
84+
### **Go**
85+
86+
```go
87+
func numTrees(n int) int {
88+
dp := make([]int, n+1)
89+
dp[0] = 1
90+
for i := 1; i <= n; i++ {
91+
for j := 0; j < i; j++ {
92+
dp[i] += dp[j] * dp[i-j-1]
93+
}
94+
}
95+
return dp[n]
96+
}
4697
```
4798

4899
### **...**

‎solution/0000-0099/0096.Unique Binary Search Trees/Solution.cpp

Lines changed: 13 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,13 @@
1+
class Solution {
2+
public:
3+
int numTrees(int n) {
4+
vector<int> dp(n + 1);
5+
dp[0] = 1;
6+
for (int i = 1; i <= n; ++i) {
7+
for (int j = 0; j < i; ++j) {
8+
dp[i] += dp[j] * dp[i - j - 1];
9+
}
10+
}
11+
return dp[n];
12+
}
13+
};

‎solution/0000-0099/0096.Unique Binary Search Trees/Solution.go

Lines changed: 10 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,10 @@
1+
func numTrees(n int) int {
2+
dp := make([]int, n+1)
3+
dp[0] = 1
4+
for i := 1; i <= n; i++ {
5+
for j := 0; j < i; j++ {
6+
dp[i] += dp[j] * dp[i-j-1]
7+
}
8+
}
9+
return dp[n]
10+
}

‎solution/0000-0099/0096.Unique Binary Search Trees/Solution.java

Lines changed: 4 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -1,15 +1,12 @@
11
class Solution {
22
public int numTrees(int n) {
3-
4-
// res[n] 表示整数n组成的二叉搜索树个数
5-
int[] res = new int[n + 1];
6-
res[0] = 1;
7-
3+
int[] dp = new int[n + 1];
4+
dp[0] = 1;
85
for (int i = 1; i <= n; ++i) {
96
for (int j = 0; j < i; ++j) {
10-
res[i] += res[j] * res[i - j - 1];
7+
dp[i] += dp[j] * dp[i - j - 1];
118
}
129
}
13-
return res[n];
10+
return dp[n];
1411
}
1512
}

‎solution/0000-0099/0096.Unique Binary Search Trees/Solution.py

Lines changed: 5 additions & 9 deletions
Original file line numberDiff line numberDiff line change
@@ -1,12 +1,8 @@
11
class Solution:
2-
def numTrees(self, n):
3-
"""
4-
:type n: int
5-
:rtype: int
6-
"""
7-
res = [0] * (n + 1)
8-
res[0] = 1
2+
def numTrees(self, n: int) -> int:
3+
dp = [0] * (n + 1)
4+
dp[0] = 1
95
for i in range(1, n + 1):
106
for j in range(i):
11-
res[i] += res[j] * res[i - j - 1]
12-
return res[n]
7+
dp[i] += dp[j] * dp[i - j - 1]
8+
return dp[-1]

‎solution/1900-1999/1933.Check if String Is Decomposable Into Value-Equal Substrings/README.md

Lines changed: 83 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,83 @@
1+
# [1933. 判断字符串是否可分解为值均等的子串](https://leetcode-cn.com/problems/check-if-string-is-decomposable-into-value-equal-substrings)
2+
3+
[English Version](/solution/1900-1999/1933.Check%20if%20String%20Is%20Decomposable%20Into%20Value-Equal%20Substrings/README_EN.md)
4+
5+
## 题目描述
6+
7+
<!-- 这里写题目描述 -->
8+
9+
<p>一个字符串的所有字符都是一样的，被称作等值字符串。</p>
10+
11+
<ul>
12+
<li>举例，<code>"1111"</code> 和 <code>"33" </code>就是等值字符串。</li>
13+
<li>相比之下，<code>"123"</code>就不是等值字符串。</li>
14+
</ul>
15+
16+
<p>规则：给出一个数字字符串s，将字符串分解成一些等值字符串，如果有且仅有一个等值子字符串长度为2，其他的等值子字符串的长度都是3.</p>
17+
18+
<p>如果能够按照上面的规则分解字符串s，就返回真，否则返回假。</p>
19+
20+
<p>子串就是原字符串中连续的字符序列。</p>
21+
22+
<p> </p>
23+
24+
<p><strong>示例 1：</strong></p>
25+
26+
<pre><strong>输入:</strong> s = "000111000"
27+
<strong>输出:</strong> false
28+
<strong>解释: </strong> s只能被分解长度为3的等值子字符串。
29+
</pre>
30+
31+
<p><strong>示例 2：</strong></p>
32+
33+
<pre><strong>输入:</strong> s = "00011111222"
34+
<strong>输出:</strong> true
35+
<strong>解释: </strong>s 能被分解为 ["000","111","11","222"].
36+
</pre>
37+
38+
<p><strong>示例 3：</strong></p>
39+
40+
<pre><strong>输入:</strong> s = "01110002223300"
41+
<strong>输出:</strong> false
42+
<strong>解释: </strong>一个不能被分解的原因是在开头有一个0.
43+
</pre>
44+
45+
<p> </p>
46+
47+
<p><strong>提示:</strong></p>
48+
49+
<ul>
50+
<li><code>1 &lt;= s.length &lt;</code><code>= 1000</code></li>
51+
<li><code>s</code> 仅包含数字。</li>
52+
</ul>
53+
54+
55+
## 解法
56+
57+
<!-- 这里可写通用的实现逻辑 -->
58+
59+
<!-- tabs:start -->
60+
61+
### **Python3**
62+
63+
<!-- 这里可写当前语言的特殊实现逻辑 -->
64+
65+
```python
66+
67+
```
68+
69+
### **Java**
70+
71+
<!-- 这里可写当前语言的特殊实现逻辑 -->
72+
73+
```java
74+
75+
```
76+
77+
### **...**
78+
79+
```
80+
81+
```
82+
83+
<!-- tabs:end -->

‎solution/1900-1999/1933.Check if String Is Decomposable Into Value-Equal Substrings/README_EN.md

Lines changed: 76 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,76 @@
1+
# [1933. Check if String Is Decomposable Into Value-Equal Substrings](https://leetcode.com/problems/check-if-string-is-decomposable-into-value-equal-substrings)
2+
3+
[中文文档](/solution/1900-1999/1933.Check%20if%20String%20Is%20Decomposable%20Into%20Value-Equal%20Substrings/README.md)
4+
5+
## Description
6+
7+
<p>A <strong>value-equal</strong> string is a string where <strong>all</strong> characters are the same.</p>
8+
9+
<ul>
10+
<li>For example, <code>&quot;1111&quot;</code> and <code>&quot;33&quot;</code> are value-equal strings.</li>
11+
<li>In contrast, <code>&quot;123&quot;</code> is not a value-equal string.</li>
12+
</ul>
13+
14+
<p>Given a digit string <code>s</code>, decompose the string into some number of <strong>consecutive value-equal</strong> substrings where <strong>exactly one</strong> substring has a <strong>length of </strong><code>2</code> and the remaining substrings have a <strong>length of </strong><code>3</code>.</p>
15+
16+
<p>Return <code>true</code><em> if you can decompose </em><code>s</code><em> according to the above rules. Otherwise, return </em><code>false</code>.</p>
17+
18+
<p>A <strong>substring</strong> is a contiguous sequence of characters in a string.</p>
19+
20+
<p>&nbsp;</p>
21+
<p><strong>Example 1:</strong></p>
22+
23+
<pre>
24+
<strong>Input:</strong> s = &quot;000111000&quot;
25+
<strong>Output:</strong> false
26+
<strong>Explanation: </strong>s cannot be decomposed according to the rules because [&quot;000&quot;, &quot;111&quot;, &quot;000&quot;] does not have a substring of length 2.
27+
</pre>
28+
29+
<p><strong>Example 2:</strong></p>
30+
31+
<pre>
32+
<strong>Input:</strong> s = &quot;00011111222&quot;
33+
<strong>Output:</strong> true
34+
<strong>Explanation: </strong>s can be decomposed into [&quot;000&quot;, &quot;111&quot;, &quot;11&quot;, &quot;222&quot;].
35+
</pre>
36+
37+
<p><strong>Example 3:</strong></p>
38+
39+
<pre>
40+
<strong>Input:</strong> s = &quot;011100022233&quot;
41+
<strong>Output:</strong> false
42+
<strong>Explanation: </strong>s cannot be decomposed according to the rules because of the first &#39;0&#39;.
43+
</pre>
44+
45+
<p>&nbsp;</p>
46+
<p><strong>Constraints:</strong></p>
47+
48+
<ul>
49+
<li><code>1 &lt;= s.length &lt;= 1000</code></li>
50+
<li><code>s</code> consists of only digits <code>&#39;0&#39;</code> through <code>&#39;9&#39;</code>.</li>
51+
</ul>
52+
53+
54+
## Solutions
55+
56+
<!-- tabs:start -->
57+
58+
### **Python3**
59+
60+
```python
61+
62+
```
63+
64+
### **Java**
65+
66+
```java
67+
68+
```
69+
70+
### **...**
71+
72+
```
73+
74+
```
75+
76+
<!-- tabs:end -->

0 commit comments

Comments
 (0)