问题由来

来新公司也大半年了，发现之前的工程实现的非常不合理，维护成本极高，内部吐槽严重，BUG 叠 BUG，修老 BUG 引入的新 BUG 层出不穷，质量堪忧。

Pros & Cons

拿到代码后简单的看了一下:

• 使用 MVC 模式，并且由于各种原因，说白了就是写的挫。将 MCV(Model-View-Controller) 写成了 MVC(Massive View Controller)
• View Controller 写的极为笨重，几乎流程都写在几个比较大的 View Controller 中。牵一发而动全身，能不出错么。
• 目前的时机比较不错，新项目要开始了，及得想办法复用之前的逻辑，又得写的没什么问题。
• 很久不写这种流程了，还是需要仔细的回归练习一下，而且还能练练 swift，何乐而不为呢

VIPER 结构简介

VIPER 是视图 (View)，交互器 (Interactor)，展示器 (Presenter)，实体 (Entity) 以及路由 (Routing) 的首字母缩写。这样根据逻辑结构的不同可以划分为不同的责任层。使得依赖更容易隔离，比如说数据库，也更容易单独测试，边界清晰。
他们的关系大概是这样的 如下图所示：

为什么要用 VIPER

互联网企业都要求快速迭代，要求周期短，质量高。如何快速的在满足需求的前提下下交付质量好的产品，是大家都想解决的问题。对于一个处于一线的程序员来讲，从根上推动整个流程的变化是不切实际的。比较稳妥且的办法是采用技术手段来提高自己的效率，降低出错的概率。
对于源源不断的需求，以及不断的需求变化。除了默默的问候这些 PM，不还是得一个字一个字的敲出来。做的不好，大家会怀疑你的能力。面子上挂不住。活那么多，身体抗不住，身为一个快乐的程序员，在减少秃头的情况下得想办法让自己轻松点嘛。

步入正题

• VIPER 的好处就是模块之前关系比较松散，模块划分清晰，几乎做到了彻底解耦。每个（VIPER）子模块都可以单独的测试，
• 避免掉了 MVC -> M(assive)VC 的情况，VC 里面几乎就是个接口调用，几乎就是完成业务流程的胶水代码，而且都是 Protocol 的接口，业务比较清晰。
• 数据模型的处理，单独的放到了 Interactor 内部，这一块对于其他模块几乎是透明。
• VC 彻底细化为View 和 Presenter，三者的交互可以参考 MVP 模式，不多说。
• Router 作为业务的入口和跳转的枢纽，将跳转逻辑也吃掉了。
• 最终 VIPER 化之后，代码量会变多、文件会变多，逻辑变得清晰可维护。
• 不同的 VIPER 模块 通信只有两个途径，一个是通过 ROUTER，另一个是通过 INTERACTOR

开始落地

设计图

• VIPER 模板
  每次手工新建五个文件着实比较蛋疼，那么使用 XCode 模板每次自动新建不是很爽。链接就是新建好的模板。方便省事，目前只有 Mac 版本，改吧改吧 iOS 版本也不是啥难事

• 以聊天页为例 VIPER 落地
  

1. 从图中可以看到该页面比较简单，聊天页面大概分两个部分，左边应该是 thread 列表，右边是 消息流。
2. 窗体的样式几乎都是自定义的。
3. 顶部存在多 TAB，方便切换不同的显示内容。
4. 由于是 IM，那就存在登陆和非登陆，因此需要目前两个 VIPER 模块。
5. 从设计来看，各种 UI 组件都需要自定义，因此需要提供一个 UI 基础组件库，给工程提供子弹。吃掉 UI 的内部细节。只要对外提供行为即可。

登陆 VIPER 结构

• 登陆需要简单的输入用户名和密码，然后呢对于登陆成功的状况，会有账户维护和消息同步。

• 设计有要求在登录页内部玩各种花活。因此目前沟通后，登录页划分为登陆输入页，和登陆行为页，两个页面的逻辑和流程不大一样。

• 登陆输入页的协议定义如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

// MARK: Wireframe - 这块 Wireframe 就是 ROUTER
protocol AZLoginMainWireframeProtocol: class {
}
// MARK: Presenter -
protocol AZLoginMainViewPresenterProtocol: class {
    // 目前只有注册的行为，因此定义好接口供 VC 使用
    func startRegistration()
}

