剑指Offer算法题-二进制中1的个数

Posted on 2018-09-03 In 算法

题目：

请实现一个函数，计算一个整数二进制表示中 1 的个数，例如：把 9 表示成二进制是 1001，有 2 位是 1

####方案一
判断该数最后一位是不是 1，然后把该数右移一位；这样每次移动一位直到这个数变为 0 为止。但是该思路有个问题就是该数是负数时，会变成死循环，因为负数的最高位是 1，即使右移之后，为了保证该数还是负数，仍会把最高位置为 1。

extension Int {
    var binaryOneNumber : Int {
        var tmp = self
        var count = 0
        while tmp != 0 {
            if tmp & 1 == 1{
                count += 1
            }
            tmp = tmp >> 1
        }
        return count
    }
}

print(0.binaryOneNumber) //输出0
print(9.binaryOneNumber) //输出2
print((-9).binaryOneNumber)//死循环

####方案二
对方案一会产生死循环的一种改良，把该数首先与 1（即为 flag）做&运算判断判断最低位是否为 1，然后把 flag 左移一位，判断第二位是否为 1，直到 flag 为 0。在 4 字节的 Int 类型里也就是移动 32 次。

1	extension Int {
2	var binaryOneNumber : Int {
3	var flag = 1
4	var count = 0
5	while flag != 0 {
6	if flag & self > 0{
7	count += 1
8	}
9	flag = flag << 1
10	}
11	//如果是负数的话，最高位会统计不上，这里在加1
12	if self < 0 {
13	count += 1
14	}
15	return count
16	}
17	}
18	print(0.binaryOneNumber) //输出0
19	print(9.binaryOneNumber) //输出2
20	//这里输出63是正确的，mac os里Int是64位的，在64位里-9的补码是
21	//1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 0111
22	print((-9).binaryOneNumber)//输出63

####方案三
在二进制中，把一个整数减去 1 之后再和原来的整数做&运算，得到的结果相当于把该整数的二进制表示中最右边的 1 变成 0。因此可以每次都把n & (n - 1)的结果赋值为 n，直到 n 为 0 结束。

extension Int {
    var binaryOneNumber : Int {
        var tmp = self
        var count = 0
        while tmp != 0 {
            //这里减一，不能直接用-,有可能会有溢出错误的
            //因为负数的最大值的补码形式是1000 0000...,此时在进行减1，就会有溢出错误
            tmp = tmp & (tmp &- 1)
            count += 1
        }

        return count
    }
}
print(0.binaryOneNumber) //输出0
print(9.binaryOneNumber) //输出2
print((-9).binaryOneNumber)//输出63
print((-1).binaryOneNumber)//输出64

剑指Offer算法题-求和

Posted on 2018-09-01 In 算法

####题目：
求 1+2+…+n，要求不能使用乘除法、for、while、if、else、switch、case 等关键字以及三目运算符

通常求 1+2+…+n 除了用公式 n(n+1)/2 之外，无外乎循环和递归两种思路。由于已经明确限制 for 和 while 的使用，循环已经不能再用了。同样，递归函数也需要用 if 语句或者条件判断语句来判断是继续递归下去还是终止递归，但现在题目已经不允许使用这两种语句了。

####思路 1
利用函数指针实现递归。
由于不能用 if 语句来终止递归，但是我们可以定义两个函数。一个函数充当递归函数的角色，另一个函数处理终止递归的情况。然后在根据情况在两个函数二选一，可以这么做，把递归过程中传进来的 n 转成 bool 类型，非 0 的话就是 true，然后再把 bool 类型转成 Int 类型，也就是 1，同时若 n 为 0，先把 n 转成 bool 类型在转回来还是 0，也就是相当于说可以把非 0 的 n 转成 1，0 还是 0.这样我们可以把两个函数放到一个数组里，根据 n 转换之后的值去数组里取函数就行了.

代码实现

func sumTeminator(number:UInt) -> UInt {
    return 0
}
func sum(number:UInt) -> UInt {
    let funcs = [sumTeminator,sum]
    let isTeminator = Bool(truncating: NSNumber(value: number - 1))
    let funcIndex = Int(truncating: NSNumber(value: isTeminator))
    let sumFunc = funcs[funcIndex]
    return number + sumFunc(number - 1)
}
print(sum(number: 100))

####思路 2
利用 KVC 里的 sum 进行求和
首先初始化一个 0 到 n 的数组，然后利用 KVC 里的 sum 进行求和,初始化数组用到了 Swift 的 Stride 这个函数。

代码实现

func sum1(number:UInt) -> UInt {
    let array = Array(stride(from: 0, to: number + 1, by: 1))
    let sum = (array as NSArray).value(forKeyPath: "@sum.integerValue") as! UInt
    return sum
}
print(sum1(number: 100))

剑指Offer算法题-机器人的运动范围

Posted on 2018-08-31 In 算法

题目

地上有一个 m 行 n 列的方格，一个机器人从坐标 $ (0,0) $的格子开始移动，它每次可以向左，右，上，下移动一格，但不能进入行坐标和列坐标的位数之和大于$k$的格子。例如，当 $k$为 18 时，机器人能够进入方格$(35,37)$,因为$3+5+3+7=18$。但它不能进入方格$(35,38)$。因为$3+5+3+8=19$。请问该机器人能够到达多少个格子？

思路

可以把方格看做一个$m \times n$的矩阵。在这个矩阵中，除边界以外的格子之外，其他格子都有四个相邻的格子。

机器人从坐标$ (0,0) $开始移动
当机器人准备进入到$ (i,j) $时，判断机器人能否进入到该格子
判断机器人是否能进入格子的条件是，行和列的位数之和小于 k，并且机器人也没有进入过次格子
若不能进入，则不去尝试进入到它周围的格子。
若能进入，则让机器人分别去尝试进入它周围的四个格子$ (i-1,j) , (i+1,j) , (i,j+1) , (i,j-1) ,$,而由于格子是从$ (0,0) $开始的，只需要向上和向右就能进入到所有能到达的格子，所以只需让机器人分别去尝试进入它上面或右面的格子 $(i+1,j) , (i,j+1) , $。也就是回到第 2 步。

代码实现（Swift）

首先用结构体Grid来表示 m 行 n 列的方格

//用来表示每个格子的坐标
typealias Coordinate = (row:Int,column:Int)
struct Grid {
    let row : Int //行数
    let column : Int //列数
    //原点坐标
    var originCoordinate : Coordinate {
        return (row:0,column:0)
    }
    //在方格内指定坐标的上面的格子，若上面已没有格子，则返回nil
    func above(coor:Coordinate) -> Coordinate? {
        if coor.row >= 0 && coor.row < row - 1 && coor.column >= 0 && coor.column < column{
            return (row:coor.row + 1,column:coor.column)
        }
        return nil
    }
    //在方格内指定坐标的下面的格子，若下面已没有格子，则返回nil
    func below(coor:Coordinate) -> Coordinate? {
        if coor.row > 0 && coor.row < row && coor.column >= 0 && coor.column < column{
            return (row:coor.row - 1,column:coor.column)
        }
        return nil
    }
    //在方格内指定坐标的左面的格子，若左面已没有格子，则返回nil
    func left(coor:Coordinate) -> Coordinate? {
        if coor.row >= 0 && coor.row < row && coor.column > 0 && coor.column < column{
            return (row:coor.row,column:coor.column - 1)
        }
        return nil
    }
    //在方格内指定坐标的右面的格子，若右面已没有格子，则返回nil
    func right(coor:Coordinate) -> Coordinate? {
        if coor.row >= 0 && coor.row < row && coor.column >= 0 && coor.column < column - 1{
            return (row:coor.row,column:coor.column + 1)
        }
        return nil
    }
}

然后在用结构体Robot来表示机器人

struct Robot {
    let k : Int
    let grid : Grid //格子

    init(k :Int, grid: Grid) {
        self.k = k
        self.grid = grid
    }

    //对外暴露的方法，做了一些数据的初始化和边界的判断。内部调用了private func movingCount(coor:Coordinate? , visited:inout [Bool]) -> Int
    func movingCount() -> Int {
        guard k >= 0, grid.column > 0, grid.row > 0 else { return 0 }
        var visited = Array(repeating: false, count: grid.row * grid.column)
        let count = movingCount(coor: grid.originCoordinate , visited : &visited)
        return count
    }

    //实现上面的思路
    private func movingCount(coor:Coordinate? , visited:inout [Bool]) -> Int {
        if let coor = coor , isVaild(coor: coor, visited: visited) {
            visited[coor.row * grid.column + coor.column] = true
            return 1 + movingCount(coor:grid.above(coor: coor), visited: &visited)
                     + movingCount(coor:grid.right(coor: coor), visited: &visited)
        }
        return 0
    }

    //用来判断是否能进入到此格子
    private func isVaild(coor:Coordinate , visited : [Bool]) -> Bool {
        return visited[coor.row * grid.column + coor.column] == false && (digitsSum(number: coor.row) + digitsSum(number: coor.column) <= k)
    }

