[Swift]LeetCode1169.查询无效交易|InvalidTransactions

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› 移动开发›Swift 教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（www.zengqiang.org）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址：
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎，请直接点击！！！

进入博主App Store主页，下载使用各个作品！！！

注：博主将坚持每月上线一个新app！！！

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.

Each transaction string transactions[i] consists of comma separated values representing the name, time (in minutes), amount, and city of the transaction.

Given a list of transactions, 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 分钟整）

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

188ms

 1 class Solution {
 2     
 3     struct  Transation: Hashable {
 4         var name: String
 5         var time: Int
 6         var price: Int
 7         var city: String
 8         
 9         func toString() -> String {
10             return "\(name),\(time),\(price),\(city)"
11         }
12     }
13     
14     func invalidTransactions(_ transactions: [String]) -> [String] {
15 //        var ans = [String]()
16         var mapNameToTransation = [String:[Transation]]()
17         for tran in transactions {
18             let componnent = tran.components(separatedBy: ",")
19             let trans = Transation(name: componnent[0], time: Int(componnent[1])!, price: Int(componnent[2])!, city: componnent[3])
20             if mapNameToTransation[trans.name] == nil {
21                 mapNameToTransation[trans.name] = [Transation]()
22             }
23             mapNameToTransation[trans.name]?.append(trans)
24         }
25 
26         var set = Set<Transation>()
27         for (_,transations2) in mapNameToTransation {
28             if transations2.count == 1 {
29                 if transations2[0].price > 1000 {
30                     set.insert(transations2[0])
31                 }
32             } else {
33                 let length = transations2.count
34                 for i in 0..<length {
35                     let first  = transations2[i]
36                     if first.price > 1000 {
37                         set.insert(first)
38                     }
39                     for j in (i + 1)..<length {
40                         let second = transations2[j]
41                         if  first.city != second.city {
42                             if abs(first.time - second.time) <= 60 {
43                                 set.insert(first)
44                                 set.insert(second)
45                             }
46                         }
47                     }
48                 }
49             }
50         }
51         
52         return set.map({ (tran) -> String in
53             tran.toString()
54         })
55     }
56 }

192ms

 1 class Solution {
 2     func invalidTransactions(_ transactions: [String]) -> [String] {
 3        var tupleDic = [String: [(String, Int, Int, String)]]()
 4         var sets = Set<String>()
 5         for str in transactions {
 6             let arr = str.split(separator: ",")
 7             let (name, time, amount, city) = (String(arr[0]), Int(arr[1])!, Int(arr[2])!, String(arr[3]))
 8             var tpls =  tupleDic[name, default: [(String, Int, Int, String)]()]
 9             tpls.append((name, time, amount, city))
10             tupleDic[name] = tpls
11         }
12         for (name, tpls) in tupleDic {
13             for i in tpls.indices {
14                 let (n, t, a, c) = tpls[i]
15                 if a >= 1000 { sets.insert(n+","+"\(t)"+","+"\(a)"+","+c) }
16                 for j in i+1..<tpls.count {
17                     let (n2, t2, a2, c2) = tpls[j]
18                     if abs(t-t2) <= 60 && c2 != c {
19                         sets.insert(n2+","+"\(t2)"+","+"\(a2)"+","+c2)
20                         sets.insert(n+","+"\(t)"+","+"\(a)"+","+c)
21                     }
22                 }
23             }
24         }
25         return Array(sets)
26     }
27 }