// MARK: Interactor -
protocol AZLoginMainInteractorProtocol: class {
    var presenter: AZLoginMainViewPresenterProtocol? { get set }
    //给 PRESENTER 提供的接口，真正的注册行为是在 INTERACTOR 中发生的
    func startRegistration()
}

// MARK: View -
protocol AZLoginMainViewProtocol: class {
  var presenter: AZLoginMainViewPresenterProtocol? { get set }
}

• 登陆行为页

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

// MARK: Wireframe -
protocol AZLoginActionWireframeProtocol: class {
    //根据业务需要，这块有可能需要直接的显示到主界面
    func showMainWindow()
}
// MARK: Presenter -
protocol AZLoginActionPresenterProtocol: class {
    // 给 VC 提供的接口可以注册和忘记密码，并且在登陆成功后可以有接口给 INTERACTOR 调用(finish)
    func login(email: String?, password: String?)
    func finished(login error: AZError?)
    func forgetPassword()
}

// MARK: Interactor -
protocol AZLoginActionInteractorProtocol: class {
    var presenter: AZLoginActionPresenterProtocol? { get set }
    // 真正的接口，具体的行为是在 INTERACTOR 中发生的，
    func login(email: String?, password: String?)
    func forgetPassword()
}

// MARK: View -
protocol AZLoginActionViewProtocol: class {
    var presenter: AZLoginActionPresenterProtocol? { get set }
    // 更新 View 的接口
    func loginError(_ error: AZError)
    func closeWindow()
}

一个简单的功能，写了这么多是不是很蛋疼，明明只需要一个 VC 就可以搞定的事情，非得这么麻烦么？

其实在真正实现之后，发现除了文件多点以为，登陆的逻辑和流程非常清晰，真正地做到了代码自解释，不同结构之间通过接口来实现交互。将与其他模块无关的功能对外隐藏,而且真正的收益是在整个工程的逻辑和功能变得越来越复杂之后才体现出来。

聊天 VIPER

登陆成功后，界面会由登陆 VIPER 模块路由到主界面 VIPER，如下图，那么界面就可以正常的切换过来了

• 搭建几个重要 VIPER 子结构
  通过分析具体的业务流程和要完成的功能 不断地补充接口，篇幅问题，省略掉大部分细节，以切换 tab 为例。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

// MARK: Wireframe -
protocol AZMainWindowWireframeProtocol: class {
    //...
}
// MARK: Presenter -
protocol AZMainWindowPresenterProtocol: class {
    var router: AZMainWindowWireframeProtocol { get }
    //...
    func switchMainWindowTabContent(_ userInfo: [AnyHashable: Any])
    //...
}

// MARK: Interactor -
protocol AZMainWindowInteractorProtocol: class {
    var presenter: AZMainWindowPresenterProtocol? { get set }
    //...
    func swithMainWindowTab(_ tab: AZTitlebarTag)
    //...
}

// MARK: View -
protocol AZMainWindowViewProtocol: class {
    var presenter: AZMainWindowPresenterProtocol? { get set }
    //...
    func switchMainWindowTabContent(_ userInfo: [AnyHashable: Any])
    //...
}

随着功能的逐渐叠加，VIPER 中不同的子结构的代码增加都很平稳，不会出现某一个模块代码量指数级的增加。
从前任写完的第一个版本的 bug 叠 bug，到这个版本的内部备受好评，其实基础功能都一致，只不过是界面看上去有着巨大的差别。但是从结果来看维护成本和收益都很不错，但实际上改变的是整个项目的基础结构，开发流程，并且带动了大家往着更合理的方向前进 。
从这个过程中，内部总结出了，代码规范，提交规范，开发规范，这么看来，每个人都应该有着不少的收获.

题目

Find the Duplicated Number
Given an array nums containing n + 1 integers where each integer is between 1 and n (inclusive), prove that at least one duplicate number must exist. Assume that there is only one duplicate number, find the duplicate one.

Example 1:

1
2

Input: [1,3,4,2,2]
Output: 2

Example 2:

1
2

Input: [3,1,3,4,2]
Output: 3

Note:

You must not modify the array (assume the array is read only).
You must use only constant, O(1) extra space.
Your runtime complexity should be less than O(n2).
There is only one duplicate number in the array, but it could be repeated more than once.

题目

