转化时间需要的最少操作数
难度:
标签:
题目描述
代码结果
运行时间: 22 ms, 内存: 16.2 MB
/*
* This implementation is similar to the basic Java solution but utilizes Java Streams where applicable.
* We still calculate the difference in minutes and use a greedy approach to minimize operations.
* The difference is calculated using streams and we use a stream for operations calculation as well.
*/
import java.util.stream.Stream;
public class TimeConverterStream {
public int convertTime(String current, String correct) {
int currMinutes = Stream.of(current.split(":"))
.mapToInt(Integer::parseInt)
.reduce(0, (a, b) -> a * 60 + b);
int corrMinutes = Stream.of(correct.split(":"))
.mapToInt(Integer::parseInt)
.reduce(0, (a, b) -> a * 60 + b);
int diff = corrMinutes - currMinutes;
return Stream.of(60, 15, 5, 1)
.mapToInt(inc -> {
int result = diff / inc;
diff %= inc;
return result;
}).sum();
}
}
解释
方法:
此题解采用贪心算法的思路。首先,将当前时间和正确时间转换为分钟数,然后计算它们之间的时间差。接着,从最大的时间单位(60分钟)开始,尽可能多地使用该时间单位进行转换,直到剩余时间小于该时间单位。然后,切换到下一个较小的时间单位(15分钟、5分钟、1分钟),重复上述过程,直到剩余时间为0。这样可以保证操作次数最少。
时间复杂度:
O(1)
空间复杂度:
O(1)