1. 赋值运算符函数
2. 实现 Singleton 模式
3. 数组中重复的数字
- 3.1 找出数组中重复的数字
- 3.2 不修改数组找出重复的数字
4. 二维数组中的查找
5. 替换空格
6. 从尾到头打印链表
7. 重建二叉树
8. 二叉树的下一个节点
9. 用两个栈实现队列
10. 斐波那契数列
- 10.1 求斐波那契数列的第 n 项
- 10.2 青蛙跳台阶问题
11. 旋转数组的最小数字
未完待续

1. 赋值运算符函数

Swift 支持运算符重载、自定义运算符。

注意

以下这些标记 =、->、//、/*、*/、.，前缀运算符 <、& 和 ?，中缀运算符 ?，后缀运算符 >、! 和 ? 是被系统保留的。这些符号不能被重载，也不能用作自定义运算符。

哪些字符能用于自定义运算符，可见 https://docs.swift.org/swift-book/ReferenceManual/LexicalStructure.html#ID418。

下面以重载 * 为例：

func *(lhs: String, rhs: Int) -> String {
  var result = lhs
  for _ in 0..<rhs {
     result += lhs
  }
  return result
}

let x = "a" * 5 // "aaaaa"

2. 实现 Singleton 模式

// 基本的 Swift 单例
public final class Singleton_1 {
  public static let shared = Singleton_1()
  
  private init() {}
}

// 单例中静态属性的额外作用
public final class Singleton_2 {
  private static let _shared = Singleton_2()
  private init() { }
  
  public static var shared: Singleton_2 {
    print("do something")
    return _shared
  }
}

对于单例而言，请使用引用类型；

将单例类型标记为 final，其实例标记为 public，构造器标记为 private；

在命名的时候，尽量使用更符合 Swift 风格的 shared，而不是 Objective-C 风格的 sharedInstance；

如果在获取单例的时候还需要引入其他的额外作用，那么可以创建一个静态的只读属性。

3. 数组中重复的数字

3.1 找出数组中重复的数字

在一个长度为 n 的数组里的所有数字都在 0~n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。例如，如果输入长度为 7 的数组｛2，3，1，0，2，5，3｝，那么对应的输出是重复的数字 2 或者 3。

func getDuplicate(_ array: inout [Int]) -> Int? {
  guard array.count > 0 else {
    print("input is empty")
    return nil
  }
  
  guard !array.contains(where: { $0 < 0 || $0 > array.count - 1 }) else {
    print("input is invalid")
    return nil
  }
  
  for i in 0..<array.count {
    while array[i] != i {
      if array[i] == array[array[i]] {
        return array[i]
      }
      
      array.swapAt(i, array[i])
    }
  }
  
  print("no duplication")
  return nil
}

var array1 = [2, 3, 1, 0, 2, 5, 3]
var array2: [Int] = []
var array3 = [2, 3, -1, 1]
var array4 = [2, 3, 1, 0, 10, 4]
var array5 = [2, 3, 1, 0, 5, 4]

getDuplicate(&array1) // 2
getDuplicate(&array2) // nil, input is empty
getDuplicate(&array3) // nil, input is invalid
getDuplicate(&array4) // nil, input is invalid
getDuplicate(&array5) // nil, no duplication

时间复杂度为 O(n)，空间复杂度为 O(1)

3.2 不修改数组找出重复的数字

在一个长度为 n+1 的数组里的所有数字都在 1~n 的范围内，所以数组中至少有一个数字是重复的。请找出数组中任意一个重复的数字，但不能修改输入的数组。例如，如果输入长度为 8 的数组｛2，3，5，4，3，2，6，7｝，那么对应的输出是重复的数字 2 或者 3

二分查找

public func getDuplicate(_ array: [Int]) -> Int? {
  guard array.count > 0 else {
    print("input is empty")
    return nil
  }

  guard !array.contains(where: { $0 < 1 || $0 > array.count - 1 }) else {
    print("input is invalid")
    return nil
  }
  
  var left = 1, right = array.count - 1
  while right >= left {
    let middle = (right - left) >> 1 + left
    let count = _helper(array, left: left, right: middle)
    
    if left == right {
      if count > 1 {
        return left
      } else {
        break
      }
    }
    
    if count > middle - left + 1 {
      right = middle
    } else {
      left = middle + 1
    }
  }
  
  return nil
}

