我一直在通过做 HackerRank 测试用例来准备编码考试,大部分时间我都做得很好,但是我在一些简单的用例上挂了,当我看不到时你们都会帮助我解决方案。我正在解决这个问题:
https://www.hackerrank.com/challenges/ctci-ransom-note
一名绑架者写了一张赎金单,但担心会被追踪到他。他找到一本杂志,想知道是否可以从中剪下完整的单词,然后用它们制作一张无法追踪的赎金票据副本。他笔记中的单词区分大小写,他必须使用杂志中可用的整个单词,这意味着他不能使用子字符串或连接来创建他需要的单词。
给定杂志中的文字和赎金条中的文字,如果他可以使用杂志中的整个文字准确地复制他的赎金条,则打印 Yes;否则打印No.
输入格式
第一行包含两个以空格分隔的整数,分别描述了(杂志中的字数)和(勒索信中的字数)的值。 第二行包含以空格分隔的字符串,表示杂志中出现的单词。 第三行包含以空格分隔的字符串,表示赎金记录中出现的单词。
每个单词都由英文字母组成(即 to 和 to )。 便条和杂志中的文字区分大小写。 输出格式
如果他可以使用该杂志创建他的赎金票据的无法追踪的副本,则打印是;否则打印No.
示例输入
6 4
give me one grand today night
give one grand today
示例输出
Yes
Explanation
写出无法追踪的赎金记录副本所需的全部四个词都出现在杂志中,因此我们打印"is"作为答案。
这是我的解决方案:
import Foundation
func main() -> String {
let v = readLine()!.components(separatedBy: " ").map{Int($0)!}
var a = [String](); var b = [String]()
if v[0] < v[1] { return "No"}
for i in 0 ..< 2 {
if i == 0 {
a = (readLine()!).components(separatedBy: " ")
} else { b = (readLine()!).components(separatedBy: " ") }
}
// Get list of elements that intersect in each array
let filtered = Set(a).intersection(Set(b))
// Map set to set of Boolean where true means set a has enough words to satisfy set b's needs
let checkB = filtered.map{ word in reduceSet(b, word: word) <= reduceSet(a, word: word) }
// If mapped set does not contain false, answer is Yes, else No
return !checkB.contains(false) ? "Yes" : "No"
}
func reduceSet(_ a: [String], word: String) -> Int {
return (a.reduce(0){ $0 + ($1 == word ? 1 : 0)})
}
print(main())
使用此解决方案,我总是在 20 个测试用例中的三个上超时。所以解决方案似乎解决了所有的测试用例,但没有在他们要求的时间限制内。这些都是很好的练习,但是当你像这样卡住时,会非常沮丧。
我应该注意,我使用了 Sets
和 Set(a).intersection(Set(b))
因为当我尝试映射一个 Strings 数组时
,一半的测试用例超时。
任何更清洁或更高效的解决方案将不胜感激!谢谢!
最佳答案
感谢@Alexander - 我能够使用 NSCountedSet
而不是我的自定义 reduce
方法来解决这个问题。它更清洁,更高效。这是解决方案:
import Foundation
func main() -> String {
let v = readLine()!.components(separatedBy: " ").map{Int($0)!}
var a = [String](); var b = [String]()
if v[0] < v[1] { return "No"}
for i in 0 ..< 2 {
if i == 0 {
a = (readLine()!).components(separatedBy: " ")
} else { b = (readLine()!).components(separatedBy: " ") }
}
let countA = NSCountedSet(array: a)
let countB = NSCountedSet(array: b)
let intersect = Set(a).intersection(Set(b))
let check = intersect.map{ countB.count(for: $0) <= countA.count(for: $0) }
return !check.contains(false) ? "Yes" : "No"
}
print(main())
非常感谢!
关于ios - 在 Swift 中重构解决方案,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/41729865/