题目 #

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.

思路1 #

分析 #

自己想的，记录之前的交易信息，新的交易信息和之前进行对比，如果出现问题就记录
使用map查找，加快速度

代码实现 #

 1type transactionInfo struct {
 2	name      string
 3	time      int64
 4	amount    int64
 5	city      string
 6	hasOut    bool
 7	originStr string
 8}
 9
10func parseTransaction(str string) (info transactionInfo) {
11	arr := strings.Split(str, ",")
12	info.name = arr[0]
13	info.time, _ = strconv.ParseInt(arr[1], 10, 64)
14	info.amount, _ = strconv.ParseInt(arr[2], 10, 64)
15	info.city = arr[3]
16	info.hasOut = false
17	info.originStr = str
18	return
19}
20
21func appendResult(info *transactionInfo, result *[]string) {
22	if info.hasOut {
23		return
24	}
25	*result = append(*result, info.originStr)
26	info.hasOut = true
27}
28
29func invalidTransactions(transactions []string) []string {
30	recordMap := make(map[string][]transactionInfo)
31
32	var result []string
33	for _, v := range transactions {
34		info := parseTransaction(v)
35
36		// 先判断是否超出1000
37		if info.amount > 1000 {
38			appendResult(&info, &result)
39		}
40
41		// 判断是否之前有记录，不存在直接继续
42		lastInfos, ok := recordMap[info.name]
43		if !ok {
44			recordMap[info.name] = []transactionInfo{info}
45			continue
46		}
47
48		// 判断是否是小于60并不在同一个城市
49		for i, lastInfo := range lastInfos {
50			if lastInfo.city != info.city && (info.time-lastInfo.time <= 60 && info.time-lastInfo.time >= -60) {
51				appendResult(&info, &result)
52				appendResult(&lastInfos[i], &result)
53			}
54		}
55		lastInfos = append(lastInfos, info)
56		recordMap[info.name] = lastInfos
57	}
58
59	return result
60}

思路2 #

分析 #

官方的也挺暴力的，就是全遍历，当前交易和后面所有对比一遍，出现问题就记录

代码实现 #

 1func invalidTransactions1(transactions []string) []string {
 2	var result []string
 3
 4	// 遍历当前交易，和后面冲突就记录，跳出继续
 5	for i, v := range transactions {
 6		info := parseTransaction(v)
 7
 8		if info.amount > 1000 {
 9			result = append(result, info.originStr)
10			continue
11		}
12
13		for j, v1 := range transactions {
14			if j == i {
15				continue
16			}
17			info1 := parseTransaction(v1)
18			if info.name == info1.name && info1.city != info.city && (info.time-info1.time <= 60 && info.time-info1.time >= -60) {
19				result = append(result, info.originStr)
20				break
21			}
22
23		}
24	}
25	return result
26}