private func _helper(_ array: [Int], left: Int, right: Int) -> Int {
  var count = 0
  for i in 0..<array.count {
    if array[i] >= left, array[i] <= right {
      count += 1
    }
  }
  return count
}

var array = [2, 3, 5, 4, 3, 2, 6, 7]

getDuplicate(array) // 3

时间复杂度为 O(nlogn)，空间复杂度为 O(1)

需要指出的是，这种算法不能保证找出所有重复的数字。例如，该算法不能找出数组｛2，3，5，4，3，2，6，7｝中重复的数字 2。这是因为在 1~2 的范围里有 1 和 2 两个数字，这个范围的数字也出现 2 次，此时我们用该算法不能确定是每个数字各出现一次还是某个数字出现了两次。

4. 二维数组中的查找

题目：在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

右上角、左下角

func find(_ number: Int, in array: [[Int]]) -> Bool {
  let rows = array.count
  guard rows > 0 else {
    print("input is invalid")
    return false
  }
  
  let columns = array[0].count
  guard columns > 0 else {
    print("input is invalid")
    return false
  }
  
  var row = 0, column = columns - 1
  while row < rows, column >= 0 {
    if number == array[row][column] {
      return true
    } else if number < array[row][column] {
      column -= 1
    } else {
      row += 1
    }
  }
  
  return false
}

let array = [
  [1, 2, 8, 9],
  [2, 4, 9, 12],
  [4, 7, 10, 13],
  [6, 8, 11, 15],
]

find(7, in: array) // true
find(1, in: array) // true
find(15, in: array) // true
find(20, in: array) // false
find(0, in: array) // false
find(3, in: array) // false
find(5, in: []) // false, input is invalid

5. 替换空格

题目：请实现一个函数，把字符串中的每个空格替换成“％20”例如，输入“We are happy.”，则输出“We％20are％20happy.”。

倒序、双指针

func replaceBlank(_ string: String) -> String {
  var chars = Array(string)
  let blankCount = chars.filter { $0 == " " }.count
  chars.append(contentsOf:
    Array(repeating: " ", count: blankCount * 2)
  )
  
  var p1 = string.count - 1, p2 = chars.count - 1
  
  while p1 != p2 {
    if chars[p1] != " " {
      chars[p2] = chars[p1]
      p2 -= 1
    } else {
      chars[p2] = "0"
      chars[p2 - 1] = "2"
      chars[p2 - 2] = "%"
      p2 -= 3
    }
    p1 -= 1
  }
  
  return String(chars)
}

replaceBlank("We are happy.") // "We%20are%20happy."
replaceBlank(" We are happy. ") // "%20We%20are%20happy.%20"
replaceBlank("Wearehappy.") // "Wearehappy."
replaceBlank("  ") // "%20%20"
replaceBlank("") // ""

6. 从尾到头打印链表

题目：输入一个链表的头节点，从尾到头反过来打印出每个节点的值。

栈、递归

func printListReversingly(_ node: ListNode<Int>?) {
  guard let node = node else {
    print("node is nil")
    return
  }
  
  if node.next != nil {
    printListReversingly(node.next!)
  }
  
  print(node.value)
}

class ListNode<Int> {
  var value: Int
  var next: ListNode<Int>?
  
  init(value: Int) {
    self.value = value
  }
}

let head = ListNode(value: 1)
head.next = ListNode(value: 2)
head.next?.next = ListNode(value: 3)
head.next?.next?.next = ListNode(value: 4)

printListReversingly(head) // 4 3 2 1
printListReversingly(head.next?.next?.next) // 4
printListReversingly(head.next?.next?.next?.next) // node is nil

7. 重建二叉树

题目：输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

二叉树：除根节点之外每个节点只有一个父节点，根节点没有父节点；除叶节点之外所有节点都有一个或多个子节点，叶节点没有子节点。父节点和子节点之间用指针链接。