Basic Calculator
Implement a basic calculator to evaluate a simple expression string.

The expression string may contain open ( and closing parentheses ), the plus + or minus sign -, non-negative integers and empty spaces .

Example 1:

1
2

Input: "1 + 1"
Output: 2

Example 2:

1
2

Input: " 2-1 + 2 "
Output: 3

Example 3:

1
2

Input: "(1+(4+5+2)-3)+(6+8)"
Output: 23

Note:
You may assume that the given expression is always valid.
Do not use the eval built-in library function.

题目

Best Time to Buy and Sell Stock IV
Say you have an array for which the i-th element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete at most k transactions.

Note:
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

Example 1:

1
2
3

Input: [2,4,1], k = 2
Output: 2
Explanation: Buy on day 1 (price = 2) and sell on day 2 (price = 4), profit = 4-2 = 2.

Example 2:

1
2
3
4

Input: [3,2,6,5,0,3], k = 2
Output: 7
Explanation: Buy on day 2 (price = 2) and sell on day 3 (price = 6), profit = 6-2 = 4.
             Then buy on day 5 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3.

动态规划套路

有一个 m*n 大小的矩阵迷宫，每次移动只能向右或者向下，文聪左上角到右下角有多少种不同的走法

暴力解法

• 从(1,1)->(m,n)的不同路径中有大量的重复，比如(1,1)->(i,j)有 k 条不同的路径，那么对于任何一条固定的路线(i,j)->(m,n)的路径，都需要走 k 遍来模拟。
• 不关心具体的走法，只关心状态，也就是走法的数量
• 同理，如果知道(i,j)->(m,n)有 k 条不同的路径，那么(1,1)->(i,j)->(m,n)的不同路径总数是k*s

动态规划

• 令(i,j)表示从(1,1)->(i,j)的不同路径数量，f(i,j) = f(i-1,j) + f(i,j-1)
• 如果要求出 f(i,j) 只需要上一个结果即可， 也就是求解f(i,j) 需要求出子问题f(i',j')

动态规划适用前提

无后效性

• 一旦确定f(i,j)，就不用关心如何计算出f(i,j)
• 想要确定f(i,j)，只要知道f(i-1,j)和f(i,j-1)

最优子结构

• f(i,j)的定义已经蕴含最优
• 大问题的最优解可以由若干小问题的最优解推出(min, max, sum)

  DP 适用的问题：可以将大问题拆成几个小问题，且无后效性，具有最优子结构的性质

记忆化递归

• 可以使用递归求解
• 有重复子问题，overlaping subproblem

题目

Majority Element
Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.

You may assume that the array is non-empty and the majority element always exist in the array.

Example 1:

1
2

Input: [3,2,3]
Output: 3

Example 2:

1
2

Input: [2,2,1,1,1,2,2]
Output: 2

题目

Single Number II
Given a non-empty array of integers, every element appears three times except for one, which appears exactly once. Find that single one.

Note:

Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

Example 1:

1
2

Input: [2,2,3,2]
Output: 3

Example 2:

1
2

Input: [0,1,0,1,0,1,99]
Output: 99

题目

Construct Binary Tree from Preorder and Postorder Traversal
Return any binary tree that matches the given preorder and postorder traversals.

Values in the traversals pre and post are distinct positive integers.

Example 1:

1
2

Input: pre = [1,2,4,5,3,6,7], post = [4,5,2,6,7,3,1]
Output: [1,2,3,4,5,6,7]

Note:

1
2
3

1 <= pre.length == post.length <= 30
pre[] and post[] are both permutations of 1, 2, ..., pre.length.
It is guaranteed an answer exists. If there exists multiple answers, you can return any of them.

来自维基百科

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

/*
        The purpose of this function is to convert an unsigned
        binary number to reflected binary Gray code.

        The operator >> is shift right. The operator ^ is exclusive or.
*/
unsigned int binaryToGray(unsigned int num)
{
        return (num >> 1) ^ num;
}

/*
        The purpose of this function is to convert a reflected binary
        Gray code number to a binary number.
*/
unsigned int grayToBinary(unsigned int num)
{
    unsigned int mask;
    for (mask = num >> 1; mask != 0; mask = mask >> 1)
    {
        num = num ^ mask;
    }
    return num;
}

LowerBound

Lower Bound 是使用二分查找的办法求 大于等于 i 的第一个位置