Giao dịch không hợp lệ trong C++

Mô tả bài toán

Cho danh sách giao dịch dạng "name,time,amount,city". Giao dịch không hợp lệ nếu:

• Số tiền > 1000.
• Hoặc xảy ra trong 60 phút (kể cả 2 đầu) của giao dịch cùng tên nhưng thành phố khác.

Trả về danh sách tất cả giao dịch không hợp lệ.

Ví dụ: ["alice,20,800,mtv","bob,50,1200,mtv"] → ["bob,50,1200,mtv"].

Giải thuật

1. Phân tích từng giao dịch thành struct {name, time, amount, city}.
2. Gom nhóm theo tên dùng map<string, vector<Transaction>>.
3. Với mỗi giao dịch mới, so sánh với tất cả giao dịch trước của cùng tên:
   • Nếu khác thành phố và |time_diff| ≤ 60 → cả hai đều không hợp lệ.
4. Nếu amount > 1000 → không hợp lệ.
5. Dùng set<string> để loại trùng lặp.

Cài đặt C++

#include <bits/stdc++.h>
using namespace std;

struct Transaction {
    string name, city;
    int time, amount;
};

class Solution {
    Transaction parse(string s) {
        Transaction t; string tmp; int idx = 0;
        for (char c : s) {
            if (c == ',') {
                if (idx == 0) t.name = tmp;
                else if (idx == 1) t.time = stoi(tmp);
                else if (idx == 2) t.amount = stoi(tmp);
                idx++; tmp.clear();
            } else tmp += c;
        }
        t.city = tmp;
        return t;
    }
public:
    vector<string> invalidTransactions(vector<string>& transactions) {
        unordered_map<string, vector<Transaction>> mp;
        set<string> invalid;
        for (auto& s : transactions) {
            Transaction cur = parse(s);
            for (auto& prev : mp[cur.name]) {
                if (prev.city != cur.city && abs(prev.time - cur.time) <= 60) {
                    invalid.insert(prev.name + "," + to_string(prev.time) + "," + to_string(prev.amount) + "," + prev.city);
                    invalid.insert(s);
                }
            }
            if (cur.amount > 1000) invalid.insert(s);
            mp[cur.name].push_back(cur);
        }
        return vector<string>(invalid.begin(), invalid.end());
    }
};

int main() {
    vector<string> v = {"alice,20,800,mtv","bob,50,1200,mtv"};
    Solution ob;
    for (auto& s : ob.invalidTransactions(v)) cout << s << endl;
    return 0;
}

Độ phức tạp

• Thời gian: O(n^2) worst-case (n giao dịch cùng tên).
• Không gian: O(n).