趣味算法题：从登录日志中计算各个用户的最长连续登录天数
1 题目描述
假设我们有一个记录用户登录的日志文件，该文件有多行记录，每一行记录包含用户 ID、登录日期（格式为：yyyy-MM-dd）和登录时间（格式为：HH:mm:ss）三个以空格分割的条目。记录并不是以时间先后排序的，而是乱序的（如：样例输入中的记录 1002 2023-02-06 12:10:01 在
1002 2023-02-05 11:10:01 之前）。请计算每个用户的最长连续登录天数，输出格式为：用户 ID: 最长连续登录天数（如：样例输出中的 1002: 5）。
样例输入：
# login.log
1001 2023-02-01 21:10:01
1001 2023-02-01 22:10:02
1002 2023-02-01 21:10:01
1002 2023-02-02 12:10:01
1002 2023-02-02 15:10:01
1001 2023-02-02 21:10:01
1001 2023-02-03 21:10:01
1001 2023-02-04 21:10:01
1002 2023-02-04 10:10:01
1002 2023-02-06 12:10:01
1002 2023-02-05 11:10:01
1002 2023-02-07 15:10:01
1002 2023-02-08 10:10:01
样例输出：
1002: 5
1001: 4
结果解释：
用户 1001 的最长连续登录天数为 4，即自 2023-02-01 到 2023-02-04 连续登录了 4 天：
1001 2023-02-01
1002 2023-02-02
1001 2023-02-03
1001 2023-02-04
用户 1002 的最长连续登录天数为 5，即自 2023-02-04 到 2023-02-08 连续登录了 5 天：
1002 2023-02-04
1002 2023-02-05
1002 2023-02-06
1002 2023-02-07
1002 2023-02-08
2 解题思路
数据读取与存储
我们首先需要使用对应的工具包将日志文件 login.log 中的内容进行逐行读取，然后在读取的过程中按照不同的用户 ID 来将登录日期（登录时间可以忽略）存储到各自的集合里边。而且这个集合最好是去重的且是排序的，以方便后续的计算。
数据计算
该部分针对上一步生成的每一个用户 ID 对应的去过重且排好序的登录日期集合进行计算，即使用一种动态规划算法从一串登录日期中计算出最长的连续天数。
3 Java 实现
针对如上解题思路，对应的 Java 实现代码如下：
import java.io.IOException;
import java.io.InputStream;
import java.time.LocalDate;
import java.time.format.DateTimeFormatter;
import java.time.temporal.ChronoUnit;
import java.util.*;
public class Solution {
private static final DateTimeFormatter DATE_FORMATTER = DateTimeFormatter.ofPattern("yyyy-MM-dd");
private static long getDurationDays(String date1, String date2) {
LocalDate localDate1 = LocalDate.parse(date1, DATE_FORMATTER);
LocalDate localDate2 = LocalDate.parse(date2, DATE_FORMATTER);
return ChronoUnit.DAYS.between(localDate1, localDate2);
}
private static int getMaxConsecutiveDays(List<String> dates) {
int maxConsecutiveDays = 1;
int candidateMaxConsecutiveDays = 1;
String previousDate = dates.get(0);
for (int i = 1; i < dates.size(); i++) {
String currentDate = dates.get(i);
if (1 == getDurationDays(previousDate, currentDate)) {
candidateMaxConsecutiveDays++;
} else {
candidateMaxConsecutiveDays = 1;
}
if (candidateMaxConsecutiveDays > maxConsecutiveDays) {
maxConsecutiveDays = candidateMaxConsecutiveDays;
}
previousDate = currentDate;
}
return maxConsecutiveDays;
}
public static void main(String[] args) {
Map<String, Set<String>> logins = new HashMap<>();
try (InputStream inputStream = Solution.class.getResourceAsStream("login.log")) {
Scanner scanner = new Scanner(inputStream);
while (scanner.hasNextLine()) {
String line = scanner.nextLine();
String[] items = line.split(" ");
String id = items[0];
String date = items[1];
if (!logins.containsKey(id)) {
logins.put(id, new TreeSet<>(Collections.singleton(date)));
} else {
Set<String> dates = logins.get(id);
dates.add(date);
logins.put(id, dates);
}
}
// print result
logins.forEach((id, dates) -> System.out.println(id + ": " + getMaxConsecutiveDays(dates.stream().toList())));
} catch (IOException e) {
throw new RuntimeException(e);
}
}
}
数据读取与存储
如上代码的
main()方法使用Scanner对login.log文件中的内容进行逐行读取。然后针对每一行，使用空格将三段信息进行分割，然后取第一段的用户 ID 和第二段的登录日期，并将结果存储到Map<String, Set<String>>数据结构中（用户 ID 为键，登录日期Set为值。注意该Set使用的实现是TreeSet，不仅可以保证去重，还可以保证顺序）。数据计算
接下来在
main()方法调用forEach，针对每个用户 ID，将其对应的登录日期TreeSet转换为一个List，然后将该登陆日期List传入getMaxConsecutiveDays()方法来获取最长的连续天数。getMaxConsecutiveDays()使用了动态规划算法来计算最长的连续天数。即使用maxConsecutiveDays和candidateMaxConsecutiveDays两个变量来表示当前计算到的最长连续天数和可能的最长连续天数，初始时都为 1；然后自第二个元素起，若当前日期与上一个日期连续，则candidateMaxConsecutiveDays++，否则candidateMaxConsecutiveDays重新置为 1，最后判断一下candidateMaxConsecutiveDays是否比maxConsecutiveDays大，若是，则将maxConsecutiveDays重新设置，这样循环计算到最后一个元素时得到的maxConsecutiveDays值即为最终的最长连续天数。注意：
getMaxConsecutiveDays()方法中使用了getDurationDays()方法来获取两个日期是否连续。
4 小结
本文首先介绍了算法题目「从登录日志中计算各个用户的最长连续登录天数」的题目要求，然后分析了解决该题目的思路，最后列出了对应的 Java 实现。完整代码已托管至 GitHub，欢迎关注或 Fork。
评论
正在加载评论......