By Loser1 from Learning AI with Loser

Chào các bạn coder thân mến! Lại Loser1 đây, đến từ Learning AI with Loser , trở lại với một bài toán “nóng hổi” khác! Thử thách hôm nay xoay quanh việc thiết kế một cấu trúc dữ liệu thông minh để xử lý luồng số và truy xuất tích của k số cuối cùng một cách hiệu quả. Cùng bắt đầu thôi nào! 🚀

Input: 
["ProductOfNumbers","add","add","add","add","add","getProduct","getProduct","getProduct","add","getProduct"]
[[],[3],[0],[2],[5],[4],[2],[3],[4],[8],[2]]
Output: 
[null,null,null,null,null,null,20,40,0,null,32]
Giải thích: 
ProductOfNumbers productOfNumbers = new ProductOfNumbers();
productOfNumbers.add(3);        // [3]
productOfNumbers.add(0);        // [3,0]
productOfNumbers.add(2);        // [3,0,2]
productOfNumbers.add(5);        // [3,0,2,5]
productOfNumbers.add(4);        // [3,0,2,5,4]
productOfNumbers.getProduct(2); // return 20. Tích của 2 số cuối là 5 * 4 = 20
productOfNumbers.getProduct(3); // return 40. Tích của 3 số cuối là 2 * 5 * 4 = 40
productOfNumbers.getProduct(4); // return 0. Tích của 4 số cuối là 0 * 2 * 5 * 4 = 0
productOfNumbers.add(8);        // [3,0,2,5,4,8]
productOfNumbers.getProduct(2); // return 32. Tích của 2 số cuối là 4 * 8 = 32
    

🌟 Intuition (Trực giác ban đầu)

"Cỗ máy thời gian" Prefix Trick

Hãy tưởng tượng bạn có một cỗ máy thời gian (hay còn gọi là mảng prefix product) ghi lại tích của tất cả các số lên đến từng thời điểm cụ thể. Khi thêm một số mới, bạn cập nhật cỗ máy này. Nhưng nếu gặp số 0, nó giống như nhấn nút reset vậy—vì bất kỳ tích nào liên quan đến 0 đều sẽ trở thành 0!

🛠 Approach (Phương pháp tiếp cận)

Chiến lược từng bước

1. Mảng Prefix Product: Duy trì một mảng mà mỗi phần tử tại chỉ số i lưu trữ tích của tất cả các số từ đầu đến i.
2. Xử lý số 0: Khi thêm số 0, reset toàn bộ mảng. Điều này đảm bảo rằng bất kỳ truy vấn tích nào vượt qua vị trí chứa 0 sẽ tự động trả về 0.
3. Truy vấn hiệu quả: Đối với getProduct(k), kiểm tra xem truy vấn có vượt quá lần reset gần nhất (gây ra bởi số 0) không. Nếu có, trả về 0. Ngược lại, tính tích bằng cách sử dụng mảng prefix.

🎨 Illustration (Minh họa)

Ví dụ từng bước

Giả sử chúng ta thêm các số [3, 0, 2, 5, 4]:

• Sau khi thêm 3: [1, 3]
• Sau khi thêm 0: [1] (reset!)
• Sau khi thêm 2: [1, 2]
• Sau khi thêm 5: [1, 2, 10]
• Sau khi thêm 4: [1, 2, 10, 40]

Khi truy vấn getProduct(2), chúng ta lấy 40 / 10 = 4. Đợi đã, không phải! Với k=2, n=4, nên prefix_sum[3] / prefix_sum[1] = 40 / 2 = 20. ✅

⏱ Complexity (Độ phức tạp)

• Thời gian:
• add(int num): O(1) – Cập nhật mảng prefix chỉ mất thời gian hằng số.
• getProduct(int k): O(1) – Tính tích cũng chỉ mất thời gian hằng số.
• Không gian:
• O(n) – Lưu trữ mảng prefix, nơi n là số lượng phần tử đã thêm.

💻 Code (Mã nguồn)

class ProductOfNumbers {
private:
    vector<int> prefix_sum; 
public:
    ProductOfNumbers() {
        prefix_sum.push_back(1); // Khởi tạo với giá trị 1
    }

    void add(int num) {
        if (num == 0) {
            prefix_sum = {1}; // Reset cỗ máy thời gian!
        } else {
            prefix_sum.push_back(prefix_sum.back() * num);
        }
    }

    int getProduct(int k) {
        int n = prefix_sum.size();
        if (k >= n) {
            return 0; // Số 0 đang ẩn trong quá khứ!
        }
        return prefix_sum[n - 1] / prefix_sum[n - k - 1];
    }
};

🚨 Pitfalls to Avoid (Những lỗi cần tránh)

1. Quên Reset: Nếu bạn không reset mảng prefix khi gặp số 0, các tích cũ sẽ làm hỏng kết quả tính toán mới.
2. Lỗi Off-by-One: Mảng prefix bắt đầu với giá trị 1, nên k phải được so sánh với n-1, không phải n.

🏆 Final Thoughts (Suy nghĩ cuối cùng)

Bài toán này dạy chúng ta sức mạnh của mảng prefix và cách reset thông minh. Nó giống như có một bức ảnh chụp lịch sử để trả lời các câu hỏi tương lai ngay lập tức! Hãy luyện tập nhiều hơn, và sớm thôi, bạn sẽ "du hành thời gian" qua code một cách dễ dàng.

Hẹn gặp lại các bạn vào Day 37! Hãy giữ vững chuỗi thử thách này nhé! 💪

👉 Bạn nghĩ sao? Nếu thêm số âm vào luồng, bạn sẽ sửa đổi giải pháp này như thế nào? Comment bên dưới để chia sẻ ý kiến của bạn nhé!

🔗 Chia sẻ bài viết này với bạn bè đang gặp khó khăn với prefix sums!

Yêu thích series này? Theo dõi @LearningAIWithLoser để nhận những bài học coding hàng ngày! 🚀

CODE EDITOR

📌 Hashtags:
#leetcode #leetcodedaily #coding #datastructures #algorithms #learningwithlosers #leetcode 3066 # leetcodedaily36