    //求一个数字的位数之和
    private func digitsSum(number:Int) -> Int {
        var sum = 0
        var topDigit = number
        while topDigit > 0 {
            sum += topDigit % 10
            topDigit = topDigit / 10
        }
        return sum
    }
}

Test

let grid = Grid(row: 100, column: 100)
for i in -2...30 {
    let robot = Robot(k: i, grid : grid)
    let count = robot.movingCount()
    print("\(i)===\(count)")
}

用Swift实现LinkedList（双向链表结构的集合）

Posted on 2018-08-30 In 数据结构

1. 什么是双向链表

双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。—维基百科

2. 集合有哪些功能

添加元素
删除元素
更新元素
查找元素
查找元素的位置

3. 文章中要实现的功能

2 中的特性
for in 遍历
通过下标进行取值赋值
*[字面量赋值
把集合转成数组
复制
自定义打印

4.未实现的功能

未把 list 定义成结构体
若把 list 改成结构体则,未实现写时复制

原因:为了了解 Swift 中的集合以及学习链表，所以就简单的来了。

5. 如何实现

定义链表结构如下

size代表链表的长度
firstNode 表示第一个节点
lastNode 表示最后一个节点
Node 表示节点的类型
通过序列初始化 list
1. 遍历序列，通过序列里的值生成节点 newNode。
2. 遍历到首个元素时，让 firstNode 和 lastNode 都指向 newNode
3. 遍历到其他元素时,把 lastNode 的 next 指向 newNode，把 newNode 的 prev 指向 lastNode,最后把 lastNode 指向 newNode
4. 每次遍历都把 size += 1

final public class LinkedList<E>  {
    private var size = 0
    private var firstNode:Node<E>?
    private var lastNode:Node<E>?

    /// 初始化一个空list
    public init() { }

     /// 通过序列初始化一个list
    public init<S>(_ s: S) where Element == S.Element, S : Sequence {
        for (index,item) in s.enumerated() {
            let newNode = Node(element: item)
            if index == 0 {
                firstNode = newNode
                lastNode = newNode
            }else {
                newNode.prev = lastNode
                lastNode?.next = newNode
                lastNode = newNode
            }
            size += 1
        }
    }
}
/// 节点
fileprivate class Node<Element> {
    /// 节点元素的值
    var item:Element
    /// 下一个节点
    var next:Node<Element>?
    /// 上一个节点
    var prev:Node<Element>?
    init(element:Element, next:Node<Element>? = nil, prev:Node<Element>? = nil) {
        self.item = element
        self.next = next
        self.prev = prev
    }
}

如何查找指定位置的元素

如果查找的位置在前半部分就顺序查找，否则就逆序查找，以顺序查找为例，从首个节点开始，一直取 next 节点，直到要查找的位置。在查找之前首先要判断查找的位置是有效的，即 index>=0 && index < size。

由于对使用者来说并不关心节点，只关心节点里的值，而且也不允许使用者修改节点的前后节点，所以对外暴露的是对外节点里的值，而不是节点。所以下面的方法定义为私有的。在文章的下面利用下标来进行取值和赋值

// MARK: - private
extension LinkedList {
    /// 通过下标找到对应的节点
    private func node(at index:Int) -> Node<E> {
        //如果下标位置无效，则直接报错
        if !indexIsVaild(index) {
            fatalError("Index out of range:\(index) not belong 0..<\(size)")
        }
        //如果节点在前一半顺序查找，否则逆序查找
        if index < (size >> 1) {
            var node = firstNode
            for _ in 0..<index {
                node = node?.next
            }
            return node!
        }else {
            var node = lastNode
            for _ in stride(from: size - 1, to: index, by: -1) {
                node = node?.prev
            }
            return node!
        }
    }
    /// 下标是否是有效的
    private func indexIsVaild(_ index:Int) -> Bool {
        return index >= 0 && index < size
    }
}

如何追加和插入元素

追加单个元素
只需要把 lastNode 的 next 指向要追加的节点，把要追加的节点的 prev 指向 lastNode,最后把 lastNode 指向要追加的节点，并且把 size+1。若追加时 list 为空，需要把 firstNode 也指向要追加的节点

插入单个元素

若插入的位置为 0 并且 list 长度为 0 时，直接把 firstNode 和 lastNode 都指向 newNode；
获取插入位置的节点 insertNode,把 newNode 的 next 指向要 insertNode，把 insertNode 的 prev 指向 newNode，把 newNode 的 prev 指向要 insertNode 的 prev，把 insertNode 的 prev 的 next 指向 newNode，若插入的位置为 0，则把 firstNode 指向 newNode，更新 size 的值

追加多个元素
只需要依次追加单个元素即可

插入多个元素

若插入的位置为 0 并且 list 长度为 0 时，则直接调用追加多个元素
把多个元素的节点连接起来，连接思路同如何通过一个序列初始化一个 list。并记录下连接起来后的 firstNode 和 lastNode，更新 size 的值
获取插入位置的节点 insertNode,把 lastNode 的 next 指向 insertNode，把 insertNode 的 prev 指向 lastNode，把 firstNode 的 prev 指向要 insertNode 的 prev，把 insertNode 的 prev 的 next 指向 firstNode。若插入的位置为 0，则把 list 的 firstNode 指向 firstNode

// MARK: - 添加元素
extension LinkedList {
    /// 追加单个元素
    public func append(_ newElement: E) {
        let newNode = Node(element: newElement, next: nil, prev: lastNode)
        if lastNode == nil {
            firstNode = newNode
        }
        lastNode?.next = newNode
        lastNode = newNode
        size += 1
    }

    /// 追加多个元素
    public func append<S>(contentsOf newElements: S) where S : Sequence, E == S.Element {
        for item in newElements {
            append(item)
        }
    }

    /// 插入单个元素
    public func insert(_ newElement: E, at i: Int){
        let newNode = Node(element: newElement, next: nil, prev: nil)
        if i == 0 && size == 0{
            firstNode = newNode
            lastNode = newNode
        }else {
            let insertNode = node(at: i)
            newNode.next = insertNode
            insertNode.prev = newNode
            newNode.prev = insertNode.prev
            insertNode.prev?.next = newNode
            if i == 0 {
                firstNode = newNode
            }
        }
        size += 1
    }

    /// 插入多个元素
    public func insert<S>(contentsOf newElements: S, at i: Int) where S : Collection, E == S.Element {
        if i == 0 && size == 0 {
            append(contentsOf: newElements)
        }else {
            let insertNode = node(at: i)
            var firstNode:Node<E>?
            var lastNode:Node<E>?
            for (index,item) in newElements.enumerated() {
                let newNode = Node(element: item, next: nil, prev: nil)
                if index == 0 {
                    firstNode = newNode
                    lastNode = newNode
                }else {
                    newNode.prev = lastNode
                    lastNode?.next = newNode
                    lastNode = newNode
                }
                size += 1
            }
            firstNode?.prev = insertNode.prev
            lastNode?.next = insertNode
            insertNode.prev?.next = firstNode
            insertNode.prev = lastNode
            if i == 0 {
                self.firstNode = firstNode
            }
        }
    }
}

删除元素

删除指定位置的元素

获取指定位置的元素 removeNode
把 removeNode 的 prev 的 next 指向 removeNode 的 next
把 removeNode 的 netx 的 prev 指向 removeNode 的 prev
把 size -= 1

删除所有元素

获取首个节点 node
若 node 不为空，取 node 的 next 为 tmp，然后 node 的 next 和 prev 置 nil
把 node 指向 tmp，重复第二步

// MARK: - 删除元素
extension LinkedList {
    /// 删除指定位置的元素
    @discardableResult
    public func remove(at position: Int) -> E {
        if (position >= 0 && position < size){
            let removeNode = node(at: position)
            removeNode.prev?.next = removeNode.next
            removeNode.next?.prev = removeNode.prev
            if (position == 0) {
                firstNode = firstNode.next
            }else if (position == size - 1){
                lastNode = lastNode.prev
            }
            size -= 1
            return removeNode.item
        }else {
            return nil
      }
    }
    /// 删除第一个元素
    @discardableResult
    public func removefirstNode() -> E? {
        if ()
        return firstNode == nil ? nil : remove(at: 0)
    }
    /// 删除最后一个元素
    @discardableResult
    public func removelastNode() -> E? {
        return lastNode == nil ? nil : remove(at: size - 1)
    }
    /// 删除所有元素
    public func removeAll() {
        var next = firstNode
        while next != nil {
            let tmp = next
            next?.next = nil
            next?.prev = nil
            next = tmp
        }
        firstNode = nil
        lastNode = nil
        size = 0
    }
}

实现 Collection 协议

实现 Collection 协议，就能拥有 Collection 协议里的方法。Collection 协议里有很多方法，如 isEmpty,count,map,filter,dropLast…等方法
Collection 参考喵神翻译的书 swift 进阶第 2 章这里不详细介绍了

for in 遍历的原理是，本质是遍历一个迭代器，一直取 next，而实现 Collection 协议时，已经返回了一个迭代器，所以实现 Collection 协议之后已经实现了 for in ,forEach 遍历

链表的迭代器：从首个元素可以，一直遍历 next，直到 next 为 nil

如何实现 Collection 协议
需要实现以下方法

public var startIndex: Int { get } 开始位置
public var endIndex: Int { get } 结束位置
public func index(after i: Int) -> Int 给定位置后面的索引值
public func makeIterator() -> Iterator 遍历时需要的迭代器
public subscript(position: Int) -> E 通过下标存取元素

// MARK: - 实现Collection协议
extension LinkedList : Collection {
    /// 开始位置
    public var startIndex: Int {  return 0 }
    /// 结束位置
    public var endIndex: Int { return size }
    /// 给定位置后面的索引值
    public func index(after i: Int) -> Int {
        return i + 1
    }
    /// 返回指定的迭代器
    public func makeIterator() -> Iterator {
        return Iterator(self)
    }
    /// 通过下标存取元素
    public subscript(position: Int) -> E {
        get {
            return node(at: position).item
        }
        set {
            node(at: position).item = newValue
        }
    }
}

// MARK: - 迭代器
extension LinkedList {
    public struct Iterator: IteratorProtocol {
        let list: LinkedList
        var index: Int
        private var nextNode:Node<E>?
        init(_ list: LinkedList) {
            self.list = list
            self.index = 0
            self.nextNode = list.firstNode
        }
        /// 获取下一个元素，在for in里若返回nil，则停止循环
        public mutating func next() -> E? {
            let item = nextNode?.item
            nextNode = nextNode?.next
            return item
        }
    }
}

查找满足特定条件的元素的位置和查找元素的位置

查找满足特定条件的元素的位置
只需要遍历，若遇到满足条件的直接返回 index

查找元素的位置
其实就是满足要元素和列表的某一元素相等，所有需要元素遵循 Equatable 协议，然后调用查找满足特定条件的元素的位置的方法即可

// MARK: - 通过条件查找位置
extension LinkedList {
    /// 顺序查找
    public func firstIndex(where predicate: (E) throws -> Bool) rethrows -> Int? {
        for (index,item) in self.enumerated() {
            if try predicate(item) {
                return index
            }
        }
        return nil
    }

    /// 倒序查找
    public func lastIndex(where predicate: (E) throws -> Bool) rethrows -> Int? {
        var prev = lastNode
        var currentIndex = size - 1
        while prev != nil {
            if try predicate(prev!.item) {
                return currentIndex
            }
            currentIndex -= 1
            prev = prev?.prev
        }
        return nil
    }

    /// 是否包含
    public func contains(where predicate: (E) throws -> Bool) rethrows -> Bool {
        for item in self{
            if try predicate(item) {
                return true
            }
        }
        return false
    }
}
// MARK: - 通过元素查找位置
extension LinkedList where E : Equatable {
    public func firstIndex(of element: E) -> Int? {
        return firstIndex { (item) -> Bool in
            return item == element
        }
    }
    public func lastIndex(of element: E) -> Int? {
        return lastIndex(where: { (item) -> Bool in
            return item == element
        })
    }

    public func contains(_ element: E) -> Bool {
        return contains(where: { (item) -> Bool in
            return item == element
        })
    }
}

实现字面量赋值

只需要实现 ExpressibleByArrayLiteral 即可

extension LinkedList : ExpressibleByArrayLiteral {
    public convenience init(arrayLiteral elements: E...) {
        //这里是调用通过序列初始化链表
        self.init(elements)
    }
}

把链表转成数组

利用 map 方法

extension LinkedList {
    public func toArray() -> [E] {
        return self.map({ (item) -> E in
            return item
        })
    }
}

实现 copy

// MARK: - Copy
extension LinkedList {
    public func copy() -> LinkedList {
        let copyList = LinkedList()
        copyList.size = self.size
        if let firstNode = firstNode {
            copyList.firstNode = Node(element: firstNode.item, next: nil, prev: nil)
            copyList.lastNode = copyList.firstNode
        }
        var nextNode = firstNode?.next
        while nextNode != nil {
            let newNode = Node(element: nextNode!.item)
            copyList.lastNode?.next = newNode
            newNode.prev = copyList.lastNode
            copyList.lastNode = newNode
            nextNode = nextNode?.next
        }
        return copyList
    }
}

实现自定义打印

只需要实现 CustomDebugStringConvertible 即可

extension LinkedList : CustomDebugStringConvertible {
    public var debugDescription: String {
        var desc = ""
        if size > 0 {
            for item in self.dropLast() {
                desc += "\(item)-->"
            }
            desc += "\(lastNode!.item)"
        }
        return desc
    }
}

demo 地址

Swift对象的初始化

Posted on 2018-08-29 In Swift

Swift 对象的初始化需要保证所有的非可选属性都被初始化。而初始化又分为 designated 和 convenience 两种。还有 required，required 可以和那两种方法进行组合。默认是非 required，designated
规则如下：

designated 和 convenience 都可以有多个实现
designated 初始化方法里必须保证的非可选属性都被初始化.
子类的 designated 初始化方法必须调用父类的 designated 初始化方法。而且对自己的独有的属性（非继承来的）的赋值语句必须写在调用父类的 designated 初始化方法之前，如果想更改父类初始化方法中的赋值，则可以在调用父类初始化方法之后，再次进行更改
convenience 初始化方法必须调用自己的 designated 初始化方法
extension 里不能有 designated 初始化方法
如果子类里有自己的初始化方法，则也必须重写父类 required 的初始化方法。允许把 required designated 重写成 designated convenience,当然反过来也可以
如果子类里重写了父类 required 的初始化方法，则不会继承父类其他的初始化方法

针对第 6，7 两点的例子如下：

class Person {
    var name : String
    var age :Int
    init(name: String, age: Int) {
        self.name = name
        self.age = age
    }
    required convenience init(name: String) {
       self.init(name: name, age: 18)
    }
}
class Student: Person {
    var grades: [String] = []
    //把父类的required convenience重写成了required designated
    required init(name: String) {
        super.init(name: name, age: 18)
    }
}
//编译不通过 错误信息：Extra argument 'age' in call
//说明没有继承父类其他的初始化方法
let student = Student(name: "lkk", age: 22)

剑指Offer算法题-旋转数组的最小数字--Swift

Posted on 2018-08-28 In 算法

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

方案一

遍历数组，找寻最小值

方案二

旋转之后的数组实际上可以划分为 2 个递增的数组。而且前面的子数组的元素都大于等于后面子数组的元素，并且最小的元素刚好是 2 个子数组的分界点。

我们可以用两个指针分别指向数组的第一个元素记为 P1 和最后一个元素记为 P2，若旋转的个数大于 0,P1 一定是大于等于 P2 的，若旋转的个数等于 0，则 P1 就是最小值。此时先考虑旋转个数大于 0 的情况。

接着我们可以找到数组的 M，如果 M 大于 P1，我们可以认为 M 位于前面的递增数组，则可以把 P1 指向 M，如果 M 小于 P2，我们可以认为 M 位于后面的递增数组，则可以把 P2 指向 M。然后把 M 指向此时 P1 与 P2 的中间，直到 P1 小于 P2 或者 P1 和 P2 的下标相邻

还有一个特殊情况就是 P1=P2=M 时，此时不知道 M 是位于前面的递增数组还是后面的递增数组，就只能遍历 P1 到 P2 之间的值，找到最小值。

方案一代码（swift）

func minInOrder<T:Comparable>(rotationArray:Array<T>) -> T? {
    var minItem = rotationArray.first
    for item in rotationArray {
        if minItem! > item {
            minItem = item
        }
    }
    return minItem
}

方案二代码（swift）

func min<T:Comparable>(rotationArray:Array<T>) -> T? {
    if rotationArray.count < 1 {
        return nil
    }
    var aheadIndex = 0
    var tailIndex = rotationArray.count - 1
    //先让中间指向头部，是因为如果头部元素如果小于尾部元素，则证明旋转了0个元素，此时头部元素等于最小值
    var middleIndex = aheadIndex
    while rotationArray[aheadIndex] >=  rotationArray[tailIndex]{
        if(tailIndex - aheadIndex == 1) {
            middleIndex = tailIndex
            break
        }
        //此处不要写成(aheadIndex + tailIndex) / 2，因为这么写，当数组元素比较多时，可以会造成溢出问题
        middleIndex = aheadIndex + (tailIndex - aheadIndex) / 2
        if rotationArray[aheadIndex] == rotationArray[tailIndex] && rotationArray[aheadIndex] == rotationArray[middleIndex] {
        //把P1到P2之间的元素，重新生成一个新数组，然后调用方案一的写法
            return minInOrder(rotationArray: Array(rotationArray[aheadIndex...tailIndex]))
        }
        if rotationArray[middleIndex] >= rotationArray[aheadIndex] {
            aheadIndex = middleIndex
        }else if rotationArray[middleIndex] <= rotationArray[tailIndex] {
            tailIndex = middleIndex
        }
    }
    return rotationArray[middleIndex]
}

如何在Markdown中画流程图

Posted on 2018-08-27 In 流程图

如何在 Markdown 中画流程图呢？当然是用mermaid了，mermaid 支持三种图形的绘制, 分别是流程图, 时序图和甘特图, 本篇文章只介绍了 mermaid 中流程图在 markdown 的使用(现在简书的 markdown 还不支持 mermaid，我本地使用的是MWeb)。

如何在 markdown 中使用 mermaid

流程图方向有下面几个值

TB 从上到下
BT 从下到上
RL 从右到左
LR 从左到右
TD 同 TB #####示例
从上到下

1	mermaid
2	graph TD
3	A --> B

效果：

从左到右

1	graph LR
2	A --> B

效果：

基本图形

id + [文字描述]矩形
id + (文字描述)圆角矩形
id + >文字描述]不对称的矩形
id + {文字描述}菱形
id + ((文字描述))圆形

