Skip to content

Commit 873947b

Browse files
yanglbmeyanglbme
authored
feat: update lc problems (doocs#3591)
1 parent b866896 commit 873947b

File tree

40 files changed

+449
-352
lines changed

40 files changed

+449
-352
lines changed

‎solution/0100-0199/0181.Employees Earning More Than Their Managers/README.md

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -44,7 +44,7 @@ id 是该表的主键（具有唯一值的列）。
4444
<p><strong>示例 1:</strong></p>
4545

4646
<pre>
47-
<strong>输入:</strong>
47+
<strong>输入:</strong>
4848
Employee 表:
4949
+----+-------+--------+-----------+
5050
| id | name | salary | managerId |
@@ -54,7 +54,7 @@ Employee 表:
5454
| 3 | Sam | 60000 | Null |
5555
| 4 | Max | 90000 | Null |
5656
+----+-------+--------+-----------+
57-
<strong>输出:</strong>
57+
<strong>输出:</strong>
5858
+----------+
5959
| Employee |
6060
+----------+

‎solution/0100-0199/0181.Employees Earning More Than Their Managers/README_EN.md

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -43,7 +43,7 @@ Each row of this table indicates the ID of an employee, their name, salary, and
4343
<p><strong class="example">Example 1:</strong></p>
4444

4545
<pre>
46-
<strong>Input:</strong>
46+
<strong>Input:</strong>
4747
Employee table:
4848
+----+-------+--------+-----------+
4949
| id | name | salary | managerId |
@@ -53,7 +53,7 @@ Employee table:
5353
| 3 | Sam | 60000 | Null |
5454
| 4 | Max | 90000 | Null |
5555
+----+-------+--------+-----------+
56-
<strong>Output:</strong>
56+
<strong>Output:</strong>
5757
+----------+
5858
| Employee |
5959
+----------+

‎solution/0700-0799/0727.Minimum Window Subsequence/README.md

Lines changed: 20 additions & 11 deletions
Original file line numberDiff line numberDiff line change
@@ -18,27 +18,36 @@ tags:
1818

1919
<!-- description:start -->
2020

21-
<p>给定字符串 <code>S</code> and <code>T</code>，找出 <code>S</code> 中最短的（连续）<strong>子串</strong> <code>W</code> ，使得 <code>T</code> 是 <code>W</code> 的 <strong>子序列</strong> 。</p>
21+
<p>给定字符串 <code>s1</code> 和&nbsp;<code>s2</code>，找出 <code>s1</code> 中最短的连续&nbsp;<strong>子串</strong>，使得 <code>s2</code> 是该子串的 <strong>子序列</strong> 。</p>
2222

23-
<p>如果 <code>S</code> 中没有窗口可以包含 <code>T</code> 中的所有字符，返回空字符串 <code>&quot;&quot;</code>。如果有不止一个最短长度的窗口，返回开始位置最靠左的那个。</p>
23+
<p>如果 <code>s1</code> 中没有窗口可以包含 <code>s2</code> 中的所有字符，返回空字符串 <code>""</code>。如果有不止一个最短长度的窗口，返回 <strong>开始位置最靠左</strong> 的那个。</p>
2424

2525
<p><strong>示例 1：</strong></p>
2626

27-
<pre><strong>输入：</strong>
28-
S = &quot;abcdebdde&quot;, T = &quot;bde&quot;
29-
<strong>输出：</strong>&quot;bcde&quot;
27+
<pre>
28+
<strong>输入：</strong>
29+
s1 = "abcdebdde", s2 = "bde"
30+
<strong>输出：</strong>"bcde"
3031
<strong>解释：</strong>
31-
&quot;bcde&quot; 是答案，因为它在相同长度的字符串 &quot;bdde&quot; 出现之前。
32-
&quot;deb&quot; 不是一个更短的答案，因为在窗口中必须按顺序出现 T 中的元素。</pre>
32+
"bcde" 是答案，因为它在相同长度的字符串 "bdde" 出现之前。
33+
"deb" 不是一个更短的答案，因为在窗口中必须按顺序出现 T 中的元素。
34+
</pre>
35+
36+
<p><strong class="example">示例 2：</strong></p>
37+
38+
<pre>
39+
<strong>输入：</strong>s1 = "jmeqksfrsdcmsiwvaovztaqenprpvnbstl", s2 = "u"
40+
<b>输出：</b>""
41+
</pre>
3342

3443
<p>&nbsp;</p>
3544

36-
<p><strong>注：</strong></p>
45+
<p><strong>提示：</strong></p>
3746

3847
<ul>
39-
<li>所有输入的字符串都只包含小写字母。All the strings in the input will only contain lowercase letters.</li>
40-
<li><code>S</code>&nbsp;长度的范围为&nbsp;<code>[1, 20000]</code>。</li>
41-
<li><code>T</code>&nbsp;长度的范围为&nbsp;<code>[1, 100]</code>。</li>
48+
<li><code>1 &lt;= s1.length &lt;= 2 * 10<sup>4</sup></code></li>
49+
<li><code>1 &lt;= s2.length &lt;= 100</code></li>
50+
<li><code>s1</code>&nbsp;和&nbsp;<code>s2</code>&nbsp;只包含小写英文字母。</li>
4251
</ul>
4352

4453
<p>&nbsp;</p>

‎solution/1500-1599/1580.Put Boxes Into the Warehouse II/README_EN.md

Lines changed: 7 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -73,7 +73,13 @@ Other valid solutions are to put the green box in room 2 or to put the orange bo
7373

7474
<!-- solution:start -->
7575

76-
### Solution 1
76+
### Solution 1: Preprocessing + Sorting + Greedy
77+
78+
First, we preprocess the warehouse to get the maximum height of each room. Then, we sort both the boxes and the warehouse. Starting with the smallest box and the smallest room, if the current room's height is greater than or equal to the current box's height, we can place the current box in the current room; otherwise, we continue to the next room.
79+
80+
Finally, we return the number of boxes that can be placed.
81+
82+
The time complexity is $O(n \times \log n)$, and the space complexity is $O(n)$. Here, $n$ is the length of the warehouse.
7783

7884
<!-- tabs:start -->
7985

‎solution/1500-1599/1582.Special Positions in a Binary Matrix/README.md

Lines changed: 73 additions & 73 deletions
Original file line numberDiff line numberDiff line change
@@ -58,13 +58,15 @@ tags:
5858

5959
<!-- solution:start -->
6060

61-
### 方法一：模拟
61+
### 方法一：计数
6262

63-
遍历矩阵 `mat`，先统计每一行，每一列中 `1` 的个数，分别记录在 `r` 和 `c` 数组中。
63+
我们可以用两个数组 $\textit{rows}$ 和 $\textit{cols}$ 分别记录每一行和每一列的 $1$ 的个数。
6464

65-
然后再遍历矩阵 `mat`，如果 `mat[i][j] == 1` 且 `row[i] == 1` 且 `col[j] == 1`，则 $(i, j)$ 是特殊位置。
65+
然后遍历矩阵，对于每一个 $1$，检查其所在的行和列是否只有一个 $1$，如果是则答案加一。
6666

67-
时间复杂度 $O(m\times n)$，空间复杂度 $O(m+n)$。其中 $m$, $n$ 分别是矩阵 `mat` 的行数和列数。
67+
遍历结束后，返回答案即可。
68+
69+
时间复杂度 $O(m \times n)$，空间复杂度 $O(m + n)$。其中 $m$ 和 $n$ 分别是矩阵 $\textit{mat}$ 的行数和列数。
6870

6971
<!-- tabs:start -->
7072

@@ -73,18 +75,16 @@ tags:
7375
```python
7476
class Solution:
7577
def numSpecial(self, mat: List[List[int]]) -> int:
76-
m, n = len(mat), len(mat[0])
77-
r = [0] * m
78-
c = [0] * n
78+
rows = [0] * len(mat)
79+
cols = [0] * len(mat[0])
7980
for i, row in enumerate(mat):
80-
for j, v in enumerate(row):
81-
r[i] += v
82-
c[j] += v
81+
for j, x in enumerate(row):
82+
rows[i] += x
83+
cols[j] += x
8384
ans = 0
84-
for i in range(m):
85-
for j in range(n):
86-
if mat[i][j] == 1 and r[i] == 1 and c[j] == 1:
87-
ans += 1
85+
for i, row in enumerate(mat):
86+
for j, x in enumerate(row):
87+
ans += x == 1 and rows[i] == 1 and cols[j] == 1
8888
return ans
8989
```
9090

@@ -94,22 +94,25 @@ class Solution:
9494
class Solution {
9595
public int numSpecial(int[][] mat) {
9696
int m = mat.length, n = mat[0].length;
97-
int[] r = new int[m];
98-
int[] c = new int[n];
97+
int[] rows = new int[m];
98+
int[] cols = new int[n];
99+
99100
for (int i = 0; i < m; ++i) {
100101
for (int j = 0; j < n; ++j) {
101-
r[i] += mat[i][j];
102-
c[j] += mat[i][j];
102+
rows[i] += mat[i][j];
103+
cols[j] += mat[i][j];
103104
}
104105
}
106+
105107
int ans = 0;
106108
for (int i = 0; i < m; ++i) {
107109
for (int j = 0; j < n; ++j) {
108-
if (mat[i][j] == 1 && r[i] == 1 && c[j] == 1) {
109-
++ans;
110+
if (mat[i][j] == 1 && rows[i] == 1 && cols[j] == 1) {
111+
ans++;
110112
}
111113
}
112114
}
115+
113116
return ans;
114117
}
115118
}
@@ -122,21 +125,25 @@ class Solution {
122125
public:
123126
int numSpecial(vector<vector<int>>& mat) {
124127
int m = mat.size(), n = mat[0].size();
125-
vector<int> r(m), c(n);
128+
vector<int> rows(m);
129+
vector<int> cols(n);
130+
126131
for (int i = 0; i < m; ++i) {
127132
for (int j = 0; j < n; ++j) {
128-
r[i] += mat[i][j];
129-
c[j] += mat[i][j];
133+
rows[i] += mat[i][j];
134+
cols[j] += mat[i][j];
130135
}
131136
}
137+
132138
int ans = 0;
133139
for (int i = 0; i < m; ++i) {
134140
for (int j = 0; j < n; ++j) {
135-
if (mat[i][j] == 1 && r[i] == 1 && c[j] == 1) {
136-
++ans;
141+
if (mat[i][j] == 1 && rows[i] == 1 && cols[j] == 1) {
142+
ans++;
137143
}
138144
}
139145
}
146+
140147
return ans;
141148
}
142149
};
@@ -145,24 +152,23 @@ public:
145152
#### Go
146153

147154
```go
148-
func numSpecial(mat [][]int) int {
149-
m, n := len(mat), len(mat[0])
150-
r, c := make([]int, m), make([]int, n)
155+
func numSpecial(mat [][]int) (ans int) {
156+
rows := make([]int, len(mat))
157+
cols := make([]int, len(mat[0]))
151158
for i, row := range mat {
152-
for j, v := range row {
153-
r[i] += v
154-
c[j] += v
159+
for j, x := range row {
160+
rows[i] += x
161+
cols[j] += x
155162
}
156163
}
157-
ans := 0
158-
for i, x := range r {
159-
for j, y := range c {
160-
if mat[i][j] == 1 && x == 1 && y == 1 {
164+
for i, row := range mat {
165+
for j, x := range row {
166+
if x == 1 && rows[i] == 1 && cols[j] == 1 {
161167
ans++
162168
}
163169
}
164170
}
165-
return ans
171+
return
166172
}
167173
```
168174

@@ -172,27 +178,23 @@ func numSpecial(mat [][]int) int {
172178
function numSpecial(mat: number[][]): number {
173179
const m = mat.length;
174180
const n = mat[0].length;
175-
const rows = new Array(m).fill(0);
176-
const cols = new Array(n).fill(0);
177-
for (let i = 0; i < m; i++) {
178-
for (let j = 0; j < n; j++) {
179-
if (mat[i][j] === 1) {
180-
rows[i]++;
181-
cols[j]++;
182-
}
181+
const rows: number[] = Array(m).fill(0);
182+
const cols: number[] = Array(n).fill(0);
183+
for (let i = 0; i < m; ++i) {
184+
for (let j = 0; j < n; ++j) {
185+
rows[i] += mat[i][j];
186+
cols[j] += mat[i][j];
183187
}
184188
}
185-
186-
let res = 0;
187-
for (let i = 0; i < m; i++) {
188-
for (let j = 0; j < n; j++) {
189+
let ans = 0;
190+
for (let i = 0; i < m; ++i) {
191+
for (let j = 0; j < n; ++j) {
189192
if (mat[i][j] === 1 && rows[i] === 1 && cols[j] === 1) {
190-
res++;
193+
++ans;
191194
}
192195
}
193196
}
194-
195-
return res;
197+
return ans;
196198
}
197199
```
198200

@@ -212,15 +214,15 @@ impl Solution {
212214
}
213215
}
214216

215-
let mut res = 0;
217+
let mut ans = 0;
216218
for i in 0..m {
217219
for j in 0..n {
218220
if mat[i][j] == 1 && rows[i] == 1 && cols[j] == 1 {
219-
res += 1;
221+
ans += 1;
220222
}
221223
}
222224
}
223-
res
225+
ans
224226
}
225227
}
226228
```
@@ -229,31 +231,29 @@ impl Solution {
229231

230232
```c
231233
int numSpecial(int** mat, int matSize, int* matColSize) {
232-
int m = matSize;
233-
int n = *matColSize;
234-
int* rows = (int*) malloc(sizeof(int) * m);
235-
int* cols = (int*) malloc(sizeof(int) * n);
236-
memset(rows, 0, sizeof(int) * m);
237-
memset(cols, 0, sizeof(int) * n);
238-
for (int i = 0; i < m; i++) {
239-
for (int j = 0; j < n; j++) {
240-
if (mat[i][j] == 1) {
241-
rows[i]++;
242-
cols[j]++;
243-
}
234+
int m = matSize, n = matColSize[0];
235+
int rows[m];
236+
int cols[n];
237+
memset(rows, 0, sizeof(rows));
238+
memset(cols, 0, sizeof(cols));
239+
240+
for (int i = 0; i < m; ++i) {
241+
for (int j = 0; j < n; ++j) {
242+
rows[i] += mat[i][j];
243+
cols[j] += mat[i][j];
244244
}
245245
}
246-
int res = 0;
247-
for (int i = 0; i < m; i++) {
248-
for (int j = 0; j < n; j++) {
246+
247+
int ans = 0;
248+
for (int i = 0; i < m; ++i) {
249+
for (int j = 0; j < n; ++j) {
249250
if (mat[i][j] == 1 && rows[i] == 1 && cols[j] == 1) {
250-
res++;
251+
ans++;
251252
}
252253
}
253254
}
254-
free(rows);
255-
free(cols);
256-
return res;
255+
256+
return ans;
257257
}
258258
```
259259

0 commit comments

Comments
 (0)