Swift 算法实战之路（一）

   <p> </p>    <p><img src="https://simg.open-open.com/show/da19d8c94e6a9d4b55206ec2c4556e07.jpg"></p>    <p>Swift是苹果新推出的编程语言，也是苹果首个开源语言。相比于原来的Objective-C，Swift要更轻便和灵活。笔者最近使用Swift实践了大量的算法（绝大部分是硅谷各大公司的面试题），将心得体会总结于下。此文并不是纯粹讨论Swift如何实现某一个具体的算法或者数据结构，如冒泡排序、深度优先遍历，或是树和栈，而是总结归纳一些Swift常用的语法和技巧，以便大家在解决面试题中使用。</p>    <h2>基本语法</h2>    <p>先来看下面一段代码</p>    <pre>  <code class="language-swift">func swap(chars:[Character],  p: Int, q: Int) {    var temp = chars[p]    chars[p] = chars[q]    chars[q] = temp  }  // Assume array is a character array and it has enough elements  swap(array, p: 0, q: 1)</code></pre>    <p>上面代码实现了一个非常简单的功能，就是交换一个数组中的两个值。乍一看非常正确，实际上存在以下几个问题。</p>    <ol>     <li>在第一个参数前应该加上 <strong>inout</strong> 关键字。因为在Swift中，struct都是按值传递，class是按引用传递；数组和字典都是struct。所以要改变原来的chars数组，在其前部加入inout关键字，表示是按引用传递。</li>     <li>p 和 q 之前应该加入下划线。Swift默认函数的第一个参数是局部（local）变量，而后续参数都是外部（external）变量，外部变量必须声明。如果在p和q前加上下划线，则在调用函数时无需声明外部变量，这样调用起来更简便。</li>     <li>temp前的var应该改为 <strong>let</strong> 。let用于声明常量（constant），var用于声明变量（variable）。swap函数中，temp并未进行修改，所以应当视为常量，用let来声明。</li>    </ol>    <p>修改过后的代码为</p>    <pre>  <code class="language-swift">func swap(inout chars:[Character],  _ p: Int, _ q: Int) {    let temp = chars[p]    chars[p] = chars[q]    chars[q] = temp  }  // Assume array is a character array and it has enough elements  swap(&array, 0, 1)</code></pre>    <p>再来看一段代码</p>    <pre>  <code class="language-swift">func toZero(x: Int) -> Int {    while x > 0 {      x -= 1    }    return x  }</code></pre>    <p>这里在 x -= 1 处会报错。原因是函数中所有的参数是常量（let），是不可以修改的。解决的方法是在函数中写上 var x = x ，之后就可以对 x 进行修改了</p>    <h2>循环</h2>    <p>Swift循环分为for和while两种，注意他们的结构跟传统的 Java, C/C++有很大区别，笔者将其总结如下</p>    <pre>  <code class="language-swift">// Assume names is an array holds enough Strings  // for loop  for name in names { }  for i in 0 ... names.count - 1 { }  for i in 0 ..<names.count { }  for _ in 0 ..< names.count { }  for name in names.reverse() { }  for i in stride(from: 0, to: names.count - 1, by: 2) { }    // while loop  var i = 0  while i < names.count { }  repeat { } while i < names.count</code></pre>    <p>以上代码非常简单。需要说明的有两个，一个是 for _ in 0 ..< names.count { } 。当我们不需要数组中每一个具体的元素值时，我们就可以用下划线来代表序号。</p>    <p>另一个是是 repeat { } while i < names.count 。这个相当于我们熟悉（java）的 do { } while (i < names.length) 。</p>    <h2>排序</h2>    <p>swift排序效率很高，写法也很简洁。笔者将其总结如下</p>    <pre>  <code class="language-swift">// Sort an Int array，ascending  nums.sortInPlace({$0 < $1})    // Sort an Int array without mutating the original one, ascending  var sortedNums = nums.sort({$0 < $1})    // Sort an array with custom-defined objects, ascending  timeIntervals.sortInPlace({$0.startTime < $1.startTime})    // Sort keys in a dictionary according to its value, ascending  let keys = Array(dict.keys)  var sortedKeys = keys.sort() {    let value0 = dict[$0]    let value1 = dict[$1]    return value0 < value1  }</code></pre>    <h2>活用Guard语句</h2>    <p>使用Guard语句可以让逻辑变得非常清楚，尤其是在处理算法问题的时候，请看下面的代码</p>    <pre>  <code class="language-swift">// Returns the index of the first occurrence of needle in haystack,   // or -1 if needle is not part of haystack  func strStr(haystack: String, _ needle: String) -> Int {    var hChars = [Character](haystack.characters)    var nChars = [Character](needle.characters)      if hChars.count < nChars.count {      return -1    }    if hChars.count == 0 {      return -1    }      for i in 0 ... hChars.count - nChars.count {      if hChars[i] == nChars[0] {        for j in 0 ..< nChars.count {          if hChars[i + j] != nChars[j] {            break          } else {            if j == nChars.count - 1 {              return i            }          }        }      }    }      return -1  }</code></pre>    <p>上面这段代码是求字符串needle在字符串haystack里首次出现的位置。我们发现for循环中的嵌套非常繁琐，但是如果使用Guard语句代码会变得清晰很多：</p>    <pre>  <code class="language-swift">func strStr(haystack: String, _ needle: String) -> Int {    var hChars = [Character](haystack.characters)    var nChars = [Character](needle.characters)      guard hChars.count >= nChars.count else {      return -1    }    if nChars.count == 0 {      return 0    }      for i in 0 ... hChars.count - nChars.count {      guard hChars[i] == nChars[0] else {        continue      }        for j in 0 ..< nChars.count {        guard hChars[i + j] == nChars[j] else {          break        }        if j == nChars.count - 1 {          return i        }      }    }      return -1  }</code></pre>    <p>Guard语句的好处是判断条件永远是我们希望的条件而不是特殊情况，且成功避免了大量的if嵌套。Guard语句详解请移步此文《Swift的Guard语句》</p>    <p>另外在上面代码中，为何要将字符串转化成数组进行处理？因为Swift中没有方法能够以O(1)的时间复杂度取得字符串中的字符，我们常用的 string.startIndex.advancedBy(n) 方法，其时间复杂度为O(n)。所以笔者在这里以空间换时间的方法进行了优化。</p>    <h2>总结</h2>    <p>Swift是一门独特的语言，本文对其基本知识和语法进行了适当归纳，文中提到的都是基本细节。下期我们会讨论更加进阶的内容。</p>    <p> </p>    <p>来自： http://www.jianshu.com/p/ee16bcf50a59</p>