feat: update solutions to lc problem: No.1921 (doocs#3873)

yanglbme · web-flow · commit 2ea23e2848da · 2024-12-20T19:56:57.000+08:00
diff --git a/solution/1900-1999/1921.Eliminate Maximum Number of Monsters/README.md b/solution/1900-1999/1921.Eliminate Maximum Number of Monsters/README.md
@@ -61,7 +61,7 @@ tags:
 <strong>输出：</strong>1
 <strong>解释：</strong>
 第 0 分钟开始时，怪物的距离是 [3,2,4]，你消灭了第一个怪物。
-第 1 分钟开始时，怪物的距离是 [X,0,2]，你输掉了游戏。 
+第 1 分钟开始时，怪物的距离是 [X,0,2]，你输掉了游戏。
 你只能消灭 1 个怪物。
 </pre>
 
@@ -83,13 +83,13 @@ tags:
 
 ### 方法一：排序 + 贪心
 
-我们用 $times$ 数组记录每个怪物最晚可被消灭的时间。对于第 $i$ 个怪物，最晚可被消灭的时间满足：
+我们用 $\textit{times}$ 数组记录每个怪物最晚可被消灭的时间。对于第 $i$ 个怪物，最晚可被消灭的时间满足：
 
-$$times[i] = \lfloor \frac{dist[i]-1}{speed[i]} \rfloor$$
+$$\textit{times}[i] = \left\lfloor \frac{\textit{dist}[i]-1}{\textit{speed}[i]} \right\rfloor$$
 
-接下来，我们对 $times$ 数组升序排列。
+接下来，我们对 $\textit{times}$ 数组升序排列。
 
-然后遍历 $times$ 数组，对于第 $i$ 个怪物，如果 $times[i] \geq i$，说明第 $i$ 个怪物可以被消灭，否则说明第 $i$ 个怪物无法被消灭，直接返回 $i$ 即可。
+然后遍历 $\textit{times}$ 数组，对于第 $i$ 个怪物，如果 $\textit{times}[i] \geq i$，说明第 $i$ 个怪物可以被消灭，否则说明第 $i$ 个怪物无法被消灭，直接返回 $i$ 即可。
 
 若所有怪物都可以被消灭，则返回 $n$。
 
@@ -176,7 +176,7 @@ func eliminateMaximum(dist []int, speed []int) int {
 ```ts
 function eliminateMaximum(dist: number[], speed: number[]): number {
     const n = dist.length;
-    const times = new Array(n).fill(0);
+    const times: number[] = Array(n).fill(0);
     for (let i = 0; i < n; ++i) {
         times[i] = Math.floor((dist[i] - 1) / speed[i]);
     }
@@ -199,17 +199,18 @@ function eliminateMaximum(dist: number[], speed: number[]): number {
  * @return {number}
  */
 var eliminateMaximum = function (dist, speed) {
-    let arr = [];
-    for (let i = 0; i < dist.length; i++) {
-        arr[i] = dist[i] / speed[i];
+    const n = dist.length;
+    const times = Array(n).fill(0);
+    for (let i = 0; i < n; ++i) {
+        times[i] = Math.floor((dist[i] - 1) / speed[i]);
     }
-    arr.sort((a, b) => a - b);
-    let ans = 0;
-    while (arr[0] > ans) {
-        arr.shift();
-        ++ans;
+    times.sort((a, b) => a - b);
+    for (let i = 0; i < n; ++i) {
+        if (times[i] < i) {
+            return i;
+        }
     }
-    return ans;
+    return n;
 };
 ```
 
diff --git a/solution/1900-1999/1921.Eliminate Maximum Number of Monsters/README_EN.md b/solution/1900-1999/1921.Eliminate Maximum Number of Monsters/README_EN.md
@@ -79,7 +79,19 @@ You can only eliminate 1 monster.
 
 <!-- solution:start -->
 
-### Solution 1
+### Solution 1: Sorting + Greedy
+
+We use the $\textit{times}$ array to record the latest time each monster can be eliminated. For the $i$-th monster, the latest time it can be eliminated is:
+
+$$\textit{times}[i] = \left\lfloor \frac{\textit{dist}[i]-1}{\textit{speed}[i]} \right\rfloor$$
+
+Next, we sort the $\textit{times}$ array in ascending order.
+
+Then, we traverse the $\textit{times}$ array. For the $i$-th monster, if $\textit{times}[i] \geq i$, it means the $i$-th monster can be eliminated. Otherwise, it means the $i$-th monster cannot be eliminated, and we return $i$ immediately.
+
+If all monsters can be eliminated, we return $n$.
+
+The time complexity is $O(n \times \log n)$, and the space complexity is $O(n)$. Here, $n$ is the length of the array.
 
 <!-- tabs:start -->
 
@@ -162,7 +174,7 @@ func eliminateMaximum(dist []int, speed []int) int {
 ```ts
 function eliminateMaximum(dist: number[], speed: number[]): number {
     const n = dist.length;
-    const times = new Array(n).fill(0);
+    const times: number[] = Array(n).fill(0);
     for (let i = 0; i < n; ++i) {
         times[i] = Math.floor((dist[i] - 1) / speed[i]);
     }
@@ -185,21 +197,22 @@ function eliminateMaximum(dist: number[], speed: number[]): number {
  * @return {number}
  */
 var eliminateMaximum = function (dist, speed) {
-    let arr = [];
-    for (let i = 0; i < dist.length; i++) {
-        arr[i] = dist[i] / speed[i];
+    const n = dist.length;
+    const times = Array(n).fill(0);
+    for (let i = 0; i < n; ++i) {
+        times[i] = Math.floor((dist[i] - 1) / speed[i]);
     }
-    arr.sort((a, b) => a - b);
-    let ans = 0;
-    while (arr[0] > ans) {
-        arr.shift();
-        ++ans;
+    times.sort((a, b) => a - b);
+    for (let i = 0; i < n; ++i) {
+        if (times[i] < i) {
+            return i;
+        }
     }
-    return ans;
+    return n;
 };
 ```
 
-#### C#
+#### C
 
 ```cs
 public class Solution {
diff --git a/solution/1900-1999/1921.Eliminate Maximum Number of Monsters/Solution.js b/solution/1900-1999/1921.Eliminate Maximum Number of Monsters/Solution.js
@@ -4,15 +4,16 @@
  * @return {number}
  */
 var eliminateMaximum = function (dist, speed) {
-    let arr = [];
-    for (let i = 0; i < dist.length; i++) {
-        arr[i] = dist[i] / speed[i];
+    const n = dist.length;
+    const times = Array(n).fill(0);
+    for (let i = 0; i < n; ++i) {
+        times[i] = Math.floor((dist[i] - 1) / speed[i]);
     }
-    arr.sort((a, b) => a - b);
-    let ans = 0;
-    while (arr[0] > ans) {
-        arr.shift();
-        ++ans;
+    times.sort((a, b) => a - b);
+    for (let i = 0; i < n; ++i) {
+        if (times[i] < i) {
+            return i;
+        }
     }
-    return ans;
+    return n;
 };
diff --git a/solution/1900-1999/1921.Eliminate Maximum Number of Monsters/Solution.ts b/solution/1900-1999/1921.Eliminate Maximum Number of Monsters/Solution.ts
@@ -1,6 +1,6 @@
 function eliminateMaximum(dist: number[], speed: number[]): number {
     const n = dist.length;
-    const times = new Array(n).fill(0);
+    const times: number[] = Array(n).fill(0);
     for (let i = 0; i < n; ++i) {
         times[i] = Math.floor((dist[i] - 1) / speed[i]);
     }
diff --git a/solution/1900-1999/1922.Count Good Numbers/README.md b/solution/1900-1999/1922.Count Good Numbers/README.md
@@ -77,17 +77,7 @@ tags:
 class Solution:
     def countGoodNumbers(self, n: int) -> int:
         mod = 10**9 + 7
-
-        def myPow(x, n):
-            res = 1
-            while n:
-                if (n & 1) == 1:
-                    res = res * x % mod
-                x = x * x % mod
-                n >>= 1
-            return res
-
-        return myPow(5, (n + 1) >> 1) * myPow(4, n >> 1) % mod
+        return pow(5, (n + 1) >> 1, mod) * pow(4, n >> 1, mod) % mod
 ```
 
 #### Java
diff --git a/solution/1900-1999/1922.Count Good Numbers/README_EN.md b/solution/1900-1999/1922.Count Good Numbers/README_EN.md
@@ -75,17 +75,7 @@ tags:
 class Solution:
     def countGoodNumbers(self, n: int) -> int:
         mod = 10**9 + 7
-
-        def myPow(x, n):
-            res = 1
-            while n:
-                if (n & 1) == 1:
-                    res = res * x % mod
-                x = x * x % mod
-                n >>= 1
-            return res
-
-        return myPow(5, (n + 1) >> 1) * myPow(4, n >> 1) % mod
+        return pow(5, (n + 1) >> 1, mod) * pow(4, n >> 1, mod) % mod
 ```
 
 #### Java
diff --git a/solution/1900-1999/1922.Count Good Numbers/Solution.py b/solution/1900-1999/1922.Count Good Numbers/Solution.py
@@ -1,14 +1,4 @@
 class Solution:
     def countGoodNumbers(self, n: int) -> int:
         mod = 10**9 + 7
-
-        def myPow(x, n):
-            res = 1
-            while n:
-                if (n & 1) == 1:
-                    res = res * x % mod
-                x = x * x % mod
-                n >>= 1
-            return res
-
-        return myPow(5, (n + 1) >> 1) * myPow(4, n >> 1) % mod
+        return pow(5, (n + 1) >> 1, mod) * pow(4, n >> 1, mod) % mod

Original file line number	Diff line number	Diff line change
`@@ -1,6 +1,6 @@`
`1`	`1`	`function eliminateMaximum(dist: number[], speed: number[]): number {`
`2`	`2`	`const n = dist.length;`
`3`		`- const times = new Array(n).fill(0);`
	`3`	`+ const times: number[] = Array(n).fill(0);`
`4`	`4`	`for (let i = 0; i < n; ++i) {`
`5`	`5`	`times[i] = Math.floor((dist[i] - 1) / speed[i]);`
`6`	`6`	`}`