| comments | difficulty | edit_url | rating | source | tags | ||||
|---|---|---|---|---|---|---|---|---|---|
true |
中等 |
1658 |
第 151 场周赛 Q1 |
|
如果出现下述两种情况，交易 可能无效：
- 交易金额超过
$1000 - 或者，它和 另一个城市 中 同名 的另一笔交易相隔不超过
60分钟（包含 60 分钟整）
给定字符串数组交易清单 transaction 。每个交易字符串 transactions[i] 由一些用逗号分隔的值组成，这些值分别表示交易的名称，时间（以分钟计），金额以及城市。
返回 transactions，返回可能无效的交易列表。你可以按 任何顺序 返回答案。
示例 1：
输入：transactions = ["alice,20,800,mtv","alice,50,100,beijing"] 输出：["alice,20,800,mtv","alice,50,100,beijing"] 解释：第一笔交易是无效的，因为第二笔交易和它间隔不超过 60 分钟、名称相同且发生在不同的城市。同样，第二笔交易也是无效的。
示例 2：
输入：transactions = ["alice,20,800,mtv","alice,50,1200,mtv"] 输出：["alice,50,1200,mtv"]
示例 3：
输入：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之间的整数
遍历交易列表，对于每笔交易，如果金额大于 1000，或者同名且城市不同且时间间隔不超过 60 分钟，则将其加入答案。
具体地，我们使用哈希表 d 记录每个交易，其中键为交易名称，值为一个列表，列表中的每个元素为一个三元组 (time, city, index)，表示在 time 时刻在 city 城市进行了编号为 index 的交易。同时，我们使用哈希表 idx 记录答案中的交易编号。
遍历交易列表，对于每笔交易，我们首先将其加入哈希表 d 中，然后判断其金额是否大于 1000，如果是，则将其编号加入答案中。然后我们遍历哈希表 d 中的交易，如果交易名称相同且城市不同且时间间隔不超过 60 分钟，则将其编号加入答案中。
最后，我们遍历答案中的交易编号，将其对应的交易加入答案即可。
时间复杂度
class Solution:
def invalidTransactions(self, transactions: List[str]) -> List[str]:
d = defaultdict(list)
idx = set()
for i, x in enumerate(transactions):
name, time, amount, city = x.split(",")
time, amount = int(time), int(amount)
d[name].append((time, city, i))
if amount > 1000:
idx.add(i)
for t, c, j in d[name]:
if c != city and abs(time - t) <= 60:
idx.add(i)
idx.add(j)
return [transactions[i] for i in idx]class Solution {
public List<String> invalidTransactions(String[] transactions) {
Map<String, List<Item>> d = new HashMap<>();
Set<Integer> idx = new HashSet<>();
for (int i = 0; i < transactions.length; ++i) {
var e = transactions[i].split(",");
String name = e[0];
int time = Integer.parseInt(e[1]);
int amount = Integer.parseInt(e[2]);
String city = e[3];
d.computeIfAbsent(name, k -> new ArrayList<>()).add(new Item(time, city, i));
if (amount > 1000) {
idx.add(i);
}
for (Item item : d.get(name)) {
if (!city.equals(item.city) && Math.abs(time - item.t) <= 60) {
idx.add(i);
idx.add(item.i);
}
}
}
List<String> ans = new ArrayList<>();
for (int i : idx) {
ans.add(transactions[i]);
}
return ans;
}
}
class Item {
int t;
String city;
int i;
Item(int t, String city, int i) {
this.t = t;
this.city = city;
this.i = i;
}
}class Solution {
public:
vector<string> invalidTransactions(vector<string>& transactions) {
unordered_map<string, vector<tuple<int, string, int>>> d;
unordered_set<int> idx;
for (int i = 0; i < transactions.size(); ++i) {
vector<string> e = split(transactions[i], ',');
string name = e[0];
int time = stoi(e[1]);
int amount = stoi(e[2]);
string city = e[3];
d[name].push_back({time, city, i});
if (amount > 1000) {
idx.insert(i);
}
for (auto& [t, c, j] : d[name]) {
if (c != city && abs(time - t) <= 60) {
idx.insert(i);
idx.insert(j);
}
}
}
vector<string> ans;
for (int i : idx) {
ans.emplace_back(transactions[i]);
}
return ans;
}
vector<string> split(string& s, char delim) {
stringstream ss(s);
string item;
vector<string> res;
while (getline(ss, item, delim)) {
res.emplace_back(item);
}
return res;
}
};func invalidTransactions(transactions []string) (ans []string) {
d := map[string][]tuple{}
idx := map[int]bool{}
for i, x := range transactions {
e := strings.Split(x, ",")
name := e[0]
time, _ := strconv.Atoi(e[1])
amount, _ := strconv.Atoi(e[2])
city := e[3]
d[name] = append(d[name], tuple{time, city, i})
if amount > 1000 {
idx[i] = true
}
for _, item := range d[name] {
if city != item.city && abs(time-item.t) <= 60 {
idx[i], idx[item.i] = true, true
}
}
}
for i := range idx {
ans = append(ans, transactions[i])
}
return
}
func abs(x int) int {
if x < 0 {
return -x
}
return x
}
type tuple struct {
t int
city string
i int
}