示例

1	mermaid
2	graph TD
3	id[带文本的矩形]
4	id4(带文本的圆角矩形)
5	id3>带文本的不对称的矩形]
6	id1{带文本的菱形}
7	id2((带文本的圆形))

效果：

节点之间的连接

A –> B A 带箭头指向 B
A — B A 不带箭头指向 B
A -.- B A 用虚线指向 B
A -.-> B A 用带箭头的虚线指向 B
A ==> B A 用加粗的箭头指向 B
A – 描述 — B A 不带箭头指向 B 并在中间加上文字描述
A – 描述 –> B A 带箭头指向 B 并在中间加上文字描述
A -. 描述 .-> B A 用带箭头的虚线指向 B 并在中间加上文字描述
A == 描述 ==> B A 用加粗的箭头指向 B 并在中间加上文字描述

示例

1	mermaid
2	graph LR
3	A[A] --> B[B]
4	A1[A] --- B1[B]
5	A4[A] -.- B4[B]
6	A5[A] -.-> B5[B]
7	A7[A] ==> B7[B]
8	A2[A] -- 描述 --- B2[B]
9	A3[A] -- 描述 --> B3[B]
10	A6[A] -. 描述 .-> B6[B]
11	A8[A] == 描述 ==> B8[B]

效果：

