Leetcode 1169:查询无效交易(超详细的解法!!!)
in leetcode with 0 comment

Leetcode 1169:查询无效交易(超详细的解法!!!)

in leetcode with 0 comment

如果出现下述两种情况,交易 可能无效

每个交易字符串 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"]

提示:

解题思路

首先不难想到暴力得分方法,通过二重循环判断第二种无效的情况,并且我们需要通过一个集合保存我们删除的元素(避免重复)。最后再遍历一遍删除第一种无效的情况即可。

class Solution:
    def invalidTransactions(self, transactions: List[str]) -> List[str]:
        data, n = [], len(transactions)
        for tran in transactions:
            t = tran.split(",")
            data.append([t[0], int(t[1]), int(t[2]), t[-1]])
        
        res, delt = [], set()
        for i in range(n):
            for j in range(i+1, n):
                if i != j and data[i][-1] != data[j][-1] and \
                    data[i][0] == data[j][0] and \
                    abs(data[i][1] - data[j][1]) <= 60:
                    delt.add(i)
                    delt.add(j)
                    
        for i in range(n):
            if i not in delt and data[i][2] > 1000:
                res.append(transactions[i])
        for i in delt:
            res.append(transactions[i])
        return res

还有一种比较快的做法,就是将所有相同名字的交易存储到一个字典中,然后对相同名字的交易根据时间排序,对排好序的交易判断时间是不是不合法。判断两个交易是不是合法,我们可以通过单调队列来做,我们可以建立一个单调递增的队列存储不合法的交易。我们遍历交易的过程中可以判断出之前最近的一个合法交易是谁,那么从合法交易到当前区间中的所有交易必然都不合法。例如,假设一个相同交易名的交易时间序列如下(为了简化说明这里只考虑时间,不考虑地点)

10 20 30 80 90 200
↑
q: 10

此时队列为空,我们需要添加元素,继续判断20

10 20 30 80 90 200
   ↑
q: 10 20

我们知道队首的元素一定是最小的,拿20和它比较,发现20-10<=60(不合法)将它加入队列。对于30采用相同的考虑。接着考虑80,我们发现80-10>60,也就是此时的10合法了,所以我们需要将它弹出,将80加入。

10 20 30 80 90 200
         ↑
q: 20 30 80

你可以发现,在遍历的过程中,我们的队列一直保存这不合法的元素。我们只要将这些不合法的元素对应位置加入到我们需要删除的结果中去即可。

class Solution:
    def invalidTransactions(self, transactions: List[str]) -> List[str]:
        data, delt = collections.defaultdict(list), set()
        for i, tran in enumerate(transactions):
            name, time, amount, city = tran.split(",")
            if int(amount) > 1000:
                delt.add(i)
            data[name].append([int(time), city, i])
            
        for it in data:
            data[it].sort()
            q = []
            for t1, c1, i1 in data[it]:
                while q and q[0][0] < t1 - 60:
                    q.pop(0)
                for t2, c2, i2 in q:
                    if c1 != c2:
                        delt.add(i2)
                        delt.add(i1)
                q.append([t1, c1, i1])
        return [transactions[i] for i in delt]

这个问题的cpp写法有一定难度,大家可以参看我的cpp实现。

我将该问题的其他语言版本添加到了我的GitHub Leetcode

如有问题,希望大家指出!!!

「如果我的文章对你有很大帮助,那么不妨~!」

coordinate

谢谢老板O(∩_∩)O~

使用微信扫描二维码完成支付

Responses