526互联

[LeetCode] 1169. Invalid Transactions

发布时间 2023-10-26 05:40:11作者: CNoodle

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 分钟（包含 60 分钟整）

给定字符串数组交易清单 transaction 。每个交易字符串 transactions[i] 由一些用逗号分隔的值组成，这些值分别表示交易的名称，时间（以分钟计），金额以及城市。

返回 transactions，返回可能无效的交易列表。你可以按 任何顺序 返回答案。

思路是 hashmap，同时这里为了处理方便，我选择把数据包成一个新的 class。

根据题意，无效的交易的定义不难理解，这里我选择用 hashmap<String, List<Data>> 存每个不同的人名下的所有交易记录。这里判断交易是否无效的第二种情形我没有什么好方法，只能从 hashmap 中将同一个人名下所有的交易拿出来用两个 for 循环进行两两比较，如果相隔不超过 60 分钟，那么两笔交易都是无效的。

注意题目给的 testcase 会有

给你两笔一模一样的交易的情形所以这种情况下两笔交易都是无效的 - 所以这里无法用 hashset 记录结果

给你两笔名字一样的交易，其中一笔 amount 无效，另一笔 amount 有效但是时间跟 amount 无效的那一笔相隔不到 60 分钟，这种情况两笔交易也都是无效的

时间O(n^2) - worst case 是所有交易都在一个人名下，我们需要两两比较

空间O(n)

Java实现

 1 class Solution {
 2     class Data {
 3         int time;
 4         int amount;
 5         String city;
 6         String str;
 7         Data(int t, int a, String c, String s) {
 8             city = c;
 9             time = t;
10             amount = a;
11             str = s;
12         }
13     }
14 
15     public List<String> invalidTransactions(String[] transactions) {
16         HashMap<String, List<Data>> map = new HashMap<>();
17         Set<Data> set = new HashSet<>();
18         // "alice,20,800,mtv"
19         // "{name},{time},{amount},{city}"
20         for (String t : transactions) {
21             String[] datas = t.split(",");
22             String name = datas[0];
23             List<Data> list = map.getOrDefault(name, new ArrayList<>());
24             list.add(new Data(
25                 Integer.parseInt(datas[1]),
26                 Integer.parseInt(datas[2]),
27                 datas[3],
28                 t
29             ));
30             map.put(name, list);
31         }
32 
33         for (String key : map.keySet()) {
34             List<Data> list = map.get(key);
35             for (int i = 0; i < list.size() - 1; i++) {
36                 for (int j = i + 1; j < list.size(); j++) {
37                     Data first = list.get(i);
38                     Data second = list.get(j);
39                     if (Math.abs(first.time - second.time) <= 60 && !first.city.equals(second.city)) {
40                         set.add(first);
41                         set.add(second);
42                     }
43                 }
44             }
45 
46             for (int i = 0; i < list.size(); i++) {
47                 Data cur = list.get(i);
48                 if (cur.amount > 1000) {
49                     set.add(list.get(i));
50                 }
51             }
52         }
53         
54         List<String> res = new ArrayList<>();
55         for (Data d : set) {
56             res.add(d.str);
57         }
58         return res;
59     }
60 }

 

LeetCode 题目总结