LeetCode每日一题(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.

---

先将 transactions 按 name， time 进行排序， 然后新建一个 stack 用以维护已检查过的 transaction， 遍历 transactions, 对于每个 transactions[i], 我们反向遍历 stack 查找是否有 stack[j].name == trasactions[i].name && transactions[i].time - stack[j].time <= 60 && stack[j].city != transactions[i].city 的 transaction 存在, 如果存在，证明 transactions[i]与 stack[j]都是 invalid. 如果该检查通过，我们还需要检查 amount < 1000。 注意，因为 invalid transaction 也是 transaction， 所以也需要压入 stack， 我们只需要添加一个标识来标识该 transaction 是不是 invalid。最后我们将 stack 中所有 invalid 的 transaction 都取出来就可以了

---

impl Solution {
    pub fn invalid_transactions(transactions: Vec<String>) -> Vec<String> {
        let mut trans: Vec<(String, i32, String, i32)> = transactions
            .into_iter()
            .map(|s| {
                let l: Vec<String> = s.split(",").map(str::to_owned).collect();
                (
                    l[0].clone(),
                    l[1].parse::<i32>().unwrap(),
                    l[3].clone(),
                    l[2].parse::<i32>().unwrap(),
                )
            })
            .collect();
        trans.sort();
        let mut stack = Vec::new();
        for (name, time, city, amount) in trans {
            if stack.is_empty() {
                stack.push((name, time, city, amount, amount < 1000));
                continue;
            }
            let mut i = stack.len() as i32 - 1;
            let mut got = false;
            while i >= 0 {
                let (p_name, p_time, p_city, _, is_ok) = &mut stack[i as usize];
                if p_name != &name || time - *p_time > 60 {
                    break;
                }
                if p_name == &name && time - *p_time <= 60 && p_city != &city {
                    *is_ok = false;
                    got = true;
                }
                i -= 1;
            }
            stack.push((name, time, city, amount, !got && amount < 1000));
        }
        stack
            .into_iter()
            .filter(|(_, _, _, _, is_ok)| is_ok == &false)
            .map(|(name, time, city, amount, _)| format!("{},{},{},{}", name, time, amount, city))
            .collect()
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43