[LeetCode] 1169. Invalid Transactions

[grandyang]

A transaction is possibly invalid if:

• the amount exceeds $1000, or;
• if it occurs within (and including) 60 minutes of another transaction with the same name in a different city.

You are given an array of strings transaction where transactions[i] consists of comma-separated values representing the name, time (in minutes), amount, and city of the transaction.

Return a list of transactions that are possibly invalid. You may return the answer in any order.

Example 1:

Input: transactions = ["alice,20,800,mtv","alice,50,100,beijing"]
Output: ["alice,20,800,mtv","alice,50,100,beijing"]
Explanation: The first transaction is invalid because the second transaction occurs within a difference of 60 minutes, have the same name and is in a different city. Similarly the second one is invalid too.

Example 2:

Input: transactions = ["alice,20,800,mtv","alice,50,1200,mtv"]
Output: ["alice,50,1200,mtv"]

Example 3:

Input: transactions = ["alice,20,800,mtv","bob,50,1200,mtv"]
Output: ["bob,50,1200,mtv"]

Constraints:

• transactions.length <= 1000
• Each transactions[i] takes the form "{name},{time},{amount},{city}"
• Each {name} and {city} consist of lowercase English letters, and have lengths between 1 and 10.
• Each {time} consist of digits, and represent an integer between 0 and 1000.
• Each {amount} consist of digits, and represent an integer between 0 and 2000.

这道题让找出所有非法的交易，这里的交易是由四个信息组成的，名称，时间，金额，和地点。这里定义的非法交易有两种情况，一种是金额大于 1000 的，另一种是跟任意一个相同名字但在其他城市的交易且在 60 分钟内发生的。这道题还是主要考察字符串的处理，信息都在一个字符串中，肯定要把它们提取出来，Java 中可以直接调用 split 函数，而 C++ 中只好使用字符串流来处理了，将四个信息拆分到不同的字符串中，然后直接判断拆分出的交易额，若大于 1000，加入到一个 HashSet 中，这里用 HashSet 是因为判断第二个非法条件时候去重复用。第二个非法条件是说相同名字，且在不同城市，比较好的处理方法就是进行分类，将所有相同名字的交易都放到同一个数组中，即建立名字和其对应的交易数组之间的映射，这里的每个交易还是保存的是拆分好的交易信息数组。现在遍历所有相同名字的交易，若城市不同，且交易时间在 60 分钟内，则将这两个互相比较的交易都加入 HashSet，现在就知道为啥使用 HashSet 了，因为可以去重复。每次记得要把当前拆分好的交易信息加入到 HashMap 对应的位置。这道题后来的 Test Cases 加入了相同交易，四个信息完全相同，虽然不会触发第二个非法条件，但是有可能都触发第一个非法条件，即交易额大于 1000，那么这两个完全相同的交易就都要出现在返回数组中，但由于前面我们定义的是用 HashSet，不能有重复项，怎么办呢？这里用个 trick，首先在遍历中就统计出每个相同的交易出现的次数，这样只要该交易在最后的 HashSet 中，就表示跟其所有相同的交易都应该在结果中，将其总出现次数减1次加入到结果 res 中即可，参见代码如下：

class Solution {
public:
    vector<string> invalidTransactions(vector<string>& transactions) {
        vector<string> res;
        unordered_set<string> st;
        unordered_map<string, vector<vector<string>>> m;
        unordered_map<string, int> cntMap;
        for (string t : transactions) {
            ++cntMap[t];
            istringstream iss(t);
            vector<string> vec(4);
            int i = 0;
            while (getline(iss, vec[i++], ','));
            if (stoi(vec[2]) > 1000) st.insert(t);
            for (auto &a : m[vec[0]]) {
                if (a[3] != vec[3] && abs(stoi(a[1]) - stoi(vec[1])) <= 60) {
                    st.insert(a[0] + "," + a[1] + "," + a[2] + "," + a[3]);
                    if (!st.count(t)) st.insert(t);
                }
            }
            m[vec[0]].push_back(vec);
        }
        for (auto &a : cntMap) {
            if (st.count(a.first)) {
                for (int i = 0; i < a.second - 1; ++i) {
                    res.push_back(a.first);
                }
            }
        }
        res.insert(res.end(), st.begin(), st.end());
        return res;
    }
};

Github 同步地址:

#1169

参考资料：

https://leetcode.com/problems/invalid-transactions/

https://leetcode.com/problems/invalid-transactions/discuss/366414/C%2B%2B-Hashtable

LeetCode All in One 题目讲解汇总(持续更新中...)