题目描述
如果出现下述两种情况,交易 可能无效:
- 交易金额超过 $1000
- 或者,它和另一个城市中同名的另一笔交易相隔不超过 60 分钟(包含 60 分钟整)
每个交易字符串 transactions[i]
由一些用逗号分隔的值组成,这些值分别表示交易的名称,时间(以分钟计),金额以及城市。
给你一份交易清单 transactions
,返回可能无效的交易列表。你可以按任何顺序返回答案。
样例
输入:transactions = ["alice,20,800,mtv","alice,50,100,beijing"]
输出:["alice,20,800,mtv","alice,50,100,beijing"]
解释:第一笔交易是无效的,因为第二笔交易和它间隔不超过 60 分钟、名称相同且发生在不同的城市。
同样,第二笔交易也是无效的。
输入:transactions = ["alice,20,800,mtv","alice,50,1200,mtv"]
输出:["alice,50,1200,mtv"]
输入:transactions = ["alice,20,800,mtv","bob,50,1200,mtv"]
输出:["bob,50,1200,mtv"]
限制
transactions.length <= 1000
- 每笔交易
transactions[i]
按"{name},{time},{amount},{city}"
的格式进行记录 - 每个交易名称
{name}
和城市{city}
都由小写英文字母组成,长度在1
到10
之间 - 每个交易时间
{time}
由一些数字组成,表示一个0
到1000
之间的整数 - 每笔交易金额
{amount}
由一些数字组成,表示一个0
到2000
之间的整数
算法
(模拟,暴力枚举) $O(n^2)$
- 对于每笔交易,如果金额大于 1000 直接判定为无效,否则,枚举其他所有的交易,判断是否出现了无效的情况。
时间复杂度
- 两重循环,最坏情况下需要 $O(n)$ 的时间。
空间复杂度
- 需要存储每笔交易的对象,由于故空间复杂度为 $O(nL)$,其中 $L$ 为字符串的最大长度。
C++ 代码
class Trans {
public:
int time, amount;
string name, city;
bool valid;
Trans(string&& name, int time, int amount, string&& city) {
this -> name = name;
this -> time = time;
this -> amount = amount;
this -> city = city;
this -> valid = true;
}
string serialization() const {
return name + "," + to_string(time) + "," + to_string(amount) + "," + city;
}
};
class Solution {
public:
vector<string> invalidTransactions(vector<string>& transactions) {
vector<Trans> trans;
for (const auto &tr: transactions) {
auto&& t = split(tr);
trans.emplace_back(move(t[0]), stoi(t[1]), stoi(t[2]), move(t[3]));
}
for (int i = 0; i < trans.size(); i++) {
auto& ti = trans[i];
if (ti.amount > 1000)
ti.valid = false;
else {
for (int j = 0; j < trans.size(); j++) {
if (i == j)
continue;
const auto& tj = trans[j];
if (ti.name == tj.name && ti.city != tj.city
&& abs(ti.time - tj.time) <= 60) {
ti.valid = false;
break;
}
}
}
}
vector<string> ans;
for (const auto& tr: trans)
if (!tr.valid)
ans.push_back(tr.serialization());
return ans;
}
private:
vector<string> split(const string &trans) {
vector<string> ret;
string cur;
for (char c : trans) {
if (c == ',')
ret.push_back(move(cur));
else
cur += c;
}
ret.push_back(move(cur));
return ret;
}
};