子流程图

格式

1	subgraph title
2	graph definition
3	end

#####示例

mermaid
graph TB
    c1-->a2
    subgraph one
    a1-->a2
    end
    subgraph two
    b1-->b2
    end
    subgraph three
    c1-->c2
    end

效果：

自定义样式

语法：style id 具体样式 #####示例

mermaid
graph LR
    id1(Start)-->id2(Stop)
    style id1 fill:#f9f,stroke:#333,stroke-width:4px,fill-opacity:0.5
    style id2 fill:#ccf,stroke:#f66,stroke-width:2px,stroke-dasharray: 10,5

效果：

demo

绘制一个流程图,找出 A、 B、 C 三个数中最大的一个数。 #####写法

mermaid
graph LR
    start[开始] --> input[输入A,B,C]
    input --> conditionA{A是否大于B}
    conditionA -- YES --> conditionC{A是否大于C}
    conditionA -- NO --> conditionB{B是否大于C}
    conditionC -- YES --> printA[输出A]
    conditionC -- NO --> printC[输出C]
    conditionB -- YES --> printB[输出B]
    conditionB -- NO --> printC[输出C]
    printA --> stop[结束]
    printC --> stop
    printB --> stop

效果：

剑指Offer算法题-青蛙跳台阶的问题

Posted on 2018-08-25 In 算法

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

答题思路

如果只有 1 级台阶，那显然只有一种跳法
如果有 2 级台阶，那么就有 2 种跳法，一种是分 2 次跳。每次跳 1 级，另一种就是一次跳 2 级
如果台阶级数大于 2，设为 n 的话，这时我们把 n 级台阶时的跳法看成 n 的函数，记为$ f(n) $,第一次跳的时候有 2 种不同的选择：一是第一次跳一级，此时跳法的数目等于后面剩下的 n-1 级台阶的跳法数目，即为$ f(n-1) $,二是第一次跳二级，此时跳法的数目等于后面剩下的 n-2 级台阶的跳法数目，即为$ f(n-2) $,因此 n 级台阶的不同跳法的总数为$ f(n) = f(n-1) + f(n-2)$，不难看出就是斐波那契数列

数学函数表示如下

