18 tháng 7 năm 2024 - Máy tính
1. Mô tả bài toán
Giả sử chúng ta có một tệp nhật ký ghi lại các lần đăng nhập của người dùng, trong đó mỗi dòng ghi lại chứa ba mục được phân cách bởi dấu cách: ID người dùng, ngày đăng nhập (định dạng: yyyy-MM-dd) và thời gian đăng nhập (định dạng: HH:mm:ss). Lưu ý rằng các dòng ghi lại này không được sắp xếp theo thứ tự thời gian mà ở trạng thái hỗn loạn (ví dụ như dòng ghi nhận 1002 2023-02-06 12:10:01 xuất hiện trước dòng 1002 2023-02-05 11:10:01).
Yêu cầu là hãy tính toán số ngày đăng nhập liên tục dài nhất của mỗi người dùng và hiển thị kết quả theo định dạng: ID người dùng: Số ngày đăng nhập liên tục dài nhất.
Ví dụ đầu vào:
# 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
Ví dụ đầu ra:
1002: 5
1001: 4
Giải thích 79bet tặng 128k trải nghiệm khi đăng kết quả:
Người dùng 1001 có số ngày đăng nhập liên tục dài nhất là 4, bắt đầu iwin58 từ ngày 2023-02-01 đến 2023-02-04, tổng cộng 4 ngày:
1001 2023-02-01
1001 2023-02-02
1001 2023-02-03
1001 2023-02-04
Người dùng 1002 có số ngày đăng nhập liên tục dài nhất là 5, bắt đầu từ ngày 2023-02-04 đến 2023-02-08, tổng cộng 5 ngày:
1002 2023-02-04
1002 2023-02-05
1002 2023-02-06 [m99 club](/post/hundreds-of-birds/)
1002 2023-02-07
1002 2023-02-08
2. Cách tiếp cận giải bài toán
Đọc và lưu trữ dữ liệu
Trước tiên, chúng ta cần sử dụng các công cụ phù hợp để đọc nội dung từng dòng của tệp nhật ký login.log. Trong quá trình đọc, chúng ta sẽ lưu trữ ngày đăng nhập (có thể bỏ qua thời gian) theo từng ID người dùng vào các tập hợp tương ứng. Tập hợp này nên đảm bảo loại bỏ các phần tử trùng lặp và sắp xếp theo thứ tự để thuận tiện cho việc tính toán sau này.
Tính toán dữ liệu
Phần này sẽ thực hiện phép tính đối với tập hợp ngày đăng nhập đã được lọc và sắp xếp cho từng ID người dùng. Chúng ta sẽ áp dụng thuật toán lập trình động để tính toán số ngày đăng nhập liên tục dài nhất từ dãy ngày đã cho.
3. Thực thi bằng Java
Dựa trên cách tiếp cận nêu trên, mã nguồn Java tương ứng được cung cấp dưới đây:
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 (getDurationDays(previousDate, currentDate) == 1) {
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);
}
}
// In kết quả
logins.forEach((id, dates) -> System.out.println(id + ": " + getMaxConsecutiveDays(new ArrayList<>(dates))));
} catch (IOException e) {
throw new RuntimeException(e);
}
}
}
-
Đọc và lưu trữ dữ liệu: Phương thức
main()sử dụng lớpScannerđể đọc từng dòng của tệplogin.log. Sau đó, mỗi dòng được chia thành ba phần thông tin bằng cách sử dụng dấu cách làm phân cách. Chúng ta lấy phần đầu tiên là ID người dùng và phần thứ hai là ngày đăng nhập, rồi lưu trữ chúng vào cấu trúc dữ liệuMap<String, Set<String>>(trong đó ID người dùng đóng vai trò là khóa, còn tập hợp các ngày đăng nhập là giá trị). Lưu ý rằng chúng ta sử dụngTreeSetđể đảm bảo tính duy nhất của các ngày và đồng thời giữ thứ tự tăng dần. -
Tính toán dữ liệu: Tiếp theo, trong phương thức
main(), chúng ta gọi hàmforEachđể xử lý từng ID người dùng. Đối với mỗi ID, tập hợp ngày đăng nhậpTreeSetđược chuyển đổi thành danh sáchList, sau đó truyền danh sách này vào phương thứcgetMaxConsecutiveDays()để tính toán số ngày đăng nhập liên tục dài nhất.
Phương thức getMaxConsecutiveDays() áp dụng thuật toán lập trình động để tìm số ngày đăng nhập liên tục dài nhất. Nó sử dụng hai biến maxConsecutiveDays và candidateMaxConsecutiveDays để lưu trữ số ngày liên tục dài nhất hiện tại và tiềm năng. Ban đầu cả hai đều được khởi tạo là 1. Khi duyệt qua danh sách các ngày, nếu khoảng cách giữa ngày hiện tại và ngày trước đó là 1, thì candidateMaxConsecutiveDays sẽ được tăng lên 1 đơn vị. Ngược lại, nó sẽ được đặt lại về 1. Cuối cùng, chúng ta kiểm tra xem candidateMaxConsecutiveDays có lớn hơn maxConsecutiveDays hay không và cập nhật giá trị nếu cần thiết.
Chú ý rằng phương thức getMaxConsecutiveDays() sử dụng phương thức getDurationDays() để xác định xem hai ngày có liền kề nhau hay không.
4. Kết luận
Bài viết này đã giới thiệu bài toán thuật toán “Tính số ngày đăng nhập liên tục dài nhất của từng người dùng từ nhật ký đăng nhập”, phân tích cách tiếp cận giải quyết vấn đề và cung cấp mã nguồn Java tương ứng. Mã nguồn đầy đủ đã được lưu trữ trên GitHub, mọi người có thể theo dõi hoặc fork dự án.
#ThuậtToán #Java