哈希表：赎金票据 - 黑客排名 Swift 超时

Question

我的代码没问题，但在某些测试用例上总是超时，有什么改进的技巧吗？我的猜测是 indexOf 函数花费的时间太长。

func checkMagazine(magazine: [String], note: [String]) -> Void {
var mutableMag = magazine
if note.count > mutableMag.count {
    print("No")
    return
}
for word in note {
    if let index = mutableMag.index(of: word) {
        mutableMag.remove(at: index)
    } else {
        print("No")
        return
    }
}
print("Yes") }

请在这个 link 中找到挑战：https://www.hackerrank.com/challenges/ctci-ransom-note/problem

Answer 1

一种通过所有测试的可能解决方案是使用 NSCountedSet 来存储笔记和杂志中的单词，并将 note 中每个单词的计数与 [= 中该单词的计数进行比较14=] 并且如果其中任何一个在 magazine 中较低，则提前制作 return 并打印 No.

我还建议将函数签名更改为 return Bool 值，即使黑客生成的函数原型排名 returns Void。最好使 checkMagazine 成为一个纯函数，而不在其中进行任何 I/O 操作。

func checkMagazine(magazine: [String], note: [String]) -> Bool {
    let magazineWords = NSCountedSet(array: magazine)
    let noteWords = NSCountedSet(array: note)
    for noteWord in noteWords {
        if magazineWords.count(for: noteWord) < noteWords.count(for: noteWord) {
            return false
        }
    }
    return true
}

那么你只需要将生成代码的末尾改为如下：

let magazineWorks = checkMagazine(magazine: magazine, note: note)
if magazineWorks {
    print("Yes")
} else {
    print("No")
}

Answer 2

func checkMagazine(magazine: [String], note: [String]) -> Void {
    var notesDictionary : [String : Int] = [:]
    var magazineDictionary : [String : Int] = [:]

    var canMakeRansom = true

    for n in note {
        var count = notesDictionary[n] ?? 0
        count += 1
        notesDictionary[n] = count
    }

    for n in magazine {
        var count = magazineDictionary[n] ?? 0
        count += 1
        magazineDictionary[n] = count
    }

    for note in notesDictionary {
        if note.value > magazineDictionary[note.key] ?? 0 {
            canMakeRansom = false
        }
    }
    print(canMakeRansom ? "Yes" : "No")
}

这是另一种解决方法。我认为这会以某种方式完成 NSCountedSet 本身的功能。

哈希表：赎金票据 - 黑客排名 Swift 超时

Hash Tables: Ransom Note - Hacker Rank in Swift Timed Out

arrays

dictionary

hashmap

swift

swift3