$$
f(x)=\left{
\begin{aligned}
& 0 & n=0 \
& 1 & n=1 \
& 2 & n=2 \
& f(n-1)+f(n-2) & n > 2
\end{aligned}
\right.
$$

code

这里需要注意一下溢出的问题，因为在 swift 里若相加溢出，则会直接 crash，所以这里相加使用了 &+，溢出后返回 nil

func fibonacci(number: UInt64) -> UInt64? {
    if number == 1 {
        return 1
    }else if number == 2 {
        return 1
    }
    var fibNMinusOne:UInt64 = 1
    var fibNMinusTwo:UInt64 = 1
    var fibN:UInt64 = 0
    for _ in 3...number {
        fibN = fibNMinusOne &+ fibNMinusTwo
        if(fibN < fibNMinusOne) {
            return nil
        }
        fibNMinusTwo = fibNMinusOne
        fibNMinusOne = fibN
    }
    return fibN
}

若把条件修改成一次可以跳一级，也可以跳 2 级…也可以跳上 n 级呢？

思路

如果台阶级数为 n 的话，这时我们把 n 级台阶时的跳法看成 n 的函数，记为$ f(n) $,第一次跳的时候有 n 种不同的选择：若是第一次跳一级，此时跳法的数目等于后面剩下的 n-1 级台阶的跳法数目，即为$ f(n-1) $,若是第一次跳 m(m<n)级，此时跳法的数目等于后面剩下的 n-m 级台阶的跳法数目，即为$ f(n-m) $,若是第一次跳 n 级，此时跳法的数目等于 1.所以 $ f(n) = f(n-1) + f(n-2) + … + f(n-m) + … + f(2) + f(1) + 1 $
因此$ f(n - 1) = f(n-2) + … + f(n-m) + … + f(2) + f(1) + 1 $
两式相减得到 $ f(n) = 2 * f(n-1) $
因此可以得到下面的结果

$$
\begin{aligned}
f(n) &= f(n-1) + f(n-2) + … + f(n-m) + … + f(2) + f(1) + 1 \
&= 1 + f(1) + f(2) + … + f(n-m) + … + f(n-2) + f(n-1) \
&= 1 + f(1) + 2*f(1) + … + 2^{n-m-1} * f(1) + … 2^{n-3} * f(1) + 2^{n-2} * f(1) \
&= 1 + 1 + 21 + … + 2^{n-m-1} + … 2^{n-3} + 2^{n-2} \
&= 2^{n-1}
\end{aligned}
$$

答案

若把条件修改成一次可以跳一级，也可以跳 2 级…也可以跳上 n 级呢，则$ f(n) = 2^{n-1}$

重构臃肿的APP Delegate（译）

Posted on 2018-08-24 In 重构

原文地址
APP Delegate 将你的 APP 和系统连接起来，通常被认为是一个 iOS 项目的核心。然而普遍的趋势是，它随着项目的发展而不断的变大，逐渐的增加新的特性和功能，开始这和那的调用并最终变成意大利面条式的代码

在 app delegate 里修改任何东西的代价都是昂贵的，因为它将会影响你的整个 APP。毫无疑问的，对于一个健康的 iOS 项目来说保持保持 APP Delegate 的简洁是至关重要的

在本文中，让我们来看一下如何使用不同的方法使 app delegate 能够简洁，可重用和可测试的

问题描述

app delegate 是你 app 的根对象，他能确保你的 app 能够正确的和系统和其他 app 进行正确的交互。app delegate 通常也会承担很多职责，这让它变得难以修改，扩展和测试

甚至Apple也鼓励你让你的 AppDelegate 至少承担起三个职责
（1、启动你的 APP;2、管理应用的状态;3、响应一些通知和事件（例如推送相关，与其他 app 交互相关…））

通过调查几十个最受欢迎的开源 iOS APP，我写了一个经常写在 APPdelegate 里职责列表，我相信每个人都写过类似的代码或者碰巧正在维护一个类似的项目

初始化第三方库
初始化 Core Data 并管理数据迁移
为单元测试和 UI 测试配置应用的状态
管理UserDefaults初始化首次加载的标志，保存和加载数据
处理闪屏页
管理推送，获取权限，存储 token，处理自定义事件，将通知广播到应用的其他地方
配置UIAppearance
管理 app 的角标数
管理后台任务
管理 UI 堆栈配置，初始化控制器，选择根控制器
播放音频
开启 debug 日志
管理设备的方向
遵循各种协议，尤其是第三方的协议
弹出一些提示框
…

像这样的臃肿的 APPdelegate 明显属于意大利面条式代码的定义，显然的，支持、扩展、测试这样的代码是非常困难和容易出错的，例如，查看 Telegram’s AppDelegate’s的源代码让我感到非常恐惧

让我们称为这样大的类叫做 Massive App Delegates，就像我们把类似的 ViewController 叫做 Massive View Controller 一样。

解决方案

在我们了解到 Massive App Delegates 的问题非常重要之后，让我们看看可能的解决方案。

每个方案必须满足一下标准

遵循单一职责原则
易扩展的
易测试的

方案 1: 命令设计模式

命令模式是描述对象被称作命令相当于是一个简单的方法或者事件。因为对象封装了触发自身所需的所有参数，因此命令的调用者不知道该命令做了什么以及响应者是谁

可以为 APPdelegate 的每一个职责定义一个命令，这个命令的名字有他们自己指定

protocol Command {
    func execute()
}

struct InitializeThirdPartiesCommand: Command {
    func execute() {
        // Third parties are initialized here
    }
}

struct InitialViewControllerCommand: Command {
    let keyWindow: UIWindow

    func execute() {
        // Pick root view controller here
        keyWindow.rootViewController = UIViewController()
    }
}

struct InitializeAppearanceCommand: Command {
    func execute() {
        // Setup UIAppearance
    }
}

struct RegisterToRemoteNotificationsCommand: Command {
    func execute() {
        // Register for remote notifications here
    }
}

然后我们定义StartupCommandsBuilder来封装如何创建命令的详细信息。APPdelegate 调用这个 builder 去初始化命令并执行这些命令

// MARK: - Builder
final class StartupCommandsBuilder {
    private var window: UIWindow!

    func setKeyWindow(_ window: UIWindow) -> StartupCommandsBuilder {
        self.window = window
        return self
    }

    func build() -> [Command] {
        return [
            InitializeThirdPartiesCommand(),
            InitialViewControllerCommand(keyWindow: window),
            InitializeAppearanceCommand(),
            RegisterToRemoteNotificationsCommand()
        ]
    }
}

// MARK: - App Delegate
@UIApplicationMain
class AppDelegate: UIResponder, UIApplicationDelegate {
    var window: UIWindow?

    func application(_ application: UIApplication, didFinishLaunchingWithOptions launchOptions: [UIApplicationLaunchOptionsKey: Any]?) -> Bool {
        StartupCommandsBuilder()
            .setKeyWindow(window!)
            .build()
            .forEach { $0.execute() }

        return true
    }
}

如果 APPdelegate 需要添加新的职责，则可以创建新的命令，然后把命令添加到 builder 里去而无需去改变 APPdelegate

我们的解决方案满足定义的标准

每个命令都有单一的职责
无需更改 APPdelegate 就可以很容易的添加新的命令
每个命令可以很容易的被单独测试

方案 2: 组合设计模式

组合模式允许你讲对象组合成树形结构来表现‘整体/部分’层次结构，一个很明显的例子就是 iOS 里的 UIView 以及它的 subviews

这个想法主要是有一个组装类和叶子类，每个叶子类负责一个职责，而组装类负责调用所有叶子类的方法


typealias AppDelegateType = UIResponder & UIApplicationDelegate

class CompositeAppDelegate: AppDelegateType {
    private let appDelegates: [AppDelegateType]

    init(appDelegates: [AppDelegateType]) {
        self.appDelegates = appDelegates
    }

    func application(_ application: UIApplication, didFinishLaunchingWithOptions launchOptions: [UIApplicationLaunchOptionsKey: Any]?) -> Bool {
        appDelegates.forEach { _ = $0.application?(application, didFinishLaunchingWithOptions: launchOptions) }
        return true
    }

    func application(_ application: UIApplication, didRegisterForRemoteNotificationsWithDeviceToken deviceToken: Data) {
        appDelegates.forEach { _ = $0.application?(application, didRegisterForRemoteNotificationsWithDeviceToken: deviceToken) }
    }
}

接下来，实现执行具体职责的叶子类

class PushNotificationsAppDelegate: AppDelegateType {
    func application(_ application: UIApplication, didRegisterForRemoteNotificationsWithDeviceToken deviceToken: Data) {
        // Registered successfully
    }
}

class StartupConfiguratorAppDelegate: AppDelegateType {
    func application(_ application: UIApplication, didFinishLaunchingWithOptions launchOptions: [UIApplicationLaunchOptionsKey: Any]?) -> Bool {
        // Perform startup configurations, e.g. build UI stack, setup UIApperance
        return true
    }
}

class ThirdPartiesConfiguratorAppDelegate: AppDelegateType {
    func application(_ application: UIApplication, didFinishLaunchingWithOptions launchOptions: [UIApplicationLaunchOptionsKey: Any]?) -> Bool {
        // Setup third parties
        return true
    }
}

我们定义AppDelegateFactory来封装创建的逻辑，在 APPdelegate 通过工厂方法创建组装类，然后通过他去调用所有的方法

enum AppDelegateFactory {
    static func makeDefault() -> AppDelegateType {
        return CompositeAppDelegate(appDelegates: [PushNotificationsAppDelegate(), StartupConfiguratorAppDelegate(), ThirdPartiesConfiguratorAppDelegate()])
    }
}

@UIApplicationMain
class AppDelegate: UIResponder, UIApplicationDelegate {

    var window: UIWindow?
    let appDelegate = AppDelegateFactory.makeDefault()

    func application(_ application: UIApplication, didFinishLaunchingWithOptions launchOptions: [UIApplicationLaunchOptionsKey: Any]?) -> Bool {
        _ = appDelegate.application?(application, didFinishLaunchingWithOptions: launchOptions)
        return true
    }

    func application(_ application: UIApplication, didRegisterForRemoteNotificationsWithDeviceToken deviceToken: Data) {
        appDelegate.application?(application, didRegisterForRemoteNotificationsWithDeviceToken: deviceToken)
    }
}

他满足我们在开始时提出的所有要求

每个叶子类都有一个单一职责
很容易添加一个叶子类,而无需改变 Appdelgate 的内容
每个叶子类能够容易的被单独测试

方案 3: 中介者设计模式

中介者模式封装了一系列对象的相互作用的方式，使得这些对象不必相互明显作用。从而使它们可以松散耦合。当某些对象之间的作用发生改变时，不会立即影响其他的一些对象之间的作用。保证这些作用可以彼此独立的变化。

如果您想了解有关此模式的更多信息，我建议您查看Mediator Pattern Case Study。

让我们定义AppLifecycleMediator将UIApplication的生命周期通知底下的监听者，这些监听者必须遵循AppLifecycleListener协议，如果需要监听者要能扩展新的方法

// MARK: - AppLifecycleListener
protocol AppLifecycleListener {
    func onAppWillEnterForeground()
    func onAppDidEnterBackground()
    func onAppDidFinishLaunching()
}

// MARK: - Mediator
class AppLifecycleMediator: NSObject {
    private let listeners: [AppLifecycleListener]

    init(listeners: [AppLifecycleListener]) {
        self.listeners = listeners
        super.init()
        subscribe()
    }

    deinit {
        NotificationCenter.default.removeObserver(self)
    }

    private func subscribe() {
        NotificationCenter.default.addObserver(self, selector: #selector(onAppWillEnterForeground), name: .UIApplicationWillEnterForeground, object: nil)
        NotificationCenter.default.addObserver(self, selector: #selector(onAppDidEnterBackground), name: .UIApplicationDidEnterBackground, object: nil)
        NotificationCenter.default.addObserver(self, selector: #selector(onAppDidFinishLaunching), name: .UIApplicationDidFinishLaunching, object: nil)
    }

    @objc private func onAppWillEnterForeground() {
        listeners.forEach { $0.onAppWillEnterForeground() }
    }

    @objc private func onAppDidEnterBackground() {
        listeners.forEach { $0.onAppDidEnterBackground() }
    }

    @objc private func onAppDidFinishLaunching() {
        listeners.forEach { $0.onAppDidFinishLaunching() }
    }
}

extension AppLifecycleMediator {
    static func makeDefaultMediator() -> AppLifecycleMediator {
        let listener1 = ...
        let listener2 = ...
        return AppLifecycleMediator(listeners: [listener1, listener2])
    }
}

现在它只需要 1 行代码就能加入到 AppDelegate 中

@UIApplicationMain
class AppDelegate: UIResponder, UIApplicationDelegate {
    var window: UIWindow?

    let mediator = AppLifecycleMediator.makeDefaultMediator()

    func application(_ application: UIApplication, didFinishLaunchingWithOptions launchOptions: [UIApplicationLaunchOptionsKey: Any]?) -> Bool {
        return true
    }
}

这个中介者自动订阅了所有的事件。AppDelegate 仅仅需要初始化它一次，就能让他正常工作。

他满足我们在开始时提出的所有要求

每个监听者都有一个单一职责
很容易添加一个监听者,而无需改变 Appdelgate 的内容
每个监听者以及中介者能够容易的被单独测试

总结

我们一致认为大多数的 AppDelegates 都不合理，过于复杂，职责太多，我们称这样的类为 Massive App Delegates。

通过使用一些软件的设计模式，Massive App Delegates 可以被分割成多个类，每个类都有单一职责，这使得它们能够被单独的测试

这样的代码很容易更改，因为他不会在你的 app 中产生一连串的更改。它非常灵活，可以在将来提取或重用

UIScrollView代理的调用时机

Posted on 2018-08-23 In iOS

func scrollViewDidScroll(_ scrollView: UIScrollView)
scrollView 滚动时调用，在滚动过程中会多次调用
func scrollViewWillBeginDragging(_ scrollView: UIScrollView)
将要开始拖拽时调用
func scrollViewWillEndDragging(_ scrollView: UIScrollView, withVelocity velocity: CGPoint, targetContentOffset: UnsafeMutablePointer<CGPoint>)
将要停止拖拽时 velocity:加速度向左滑动 x 为负值，否则为正值向上滚动为 y 为负值否则为正值；targetContentOffset:滚动停止时的 ContentOffset
func scrollViewDidEndDragging(_ scrollView: UIScrollView, willDecelerate decelerate: Bool)
停止拖拽时调用， willDecelerate:停止拖拽时是否要减速，若值为 false 表示已经停止减速，也就意味着滚动已停止，此时不会调用 scrollViewWillBeginDecelerating 和 scrollViewDidEndDecelerating;若值为 true，则代表 scrollView 正在减速滚动
func scrollViewWillBeginDecelerating(_ scrollView: UIScrollView)
开始减速的时候调用(也就是松开手指时)，在拖拽滚动的时候，如果松手时已经停止滚动则不会调用
func scrollViewDidEndDecelerating(_ scrollView: UIScrollView)
停止减速的时候调用（也就是停止滚动的时候调用），在拖拽滚动的时候，如果松手时已经停止滚动则不会调用
func scrollViewDidEndScrollingAnimation(_ scrollView: UIScrollView)
当调用 setContentOffset(_ contentOffset: CGPoint, animated: Bool)/scrollRectToVisible(_ rect: CGRect, animated: Bool)API 并且 animated 参数为 true 时,会在 scrollView 滚动结束时调用。若是 UITableView 或者 UICollectionView,调用 scrollToRow 也和上面一样
func viewForZooming(in scrollView: UIScrollView) -> UIView?
放回要缩放的 view，此 view 必须是 scrollView 的 subview
func scrollViewDidZoom(_ scrollView: UIScrollView)
当 scrollView 缩放时调用,在缩放过程中会被多次调用
func scrollViewWillBeginZooming(_ scrollView: UIScrollView, with view: UIView?)
scrollView 开始缩放时调用
func scrollViewDidEndZooming(_ scrollView: UIScrollView, with view: UIView?, atScale scale: CGFloat)
scrollView 结束缩放时调用

func scrollViewShouldScrollToTop(_ scrollView: UIScrollView) -> Bool
是否允许点击 scrollview 的头部，让其滚动到最上面,若不实现此代理，则默认为 true

func scrollViewDidScrollToTop(_ scrollView: UIScrollView)
当滚动到最上面时调用

1	extension Int {
2	var binaryOneNumber : Int {
3	var tmp = self
4	var count = 0
5	while tmp != 0 {
6	if tmp & 1 == 1{
7	count += 1
8	}
9	tmp = tmp >> 1
10	}
11	return count
12	}
13	}
14
15	print(0.binaryOneNumber) //输出0
16	print(9.binaryOneNumber) //输出2
17	print((-9).binaryOneNumber)//死循环

1	func sumTeminator(number:UInt) -> UInt {
2	return 0
3	}
4	func sum(number:UInt) -> UInt {
5	let funcs = [sumTeminator,sum]
6	let isTeminator = Bool(truncating: NSNumber(value: number - 1))
7	let funcIndex = Int(truncating: NSNumber(value: isTeminator))
8	let sumFunc = funcs[funcIndex]
9	return number + sumFunc(number - 1)
10	}
11	print(sum(number: 100))

1	func sum1(number:UInt) -> UInt {
2	let array = Array(stride(from: 0, to: number + 1, by: 1))
3	let sum = (array as NSArray).value(forKeyPath: "@sum.integerValue") as! UInt
4	return sum
5	}
6	print(sum1(number: 100))

1	//用来表示每个格子的坐标
2	typealias Coordinate = (row:Int,column:Int)
3	struct Grid {
4	let row : Int //行数
5	let column : Int //列数
6	//原点坐标
7	var originCoordinate : Coordinate {
8	return (row:0,column:0)
9	}
10	//在方格内指定坐标的上面的格子，若上面已没有格子，则返回nil
11	func above(coor:Coordinate) -> Coordinate? {
12	if coor.row >= 0 && coor.row < row - 1 && coor.column >= 0 && coor.column < column{
13	return (row:coor.row + 1,column:coor.column)
14	}
15	return nil
16	}
17	//在方格内指定坐标的下面的格子，若下面已没有格子，则返回nil
18	func below(coor:Coordinate) -> Coordinate? {
19	if coor.row > 0 && coor.row < row && coor.column >= 0 && coor.column < column{
20	return (row:coor.row - 1,column:coor.column)
21	}
22	return nil
23	}
24	//在方格内指定坐标的左面的格子，若左面已没有格子，则返回nil
25	func left(coor:Coordinate) -> Coordinate? {
26	if coor.row >= 0 && coor.row < row && coor.column > 0 && coor.column < column{
27	return (row:coor.row,column:coor.column - 1)
28	}
29	return nil
30	}
31	//在方格内指定坐标的右面的格子，若右面已没有格子，则返回nil
32	func right(coor:Coordinate) -> Coordinate? {
33	if coor.row >= 0 && coor.row < row && coor.column >= 0 && coor.column < column - 1{
34	return (row:coor.row,column:coor.column + 1)
35	}
36	return nil
37	}
38	}

1	struct Robot {
2	let k : Int
3	let grid : Grid //格子
4
5	init(k :Int, grid: Grid) {
6	self.k = k
7	self.grid = grid
8	}
9
10	//对外暴露的方法，做了一些数据的初始化和边界的判断。内部调用了private func movingCount(coor:Coordinate? , visited:inout [Bool]) -> Int
11	func movingCount() -> Int {
12	guard k >= 0, grid.column > 0, grid.row > 0 else { return 0 }
13	var visited = Array(repeating: false, count: grid.row * grid.column)
14	let count = movingCount(coor: grid.originCoordinate , visited : &visited)
15	return count
16	}
17
18	//实现上面的思路
19	private func movingCount(coor:Coordinate? , visited:inout [Bool]) -> Int {
20	if let coor = coor , isVaild(coor: coor, visited: visited) {
21	visited[coor.row * grid.column + coor.column] = true
22	return 1 + movingCount(coor:grid.above(coor: coor), visited: &visited)
23	+ movingCount(coor:grid.right(coor: coor), visited: &visited)
24	}
25	return 0
26	}
27
28	//用来判断是否能进入到此格子
29	private func isVaild(coor:Coordinate , visited : [Bool]) -> Bool {
30	return visited[coor.row * grid.column + coor.column] == false && (digitsSum(number: coor.row) + digitsSum(number: coor.column) <= k)
31	}
32
33	//求一个数字的位数之和
34	private func digitsSum(number:Int) -> Int {
35	var sum = 0
36	var topDigit = number
37	while topDigit > 0 {
38	sum += topDigit % 10
39	topDigit = topDigit / 10
40	}
41	return sum
42	}
43	}

1	let grid = Grid(row: 100, column: 100)
2	for i in -2...30 {
3	let robot = Robot(k: i, grid : grid)
4	let count = robot.movingCount()
5	print("\(i)===\(count)")
6	}

1	final public class LinkedList<E> {
2	private var size = 0
3	private var firstNode:Node<E>?
4	private var lastNode:Node<E>?
5
6	/// 初始化一个空list
7	public init() { }
8
9	/// 通过序列初始化一个list
10	public init<S>(_ s: S) where Element == S.Element, S : Sequence {
11	for (index,item) in s.enumerated() {
12	let newNode = Node(element: item)
13	if index == 0 {
14	firstNode = newNode
15	lastNode = newNode
16	}else {
17	newNode.prev = lastNode
18	lastNode?.next = newNode
19	lastNode = newNode
20	}
21	size += 1
22	}
23	}
24	}
25	/// 节点
26	fileprivate class Node<Element> {
27	/// 节点元素的值
28	var item:Element
29	/// 下一个节点
30	var next:Node<Element>?
31	/// 上一个节点
32	var prev:Node<Element>?
33	init(element:Element, next:Node<Element>? = nil, prev:Node<Element>? = nil) {
34	self.item = element
35	self.next = next
36	self.prev = prev
37	}
38	}

1	// MARK: - private
2	extension LinkedList {
3	/// 通过下标找到对应的节点
4	private func node(at index:Int) -> Node<E> {
5	//如果下标位置无效，则直接报错
6	if !indexIsVaild(index) {
7	fatalError("Index out of range:\(index) not belong 0..<\(size)")
8	}
9	//如果节点在前一半顺序查找，否则逆序查找
10	if index < (size >> 1) {
11	var node = firstNode
12	for _ in 0..<index {
13	node = node?.next
14	}
15	return node!
16	}else {
17	var node = lastNode
18	for _ in stride(from: size - 1, to: index, by: -1) {
19	node = node?.prev
20	}
21	return node!
22	}
23	}
24	/// 下标是否是有效的
25	private func indexIsVaild(_ index:Int) -> Bool {
26	return index >= 0 && index < size
27	}
28	}

1	// MARK: - 添加元素
2	extension LinkedList {
3	/// 追加单个元素
4	public func append(_ newElement: E) {
5	let newNode = Node(element: newElement, next: nil, prev: lastNode)
6	if lastNode == nil {
7	firstNode = newNode
8	}
9	lastNode?.next = newNode
10	lastNode = newNode
11	size += 1
12	}
13
14	/// 追加多个元素
15	public func append<S>(contentsOf newElements: S) where S : Sequence, E == S.Element {
16	for item in newElements {
17	append(item)
18	}
19	}
20
21	/// 插入单个元素
22	public func insert(_ newElement: E, at i: Int){
23	let newNode = Node(element: newElement, next: nil, prev: nil)
24	if i == 0 && size == 0{
25	firstNode = newNode
26	lastNode = newNode
27	}else {
28	let insertNode = node(at: i)
29	newNode.next = insertNode
30	insertNode.prev = newNode
31	newNode.prev = insertNode.prev
32	insertNode.prev?.next = newNode
33	if i == 0 {
34	firstNode = newNode
35	}
36	}
37	size += 1
38	}
39
40	/// 插入多个元素
41	public func insert<S>(contentsOf newElements: S, at i: Int) where S : Collection, E == S.Element {
42	if i == 0 && size == 0 {
43	append(contentsOf: newElements)
44	}else {
45	let insertNode = node(at: i)
46	var firstNode:Node<E>?
47	var lastNode:Node<E>?
48	for (index,item) in newElements.enumerated() {
49	let newNode = Node(element: item, next: nil, prev: nil)
50	if index == 0 {
51	firstNode = newNode
52	lastNode = newNode
53	}else {
54	newNode.prev = lastNode
55	lastNode?.next = newNode
56	lastNode = newNode
57	}
58	size += 1
59	}
60	firstNode?.prev = insertNode.prev
61	lastNode?.next = insertNode
62	insertNode.prev?.next = firstNode
63	insertNode.prev = lastNode
64	if i == 0 {
65	self.firstNode = firstNode
66	}
67	}
68	}
69	}

1	// MARK: - 删除元素
2	extension LinkedList {
3	/// 删除指定位置的元素
4	@discardableResult
5	public func remove(at position: Int) -> E {
6	if (position >= 0 && position < size){
7	let removeNode = node(at: position)
8	removeNode.prev?.next = removeNode.next
9	removeNode.next?.prev = removeNode.prev
10	if (position == 0) {
11	firstNode = firstNode.next
12	}else if (position == size - 1){
13	lastNode = lastNode.prev
14	}
15	size -= 1
16	return removeNode.item
17	}else {
18	return nil
19	}
20	}
21	/// 删除第一个元素
22	@discardableResult
23	public func removefirstNode() -> E? {
24	if ()
25	return firstNode == nil ? nil : remove(at: 0)
26	}
27	/// 删除最后一个元素
28	@discardableResult
29	public func removelastNode() -> E? {
30	return lastNode == nil ? nil : remove(at: size - 1)
31	}
32	/// 删除所有元素
33	public func removeAll() {
34	var next = firstNode
35	while next != nil {
36	let tmp = next
37	next?.next = nil
38	next?.prev = nil
39	next = tmp
40	}
41	firstNode = nil
42	lastNode = nil
43	size = 0
44	}
45	}

1	// MARK: - 实现Collection协议
2	extension LinkedList : Collection {
3	/// 开始位置
4	public var startIndex: Int { return 0 }
5	/// 结束位置
6	public var endIndex: Int { return size }
7	/// 给定位置后面的索引值
8	public func index(after i: Int) -> Int {
9	return i + 1
10	}
11	/// 返回指定的迭代器
12	public func makeIterator() -> Iterator {
13	return Iterator(self)
14	}
15	/// 通过下标存取元素
16	public subscript(position: Int) -> E {
17	get {
18	return node(at: position).item
19	}
20	set {
21	node(at: position).item = newValue
22	}
23	}
24	}
25
26	// MARK: - 迭代器
27	extension LinkedList {
28	public struct Iterator: IteratorProtocol {
29	let list: LinkedList
30	var index: Int
31	private var nextNode:Node<E>?
32	init(_ list: LinkedList) {
33	self.list = list
34	self.index = 0
35	self.nextNode = list.firstNode
36	}
37	/// 获取下一个元素，在for in里若返回nil，则停止循环
38	public mutating func next() -> E? {
39	let item = nextNode?.item
40	nextNode = nextNode?.next
41	return item
42	}
43	}
44	}

1	// MARK: - 通过条件查找位置
2	extension LinkedList {
3	/// 顺序查找
4	public func firstIndex(where predicate: (E) throws -> Bool) rethrows -> Int? {
5	for (index,item) in self.enumerated() {
6	if try predicate(item) {
7	return index
8	}
9	}
10	return nil
11	}
12
13	/// 倒序查找
14	public func lastIndex(where predicate: (E) throws -> Bool) rethrows -> Int? {
15	var prev = lastNode
16	var currentIndex = size - 1
17	while prev != nil {
18	if try predicate(prev!.item) {
19	return currentIndex
20	}
21	currentIndex -= 1
22	prev = prev?.prev
23	}
24	return nil
25	}
26
27	/// 是否包含
28	public func contains(where predicate: (E) throws -> Bool) rethrows -> Bool {
29	for item in self{
30	if try predicate(item) {
31	return true
32	}
33	}
34	return false
35	}
36	}
37	// MARK: - 通过元素查找位置
38	extension LinkedList where E : Equatable {
39	public func firstIndex(of element: E) -> Int? {
40	return firstIndex { (item) -> Bool in
41	return item == element
42	}
43	}
44	public func lastIndex(of element: E) -> Int? {
45	return lastIndex(where: { (item) -> Bool in
46	return item == element
47	})
48	}
49
50	public func contains(_ element: E) -> Bool {
51	return contains(where: { (item) -> Bool in
52	return item == element
53	})
54	}
55	}

1	extension LinkedList : ExpressibleByArrayLiteral {
2	public convenience init(arrayLiteral elements: E...) {
3	//这里是调用通过序列初始化链表
4	self.init(elements)
5	}
6	}

1	extension LinkedList {
2	public func toArray() -> [E] {
3	return self.map({ (item) -> E in
4	return item
5	})
6	}
7	}

1	// MARK: - Copy
2	extension LinkedList {
3	public func copy() -> LinkedList {
4	let copyList = LinkedList()
5	copyList.size = self.size
6	if let firstNode = firstNode {
7	copyList.firstNode = Node(element: firstNode.item, next: nil, prev: nil)
8	copyList.lastNode = copyList.firstNode
9	}
10	var nextNode = firstNode?.next
11	while nextNode != nil {
12	let newNode = Node(element: nextNode!.item)
13	copyList.lastNode?.next = newNode
14	newNode.prev = copyList.lastNode
15	copyList.lastNode = newNode
16	nextNode = nextNode?.next
17	}
18	return copyList
19	}
20	}

1	extension LinkedList : CustomDebugStringConvertible {
2	public var debugDescription: String {
3	var desc = ""
4	if size > 0 {
5	for item in self.dropLast() {
6	desc += "\(item)-->"
7	}
8	desc += "\(lastNode!.item)"
9	}
10	return desc
11	}
12	}

1	class Person {
2	var name : String
3	var age :Int
4	init(name: String, age: Int) {
5	self.name = name
6	self.age = age
7	}
8	required convenience init(name: String) {
9	self.init(name: name, age: 18)
10	}
11	}
12	class Student: Person {
13	var grades: [String] = []
14	//把父类的required convenience重写成了required designated
15	required init(name: String) {
16	super.init(name: name, age: 18)
17	}
18	}
19	//编译不通过错误信息：Extra argument 'age' in call
20	//说明没有继承父类其他的初始化方法
21	let student = Student(name: "lkk", age: 22)

1	func minInOrder<T:Comparable>(rotationArray:Array<T>) -> T? {
2	var minItem = rotationArray.first
3	for item in rotationArray {
4	if minItem! > item {
5	minItem = item
6	}
7	}
8	return minItem
9	}

1	func min<T:Comparable>(rotationArray:Array<T>) -> T? {
2	if rotationArray.count < 1 {
3	return nil
4	}
5	var aheadIndex = 0
6	var tailIndex = rotationArray.count - 1
7	//先让中间指向头部，是因为如果头部元素如果小于尾部元素，则证明旋转了0个元素，此时头部元素等于最小值
8	var middleIndex = aheadIndex
9	while rotationArray[aheadIndex] >= rotationArray[tailIndex]{
10	if(tailIndex - aheadIndex == 1) {
11	middleIndex = tailIndex
12	break
13	}
14	//此处不要写成(aheadIndex + tailIndex) / 2，因为这么写，当数组元素比较多时，可以会造成溢出问题
15	middleIndex = aheadIndex + (tailIndex - aheadIndex) / 2
16	if rotationArray[aheadIndex] == rotationArray[tailIndex] && rotationArray[aheadIndex] == rotationArray[middleIndex] {
17	//把P1到P2之间的元素，重新生成一个新数组，然后调用方案一的写法
18	return minInOrder(rotationArray: Array(rotationArray[aheadIndex...tailIndex]))
19	}
20	if rotationArray[middleIndex] >= rotationArray[aheadIndex] {
21	aheadIndex = middleIndex
22	}else if rotationArray[middleIndex] <= rotationArray[tailIndex] {
23	tailIndex = middleIndex
24	}
25	}
26	return rotationArray[middleIndex]
27	}

1	mermaid
2	graph TB
3	c1-->a2
4	subgraph one
5	a1-->a2
6	end
7	subgraph two
8	b1-->b2
9	end
10	subgraph three
11	c1-->c2
12	end

题目：

代码实现

代码实现

题目

思路

代码实现（Swift）

Test

1. 什么是双向链表

2. 集合有哪些功能

3. 文章中要实现的功能

4.未实现的功能

5. 如何实现

定义链表结构如下

如何查找指定位置的元素

如何追加和插入元素

删除元素

实现 Collection 协议

查找满足特定条件的元素的位置和查找元素的位置

实现字面量赋值

把链表转成数组

实现 copy

实现自定义打印

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

方案一

方案二

方案一代码（swift）

方案二代码 （swift）

如何在 markdown 中使用 mermaid

基本图形

示例

节点之间的连接

示例

子流程图

自定义样式

demo

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

答题思路

数学函数表示如下

code

若把条件修改成一次可以跳一级，也可以跳 2 级…也可以跳上 n 级呢？

思路

答案

问题描述

解决方案

方案 1: 命令设计模式

方案 2: 组合设计模式

方案 3: 中介者设计模式

总结

方案二代码（swift）

1	mermaid
2	graph LR
3	id1(Start)-->id2(Stop)
4	style id1 fill:#f9f,stroke:#333,stroke-width:4px,fill-opacity:0.5
5	style id2 fill:#ccf,stroke:#f66,stroke-width:2px,stroke-dasharray: 10,5

1	mermaid
2	graph LR
3	start[开始] --> input[输入A,B,C]
4	input --> conditionA{A是否大于B}
5	conditionA -- YES --> conditionC{A是否大于C}
6	conditionA -- NO --> conditionB{B是否大于C}
7	conditionC -- YES --> printA[输出A]
8	conditionC -- NO --> printC[输出C]
9	conditionB -- YES --> printB[输出B]
10	conditionB -- NO --> printC[输出C]
11	printA --> stop[结束]
12	printC --> stop
13	printB --> stop

1	func fibonacci(number: UInt64) -> UInt64? {
2	if number == 1 {
3	return 1
4	}else if number == 2 {
5	return 1
6	}
7	var fibNMinusOne:UInt64 = 1
8	var fibNMinusTwo:UInt64 = 1
9	var fibN:UInt64 = 0
10	for _ in 3...number {
11	fibN = fibNMinusOne &+ fibNMinusTwo
12	if(fibN < fibNMinusOne) {
13	return nil
14	}
15	fibNMinusTwo = fibNMinusOne
16	fibNMinusOne = fibN
17	}
18	return fibN
19	}

1	protocol Command {
2	func execute()
3	}
4
5	struct InitializeThirdPartiesCommand: Command {
6	func execute() {
7	// Third parties are initialized here
8	}
9	}
10
11	struct InitialViewControllerCommand: Command {
12	let keyWindow: UIWindow
13
14	func execute() {
15	// Pick root view controller here
16	keyWindow.rootViewController = UIViewController()
17	}
18	}
19
20	struct InitializeAppearanceCommand: Command {
21	func execute() {
22	// Setup UIAppearance
23	}
24	}
25
26	struct RegisterToRemoteNotificationsCommand: Command {
27	func execute() {
28	// Register for remote notifications here
29	}
30	}

1	// MARK: - Builder
2	final class StartupCommandsBuilder {
3	private var window: UIWindow!
4
5	func setKeyWindow(_ window: UIWindow) -> StartupCommandsBuilder {
6	self.window = window
7	return self
8	}
9
10	func build() -> [Command] {
11	return [
12	InitializeThirdPartiesCommand(),
13	InitialViewControllerCommand(keyWindow: window),
14	InitializeAppearanceCommand(),
15	RegisterToRemoteNotificationsCommand()
16	]
17	}
18	}
19
20	// MARK: - App Delegate
21	@UIApplicationMain
22	class AppDelegate: UIResponder, UIApplicationDelegate {
23	var window: UIWindow?
24
25	func application(_ application: UIApplication, didFinishLaunchingWithOptions launchOptions: [UIApplicationLaunchOptionsKey: Any]?) -> Bool {
26	StartupCommandsBuilder()
27	.setKeyWindow(window!)
28	.build()
29	.forEach { $0.execute() }
30
31	return true
32	}
33	}

1
2	typealias AppDelegateType = UIResponder & UIApplicationDelegate
3
4	class CompositeAppDelegate: AppDelegateType {
5	private let appDelegates: [AppDelegateType]
6
7	init(appDelegates: [AppDelegateType]) {
8	self.appDelegates = appDelegates
9	}
10
11	func application(_ application: UIApplication, didFinishLaunchingWithOptions launchOptions: [UIApplicationLaunchOptionsKey: Any]?) -> Bool {
12	appDelegates.forEach { _ = $0.application?(application, didFinishLaunchingWithOptions: launchOptions) }
13	return true
14	}
15
16	func application(_ application: UIApplication, didRegisterForRemoteNotificationsWithDeviceToken deviceToken: Data) {
17	appDelegates.forEach { _ = $0.application?(application, didRegisterForRemoteNotificationsWithDeviceToken: deviceToken) }
18	}
19	}

1	class PushNotificationsAppDelegate: AppDelegateType {
2	func application(_ application: UIApplication, didRegisterForRemoteNotificationsWithDeviceToken deviceToken: Data) {
3	// Registered successfully
4	}
5	}
6
7	class StartupConfiguratorAppDelegate: AppDelegateType {
8	func application(_ application: UIApplication, didFinishLaunchingWithOptions launchOptions: [UIApplicationLaunchOptionsKey: Any]?) -> Bool {
9	// Perform startup configurations, e.g. build UI stack, setup UIApperance
10	return true
11	}
12	}
13
14	class ThirdPartiesConfiguratorAppDelegate: AppDelegateType {
15	func application(_ application: UIApplication, didFinishLaunchingWithOptions launchOptions: [UIApplicationLaunchOptionsKey: Any]?) -> Bool {
16	// Setup third parties
17	return true
18	}
19	}

1	enum AppDelegateFactory {
2	static func makeDefault() -> AppDelegateType {
3	return CompositeAppDelegate(appDelegates: [PushNotificationsAppDelegate(), StartupConfiguratorAppDelegate(), ThirdPartiesConfiguratorAppDelegate()])
4	}
5	}
6
7	@UIApplicationMain
8	class AppDelegate: UIResponder, UIApplicationDelegate {
9
10	var window: UIWindow?
11	let appDelegate = AppDelegateFactory.makeDefault()
12
13	func application(_ application: UIApplication, didFinishLaunchingWithOptions launchOptions: [UIApplicationLaunchOptionsKey: Any]?) -> Bool {
14	_ = appDelegate.application?(application, didFinishLaunchingWithOptions: launchOptions)
15	return true
16	}
17
18	func application(_ application: UIApplication, didRegisterForRemoteNotificationsWithDeviceToken deviceToken: Data) {
19	appDelegate.application?(application, didRegisterForRemoteNotificationsWithDeviceToken: deviceToken)
20	}
21	}

1	// MARK: - AppLifecycleListener
2	protocol AppLifecycleListener {
3	func onAppWillEnterForeground()
4	func onAppDidEnterBackground()
5	func onAppDidFinishLaunching()
6	}
7
8	// MARK: - Mediator
9	class AppLifecycleMediator: NSObject {
10	private let listeners: [AppLifecycleListener]
11
12	init(listeners: [AppLifecycleListener]) {
13	self.listeners = listeners
14	super.init()
15	subscribe()
16	}
17
18	deinit {
19	NotificationCenter.default.removeObserver(self)
20	}
21
22	private func subscribe() {
23	NotificationCenter.default.addObserver(self, selector: #selector(onAppWillEnterForeground), name: .UIApplicationWillEnterForeground, object: nil)
24	NotificationCenter.default.addObserver(self, selector: #selector(onAppDidEnterBackground), name: .UIApplicationDidEnterBackground, object: nil)
25	NotificationCenter.default.addObserver(self, selector: #selector(onAppDidFinishLaunching), name: .UIApplicationDidFinishLaunching, object: nil)
26	}
27
28	@objc private func onAppWillEnterForeground() {
29	listeners.forEach { $0.onAppWillEnterForeground() }
30	}
31
32	@objc private func onAppDidEnterBackground() {
33	listeners.forEach { $0.onAppDidEnterBackground() }
34	}
35
36	@objc private func onAppDidFinishLaunching() {
37	listeners.forEach { $0.onAppDidFinishLaunching() }
38	}
39	}
40
41	extension AppLifecycleMediator {
42	static func makeDefaultMediator() -> AppLifecycleMediator {
43	let listener1 = ...
44	let listener2 = ...
45	return AppLifecycleMediator(listeners: [listener1, listener2])
46	}
47	}