228ms

 1 class Solution {
 2     struct Transaction {
 3         var name: String
 4         var minute: Int
 5         var amount: Int
 6         var place: String
 7         var idx: Int
 8     }
 9     
10     func invalidTransactions(_ transactions: [String]) -> [String] {
11         var res = Set<String>()
12         var db = [String : [Transaction]]()
13         
14         for (idx, transaction) in transactions.enumerated() {
15             let detail = transaction.components(separatedBy: ",")
16             let t = Transaction(name: detail[0], minute: Int(detail[1]) ?? 0, amount: Int(detail[2]) ?? 0, place: detail[3], idx: idx)
17             
18             if t.amount > 1000 {
19                 res.insert(transaction)
20             }
21             
22             var existed = db[t.name, default: [Transaction]()]
23             for et in existed where abs(et.minute - t.minute) <= 60 && et.place != t.place {
24                 res.insert(transaction)
25                 res.insert(transactions[et.idx])
26             }
27             existed.append(t)
28             db[t.name] = existed
29         }
30         
31         return Array(res)
32     }
33 }

312ms

 1 class Solution {
 2     
 3     class Transaction {
 4         var name = ""
 5         var time = 0
 6         var amount = 0
 7         var city = ""
 8         
 9         init(_ transaction: String) {
10             let components = transaction.components(separatedBy: ",")
11             name = components[0]
12             time = Int(components[1])!
13             amount = Int(components[2])!
14             city = components[3]
15         }
16         
17         func toString() -> String {
18             return "\(name),\(time),\(amount),\(city)"
19         }
20     }
21     func invalidTransactions(_ transactions: [String]) -> [String] {
22         var dict: [String: [Transaction]] = [:]
23         var invalid: [String] = []
24         for transaction in transactions {
25             let newElem = Transaction(transaction)
26             if let elems = dict[newElem.name] {
27                 for (index, elem) in elems.enumerated() {
28                     if elem.city != newElem.city && abs(elem.time - newElem.time) <= 60 {
29                         invalid.append(transaction)
30                         invalid.append(elem.toString())
31                     }
32                 }
33                 dict[newElem.name]!.append(newElem)
34             } else {
35                 dict[newElem.name] = [newElem]
36             }
37             if newElem.amount > 1000 {
38                 invalid.append(transaction)
39             }
40         }
41         return Array(Set(invalid))
42     }
43 }

Runtime: 328 ms

Memory Usage: 23 MB

 1 class Solution {
 2     func invalidTransactions(_ transactions: [String]) -> [String] {
 3         let N:Int = transactions.count
 4         var t:[Trans] = [Trans](repeating:Trans(),count:N)
 5         for i in 0..<N
 6         {
 7             t[i] = Trans.fromString(transactions[i])
 8         }
 9         var lst:[String] = [String]()
10         for x in t
11         {
12             if x.money > 1000 || hasConflict(x, t)
13             {
14                 lst.append(x.orig)
15             }
16         }
17         return lst        
18     }
19     
20     func hasConflict(_ x:Trans,_ t:[Trans]) -> Bool
21     {
22         for y in t
23         {
24             if x == y {continue}
25             if x.name.isEqual(y.name) && !x.city.isEqual(y.city) && abs(x.time - y.time) <= 60
26             {
27                 return true
28             }
29         }
30         return false        
31     }
32 }
33 
34 class Trans:Hashable
35 {
36     var name:String = String()
37     var city:String = String()
38     var orig:String = String()
39     var time:Int = 0
40     var money:Int = 0
41     
42     static func == (lhs: Trans, rhs: Trans) -> Bool {
43         return lhs.name == rhs.name && lhs.city == rhs.city && lhs.orig == rhs.orig && lhs.time == rhs.time && lhs.money == rhs.money
44     }
45     
46     func hash(into hasher: inout Hasher)
47     {
48         hasher.combine(name)
49         hasher.combine(city)
50         hasher.combine(orig)
51         hasher.combine(time)
52         hasher.combine(money)
53     }
54     
55     static func fromString(_ s:String) -> Trans
56     {
57         let parts:[String] = s.components(separatedBy:",")
58         var t:Trans = Trans()
59         t.name = parts[0]
60         t.time = Int(parts[1]) ?? 0
61         t.money = Int(parts[2]) ?? 0
62         t.city = parts[3]
63         t.orig = s   
64         return t
65     }
66 }