1169. Invalid Transactions

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 同步地址:

https://github.com/grandyang/leetcode/issues/1169

参考资料:

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

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

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


转载请注明来源于 Grandyang 的博客 (grandyang.com),欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 grandyang@qq.com

💰


微信打赏


Venmo 打赏

(欢迎加入博主的知识星球,博主将及时答疑解惑,并分享刷题经验与总结,试运营期间前五十位可享受半价优惠~)

×

Help us with donation