前序遍历：先访问根节点，再访问左子节点，最后访问右子节点。
中序遍历：先访问左子节点，再访问根节点，最后访问右子节点。
后序遍历：先访问左子节点，再访问右子节点，最后访问根节点。

以上图为例：

前序遍历：2, 7, 2, 6, 5, 11, 5, 9, 4
中序遍历：2, 7, 5, 6, 11, 2, 5, 4, 9
后序遍历：2, 5, 11, 6, 7, 4, 9, 5, 2

递归

func construct(preorder: [Int], inorder: [Int]) -> BinaryTreeNode? {
  guard preorder.count > 0, preorder.count == inorder.count else {
    print("Invalid input")
    return nil
  }
  
  return _helper(preorder, inorder)
}

private func _helper(_ preorder: [Int], _ inorder: [Int]) -> BinaryTreeNode? {
  let root = BinaryTreeNode(value: preorder.first!)
  
  if preorder.count == 1 {
    if inorder.count == 1 {
      return root
    } else {
      print("Invalid input")
      return nil
    }
  }
  
  // find root node in inorder
  guard let rootIndex = inorder.firstIndex(of: preorder.first!) else {
    print("Invalid input")
    return nil
  }
  
  let leftInorder = inorder[..<rootIndex]
  let rightInorder = inorder[(rootIndex + 1)...]
  
  // construct left subtree
  if leftInorder.count > 0 {
    root.left = _helper(Array(preorder[1...rootIndex]),
                        Array(leftInorder))
  }
  // construct right subtree
  if rightInorder.count > 0 {
    root.right = _helper(Array(preorder[(rootIndex + 1)...]),
                         Array(rightInorder))
  }
  
  return root
}

class BinaryTreeNode {
  let value: Int
  var left: BinaryTreeNode? = nil
  var right: BinaryTreeNode? = nil
  
  init(value: Int) {
    self.value = value
  }
}

let root = construct(preorder: [1, 2, 4, 7, 3, 5, 6, 8],
                     inorder: [4, 7, 2, 1, 5, 3, 8, 6])
root?.value // 1
root?.left?.value // 2
root?.left?.left?.value // 4
root?.left?.left?.right?.value // 7
root?.right?.value // 3
root?.right?.right?.left?.value // 8

// Invalid input
let root2 = construct(preorder: [1, 2, 4, 7, 3, 5, 6, 8],
                      inorder: [4, 7, 2, 5, 1, 3, 8, 6])

8. 二叉树的下一个节点

题目：给定一棵二叉树和其中的一个节点，如何找出中序遍历序列的下一个节点？树中的节点除了有两个分别指向左、右子节点的指针，还有个指向父节点的指针。

func getNext(node: BinaryTreeNode<String>) -> BinaryTreeNode<String>? {
  if node.right != nil {
    var next = node.right
    while next!.left != nil {
      next = next!.left
    }
    
    return next
  } else if node.parent != nil {
    var next: BinaryTreeNode? = node, parent = node.parent
    while parent != nil, parent?.right == next {
      next = parent
      parent = parent?.parent
    }
    next = parent
    
    return next
  }
  
  return nil
}

class BinaryTreeNode<T> where T: Equatable {
  let value: T
  var left: BinaryTreeNode<T>? = nil
  var right: BinaryTreeNode<T>? = nil
  weak var parent: BinaryTreeNode<T>? = nil
  
  init(value: T, parent: BinaryTreeNode<T>? = nil) {
    self.value = value
    self.parent = parent
  }
}

extension BinaryTreeNode: Equatable {
  static func == (lhs: BinaryTreeNode<T>, rhs: BinaryTreeNode<T>) -> Bool {
    return lhs.value == rhs.value
  }
}

let a = BinaryTreeNode(value: "a")
a.left = BinaryTreeNode(value: "b", parent: a)
a.left?.left = BinaryTreeNode(value: "d", parent: a.left)
a.left?.right = BinaryTreeNode(value: "e", parent: a.left)
a.left?.right?.left = BinaryTreeNode(value: "h", parent: a.left?.right)
a.left?.right?.right = BinaryTreeNode(value: "i", parent: a.left?.right)

