Skip to content

Commit 3007c80

Browse files
yanglbmeyanglbme
authored
feat: add solutions to lc problems: No.0577,0580,0581,1661 (doocs#1830)
* No.0577.Employee Bonus * No.0580.Count Student Number in Departments * No.0581.Shortest Unsorted Continuous Subarray * No.1661.Average Time of Process per Machine
1 parent 0c24e5b commit 3007c80

File tree

17 files changed

+575
-146
lines changed

17 files changed

+575
-146
lines changed

‎.prettierrc

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -37,6 +37,7 @@
3737
"solution/1500-1599/1501.Countries You Can Safely Invest In/Solution.sql",
3838
"solution/1500-1599/1511.Customer Order Frequency/Solution.sql",
3939
"solution/1500-1599/1555.Bank Account Summary/Solution.sql",
40+
"solution/1600-1699/1661.Average Time of Process per Machine/Solution.sql",
4041
"solution/1600-1699/1667.Fix Names in a Table/Solution.sql",
4142
"solution/1600-1699/1699.Number of Calls Between Two Persons/Solution.sql",
4243
"solution/1700-1799/1777.Product's Price for Each Store/Solution.sql",

‎solution/0500-0599/0577.Employee Bonus/README.md

Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -80,6 +80,10 @@ Bonus table:
8080

8181
<!-- 这里可写通用的实现逻辑 -->
8282

83+
**方法一：左连接**
84+
85+
我们可以使用左连接，将 `Employee` 表和 `Bonus` 表按照 `empId` 进行连接，然后筛选出奖金小于 $1000$ 的员工。注意，连接后的表中，`bonus` 为 `NULL` 的员工也应该被筛选出来，因此我们需要使用 `IFNULL` 函数将 `NULL` 值转换为 $0$。
86+
8387
<!-- tabs:start -->
8488

8589
### **SQL**

‎solution/0500-0599/0577.Employee Bonus/README_EN.md

Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -76,6 +76,10 @@ Bonus table:
7676

7777
## Solutions
7878

79+
**Solution 1: Left Join**
80+
81+
We can use a left join to join the `Employee` table and the `Bonus` table on `empId`, and then filter out the employees whose bonus is less than $1000$. Note that the employees with `NULL` bonus values after the join should also be filtered out, so we need to use the `IFNULL` function to convert `NULL` values to $0$.
82+
7983
<!-- tabs:start -->
8084

8185
### **SQL**

‎solution/0500-0599/0580.Count Student Number in Departments/README.md

Lines changed: 8 additions & 9 deletions
Original file line numberDiff line numberDiff line change
@@ -79,22 +79,21 @@ Department 表:
7979

8080
<!-- 这里可写通用的实现逻辑 -->
8181

82+
**方法一：左连接 + 分组统计**
83+
84+
我们可以使用左连接，将 `Department` 表与 `Student` 表按照 `dept_id` 进行连接，然后按照 `dept_id` 分组统计学生人数，最后按照 `student_number` 降序、`dept_name` 升序排序即可。
85+
8286
<!-- tabs:start -->
8387

8488
### **SQL**
8589

8690
```sql
8791
# Write your MySQL query statement below
88-
WITH
89-
S AS (
90-
SELECT dept_id, COUNT(1) AS cnt
91-
FROM Student
92-
GROUP BY dept_id
93-
)
94-
SELECT dept_name, IFNULL(cnt, 0) AS student_number
92+
SELECT dept_name, COUNT(student_id) AS student_number
9593
FROM
96-
S
97-
RIGHT JOIN Department USING (dept_id)
94+
Department
95+
LEFT JOIN Student USING (dept_id)
96+
GROUP BY dept_id
9897
ORDER BY 2 DESC, 1;
9998
```
10099

‎solution/0500-0599/0580.Count Student Number in Departments/README_EN.md

Lines changed: 8 additions & 9 deletions
Original file line numberDiff line numberDiff line change
@@ -76,22 +76,21 @@ Department table:
7676

7777
## Solutions
7878

79+
**Solution 1: Left Join + Grouping**
80+
81+
We can use a left join to join the `Department` table and the `Student` table on `dept_id`, and then group by `dept_id` to count the number of students in each department. Finally, we can sort the result by `student_number` in descending order and `dept_name` in ascending order.
82+
7983
<!-- tabs:start -->
8084

8185
### **SQL**
8286

8387
```sql
8488
# Write your MySQL query statement below
85-
WITH
86-
S AS (
87-
SELECT dept_id, COUNT(1) AS cnt
88-
FROM Student
89-
GROUP BY dept_id
90-
)
91-
SELECT dept_name, IFNULL(cnt, 0) AS student_number
89+
SELECT dept_name, COUNT(student_id) AS student_number
9290
FROM
93-
S
94-
RIGHT JOIN Department USING (dept_id)
91+
Department
92+
LEFT JOIN Student USING (dept_id)
93+
GROUP BY dept_id
9594
ORDER BY 2 DESC, 1;
9695
```
9796

‎solution/0500-0599/0580.Count Student Number in Departments/Solution.sql

Lines changed: 4 additions & 9 deletions
Original file line numberDiff line numberDiff line change
@@ -1,12 +1,7 @@
11
# Write your MySQL query statement below
2-
WITH
3-
S AS (
4-
SELECT dept_id, COUNT(1) AS cnt
5-
FROM Student
6-
GROUP BY dept_id
7-
)
8-
SELECT dept_name, IFNULL(cnt, 0) AS student_number
2+
SELECT dept_name, COUNT(student_id) AS student_number
93
FROM
10-
S
11-
RIGHT JOIN Department USING (dept_id)
4+
Department
5+
LEFT JOIN Student USING (dept_id)
6+
GROUP BY dept_id
127
ORDER BY 2 DESC, 1;

‎solution/0500-0599/0581.Shortest Unsorted Continuous Subarray/README.md

Lines changed: 184 additions & 38 deletions
Original file line numberDiff line numberDiff line change
@@ -57,11 +57,15 @@
5757

5858
**方法一：排序**
5959

60-
将排序后的数组与原数组进行比较，确定左右边界。
60+
我们可以先对数组进行排序，然后比较排序后的数组和原数组，找到最左边和最右边不相等的位置，它们之间的长度就是我们要找的最短无序连续子数组的长度。
6161

62-
时间复杂度 $O(nlogn)$，其中 $n$ 表示 $nums$ 数组的长度。
62+
时间复杂度 $O(n \times \log n)$，空间复杂度 $O(n)$。其中 $n$ 是数组的长度。
6363

64-
更进一步优化，可以通过维护最大值和最小值，一次遍历得出结果（见 Golang 解法）
64+
**方法二：维护左侧最大值和右侧最小值**
65+
66+
我们可以从左到右遍历数组，维护一个最大值 $mx$，如果当前值小于 $mx$，说明当前值不在正确的位置上，我们更新右边界 $r$ 为当前位置。同理，我们可以从右到左遍历数组，维护一个最小值 $mi$，如果当前值大于 $mi$，说明当前值不在正确的位置上，我们更新左边界 $l$ 为当前位置。在初始化时，我们将 $l$ 和 $r$ 都初始化为 $-1$，如果 $l$ 和 $r$ 都没有被更新，说明数组已经有序，返回 $0$，否则返回 $r - l + 1$。
67+
68+
时间复杂度 $O(n)$，其中 $n$ 是数组的长度。空间复杂度 $O(1)$。
6569

6670
<!-- tabs:start -->
6771

@@ -73,12 +77,30 @@
7377
class Solution:
7478
def findUnsortedSubarray(self, nums: List[int]) -> int:
7579
arr = sorted(nums)
76-
left, right = 0, len(nums) - 1
77-
while left <= right and nums[left] == arr[left]:
78-
left += 1
79-
while left <= right and nums[right] == arr[right]:
80-
right -= 1
81-
return right - left + 1
80+
l, r = 0, len(nums) - 1
81+
while l <= r and nums[l] == arr[l]:
82+
l += 1
83+
while l <= r and nums[r] == arr[r]:
84+
r -= 1
85+
return r - l + 1
86+
```
87+
88+
```python
89+
class Solution:
90+
def findUnsortedSubarray(self, nums: List[int]) -> int:
91+
mi, mx = inf, -inf
92+
l = r = -1
93+
n = len(nums)
94+
for i, x in enumerate(nums):
95+
if mx > x:
96+
r = i
97+
else:
98+
mx = x
99+
if mi < nums[n - i - 1]:
100+
l = n - i - 1
101+
else:
102+
mi = nums[n - i - 1]
103+
return 0 if r == -1 else r - l + 1
82104
```
83105

84106
### **Java**
@@ -90,14 +112,38 @@ class Solution {
90112
public int findUnsortedSubarray(int[] nums) {
91113
int[] arr = nums.clone();
92114
Arrays.sort(arr);
93-
int left = 0, right = nums.length - 1;
94-
while (left <= right && nums[left] == arr[left]) {
95-
++left;
115+
int l = 0, r = arr.length - 1;
116+
while (l <= r && nums[l] == arr[l]) {
117+
l++;
96118
}
97-
while (left <= right && nums[right] == arr[right]) {
98-
--right;
119+
while (l <= r && nums[r] == arr[r]) {
120+
r--;
99121
}
100-
return right - left + 1;
122+
return r - l + 1;
123+
}
124+
}
125+
```
126+
127+
```java
128+
class Solution {
129+
public int findUnsortedSubarray(int[] nums) {
130+
final int inf = 1 << 30;
131+
int n = nums.length;
132+
int l = -1, r = -1;
133+
int mi = inf, mx = -inf;
134+
for (int i = 0; i < n; ++i) {
135+
if (mx > nums[i]) {
136+
r = i;
137+
} else {
138+
mx = nums[i];
139+
}
140+
if (mi < nums[n - i - 1]) {
141+
l = n - i - 1;
142+
} else {
143+
mi = nums[n - i - 1];
144+
}
145+
}
146+
return r == -1 ? 0 : r - l + 1;
101147
}
102148
}
103149
```
@@ -110,10 +156,39 @@ public:
110156
int findUnsortedSubarray(vector<int>& nums) {
111157
vector<int> arr = nums;
112158
sort(arr.begin(), arr.end());
113-
int left = 0, right = arr.size() - 1;
114-
while (left <= right && nums[left] == arr[left]) ++left;
115-
while (left <= right && nums[right] == arr[right]) --right;
116-
return right - left + 1;
159+
int l = 0, r = arr.size() - 1;
160+
while (l <= r && arr[l] == nums[l]) {
161+
l++;
162+
}
163+
while (l <= r && arr[r] == nums[r]) {
164+
r--;
165+
}
166+
return r - l + 1;
167+
}
168+
};
169+
```
170+
171+
```cpp
172+
class Solution {
173+
public:
174+
int findUnsortedSubarray(vector<int>& nums) {
175+
const int inf = 1e9;
176+
int n = nums.size();
177+
int l = -1, r = -1;
178+
int mi = inf, mx = -inf;
179+
for (int i = 0; i < n; ++i) {
180+
if (mx > nums[i]) {
181+
r = i;
182+
} else {
183+
mx = nums[i];
184+
}
185+
if (mi < nums[n - i - 1]) {
186+
l = n - i - 1;
187+
} else {
188+
mi = nums[n - i - 1];
189+
}
190+
}
191+
return r == -1 ? 0 : r - l + 1;
117192
}
118193
};
119194
```
@@ -122,42 +197,113 @@ public:
122197

123198
```go
124199
func findUnsortedSubarray(nums []int) int {
125-
n := len(nums)
126-
arr := make([]int, n)
200+
arr := make([]int, len(nums))
127201
copy(arr, nums)
128202
sort.Ints(arr)
129-
left, right := 0, n-1
130-
for left <= right && nums[left] == arr[left] {
131-
left++
203+
l, r := 0, len(arr)-1
204+
for l <= r && nums[l] == arr[l] {
205+
l++
132206
}
133-
for left <= right && nums[right] == arr[right] {
134-
right--
207+
for l <= r && nums[r] == arr[r] {
208+
r--
135209
}
136-
return right - left + 1
210+
return r - l + 1
137211
}
138212
```
139213

140214
```go
141215
func findUnsortedSubarray(nums []int) int {
216+
const inf = 1 << 30
142217
n := len(nums)
143-
maxn, minn := math.MinInt32, math.MaxInt32
144-
left, right := -1, -1
145-
for i := 0; i < n; i++ {
146-
if maxn > nums[i] {
147-
right = i
218+
l, r := -1, -1
219+
mi, mx := inf, -inf
220+
for i, x := range nums {
221+
if mx > x {
222+
r = i
148223
} else {
149-
maxn = nums[i]
224+
mx = x
150225
}
151-
if minn < nums[n-i-1] {
152-
left = n - i - 1
226+
if mi < nums[n-i-1] {
227+
l = n - i - 1
153228
} else {
154-
minn = nums[n-i-1]
229+
mi = nums[n-i-1]
155230
}
156231
}
157-
if right == -1 {
232+
if r == -1 {
158233
return 0
159234
}
160-
return right - left + 1
235+
return r - l + 1
236+
}
237+
```
238+
239+
### **TypeScript**
240+
241+
```ts
242+
function findUnsortedSubarray(nums: number[]): number {
243+
const arr = [...nums];
244+
arr.sort((a, b) => a - b);
245+
let [l, r] = [0, arr.length - 1];
246+
while (l <= r && arr[l] === nums[l]) {
247+
++l;
248+
}
249+
while (l <= r && arr[r] === nums[r]) {
250+
--r;
251+
}
252+
return r - l + 1;
253+
}
254+
```
255+
256+
```ts
257+
function findUnsortedSubarray(nums: number[]): number {
258+
let [l, r] = [-1, -1];
259+
let [mi, mx] = [Infinity, -Infinity];
260+
const n = nums.length;
261+
for (let i = 0; i < n; ++i) {
262+
if (mx > nums[i]) {
263+
r = i;
264+
} else {
265+
mx = nums[i];
266+
}
267+
if (mi < nums[n - i - 1]) {
268+
l = n - i - 1;
269+
} else {
270+
mi = nums[n - i - 1];
271+
}
272+
}
273+
return r === -1 ? 0 : r - l + 1;
274+
}
275+
```
276+
277+
```rust
278+
impl Solution {
279+
pub fn find_unsorted_subarray(nums: Vec<i32>) -> i32 {
280+
let inf = 1 << 30;
281+
let n = nums.len();
282+
let mut l = -1;
283+
let mut r = -1;
284+
let mut mi = inf;
285+
let mut mx = -inf;
286+
287+
for i in 0..n {
288+
if mx > nums[i] {
289+
r = i as i32;
290+
} else {
291+
mx = nums[i];
292+
}
293+
294+
if mi < nums[n - i - 1] {
295+
l = (n - i - 1) as i32;
296+
} else {
297+
mi = nums[n - i - 1];
298+
}
299+
}
300+
301+
if r == -1 {
302+
0
303+
} else {
304+
r - l + 1
305+
}
306+
}
161307
}
162308
```
163309

0 commit comments

Comments
 (0)