LEETCODE 1169. Invalid Transactions 解题思路分析

题目大意:

查询无效交易

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

  • 交易金额超过 ¥1000
  • 或者,它和另一个城市中同名的另一笔交易相隔不超过 60 分钟(包含 60 分钟整)

每个交易字符串 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 之间的整数

如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=1169

解题思路分析:

个人感觉本题出的不是很好,非常不适合在面试中使用。不过既然已经打开题目了,还是分析一下吧。

对于第二个条件,交易金额的判断很简单,关键在于第一个条件,同名异地的两笔交易不超过60分钟。由于本题的数据规模并不大,暴力解是可行的,用两层循环,一一比对每一笔交易,当姓名相同,城市不同,并且交易时间不超过60分钟时,当前2笔交易均为无效交易。比对完所有交易后,也就会统计出所有无效交易。(此算法可以通过所有测试)

接下来,我们可以适当优化一下算法。无效交易的核心是需要同名,如果不是同一人的交易,那么肯定不是我们需要的结果,因此我们可以先将所有数据按照人名进行分组,分组后,再在每一组中按照上面的暴力算法求解,可大幅提高算法效率。

实现代码:

class Data{ // 将每个字符串存储为一个Object
    int time; // 交易时间
    int amount; // 交易金额
    String city; // 城市
    String str; // 元字符串
    Data(int t, int a, String c,String s){
        city=c;
        time=t;
        amount=a;
        str=s;
    }
}
public List<String> invalidTransactions(String[] transactions) {
    // 按姓名将数据分组
    Map<String, List<Data>> map = new HashMap<>();
    // 返回结果
    Set<String> res = new HashSet<>();
    // 循环每个字符串
    for(String t : transactions){
        // 交易的详细信息
        String[] datas = t.split(",");
        // 以姓名作为key
        String key=datas[0];
        // 取得该姓名的所有交易
        List<Data> q =map.getOrDefault(key,new ArrayList<>());
        // 将当前交易加入列表
        q.add(new Data(Integer.parseInt(datas[1]), 
                         Integer.parseInt(datas[2]), 
                         datas[3], t));
        map.put(key, q);
    }
    // 循环每个姓名下的所有交易
    for(String key: map.keySet()){
        // 当前姓名下的所有交易
        List<Data> list = map.get(key);
        // 一一比对每一笔交易
        for(int i=0;i<list.size();i++){
            Data di=list.get(i);
            for(int j=i+1;j<list.size();j++){
                Data dj=list.get(j);
                // 如果交易时间小于等于60并且为异地
                if(Math.abs(di.time-dj.time)<=60
                  && !di.city.equals(dj.city)){
                    // 当前两笔交易均为无效交易
                    res.add(di.str);    
                    res.add(dj.str);
                }
            }
        }
        // 找出金额大于1000的交易
        for(int i=0;i<list.size();i++){
            if(list.get(i).amount>1000){
                res.add(list.get(i).str);    
            }
        }
    }
    return new ArrayList<>(res);
}

本题解法执行时间为20ms。

Runtime: 20 ms, faster than 74.19% of Java online submissions for Invalid Transactions.

Memory Usage: 38 MB, less than 100.00% of Java online submissions for Invalid Transactions.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: https://leetcode.jp/leetcode-1169-invalid-transactions-解题思路分析/
此条目发表在leetcode分类目录,贴了, , 标签。将固定链接加入收藏夹。

发表评论

您的电子邮箱地址不会被公开。