a.right = BinaryTreeNode(value: "c", parent: a)
a.right?.left = BinaryTreeNode(value: "f", parent: a.right)
a.right?.right = BinaryTreeNode(value: "g", parent: a.right)

let b = a.left!
let d = a.left!.left!
let e = a.left!.right!
let h = a.left!.right!.left!
let i = a.left!.right!.right!
let c = a.right!
let f = a.right!.left!
let g = a.right!.right!

getNext(node: b)?.value // h
getNext(node: a)?.value // f
getNext(node: d)?.value // b
getNext(node: f)?.value // c
getNext(node: i)?.value // a
getNext(node: g)?.value // nil

9. 用两个栈实现队列

题目：用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 appendTail 和 deleteHead，分别完成在队列尾部插入节点和在队列头部删除节点的功能。

template <typename T> class CQueue
{
public:
  CQueue(void);
  ~CQueue(void);
  
  void appendTail(const T& node);
  T deleteHead();

private:
  stack<T> stackl;
  stack<T> stack2;
};

Swift 实现如下：

var stack1 = Stack<Any>()
var stack2 = Stack<Any>()

func appendTail(element: Any) {
  stack1.push(element)
}

func deleteHead() -> Any? {
  if stack2.count == 0 {
    if stack1.count == 0 {
      print("queue is empty")
      return nil
    } else {
      while stack1.count > 0 {
        stack2.push(stack1.pop()!)
      }
      return stack2.pop()
    }
  } else {
    return stack2.pop()
  }
}

栈的 Swift 实现如下：

// 见：https://kiligwyu.com/数据结构和排序算法inswift/#栈的实现

public struct Stack<T> {
  private var stackArray = [T]()
  
  public var count: Int {
    return stackArray.count
  }
  
  public var isEmpty: Bool {
    return stackArray.isEmpty
  }
  
  public var top: T? {
    return stackArray.last
  }
}

extension Stack {
  /// push operation
  public mutating func push(_ element: T) {
    stackArray.append(element)
  }
  
  /// pop operation
  public mutating func pop() -> T? {
    guard !stackArray.isEmpty else {
      print("stack is empty")
      return nil
    }
    
    return stackArray.removeLast()
  }
  
  /// print all elements
  public mutating func printAllElements() {
    for (index, value) in stackArray.enumerated() {
      print("[\(index)]\(value)")
    }
  }
}

10. 斐波那契数列

10.1 求斐波那契数列的第 n 项

写一个函数，输入 n，求斐波那契（Fibonacci）数列的第 n 项。斐波那契数列的定义如下：

f(n)=\begin{cases} 0 \qquad\qquad\qquad\quad\ \ n = 0 \\\\ 1 \qquad\qquad\qquad\quad\ \ n = 1 \\\\ f(n-1)+f(n-2) \quad n > 1 \end{cases}

解法 1

时间复杂度为 O(n)

避免重复运算

func fibonacci(n: Int) -> UInt64 {
  if n == 0 { return 0 }
  if n == 1 { return 1 }
  
  var fibNMinusOne: UInt64 = 1
  var fibNMinusTwo: UInt64 = 0
  var fibN: UInt64 = 0
  for _ in 2...n {
    fibN = fibNMinusOne + fibNMinusTwo
    
    fibNMinusTwo = fibNMinusOne
    fibNMinusOne = fibN
  }
  
  return fibN
}

fibonacci(n: 0) // 0
fibonacci(n: 1) // 1
fibonacci(n: 2) // 1
fibonacci(n: 3) // 2
fibonacci(n: 4) // 3
fibonacci(n: 5) // 5
fibonacci(n: 6) // 8
fibonacci(n: 7) // 13
fibonacci(n: 8) // 21
fibonacci(n: 9) // 34
fibonacci(n: 10) // 55
fibonacci(n: 20) // 6765
fibonacci(n: 30) // 832040
fibonacci(n: 40) // 102334155
fibonacci(n: 50) // 12586269025

解法 2

时间复杂度为 O(logn)

