LeetCode 1169:クエリ無効取引(Invalid Transactions)解法要約

文書ディレクトリ

Solution

より多くのLeetCodeの問題解
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.

Each transaction string transactions[i] consists of comma separated values representing the name, time (in minutes), amount, and city of the transaction.
Given a list of transactions, 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 .

Solution
必ずstringのsplitをループの外に置いて先に処理し、ループ内に置くと、stringごとにsplit,TLEが複数回呼び出されます.

class Solution {
public:
    vector<string> invalidTransactions(vector<string>& transactions) {
        vector<vector<string> > transactionsSplited;
        for(auto trans :transactions){
            vector<string> transSplited;
            SplitString(trans, transSplited, ",");
            transactionsSplited.push_back(transSplited);
        }
        set<string> invalidTrans;
        for(int i =0;i<transactionsSplited.size();i++){
            bool flag = false;
            for(int j = i+1;j<transactionsSplited.size();j++){
                if(transactionsSplited[i][3] == transactionsSplited[j][3] || transactionsSplited[i][0] != transactionsSplited[j][0]){
                    continue;
                }
                if(abs(atoi(transactionsSplited[i][1].c_str())-atoi(transactionsSplited[j][1].c_str())) <= 60){
                    invalidTrans.insert(transactions[j]);
                    flag = true;
                }
            }
            if(flag){
                invalidTrans.insert(transactions[i]);
            }
        }
        for(int i; i<transactionsSplited.size(); i++){
            if(atoi(transactionsSplited[i][2].c_str()) > 1000){
                invalidTrans.insert(transactions[i]);
            }
        }

        vector<string> res;
        for(auto s:invalidTrans){
            res.push_back(s);
        }

        return res;
    }
    void SplitString(const std::string& s, std::vector<std::string>& v, const std::string& c)
    {
        std::string::size_type pos1, pos2;
        pos2 = s.find(c);
        pos1 = 0;
        while(std::string::npos != pos2)
        {
            v.push_back(s.substr(pos1, pos2-pos1));

            pos1 = pos2 + c.size();
            pos2 = s.find(c, pos1);
        }
        if(pos1 != s.length())
            v.push_back(s.substr(pos1));
    }
};