Swift的竞争性编程

最初发布于 swiftrocks.com 。

竞争编程是掌握特定编程语言的一种好方法。 即使您对参加诸如Facebook Hacker Cup之类的世界大赛不感兴趣，仅使用语言的基础知识来解决棘手的算法问题，也会使您面临该语言所没有的方面/捷径，例如效率某些方法/操作以及如何编写更好的替代方法。 这是一个很酷的爱好，而且，作为奖励，您甚至可以间接地为自己备受恐惧的Big 4采访做好准备，在这些采访中您必须在白板上解决算法问题！

尽管在真正的竞争中，使用Swift编码会造成很大的麻烦（因为与其他语言相比，它有点慢，并且几乎没有本地数据结构），但是许多流行的在线平台（如LeetCode，HackerRank和Codefights）都支持Swift，它们是一种很好的方式以使自己成为更好的iOS开发人员，特别是因为竞争问题只会接受非常快速的算法作为可能的解决方案。 如果您以前从未这样做过，我强烈建议您尝试一下。

在本文中，我将为您提供有关如何使用Swift读取输入数据的简短教程，以及一些解决Swift中竞争问题的技巧。

使用Swift读取标准输入

在竞争性编程中，问题的输入通常被馈送到命令行应用程序，该命令程序对此有所了解并输出所需的结果。

诸如LeetCode和CodeFights之类的平台将自动为您处理输入数据，并公开一个空的Swift方法，该方法应返回问题的解决方案，但是其他平台（如HackerRank）有时会让您手动读取，解析标准输入然后打印结果。 幸运的是，这并不像听起来那样复杂。

要模拟竞争性编程环境，请在Xcode中创建一个命令行工具项目：

请注意，命令行工具不是Cocoa应用程序，因此您将无法访问UIKit东西！ 像Foundation这样的核心框架就在这里。

在main.swift ，键入并运行以下代码：

 let line = readLine() 
 print("Got something! \(line)") 

此时，程序将被冻结。 readLine()是一种标准库方法，可以同步读取标准输入并返回String? 一旦检索到整行，或者如果达到EOF，则返回nil 。

如果您在Xcode的控制台中键入内容，程序将继续执行并打印您编写的内容：

但是，竞争性编程问题可能需要数百行输入。 您可以使用while循环使代码运行直到输入结束：

 while let line = readLine() { 
 print("Got something! \(line)") 
 } 

这就是您开始需要了解的所有信息。 从现在开始，您使用纯Swift的技能是唯一的变量。

如果您以前从未这样做过，这是一个示例问题：

示例问题

给定一个整数数组，找到其元素的总和。

输入格式

第一行包含一个整数，表示数组的大小。

第二行包含n空格分隔的整数，它们表示数组的元素。

输出格式

将数组元素的总和打印为单个整数。

样本输入

 6 1 2 3 4 10 11 

样本输出

31

解

每个问题都有多种可能的解决方案。 为此，我们可以利用reduce ：

 import Foundation 

 _ = readLine() //Read and drop the array size line. 
 //Knowing the size of the array beforehand is needed for some languages 
 //But as readLine() returns the whole line, Swift doesn't need it! 

 let array = readLine()!.components(separatedBy: " ").map { 
 Int($0)! 
 } 
 
 let result = array.reduce(0, +) 
 print(result) 

竞争性编程的快速技巧

竞争性编程的好处在于仅解决问题是不够的-您的程序必须尽快解决问题。

关于运行时复杂性有很多要讨论的地方，但是本节应该涵盖Swift技巧，这些技巧在需要快速处理时非常有用。

如果您没有这里提供的提示，请随时与我联系，我会添加并在此表示感谢！

使用溢出运算符

Swift可以自然保护您免遭数字溢出（以性能为代价）的麻烦。 这可能会花费您一些宝贵的纳秒，甚至有些问题甚至可能希望您使数字溢出。 幸运的是，Swift具有特殊的算术运算符，它们会忽略溢出检查，从而使其比常规运算符更快：

 1 &+ 1 
 1 &- 1 
 1 &* 1 
 1 &>> 1 

打印速度慢

print(_:)方法非常慢，在打印Arrays东西时可能特别痛苦。 如果一次打印所有内容，则可以提高性能。

 let array = [String](repeating: "A", count: 1000) 
 for a in array { 
 print(separated, terminator: " ") // slow 
 } 

 ///// 

 let separated = array.joined(separator: " ") 
 print(separated) // a lot quicker, even though we're processing the array beforehand 

预先分配阵列容量

Swift的Arrays具有动态大小，这意味着该语言会随着大小的增加自动为其分配更多的内存空间。 即使这非常快，也可以通过使用Array.reserveCapacity(_:)方法提前知道数组大小，从而使其更快。 如果您遇到的问题是解决方案是具有特定大小的Array ，这将很有用。

 let arraySize = Int(readLine()!)! 
 var array = [Int]() 
 array.reserveCapacity(arraySize) //Runtime is slightly slower without manually setting the array's capacity. 

 for i in 0..<arraySize { 
 array.append(solve(for: i)) 
 } 

另外，当您需要预填充的数组时，可以使用repeating:count:初始值设定项：

 let fiveZs = Array(repeating: "Z", count: 5) 
 print(fiveZs) 
 // Prints "["Z", "Z", "Z", "Z", "Z"]" 

滥用隐式展开的可选

一阵恐惧! 在实际应用中应避免使用，在竞争性编程中安全性不是问题。 由于保证输入始终相同，因此您可以完全跳过展开可选选项的开销。

使用inout – Dmitry Volevodz

在递归函数中传递数据时，使用inout参数确实非常有用，而且我能够确认在传递带有内部引用类型的值类型时， inout参数的创建速度比常规参数要快。

减去日期以衡量绩效— Rodrigo Carvalho

以下代码段将衡量运行某些内容所需的时间：

 func measure(function: () -> Void) { 
 let start = Date() 
 function() 
 let end = Date() 
 print("Elapsed time: \(end.timeIntervalSince(start))") 
 } 

 measure { 
 timeIntensiveTask() 
 } 

当您有多种方法并且不确定哪种方法更快时，这可能很有用。 请确保在启用优化以正确衡量事物的情况下运行此程序，因为大多数Swift编译器的技巧都需要它。

迅捷算法俱乐部

大多数竞争性编程问题都将依赖于特定的数据结构，并且不幸的是，由于Swift没有对大多数数据提供本机支持，这意味着您必须自己编写代码。

幸运的是，swift-algorithm-club仓库具有几乎所有内容的Swift实现，这使其成为学习如何在Swift中编写流行数据结构的好地方。

还有什么？

无论您是在学习面试，想参加世界级赛事还是只是想在iOS开发上变得更好，解决竞争性编程问题都是提高Swift技能的一种非常有趣的方式。 我个人从中受益匪浅，很想知道您对此有何看法。

参考文献和优秀读物

大O符号
Swift中的性能数组
Apple Docs：readLine（）