矩阵乘方
$\begin{bmatrix}f(n) & f(n-1)\\\\f(n-1) &f(n-2)\end{bmatrix}=\begin{bmatrix}1 & 1\\\\1 &0\end{bmatrix}^{n-1}$ $a^n=\begin{cases} a^{n/2}a^{n/2} \qquad\qquad n 为偶数 \\\\ a^{(n-1)/2}a^{(n-1)/2}a \quad\ n 为奇数 \\\\ \end{cases}$

func fibonacci2(n: Int) -> UInt64 {
  if n == 0 { return 0 }
  if n == 1 { return 1 }
  
  return _helper(n: n - 1)[0][0]
}

private func _helper(n: Int) -> Matrix {
  if n == 1 {
    return matrix0
  }
  if n == 2 {
    return matrix0 × matrix0
  }
  
  if n % 2 == 0 {
    return _helper(n: n / 2) × _helper(n: n / 2)
  } else {
    return _helper(n: (n - 1) / 2) × _helper(n: (n - 1) / 2) × matrix0
  }
}

typealias Matrix = [[UInt64]]
let matrix0: Matrix = [
  [1, 1],
  [1, 0]
]

infix operator × : MultiplicationPrecedence
func × (lhs: Matrix, rhs: Matrix) -> Matrix {
  let row = lhs.count, col = rhs.first!.count, len = lhs.first!.count
  let rowArray = Array(repeating: UInt64(0), count: col)
  var out = Matrix(repeating: rowArray, count: row)
  for i in 0 ..< row {
    for j in 0 ..< col {
      for k in 0 ..< len {
        out[i][j] += lhs[i][k] * rhs[k][j]
      }
    }
  }
  return out
}

fibonacci2(n: 0) // 0
fibonacci2(n: 1) // 1
fibonacci2(n: 2) // 1
fibonacci2(n: 3) // 2
fibonacci2(n: 4) // 3
fibonacci2(n: 5) // 5
fibonacci2(n: 6) // 8
fibonacci2(n: 7) // 13
fibonacci2(n: 8) // 21
fibonacci2(n: 9) // 34
fibonacci2(n: 10) // 55
fibonacci2(n: 20) // 6765
fibonacci2(n: 30) // 832040
fibonacci2(n: 40) // 102334155
fibonacci2(n: 50) // 12586269025

10.2 青蛙跳台阶问题

一只青蛙一次可以跳上 1 级台阶，也可以跳上 2 级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。

$f(n)=\begin{cases} 1 \qquad\qquad\qquad\quad\ \ n = 1 \\\\ 2 \qquad\qquad\qquad\quad\ \ n = 2 \\\\ f(n-1)+f(n-2) \quad n > 2 \end{cases}$
解法同 10.1。
另，假如该青蛙一次可以跳上 1 级台阶，也可以跳上 2 级台阶…也可以跳上 n 级，那么该青蛙跳上一个 n 级的台阶总共有多少种跳法。此时 $$f(n)=2^{n-1}$$。

11. 旋转数组的最小数字

题目：把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如，数组 {3，4，5，1，2} 为 {1，2，3，4，5} 的一个旋转，该数组的最小值为 1。

func findMin(in numbers: [Int]) -> Int? {
  guard numbers.count > 0 else { return nil }
  guard numbers.count > 1 else { return numbers[0] }
  
  var index1 = 0, index2 = numbers.count - 1, indexMid = index1
  while numbers[index1] >= numbers[index2] {
    if index2 - index1 == 1 {
      indexMid = index2
      break
    }
    
    indexMid = (index1 + index2) / 2
    
    if numbers[index1] == numbers[indexMid],
      numbers[index2] == numbers[indexMid] {
      var result = numbers[index1]
      for i in index1 + 1...index2 {
        result = min(result, numbers[i])
      }
      
      return result
    }
    
    if numbers[indexMid] >= numbers[index1] {
      index1 = indexMid
    } else if numbers[indexMid] <= numbers[index2] {
      index2 = indexMid
    }
  }
  
  return numbers[indexMid]
}

findMin(in: [3, 4, 5, 1, 2]) // 1
findMin(in: [1, 2, 3, 4]) // 1
findMin(in: [1]) // 1
findMin(in: []) // nil
findMin(in: [1, 1, 1, 0, 1]) // 0

剑指 Offer 编程题 in Swift