Skip to content

Commit 4d9760a

Browse files
yanglbmeyanglbme
authored
feat: add solutions to lc/lcof2 problem (doocs#3145)
* lc No.0539 & lcof2 No.035.Minimum Time Difference
1 parent 6a466f6 commit 4d9760a

File tree

17 files changed

+579
-277
lines changed

17 files changed

+579
-277
lines changed

‎lcof2/剑指 Offer II 035. 最小时间差/README.md

Lines changed: 94 additions & 52 deletions
Original file line numberDiff line numberDiff line change
@@ -50,11 +50,11 @@ edit_url: https://github.com/doocs/leetcode/edit/main/lcof2/%E5%89%91%E6%8C%87%2
5050

5151
### 方法一：排序
5252

53-
我们注意到，时间点最多只有 $24 \times 60$ 个，因此，当 $timePoints$ 长度超过 $24 \times 60$，说明有重复的时间点，提前返回 $0$。
53+
我们注意到，时间点最多只有 $24 \times 60 = 1440$ 个，因此，当 $timePoints$ 长度超过 $1440$，说明有重复的时间点，提前返回 $0$。
5454

55-
接下来，我们首先遍历时间列表，将其转换为“分钟制”列表 $mins$，比如，对于时间点 `13:14`，将其转换为 $13 \times 60 + 14$。
55+
接下来，我们首先遍历时间列表，将其转换为“分钟制”列表 $nums$，比如，对于时间点 `13:14`，将其转换为 $13 \times 60 + 14$。
5656

57-
接着将“分钟制”列表按升序排列，然后将此列表的最小时间 $mins[0]$ 加上 $24 \times 60$ 追加至列表尾部，用于处理最大值、最小值的差值这种特殊情况。
57+
接着将“分钟制”列表按升序排列，然后将此列表的最小时间 $nums[0]$ 加上 $1440$ 追加至列表尾部，用于处理最大值、最小值的差值这种特殊情况。
5858

5959
最后遍历“分钟制”列表，找出相邻两个时间的最小值即可。
6060

@@ -67,31 +67,32 @@ edit_url: https://github.com/doocs/leetcode/edit/main/lcof2/%E5%89%91%E6%8C%87%2
6767
```python
6868
class Solution:
6969
def findMinDifference(self, timePoints: List[str]) -> int:
70-
if len(timePoints) > 24 * 60:
70+
if len(timePoints) > 1440:
7171
return 0
72-
mins = sorted(int(t[:2]) * 60 + int(t[3:]) for t in timePoints)
73-
mins.append(mins[0] + 24 * 60)
74-
return min(b - a for a, b in pairwise(mins))
72+
nums = sorted(int(x[:2]) * 60 + int(x[3:]) for x in timePoints)
73+
nums.append(nums[0] + 1440)
74+
return min(b - a for a, b in pairwise(nums))
7575
```
7676

7777
#### Java
7878

7979
```java
8080
class Solution {
8181
public int findMinDifference(List<String> timePoints) {
82-
if (timePoints.size() > 24 * 60) {
82+
if (timePoints.size() > 1440) {
8383
return 0;
8484
}
85-
List<Integer> mins = new ArrayList<>();
86-
for (String t : timePoints) {
87-
String[] time = t.split(":");
88-
mins.add(Integer.parseInt(time[0]) * 60 + Integer.parseInt(time[1]));
85+
int n = timePoints.size();
86+
int[] nums = new int[n + 1];
87+
for (int i = 0; i < n; ++i) {
88+
String[] t = timePoints.get(i).split(":");
89+
nums[i] = Integer.parseInt(t[0]) * 60 + Integer.parseInt(t[1]);
8990
}
90-
Collections.sort(mins);
91-
mins.add(mins.get(0) + 24 * 60);
91+
Arrays.sort(nums, 0, n);
92+
nums[n] = nums[0] + 1440;
9293
int ans = 1 << 30;
93-
for (int i = 1; i < mins.size(); ++i) {
94-
ans = Math.min(ans, mins.get(i) - mins.get(i - 1));
94+
for (int i = 1; i <= n; ++i) {
95+
ans = Math.min(ans, nums[i] - nums[i - 1]);
9596
}
9697
return ans;
9798
}
@@ -104,18 +105,21 @@ class Solution {
104105
class Solution {
105106
public:
106107
int findMinDifference(vector<string>& timePoints) {
107-
if (timePoints.size() > 24 * 60) {
108+
if (timePoints.size() > 1440) {
108109
return 0;
109110
}
110-
vector<int> mins;
111-
for (auto& t : timePoints) {
112-
mins.push_back(stoi(t.substr(0, 2)) * 60 + stoi(t.substr(3)));
111+
int n = timePoints.size();
112+
vector<int> nums(n + 1);
113+
for (int i = 0; i < n; ++i) {
114+
int hours = stoi(timePoints[i].substr(0, 2));
115+
int minutes = stoi(timePoints[i].substr(3, 2));
116+
nums[i] = hours * 60 + minutes;
113117
}
114-
sort(mins.begin(), mins.end());
115-
mins.push_back(mins[0] + 24 * 60);
116-
int ans = 1 << 30;
117-
for (int i = 1; i < mins.size(); ++i) {
118-
ans = min(ans, mins[i] - mins[i - 1]);
118+
sort(nums.begin(), nums.begin() + n);
119+
nums[n] = nums[0] + 1440;
120+
int ans = INT_MAX;
121+
for (int i = 1; i <= n; ++i) {
122+
ans = min(ans, nums[i] - nums[i - 1]);
119123
}
120124
return ans;
121125
}
@@ -126,22 +130,27 @@ public:
126130
127131
```go
128132
func findMinDifference(timePoints []string) int {
129-
if len(timePoints) > 24*60 {
133+
if len(timePoints) > 1440 {
130134
return 0
131135
}
132-
var mins []int
133-
for _, t := range timePoints {
134-
time := strings.Split(t, ":")
135-
h, _ := strconv.Atoi(time[0])
136-
m, _ := strconv.Atoi(time[1])
137-
mins = append(mins, h*60+m)
136+
137+
n := len(timePoints)
138+
nums := make([]int, n+1)
139+
for i, time := range timePoints {
140+
parts := strings.Split(time, ":")
141+
hours, _ := strconv.Atoi(parts[0])
142+
minutes, _ := strconv.Atoi(parts[1])
143+
nums[i] = hours*60 + minutes
138144
}
139-
sort.Ints(mins)
140-
mins = append(mins, mins[0]+24*60)
145+
146+
sort.Ints(nums[:n])
147+
nums[n] = nums[0] + 1440
148+
141149
ans := 1 << 30
142-
for i, x := range mins[1:] {
143-
ans = min(ans, x-mins[i])
150+
for i := 1; i <= n; i++ {
151+
ans = min(ans, nums[i]-nums[i-1])
144152
}
153+
145154
return ans
146155
}
147156
```
@@ -150,45 +159,78 @@ func findMinDifference(timePoints []string) int {
150159

151160
```ts
152161
function findMinDifference(timePoints: string[]): number {
153-
if (timePoints.length > 24 * 60) {
162+
if (timePoints.length > 1440) {
154163
return 0;
155164
}
156-
const mins: number[] = timePoints.map(timePoint => {
157-
const [hour, minute] = timePoint.split(':').map(num => parseInt(num));
158-
return hour * 60 + minute;
159-
});
160-
mins.sort((a, b) => a - b);
161-
mins.push(mins[0] + 24 * 60);
165+
const n = timePoints.length;
166+
const nums: number[] = Array(n + 1);
167+
for (let i = 0; i < n; ++i) {
168+
const [hours, minutes] = timePoints[i].split(':').map(Number);
169+
nums[i] = hours * 60 + minutes;
170+
}
171+
nums.sort((a, b) => a - b);
172+
nums[n] = nums[0] + 1440;
162173
let ans = 1 << 30;
163-
for (let i = 1; i < mins.length; ++i) {
164-
ans = Math.min(ans, mins[i] - mins[i - 1]);
174+
for (let i = 1; i <= n; ++i) {
175+
ans = Math.min(ans, nums[i] - nums[i - 1]);
165176
}
166177
return ans;
167178
}
168179
```
169180

181+
#### Rust
182+
183+
```rust
184+
impl Solution {
185+
pub fn find_min_difference(time_points: Vec<String>) -> i32 {
186+
if time_points.len() > 1440 {
187+
return 0;
188+
}
189+
190+
let n = time_points.len();
191+
let mut nums: Vec<i32> = Vec::with_capacity(n + 1);
192+
193+
for time in time_points.iter() {
194+
let parts: Vec<i32> = time.split(':').map(|s| s.parse().unwrap()).collect();
195+
let minutes = parts[0] * 60 + parts[1];
196+
nums.push(minutes);
197+
}
198+
199+
nums.sort();
200+
nums.push(nums[0] + 1440);
201+
202+
let mut ans = i32::MAX;
203+
for i in 1..=n {
204+
ans = ans.min(nums[i] - nums[i - 1]);
205+
}
206+
207+
ans
208+
}
209+
}
210+
```
211+
170212
#### Swift
171213

172214
```swift
173215
class Solution {
174216
func findMinDifference(_ timePoints: [String]) -> Int {
175-
if timePoints.count > 24 * 60 {
217+
if timePoints.count > 1440 {
176218
return 0
177219
}
178220

179-
var mins = [Int]()
221+
var nums = [Int]()
180222

181223
for t in timePoints {
182224
let time = t.split(separator: ":").map { Int($0)! }
183-
mins.append(time[0] * 60 + time[1])
225+
nums.append(time[0] * 60 + time[1])
184226
}
185227

186-
mins.sort()
187-
mins.append(mins[0] + 24 * 60)
228+
nums.sort()
229+
nums.append(nums[0] + 1440)
188230

189231
var ans = Int.max
190-
for i in 1..<mins.count {
191-
ans = min(ans, mins[i] - mins[i - 1])
232+
for i in 1..<nums.count {
233+
ans = min(ans, nums[i] - nums[i - 1])
192234
}
193235

194236
return ans

‎lcof2/剑指 Offer II 035. 最小时间差/Solution.cpp

Lines changed: 12 additions & 9 deletions
Original file line numberDiff line numberDiff line change
@@ -1,18 +1,21 @@
11
class Solution {
22
public:
33
int findMinDifference(vector<string>& timePoints) {
4-
if (timePoints.size() > 24 * 60) {
4+
if (timePoints.size() > 1440) {
55
return 0;
66
}
7-
vector<int> mins;
8-
for (auto& t : timePoints) {
9-
mins.push_back(stoi(t.substr(0, 2)) * 60 + stoi(t.substr(3)));
7+
int n = timePoints.size();
8+
vector<int> nums(n + 1);
9+
for (int i = 0; i < n; ++i) {
10+
int hours = stoi(timePoints[i].substr(0, 2));
11+
int minutes = stoi(timePoints[i].substr(3, 2));
12+
nums[i] = hours * 60 + minutes;
1013
}
11-
sort(mins.begin(), mins.end());
12-
mins.push_back(mins[0] + 24 * 60);
13-
int ans = 1 << 30;
14-
for (int i = 1; i < mins.size(); ++i) {
15-
ans = min(ans, mins[i] - mins[i - 1]);
14+
sort(nums.begin(), nums.begin() + n);
15+
nums[n] = nums[0] + 1440;
16+
int ans = INT_MAX;
17+
for (int i = 1; i <= n; ++i) {
18+
ans = min(ans, nums[i] - nums[i - 1]);
1619
}
1720
return ans;
1821
}

‎lcof2/剑指 Offer II 035. 最小时间差/Solution.go

Lines changed: 16 additions & 11 deletions
Original file line numberDiff line numberDiff line change
@@ -1,19 +1,24 @@
11
func findMinDifference(timePoints []string) int {
2-
if len(timePoints) > 24*60 {
2+
if len(timePoints) > 1440 {
33
return 0
44
}
5-
var mins []int
6-
for _, t := range timePoints {
7-
time := strings.Split(t, ":")
8-
h, _ := strconv.Atoi(time[0])
9-
m, _ := strconv.Atoi(time[1])
10-
mins = append(mins, h*60+m)
5+
6+
n := len(timePoints)
7+
nums := make([]int, n+1)
8+
for i, time := range timePoints {
9+
parts := strings.Split(time, ":")
10+
hours, _ := strconv.Atoi(parts[0])
11+
minutes, _ := strconv.Atoi(parts[1])
12+
nums[i] = hours*60 + minutes
1113
}
12-
sort.Ints(mins)
13-
mins = append(mins, mins[0]+24*60)
14+
15+
sort.Ints(nums[:n])
16+
nums[n] = nums[0] + 1440
17+
1418
ans := 1 << 30
15-
for i, x := range mins[1:] {
16-
ans = min(ans, x-mins[i])
19+
for i := 1; i <= n; i++ {
20+
ans = min(ans, nums[i]-nums[i-1])
1721
}
22+
1823
return ans
1924
}

‎lcof2/剑指 Offer II 035. 最小时间差/Solution.java

Lines changed: 10 additions & 9 deletions
Original file line numberDiff line numberDiff line change
@@ -1,18 +1,19 @@
11
class Solution {
22
public int findMinDifference(List<String> timePoints) {
3-
if (timePoints.size() > 24 * 60) {
3+
if (timePoints.size() > 1440) {
44
return 0;
55
}
6-
List<Integer> mins = new ArrayList<>();
7-
for (String t : timePoints) {
8-
String[] time = t.split(":");
9-
mins.add(Integer.parseInt(time[0]) * 60 + Integer.parseInt(time[1]));
6+
int n = timePoints.size();
7+
int[] nums = new int[n + 1];
8+
for (int i = 0; i < n; ++i) {
9+
String[] t = timePoints.get(i).split(":");
10+
nums[i] = Integer.parseInt(t[0]) * 60 + Integer.parseInt(t[1]);
1011
}
11-
Collections.sort(mins);
12-
mins.add(mins.get(0) + 24 * 60);
12+
Arrays.sort(nums, 0, n);
13+
nums[n] = nums[0] + 1440;
1314
int ans = 1 << 30;
14-
for (int i = 1; i < mins.size(); ++i) {
15-
ans = Math.min(ans, mins.get(i) - mins.get(i - 1));
15+
for (int i = 1; i <= n; ++i) {
16+
ans = Math.min(ans, nums[i] - nums[i - 1]);
1617
}
1718
return ans;
1819
}

‎lcof2/剑指 Offer II 035. 最小时间差/Solution.py

Lines changed: 4 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -1,7 +1,7 @@
11
class Solution:
22
def findMinDifference(self, timePoints: List[str]) -> int:
3-
if len(timePoints) > 24 * 60:
3+
if len(timePoints) > 1440:
44
return 0
5-
mins = sorted(int(t[:2]) * 60 + int(t[3:]) for t in timePoints)
6-
mins.append(mins[0] + 24 * 60)
7-
return min(b - a for a, b in pairwise(mins))
5+
nums = sorted(int(x[:2]) * 60 + int(x[3:]) for x in timePoints)
6+
nums.append(nums[0] + 1440)
7+
return min(b - a for a, b in pairwise(nums))

‎lcof2/剑指 Offer II 035. 最小时间差/Solution.rs

Lines changed: 26 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,26 @@
1+
impl Solution {
2+
pub fn find_min_difference(time_points: Vec<String>) -> i32 {
3+
if time_points.len() > 1440 {
4+
return 0;
5+
}
6+
7+
let n = time_points.len();
8+
let mut nums: Vec<i32> = Vec::with_capacity(n + 1);
9+
10+
for time in time_points.iter() {
11+
let parts: Vec<i32> = time.split(':').map(|s| s.parse().unwrap()).collect();
12+
let minutes = parts[0] * 60 + parts[1];
13+
nums.push(minutes);
14+
}
15+
16+
nums.sort();
17+
nums.push(nums[0] + 1440);
18+
19+
let mut ans = i32::MAX;
20+
for i in 1..=n {
21+
ans = ans.min(nums[i] - nums[i - 1]);
22+
}
23+
24+
ans
25+
}
26+
}

0 commit comments

Comments
 (0)