feat: update solutions to lc problems: No.1893,1894 (doocs#3257)

yanglbme · web-flow · commit 8001ba68c42a · 2024-07-11T16:43:49.000+08:00
diff --git a/solution/1800-1899/1893.Check if All the Integers in a Range Are Covered/README.md b/solution/1800-1899/1893.Check if All the Integers in a Range Are Covered/README.md
@@ -65,13 +65,15 @@ tags:
 
 ### 方法一：差分数组
 
-我们可以使用差分数组的思想，对于每个区间 $[l, r]$，我们将 $diff[l]$ 加 $1$，将 $diff[r + 1]$ 减 $1$。
+我们可以使用差分数组的思想，创建一个长度为 $52$ 的差分数组 $\textit{diff}$。
 
-最后遍历差分数组，累加每个位置的值，记为 $cur$，如果 $left \le i \le right$ 且 $cur = 0$，则说明 $i$ 没有被任何区间覆盖，返回 `false`。
+接下来，我们遍历数组 $\textit{ranges}$，对于每个区间 $[l, r]$，我们令 $\textit{diff}[l]$ 自增 $1$，而 $\textit{diff}[r + 1]$ 自减 $1$。
 
-否则遍历结束后，返回 `true`。
+接着，我们遍历差分数组 $\textit{diff}$，维护一个前缀和 $s$，对于每个位置 $i$，我们令 $s$ 自增 $\textit{diff}[i]$，如果 $s \le 0$ 且 $left \le i \le right$，则说明区间 $[left, right]$ 中有一个整数 $i$ 没有被覆盖，返回 $\textit{false}$。
 
-时间复杂度 $O(n + M)$，空间复杂度 $O(M)$。其中 $n$ 和 $M$ 分别为区间的数量和区间的范围。
+如果遍历完差分数组 $\textit{diff}$ 后都没有返回 $\textit{false}$，则说明区间 $[left, right]$ 中的每个整数都被 $\textit{ranges}$ 中至少一个区间覆盖，返回 $\textit{true}$。
+
+时间复杂度 $O(n + M)$，空间复杂度 $O(M)$。其中 $n$ 是数组 $\textit{ranges}$ 的长度，而 $M$ 是区间的最大值，本题中 $M \le 50$。
 
 <!-- tabs:start -->
 
@@ -84,10 +86,10 @@ class Solution:
         for l, r in ranges:
             diff[l] += 1
             diff[r + 1] -= 1
-        cur = 0
+        s = 0
         for i, x in enumerate(diff):
-            cur += x
-            if left <= i <= right and cur == 0:
+            s += x
+            if s <= 0 and left <= i <= right:
                 return False
         return True
 ```
@@ -103,10 +105,10 @@ class Solution {
             ++diff[l];
             --diff[r + 1];
         }
-        int cur = 0;
+        int s = 0;
         for (int i = 0; i < diff.length; ++i) {
-            cur += diff[i];
-            if (i >= left && i <= right && cur == 0) {
+            s += diff[i];
+            if (s <= 0 && left <= i && i <= right) {
                 return false;
             }
         }
@@ -121,16 +123,16 @@ class Solution {
 class Solution {
 public:
     bool isCovered(vector<vector<int>>& ranges, int left, int right) {
-        int diff[52]{};
+        vector<int> diff(52);
         for (auto& range : ranges) {
             int l = range[0], r = range[1];
             ++diff[l];
             --diff[r + 1];
         }
-        int cur = 0;
-        for (int i = 0; i < 52; ++i) {
-            cur += diff[i];
-            if (i >= left && i <= right && cur <= 0) {
+        int s = 0;
+        for (int i = 0; i < diff.size(); ++i) {
+            s += diff[i];
+            if (s <= 0 && left <= i && i <= right) {
                 return false;
             }
         }
@@ -144,15 +146,15 @@ public:
 ```go
 func isCovered(ranges [][]int, left int, right int) bool {
 	diff := [52]int{}
-	for _, rg := range ranges {
-		l, r := rg[0], rg[1]
+	for _, e := range ranges {
+		l, r := e[0], e[1]
 		diff[l]++
 		diff[r+1]--
 	}
-	cur := 0
+	s := 0
 	for i, x := range diff {
-		cur += x
-		if i >= left && i <= right && cur <= 0 {
+		s += x
+		if s <= 0 && left <= i && i <= right {
 			return false
 		}
 	}
@@ -164,15 +166,15 @@ func isCovered(ranges [][]int, left int, right int) bool {
 
 ```ts
 function isCovered(ranges: number[][], left: number, right: number): boolean {
-    const diff = new Array(52).fill(0);
+    const diff: number[] = Array(52).fill(0);
     for (const [l, r] of ranges) {
         ++diff[l];
         --diff[r + 1];
     }
-    let cur = 0;
-    for (let i = 0; i < 52; ++i) {
-        cur += diff[i];
-        if (i >= left && i <= right && cur <= 0) {
+    let s = 0;
+    for (let i = 0; i < diff.length; ++i) {
+        s += diff[i];
+        if (s <= 0 && left <= i && i <= right) {
             return false;
         }
     }
@@ -190,15 +192,15 @@ function isCovered(ranges: number[][], left: number, right: number): boolean {
  * @return {boolean}
  */
 var isCovered = function (ranges, left, right) {
-    const diff = new Array(52).fill(0);
+    const diff = Array(52).fill(0);
     for (const [l, r] of ranges) {
         ++diff[l];
         --diff[r + 1];
     }
-    let cur = 0;
-    for (let i = 0; i < 52; ++i) {
-        cur += diff[i];
-        if (i >= left && i <= right && cur <= 0) {
+    let s = 0;
+    for (let i = 0; i < diff.length; ++i) {
+        s += diff[i];
+        if (s <= 0 && left <= i && i <= right) {
             return false;
         }
     }
diff --git a/solution/1800-1899/1893.Check if All the Integers in a Range Are Covered/README_EN.md b/solution/1800-1899/1893.Check if All the Integers in a Range Are Covered/README_EN.md
@@ -61,7 +61,17 @@ tags:
 
 <!-- solution:start -->
 
-### Solution 1
+### Solution 1: Difference Array
+
+We can use the idea of a difference array to create a difference array $\textit{diff}$ of length $52$.
+
+Next, we iterate through the array $\textit{ranges}$. For each interval $[l, r]$, we increment $\textit{diff}[l]$ by $1$ and decrement $\textit{diff}[r + 1]$ by $1$.
+
+Then, we iterate through the difference array $\textit{diff}$, maintaining a prefix sum $s$. For each position $i$, we increment $s$ by $\textit{diff}[i]$. If $s \le 0$ and $left \le i \le right$, it indicates that an integer $i$ within the interval $[left, right]$ is not covered, and we return $\textit{false}$.
+
+If we finish iterating through the difference array $\textit{diff}$ without returning $\textit{false}$, it means that every integer within the interval $[left, right]$ is covered by at least one interval in $\textit{ranges}$, and we return $\textit{true}$.
+
+The time complexity is $O(n + M)$, and the space complexity is $O(M)$. Here, $n$ is the length of the array $\textit{ranges}$, and $M$ is the maximum value of the interval, which in this case is $M \le 50$.
 
 <!-- tabs:start -->
 
@@ -74,10 +84,10 @@ class Solution:
         for l, r in ranges:
             diff[l] += 1
             diff[r + 1] -= 1
-        cur = 0
+        s = 0
         for i, x in enumerate(diff):
-            cur += x
-            if left <= i <= right and cur == 0:
+            s += x
+            if s <= 0 and left <= i <= right:
                 return False
         return True
 ```
@@ -93,10 +103,10 @@ class Solution {
             ++diff[l];
             --diff[r + 1];
         }
-        int cur = 0;
+        int s = 0;
         for (int i = 0; i < diff.length; ++i) {
-            cur += diff[i];
-            if (i >= left && i <= right && cur == 0) {
+            s += diff[i];
+            if (s <= 0 && left <= i && i <= right) {
                 return false;
             }
         }
@@ -111,16 +121,16 @@ class Solution {
 class Solution {
 public:
     bool isCovered(vector<vector<int>>& ranges, int left, int right) {
-        int diff[52]{};
+        vector<int> diff(52);
         for (auto& range : ranges) {
             int l = range[0], r = range[1];
             ++diff[l];
             --diff[r + 1];
         }
-        int cur = 0;
-        for (int i = 0; i < 52; ++i) {
-            cur += diff[i];
-            if (i >= left && i <= right && cur <= 0) {
+        int s = 0;
+        for (int i = 0; i < diff.size(); ++i) {
+            s += diff[i];
+            if (s <= 0 && left <= i && i <= right) {
                 return false;
             }
         }
@@ -134,15 +144,15 @@ public:
 ```go
 func isCovered(ranges [][]int, left int, right int) bool {
 	diff := [52]int{}
-	for _, rg := range ranges {
-		l, r := rg[0], rg[1]
+	for _, e := range ranges {
+		l, r := e[0], e[1]
 		diff[l]++
 		diff[r+1]--
 	}
-	cur := 0
+	s := 0
 	for i, x := range diff {
-		cur += x
-		if i >= left && i <= right && cur <= 0 {
+		s += x
+		if s <= 0 && left <= i && i <= right {
 			return false
 		}
 	}
@@ -154,15 +164,15 @@ func isCovered(ranges [][]int, left int, right int) bool {
 
 ```ts
 function isCovered(ranges: number[][], left: number, right: number): boolean {
-    const diff = new Array(52).fill(0);
+    const diff: number[] = Array(52).fill(0);
     for (const [l, r] of ranges) {
         ++diff[l];
         --diff[r + 1];
     }
-    let cur = 0;
-    for (let i = 0; i < 52; ++i) {
-        cur += diff[i];
-        if (i >= left && i <= right && cur <= 0) {
+    let s = 0;
+    for (let i = 0; i < diff.length; ++i) {
+        s += diff[i];
+        if (s <= 0 && left <= i && i <= right) {
             return false;
         }
     }
@@ -180,15 +190,15 @@ function isCovered(ranges: number[][], left: number, right: number): boolean {
  * @return {boolean}
  */
 var isCovered = function (ranges, left, right) {
-    const diff = new Array(52).fill(0);
+    const diff = Array(52).fill(0);
     for (const [l, r] of ranges) {
         ++diff[l];
         --diff[r + 1];
     }
-    let cur = 0;
-    for (let i = 0; i < 52; ++i) {
-        cur += diff[i];
-        if (i >= left && i <= right && cur <= 0) {
+    let s = 0;
+    for (let i = 0; i < diff.length; ++i) {
+        s += diff[i];
+        if (s <= 0 && left <= i && i <= right) {
             return false;
         }
     }
diff --git a/solution/1800-1899/1893.Check if All the Integers in a Range Are Covered/Solution.cpp b/solution/1800-1899/1893.Check if All the Integers in a Range Are Covered/Solution.cpp
@@ -1,16 +1,16 @@
 class Solution {
 public:
     bool isCovered(vector<vector<int>>& ranges, int left, int right) {
-        int diff[52]{};
+        vector<int> diff(52);
         for (auto& range : ranges) {
             int l = range[0], r = range[1];
             ++diff[l];
             --diff[r + 1];
         }
-        int cur = 0;
-        for (int i = 0; i < 52; ++i) {
-            cur += diff[i];
-            if (i >= left && i <= right && cur <= 0) {
+        int s = 0;
+        for (int i = 0; i < diff.size(); ++i) {
+            s += diff[i];
+            if (s <= 0 && left <= i && i <= right) {
                 return false;
             }
         }
diff --git a/solution/1800-1899/1893.Check if All the Integers in a Range Are Covered/Solution.go b/solution/1800-1899/1893.Check if All the Integers in a Range Are Covered/Solution.go
@@ -1,14 +1,14 @@
 func isCovered(ranges [][]int, left int, right int) bool {
 	diff := [52]int{}
-	for _, rg := range ranges {
-		l, r := rg[0], rg[1]
+	for _, e := range ranges {
+		l, r := e[0], e[1]
 		diff[l]++
 		diff[r+1]--
 	}
-	cur := 0
+	s := 0
 	for i, x := range diff {
-		cur += x
-		if i >= left && i <= right && cur <= 0 {
+		s += x
+		if s <= 0 && left <= i && i <= right {
 			return false
 		}
 	}
diff --git a/solution/1800-1899/1893.Check if All the Integers in a Range Are Covered/Solution.java b/solution/1800-1899/1893.Check if All the Integers in a Range Are Covered/Solution.java
@@ -6,10 +6,10 @@ public boolean isCovered(int[][] ranges, int left, int right) {
             ++diff[l];
             --diff[r + 1];
         }
-        int cur = 0;
+        int s = 0;
         for (int i = 0; i < diff.length; ++i) {
-            cur += diff[i];
-            if (i >= left && i <= right && cur == 0) {
+            s += diff[i];
+            if (s <= 0 && left <= i && i <= right) {
                 return false;
             }
         }
diff --git a/solution/1800-1899/1893.Check if All the Integers in a Range Are Covered/Solution.js b/solution/1800-1899/1893.Check if All the Integers in a Range Are Covered/Solution.js
@@ -5,15 +5,15 @@
  * @return {boolean}
  */
 var isCovered = function (ranges, left, right) {
-    const diff = new Array(52).fill(0);
+    const diff = Array(52).fill(0);
     for (const [l, r] of ranges) {
         ++diff[l];
         --diff[r + 1];
     }
-    let cur = 0;
-    for (let i = 0; i < 52; ++i) {
-        cur += diff[i];
-        if (i >= left && i <= right && cur <= 0) {
+    let s = 0;
+    for (let i = 0; i < diff.length; ++i) {
+        s += diff[i];
+        if (s <= 0 && left <= i && i <= right) {
             return false;
         }
     }
diff --git a/solution/1800-1899/1893.Check if All the Integers in a Range Are Covered/Solution.py b/solution/1800-1899/1893.Check if All the Integers in a Range Are Covered/Solution.py
@@ -4,9 +4,9 @@ def isCovered(self, ranges: List[List[int]], left: int, right: int) -> bool:
         for l, r in ranges:
             diff[l] += 1
             diff[r + 1] -= 1
-        cur = 0
+        s = 0
         for i, x in enumerate(diff):
-            cur += x
-            if left <= i <= right and cur == 0:
+            s += x
+            if s <= 0 and left <= i <= right:
                 return False
         return True
diff --git a/solution/1800-1899/1893.Check if All the Integers in a Range Are Covered/Solution.ts b/solution/1800-1899/1893.Check if All the Integers in a Range Are Covered/Solution.ts
@@ -1,13 +1,13 @@
 function isCovered(ranges: number[][], left: number, right: number): boolean {
-    const diff = new Array(52).fill(0);
+    const diff: number[] = Array(52).fill(0);
     for (const [l, r] of ranges) {
         ++diff[l];
         --diff[r + 1];
     }
-    let cur = 0;
-    for (let i = 0; i < 52; ++i) {
-        cur += diff[i];
-        if (i >= left && i <= right && cur <= 0) {
+    let s = 0;
+    for (let i = 0; i < diff.length; ++i) {
+        s += diff[i];
+        if (s <= 0 && left <= i && i <= right) {
             return false;
         }
     }
diff --git a/solution/1800-1899/1894.Find the Student that Will Replace the Chalk/README.md b/solution/1800-1899/1894.Find the Student that Will Replace the Chalk/README.md
@@ -161,10 +161,7 @@ func chalkReplacer(chalk []int, k int) int {
 
 ```ts
 function chalkReplacer(chalk: number[], k: number): number {
-    let s = 0;
-    for (const x of chalk) {
-        s += x;
-    }
+    const s = chalk.reduce((acc, cur) => acc + cur, 0);
     k %= s;
     for (let i = 0; ; ++i) {
         if (k < chalk[i]) {
diff --git a/solution/1800-1899/1894.Find the Student that Will Replace the Chalk/README_EN.md b/solution/1800-1899/1894.Find the Student that Will Replace the Chalk/README_EN.md
@@ -159,10 +159,7 @@ func chalkReplacer(chalk []int, k int) int {
 
 ```ts
 function chalkReplacer(chalk: number[], k: number): number {
-    let s = 0;
-    for (const x of chalk) {
-        s += x;
-    }
+    const s = chalk.reduce((acc, cur) => acc + cur, 0);
     k %= s;
     for (let i = 0; ; ++i) {
         if (k < chalk[i]) {
diff --git a/solution/1800-1899/1894.Find the Student that Will Replace the Chalk/Solution.ts b/solution/1800-1899/1894.Find the Student that Will Replace the Chalk/Solution.ts
diff --git a/solution/3200-3299/3213.Construct String with Minimum Cost/README.md b/solution/3200-3299/3213.Construct String with Minimum Cost/README.md

Original file line number	Diff line number	Diff line change
`@@ -6,10 +6,10 @@ public boolean isCovered(int[][] ranges, int left, int right) {`
`6`	`6`	`++diff[l];`
`7`	`7`	`--diff[r + 1];`
`8`	`8`	`}`
`9`		`- int cur = 0;`
	`9`	`+ int s = 0;`
`10`	`10`	`for (int i = 0; i < diff.length; ++i) {`
`11`		`- cur += diff[i];`
`12`		`- if (i >= left && i <= right && cur == 0) {`
	`11`	`+ s += diff[i];`
	`12`	`+ if (s <= 0 && left <= i && i <= right) {`
`13`	`13`	`return false;`
`14`	`14`	`}`
`15`	`15`	`}`
Original file line number	Diff line number	Diff line change
`@@ -1,13 +1,13 @@`
`1`	`1`	`function isCovered(ranges: number[][], left: number, right: number): boolean {`
`2`		`- const diff = new Array(52).fill(0);`
	`2`	`+ const diff: number[] = Array(52).fill(0);`
`3`	`3`	`for (const [l, r] of ranges) {`
`4`	`4`	`++diff[l];`
`5`	`5`	`--diff[r + 1];`
`6`	`6`	`}`
`7`		`- let cur = 0;`
`8`		`- for (let i = 0; i < 52; ++i) {`
`9`		`- cur += diff[i];`
`10`		`- if (i >= left && i <= right && cur <= 0) {`
	`7`	`+ let s = 0;`
	`8`	`+ for (let i = 0; i < diff.length; ++i) {`
	`9`	`+ s += diff[i];`
	`10`	`+ if (s <= 0 && left <= i && i <= right) {`
`11`	`11`	`return false;`
`12`	`12`	`}`
`13`	`13`	`}`