1.网络

1.网络七层协议有哪些？

物理层：

主要功能：传输比特流；

典型设备：集线器、中继器；

典型协议标准和应用：V.35、EIA/TIA-232

数据链路层：

主要功能：保证无差错的疏忽链路的

典型设备：交换机、网桥、网卡

典型协议标准和应用：802.2、802.3ATM、HDLC、FRAME RELAY

网络层：

主要功能：路由、寻址

典型设备：路由器

典型协议标准和应用：IP、IPX、APPLETALK、ICMP

传输层：

主要功能：端到端控制

典型设备：网关

典型协议标准和应用：TCP、UDP、SPX

会话层：

主要功能：会话的建立和结束

典型设备：网关

典型协议标准和应用：RPC、SQL、NFS、X WINDOWS、ASP

表示层：

表示层相当于一个东西的表示，表示的一些协议，比如图片声音视频MPEG等

主要功能：数据表示、压缩和加密

典型设备：网关

典型协议标准和应用：ASCLL、PICT、TIFF、JPEG｜MPEG

应用层：

主要功能：应用接口、应用程序

典型设备：网关

典型协议标准和应用：TELNET、FTP、HTTP

2.Http 和 Https 的区别？Https为什么更加安全？

区别：

1. HTTP是明文传输， https是基于SSL进行的加密传输、有身份验证环节，更加安全
2. HTTP默认端口号是80，HTTPS默认端口号是443
3. HTTPS需要CA证书，极少免费。

安全的原因：HTTPS是基于SSL(安全套接字)和TLS(传输层安全)，对网络进行加密处理，保障数据的完整性，更加安全。

3.HTTPS的连接建立流程

HTTPS为了兼顾安全与效率，同时使用了对称加密和非对称加密。在传输中涉及到3个密钥：服务端到公钥和私钥用于非对称加密，客户端生成的随机密钥用来进行对称加密

image.png

如图HTTPS连接过程大致分为8步

1. 客户端访问HTTPS连接：客户端把安全协议版本号、客户端支持的加密算法列表、随机数C发给服务端。
2. 服务端发送证书给客户端：服务端接受密钥算法配件后，会和自己支持的加密算法列表进行对比，如果不符合则断开连接。否则会在该算法列表中选择一种对称算法(如AES)、一种公钥算法(如具有特定密钥长度的RSA)和一种MAC算法发给客户端。服务端有一个密钥对（公钥和私钥）用来进行非对称加密使用，服务端保存着私钥，公钥可以发送给任何人。在发送加密算法的同时还会把数字证书和随机数S发送给客户端
3. 客户端验证server证书：客户端会对server公钥进行检查，验证其合法性，如果公钥有问题，那么HTTPS传输就无法继续。
4. 客户端组装会话密钥：如果公钥合格，那么客户端就会用服务端公钥来生成一个前主密钥(Pre-Master Secret,PMS),并通过该前主密钥和随机数C、S来组装成会话密钥
5. 客户端将前主密钥发送给服务端：通过服务端端公钥对前主密钥进行非对称加密，发送给服务端
6. 服务端通过私钥解密得到前主密钥：服务端接受到加密信息后，用私钥解密得到前主密钥。
7. 服务端组装会话密钥：服务端通过前主密钥和随机数C、S来组装会话密钥。至此，服务端和客户端都已经知道了用于此次会话都都主密钥。
8. 数据传输：客户端收到服务器发送来的秘文，用客户端密钥对其进行对称解密，得到服务器发送的数据。同理，服务端收到客户端发送的秘文，用服务端密钥进行对称解密得到客户端发送的数据。

4.解释一下 三次握手 和 四次挥手

• • 三次握手：
    1. 客户端向服务端发送SYN同步报文
    2. 服务端收到SYN同步报文后，会返回给客户端SYN同步报文和ACK确认报文
    3. 客户端向服务端发送ACK确认报文，此时客户端和服务端的连接正式建立
  • 建立连接：
    1. 这个时候客户端就可以通过HTTP请求报文向服务端发送数据
    2. 服务端收到客户端的请求之后，向客户端回复HTTP响应报文
  • 四次挥手：当客户端和服务端的连接想要断开的时候，要经历四次挥手的过程，客户端和服务端双方都要知道结束了。
    1. 先由客户端向服务端发送FIN结束报文
    2. 服务端会返回给客户端ACK确认报文。此时，由客户端发起的断开连接已经完成。
    3. 服务端会发送给客户端FIN结束报文和ACK确认报文。
    4. 客户端会返回ACK确认报文到服务端，至此，由服务端方向的断开连接已经完成。

5.TCP 和 UDP的区别

TCP:面向连接、传输可靠(保证数据正确性、保证数据顺序)，用于传输大量数据(流模式),速度慢、建立连接需要开销较多(时间、系统资源)

UDP:面向非连接、传输不可靠、用于传输少量数据(数据包模式)、速度快

6.Cookie和Session

Cookie:cookie主要用来记录用户状态，区分用户，状态保存在客户端。cookie功能需要浏览器支持。如果浏览器不支持cookie(如大部分手机中的浏览器)或者把cookie禁用了，cookie功能就会失效。

• cookie的使用：首次访问某网站时，客户端会发送一个HTTP请求到服务器，服务器发送一个HTTP响应到客户端，其中包含set-cookie头部；客户端再发送HTTP请求时，包含cookie头部，服务端返回HTTP响应到客户端；隔断时间再访问时，客户端会直接发包含cookie头部的http请求，服务端响应客户端

• cookie的修改和删除：在修改cookie的时候，只需要新cookie覆盖旧cookie即可，在覆盖的时候，由于cookie具有不可跨域名性，主要name、path、domain需与原cookie一致。删除cookie也一样，设置cookie的过期时间为过去的一个时间点或者maxage=0即可。

• cookie的安全：cookie的使用存在争议，因为它被认为是对用户隐私的侵害，并且cookie并不安全。http协议不仅是无状态的，而且是不安全的，使用http协议的数据使用明文在网络传播有被截获的可能。如果不希望cookie在http非安全协议中传输可以设置cookie的Secure属性为true，浏览器只会在https和ssl等安全协议中传输此类cookie。Secure属性并不能对cookie内容加密，因而不能保证却对安全。如果需要提高安全性，需要在程序中对cookie进行加解密。除了Secure属性，也可设置cookie为httponly，如果设置此属性，那么通过js脚本将无法读取到cookie信息，能有效防止XSS攻击(跨站脚本攻击)

Session：是服务端使用的 一种记录客户端状态的机制。使用上比cookie简单，响应的增加了服务器的存储压力。不同于cookie保存在客户端浏览器中，session保存在服务器上，客户端访问浏览器时，服务端把客户端信息以某种形式记录在服务器上，这就是session。客户端浏览器再次访问时只需要从该session 中查找该客户的状态就可以了。

当程序需要为某个客户端的请求创建session时，会先检索客户端的请求里是否包含session表示（称为sessionid）如果包含则说明之前已经为此客户端创建过会话，服务器就按标识把这个session检索出来使用，检索不到会新建一个。如果客户端请求不包含会话标识，服务端会创建一个session并生成关联的会话id，这个sessionid将在本次响应中返回给客户端保存。

• cookie和session的区别
  • cookie存储在客户端浏览器上，session数据存在服务器上
  • cookie相比session不是很安全
  • session会在一定时间内保存在服务器上，当访问增多会占用服务器性能，考虑减轻服务器性能可以使用cookie
  • 单个cookie保存数据不能超过4k，很多浏览器都限制一个站点最多保存20个。而session没有限制
  • 所以可以将登陆等重要信息存放session，其他如果需要保留可以放在cookie中

7.DNS是什么？

域名系统：domain name system， 用于 主机名到ip地址到转换。

因特网上的主机可以用多种方式标识，比如主机名或ip地址。主机名比如www.baidu.com 这种方式便于人们记忆和接受，但这种长度不一没有规律的字符串不方便路由器处理。路由器比较热衷于 定长的有清晰层次结构的ip地址。为了这种这两种方式，我们需要一种能进行主机名到ip地址转换到服务，这就是域名系统DNS。

DNS是一个由分层的DNS服务器实现的分布式数据库。一个使得主机能够查询分布式数据库的应用层协议： DNS服务器通常是运行BIND软件的UNIX机器，DNS协议运行在UDP上使用53号端口。DNS通常是由其他应用层协议所使用的，包括HTTP、SMTP等。其作用是将用户提供的主机名解析为ip地址。DNS的一种简单设计就是在因特网上只使用一个DNS服务器，该服务器包含所有的映射。很明显这种设计有很大问题：单点故障：如果该DNS服务器崩溃全世界网络随之瘫痪；通信容量：单个DNS服务器必须处理所有的DNS查询；远距离的集中式数据库：单个DNS服务器必须面对所有用户，距离过远会有严重时延。维护：该数据库过于庞大，还需要对新添加的主机频繁更新。所以DNS被设计成了一个分布式、层次数据库。

8.DNS解析过程

以www.163.com为例:

• 客户端打开浏览器，输入一个域名。比如输入www.163.com，这时，客户端会发出一个DNS请求到本地DNS服务器。本地DNS服务器一般都是你的网络接入服务器商提供，比如中国电信，中国移动。
• 查询www.163.com的DNS请求到达本地DNS服务器之后，本地DNS服务器会首先查询它的缓存记录，如果缓存中有此条记录，就可以直接返回结果。如果没有，本地DNS服务器还要向DNS根服务器进行查询。
• 根DNS服务器没有记录具体的域名和IP地址的对应关系，而是告诉本地DNS服务器，你可以到域服务器上去继续查询，并给出域服务器的地址。
• 本地DNS服务器继续向域服务器发出请求，在这个例子中，请求的对象是.com域服务器。.com域服务器收到请求之后，也不会直接返回域名和IP地址的对应关系，而是告诉本地DNS服务器，你的域名的解析服务器的地址。
• 最后，本地DNS服务器向域名的解析服务器发出请求，这时就能收到一个域名和IP地址对应关系，本地DNS服务器不仅要把IP地址返回给用户电脑，还要把这个对应关系保存在缓存中，以备下次别的用户查询时，可以直接返回结果，加快网络访问。

2.多线程

1.进程与线程分别是什么意思？

进程是系统中正在运行的程序，就是一段程序的执行过程，我们可以理解为手机上一个正在运行的app。进程是操作系统分配资源的基本单元。每个进程之间相互独立，每个进程均运行在其专用且受保护的内存空间内，拥有独立运行所需的全部资源。

线程是程序执行的最小单元，是进程中的一个实体。一个进程想要执行任务必须至少有一条线程。应用程序启动时，系统会默认开启一条线程，也就是主线程。

进程和线程的关系：线程是进程的执行单元，进程中的所有任务都是在线程中执行的；线程是CPU分配资源和调度的最小单元；一个程序可以对应多个进程，一个进程至少有一条线程；同一个进程内的线程共享进程资源。

2.什么是多线程？

一个进程至少有一个线程，如果有多个线程在执行就是多线程。多线程的实现原理，如果是单核CPU，则是CPU在多个线程之间快速切换，造成多个线程同时执行的假象。如果是多核CPU，就真的可以实现多个线程同时执行。多线程的目的是为了同步完成多项任务，通过提高系统资源的利用率来提高工作效率。

3.多线程的优点和缺点有哪些？

优点：能适当的提高程序的执行效率；能适当提高资源的利用率（CPU、内存利用率）

缺点：每个线程都有一定的开销，从而影响性能。不仅有创建时的时间开销，还有消耗内存。每个线程大约消耗1kb的内核内存空间，用于存储与线程有关的数据结构和属性，这块儿内存是联动内存，无法被分页。此外还占用一定的栈空间，默认主线程占1M，子线程占512k，注意完整的栈不会被立即创建，实际消耗的栈空间随着使用而增加，如果开启大量线程，会占用大量内存空间降低程序性能；线程越多CPU调度线程的开销就越大。程序设计更加复杂比如线程之间的通信多线程的数据共享等。

4.多线程的 并行 和 并发 有什么区别？

并行：充分利用计算机的多核，在多个线程上同步进行

并发：CPU快速切换线程，让人感觉在同步进行

5.iOS中实现多线程的几种方案，各自有什么特点？

NSThread 面向对象，需手动创建线程，但不需要手动销毁。自线程间通信很难；

GCD C语言，充分利用了设备的多核，自动管理线程生命周期。比NSOperation高效；

NSOPeration 基于GCD封装，更加面向对象。比GCD多了一些功能，比如设置最大并发数，可以监控任务状态，轻松设置任务依赖等。

6.多个网络请求完成后如何执行？

• 使用GCD的任务组

创建一个任务组 dispatch_group_t,每次网络请求前先进入组 dispatch_group_enter，请求回调后再离开组 dispatch_group_leave。进入和离开必须成对使用，否则组会一直存在。当所有enter都leave之后，会执行组通知dispatch_group_notify的block。

• 使用GCD的信号量

信号量是基于计数器的一种多线程同步机制。如果信号计数大于1，计数-1返回，程序继续执行。如果计数为0则等待。

增加信号量 dispatch_semaphore_signal(semaphore)为计数+1操作。dispatch_semaphore_wait(sema,DISPATCH_TIME_FOREVER)为设置等待的时间，这里设置的是一直等待。

创建信号量为0，等待。等10个网络请求都完成了，信号量dispatch_semaphore_signal计数为1，然后计数-1返回。

dispatch_semaphore_t sem = dispatch_semaphore_create(0);
for (int i=0; i<10; i++) {
    
    NSURLSessionDataTask *task = [session dataTaskWithRequest:request completionHandler:^(NSData * _Nullable data, NSURLResponse * _Nullable response, NSError * _Nullable error) {
        NSLog(@"%d---%d",i,i);
        count++;
        if (count==10) {
            dispatch_semaphore_signal(sem);
            count = 0;
        }
    }];
    [task resume];
}
dispatch_semaphore_wait(sem, DISPATCH_TIME_FOREVER);

dispatch_async(dispatch_get_main_queue(), ^{
    NSLog(@"end");
});

7.多个网络请求顺序执行后如何执行下一步？

使用信号量，每一次遍历，都让信号量等待，阻塞当前线程，直到信号增加调用之后

dispatch_semaphore_t sem = dispatch_semaphore_create(0);
for (int i=0; i<10; i++) {
    
    NSURLSessionDataTask *task = [session dataTaskWithRequest:request completionHandler:^(NSData * _Nullable data, NSURLResponse * _Nullable response, NSError * _Nullable error) {
        
        NSLog(@"%d---%d",i,i);
        dispatch_semaphore_signal(sem);
    }];
    
    [task resume];
    dispatch_semaphore_wait(sem, DISPATCH_TIME_FOREVER);
}

dispatch_async(dispatch_get_main_queue(), ^{
    NSLog(@"end");
});

8.如何理解多线程中的死锁？

死锁是由于多个线程(进程)在执行过程中，因为争夺资源而造成的相互等待的现象。可以理解为卡住了。产生死锁的必要条件有4个：

• 互斥条件：指进程对分配到的资源进行排他性使用，即在一段时间内某资源只由一个进程占用，如果此时还有其他进程请求资源，则请求者只能等待，直到占有资源的进程用毕释放。
• 请求和保持条件：指进程已经保持至少一个资源，但又提出了新的资源请求，而该资源已经被其他进程占有，此时请求阻塞，但又对自己已获得的其他资源保持不放。
• 不可剥夺条件：指进程已获得的资源，在未使用完之前，不能被剥夺，只能在使用完时由自己释放。
• 环路等待条件：在发生死锁时，必然存在一个进程资源的环形链，即进程集合P{P0,P1,P2,...,Pn}中的P0正在等待一个P1占用的资源，P1正在等待P2占用的资源...Pn正在等待已被P0占用的资源
• 最常见的就是同步函数+主队列的组合，本质是队列阻塞

9.如何去理解GCD执行原理？

GCD 维护着一个线程池，这个池中存放着一个个线程。这个池中线程是可以重用的，当一个段时间后这个线程没有调用的话，这个线程就会被销毁。注意开多少条线程是由底层线程池决定的(线程建议控制在3-5条)，池是系统自动维护，不需要程序员干预。程序员需要关心的是向队列中添加任务，队列调度即可。

如果队列中存放的是同步任务，则任务出队之后，底层线程池中会提供一条线程供这个任务执行，任务执行完毕后这条线程再回到线程池。这样队列中的任务反复调度，因为是同步的，所以当我们调用current Thread的时候，就是同一条线程。

如果队列中存放的是异步任务(注意异步可以开线程),当任务出队之后，底层线程池会提供一个线程供任务执行，因为是异步执行，队列中的任务不需要等待当前任务执行完毕就可以调度下一个任务，这时线程池会再次提供一个线程供第二个任务执行，执行完毕后再回到线程池中。

这样就对线程完成一个复用，而不需要每一个任务都开启新的线程。也就节约了系统开销，提高了效率。

3.架构 + 设计模式

一，项目架构

1.MVC、MVP、MVVM模式

MVC是比较直观的架构模式，最核心的就是通过Controller层来进行调控，首先看一下官方提供的MVC示意图：

image.png

• Model和View永远不能相互通信，只能通过Controller传递
• Controller可以直接与Model对话（读写调用Model），Model通过NOtification和KVO机制与Controller间接通信

Controller可以直接与View对话，通过IBoutlet直接操作View，IBoutlet直接对应View的控件（例如创建一个Button：需声明一个 IBOutlet UIButton * btn），View通过action向Controller报告时间的发生(用户点击了按钮)。Controller是View的直接数据源

• 优点：对于混乱的项目组织方式，有了一个明确的组织方式。通过Controller来掌控全局，同时将View展示和Model的变化分开
• 缺点：愈发笨重的Controller，随着业务逻辑的增加，大量的代码放进Controller，导致Controller越来越臃肿，堆积成千上万行代码，后期维护起来费时费力

MVP（Model、View、Presenter）

MVP模式是MVC模式的一个演化版本，其中Model与MVC模式中Model层没有太大区别，主要提供数据存储功能，一般都是用来封装网络获取的json数据；View与MVC中的View层有一些差别，MVP中的View层可以是viewController、view等控件；Presenter层则是作为Model和View的中介，从Model层获取数据之后传给View。

image.png

从上图可以看出，从MVC模式中增加了Presenter层，将UIViewController中复杂的业务逻辑、网络请求等剥离出来。

• 优点 模型和视图完全分离，可以做到修改视图而不影响模型；更高效的使用模型，View不依赖Model，可以说VIew能做到对业务逻辑完全分离
• 缺点 Presenter中除了处理业务逻辑以外，还要处理View-Model两层的协调，也会导致Presenter层的臃肿

2.关于RAC你有怎样运用到解决不同API依赖关系

3.@weakify和我们宏定义的WeakSelf有什么区别？

4. 微服务的架构设想

MVVM（Model、Controller/View、ViewModel）

在MVVM中，view和ViewCOntroller联系在一起，我们把它们视为一个组件，view和ViewController都不能直接引用model，而是引用是视图模型即ViewModel。viewModel是一个用来放置用户输入验证逻辑、视图显示逻辑、网络请求等业务逻辑的地方，这样的设计模式，会轻微增加代码量，但是会减少代码的复杂性

• 优点 VIew可以独立于Model的变化和修改，一个ViewModel可以绑定到不同的View上，降低耦合，增加重用
• 缺点 过于简单的项目不适用、大型的项目视图状态较多时构建和维护成本太大

合理的运用架构模式有利于项目、团队开发工作，但是到底选择哪个设计模式，哪种设计模式更好，就像本文开头所说，不同的设计模式，只是让不同的场景有了更多的选择方案。根据项目场景和开发需求，选择最合适的解决方案。

关于RAC你有怎样运用到解决不同API依赖关系

• 信号的依赖：使用场景是当信号A执行完才会执行信号B,和请求的依赖很类似,例如请求A请求完毕才执行请求B,我们需要注意信号A必须要执行发送完成信号,否则信号B无法执行

@weakify和我们宏定义的WeakSelf有什么区别？

• @weakify 可以多参数使用

二，设计模式

1. iOS有哪些常见的设计模式?

   单例模式：单例保证了应用程序生命周期内仅有一个该类的实例对象，而且易于外界访问。在iOS SDK中，UIApplication, NSBundle, NSNotificationCenter, NSFileManager, NSUserDefault, NSURLCache等都是单例.

   委托模式：委托代理是协议的一种，通过protocol方式实现，常见的有tableview及textFiled都采用了委托代理模式。

   观察者模式：观察者模式定义了一种一对多的依赖关系，让多个观察者同时监听某一个主题对象。在iOS中，观察者模式的具体实现有两种：通知机制 和 KVO

2. 单例会有什么弊端？

优点：提供了对唯一实例的受控访问。系统内存中只存在一个对象，可以节约系统资源，对于一些需要频繁创建和销毁的对象，单例模式无疑可以提高系统性能。允许可变数目的实例。

缺点：单例模式中没有抽象层，因此但李磊的扩展有很大困难。单例类的职责过重，在一定程度上违背了单一职责原则。滥用单例会有负面问题，比如为了节省资源将数据库连接池对象设计为单例类，可能会导致共享连接池对象过多而出现连接池溢出。

3. 编程中的六大设计原则？

   • 单一职责原则：一个类只做一件事，CALayer负责动画和视图的显示。UIView只负责事件的传递和响应

   • 开闭原则：对修改关闭，对扩展开放。要考虑到后续的扩展性，而不是在原有的基础上来回修改

   • 接口隔离原则：使用多个专门的协议，而不是一个庞大臃肿的协议，如UITableviewDelegate + UITableViewDataSource

   • 依赖倒置原则：抽象不应该依赖于具体实现，具体实现可以依赖于抽象。调用接口感觉不到内部是如何操作的

   • 里式替换原则：父类可以被子类无缝替换，且原有功能不受任何影响。如kvo

   • 迪米特法则：一个对象应当对其他对象尽可能少的了解，实现高聚合、低耦合

4. 如何设计一个图片缓存框架？

   可以模仿sdwebimage。图片的存储是以图片的单向hash值为key。内存设计需要考虑存储的大小。因为内存空间有限，我们针对不同的图片给出不同的方案。比如 10k以下的50个，100k以下的20个，100k以上的10个。

   内存淘汰策略可以采用LRU，最近最少使用算法。触发淘汰策略的时机有三种：定期检查（不建议，耗性能）前后台切换时、每次读写时。

   磁盘设计需要考虑的问题：存储方式，移除策略可以设置为7天或者15天，图片请求的最大并发量，请求超时策略，请求优先级。

   图片解码：应用策略模式，针对jpg，png，gif等不同格式的图片进行解码。图片解码的时机，在子线程图片刚下载完时，在子线程刚从磁盘读取完时，避免在主线程压缩、解码，避免卡顿。

5. 如何设计一个时长统计框架？

   记录器：页面式记录器、流式记录器、自定义式

   记录管理者：内存记录缓存、磁盘存储、上传器

   如何降低数据丢失率：定期写入磁盘、每当达到某个值时写入磁盘

   记录上传时机：前后台切换的时候可以上传、从无网络切换到有网络的时候可以上传

   上传时机的选择：立即上传、定时上传、延时上传

4.组件化+性能优化

组件化有什么好处？

• 业务分层、解耦，使代码变得可维护
• 有效的拆分、组织日益庞大的工程代码，使工程目录变得可维护
• 便于各业务功能拆分、抽离，实现真正的功能复用
• 业务隔离，跨团队开发代码控制和版本风险控制的实现
• 模块化对代码的封装性、合理性都有一定的要求，提升开发同学的设计能力
• 在维护好各级组件的情况下，随意组合满足不同客户需求。只需要将之前的多个业务组件模块在新的主app中进行组装即可快速迭代出下一个全新APP

你是如何组件化解耦的？

• 分层
  • 基础功能组件：按功能分库，不设计产品业务需求，跟库library类似，通过良好的接口供上层业务组件调用；不写入产品定制逻辑，通过扩展接口完成定制。
  • 基础UI组件：各个业务模块依赖使用，但需要保持好定制扩展的设计。
  • 业务组件：业务功能间相互独立，相互间没有model共享的依赖；业务之间的页面调用只能通过UIBus总线进行跳转；业务之间的逻辑Action调用只能通过服务提供。
• 中间件：target-action，url-block，protocol-class

为什么CTMediator方案优于Router方案？

Router的缺点：

• 在实施组件化的过程中，注册URL并不是充分必要条件，组件是不需要向组建管理器注册URL的，注册了URL之后，会造成不必要的内存常驻。
• 注册URL的目的其实是一个服务发现的过程。在iOS领域中，服务发现的方式是不需要通过主动注册的，使用runtime就可以。
• 注册部分的代码维护也是一个相对麻烦的事情，每一次支持新调用时，都要去维护一次注册列表。如果有调用被弃用了，可能会忘记删除。runtime由于不存在注册过程，也就不会产生维护操作，降低了维护成本。
• 由于通过runtime做到了服务的自动发现，拓展接口调用的任务就仅在于各自的模块，任何一次新接口的添加，新业务添加，都不必去主工程做操作，十分透明。
• 在iOS领域里，一定是组件化的中间件为openURL提供服务，而不是openURL方式为组件化提供服务。
• 如果在给APP实现组件化方案的过程中是基于openURL的方案的话，有一个致命缺陷：非常规对象（不能被字符串化到URL中的对象，例如UIImage）无法参与本地化组件间调度。
• 在本地调用中使用URL的方式其实是不必要的，如果业务工程师在本地间调度时需要给出RUL，那么就不可避免要提供params，在调用时要提供哪些params是业务工程师容易懵逼的地方
• 为了支持传递非常规参数，蘑菇街的方案采用了protocol，这个会侵入业务。由于业务中的某个对象需要被调用，因此必须要符合某个可被调用的protocol，然而这个protocol又不存在当前的业务领域，于是当前业务就不得不依赖public protocol，这对将来的业务迁移有非常大的影响。

CTMediator的优点：

• 调用时，区分了本地调用和远程应用调用。本地调用为远程调用提供服务
• 组件仅通过action暴露可调用的接口，模块之间的接口被固化在了target-action这一层，避免了实施组件化的改造过程中，对业务的入侵，同时也提高了组件化接口的可维护性
• 方便传递各种类型的参数

基于CTMediator的组件化方案，有哪些核心组成？

• CTMediator中间件：集成就可以了
• 模块Target_%@:模块的实现及提供对外的方法调用Action_methodName,需要传递参数时，都统一以nsdictionary的形式传入
• CTMediator+%@扩展：扩展里声明了模块业务的对外接口，参数明确，这样外部调用可以很容易理解如何调用接口。

性能优化：

造成tableview卡顿的原因有哪些？

• 最常用的就是cell的复用，注册重用标识符。

  如果不重用cell时，每当一个cell显示到屏幕上时，就会重新创建一个新的cell，如果有很多数据的时候，就会堆积很多cell。如果重用cell，为cell重建一个id，每当需要显示的时候，就先从缓冲池中寻找可循环利用的cell，如果没有再新建cell

• 避免cell重新布局

  cell的布局填充等操作，比较耗时，一般创建时就布局好。如可以将cell单独放到一个自定义类，初始化时就布局好

• 提前计算病患搓cell的属性及内容

  当我们创建cell的数据源方法时，编译器并不是先创建cell再定cell高度的，而是先根据内容一次确定每一个cell的高度，高度确定后，再创建要显示的cell，滚动时，每当cell进入屏幕都会计算高度，提高估算高度告诉编译器，编译器知道高度后，紧接着就会创建cell，这时再调用高度的具体计算方法。

• 减少cell中控件的数量

  尽量使cell的布局大致相同，不同风格的cell可以使用不同的重用标识符，初始化时添加控件，不使用的可以先隐藏。

• 不要使用clearcolor，无背景色，透明度也不要设置为0，渲染消耗事件比较长。

• 使用局部更新：如果只是更新某组的话，使用reloadsection进行局部更新。

• 加载网络数据，下载图片，使用异步加载并缓存

• 少使用addsubView给cell动态添加view

• 按需加载cell，cell滚动很快时，只加载范围内的cell

• 不要实现无用的代理方法

• 缓存行高：estimatedHeightForRow不能和HeightForRow里面的layoutIfNeed同时存在，这两者同时存在才会出现“窜动”的bug。所以我的建议是：只要是固定行高就写预估行高来减少行高调用次数提升性能。如果是动态行高就不要写预估方法了，用一个行高的缓存字典来减少代码的调用次数即可

• 不要做多余的绘制工作。在实现drawRect:的时候，它的rect参数就是需要绘制的区域，这个区域之外的不需要进行绘制。例如上例中，就可以用CGRectIntersectsRect、CGRectIntersection或CGRectContainsRect判断是否需要绘制image和text，然后再调用绘制方法。

• 预渲染图像。当新的图像出现时，仍然会有短暂的停顿现象。解决的办法就是在bitmap context里先将其画一遍，导出成UIImage对象，然后再绘制到屏幕；

• 使用正确的数据结构来存储数据

如何提升tableview的流畅度？

• 本质上是降低CPU、GPU的工作，从这两大方面去提升性能。
  • CPU：对象的创建和销毁、对象属性的调整、布局计算、文本的计算和排版、图片的格式转换和解码、图像的绘制
  • GPU：纹理的渲染
• 卡顿优化在CPU层面
  • 尽量使用轻量级对象，比如用不到事件的地方，可以考虑用CALayer取代UIView
  • 不要频繁调用UIView的相关属性，比如frame，bounds，transform等属性，尽量减少不必要的修改
  • 尽量提前好布局，在有需要时一次性调整对应的属性，不要多次修改属性
  • autolayout会比直接设置frame消耗更多的cpu资源
  • 图片的size最好刚好和UIimageview的size一致
  • 控制线程的最大并发数量
  • 尽量把耗时操作放到子线程，文本处理 尺寸计算、绘制 图片的解码绘制
• 卡顿优化在GPU层面
  • 尽量避免短时间内大量图片的显示，尽可能将多张图片合成一张进行显示
  • GPU能处理的最大纹理尺寸是4096*4096，一旦超过这个尺寸，会占用CPU资源进行处理，所以纹理尽量不要超过这个尺寸
  • 尽量减少视图数量和层次
  • 减少透明的视图，不透明的就设置opaque为YES
  • 尽量避免出现离屏渲染

iOS保持界面流畅的技巧

• 预排版，提前计算。

  在接收到服务端返回的数据后，尽量将coretext排版的结果，单个控件的高度，cell整体的高度提前计算好，将其存储在模型的属性中，需要使用时，直接从模型中往外取，避免后续计算的过程。尽量少用UILabel，可以使用CALayer。

• 预渲染，提前绘制。

  例如圆形的图标，可以提前在接收到网络返回的数据时，在后台线程进行处理，直接存储在模型数据里面，回到主线程后直接调用就可以了。避免使用CALayer的border、Corner、shadow、mask等技术，这些都会触发离屏渲染。

• 异步绘制

• 全局并发线程

• 高效的图片异步加载

APP启动时间应从哪些方面优化？

启动时间可以通过xcode提供的工具来度量，在xcode的product-scheme-edit scheme - run -auguments中，将环境变量DYLD_PRINT_STATISTICS设置为YES，优化需以下方面入手：

• dylib loading time：核心思想时减少dylibs的引用，合并现有的dylibs(最好是6个以内)，使用静态库

• rebase/binding time:核心思想时减少DATA块内的指针；减少objectC元数据量，减少objc类数量，减少实例变量和函数；减少c++虚函数；多使用Swift结构体，推荐使用Swift

• objc setup time：核心思想同上，这部分内容基本上在上一阶段优化过后就不会太过耗时

• initalizer time： 使用initalize替代load方法；减少使用c/C++的attribute；推荐使用dispatch_once，pthread_once等方法；推荐使用swift。不要再初始化中调用dlopen方法，因为加载过程是单线程，无锁，如果调用dlopen则会变成多线程，会开启锁的消耗，同时有可能死锁

  参考资料：https://www.jianshu.com/p/cf95d020e1b2

如何降低app包的大小？

降低包大小，需要从两方面着手：

• 可执行文件：

  编译器优化：Strip Linked Product、Make Strings Read-Only、Symbols Hidden by Default 设置为 YES，去掉异常支持，Enable C++ Exceptions、Enable Objective-C Exceptions 设置为 NO， Other C Flags 添加 -fno-exceptions 利用 AppCode 检测未使用的代码：菜单栏 -> Code -> Inspect Code

  • 资源：对资源进行无损压缩、去除无用的资源

怎么检测图文混合？

1、模拟器debug中color blended layers红色区域表示图层发生了混合

2、Instrument-选中Core Animation-勾选Color Blended Layers

避免图层混合：

• 确保控件的opaque属性设置为true，确保backgroundColor和父视图颜色一致且不透明
• 如无特殊需要，不要设置低于1的alpha值
• 确保UIImage没有alpha通道

UILabel图层混合解决方法：

iOS8以后设置背景色为非透明色并且设置label.layer.masksToBounds=YES让label只会渲染她的实际size区域，就能解决UILabel的图层混合问题

iOS8 之前只要设置背景色为非透明的就行

为什么设置了背景色但是在iOS8上仍然出现了图层混合呢？

UILabel在iOS8前后的变化，在iOS8以前，UILabel使用的是CALayer作为底图层，而在iOS8开始，UILabel的底图层变成了_UILabelLayer，绘制文本也有所改变。

在背景色的四周多了一圈透明的边，而这一圈透明的边明显超出了图层的矩形区域，设置图层的masksToBounds为YES时，图层将会沿着Bounds进行裁剪 图层混合问题解决了

日常如何检查内存泄漏？

目前我知道的方式有以下几种

• Memory Leaks
• Alloctions
• Analyse
• Debug Memory Graph
• MLeaksFinder

泄露的内存主要有以下两种：

• Leak Memory 这种是忘记 Release 操作所泄露的内存。
• Abandon Memory 这种是循环引用，无法释放掉的内存。

如何优化app电量？

• 程序的耗电主要在以下四个方面：

CPU 处理
定位
网络
图像

• 优化的途径主要体现在以下几个方面：

尽可能降低 CPU、GPU 的功耗。
尽量少用 定时器。
优化 I/O 操作。

不要频繁写入小数据，而是积攒到一定数量再写入
读写大量的数据可以使用 Dispatch_io ，GCD 内部已经做了优化。
数据量比较大时，建议使用数据库

• 网络方面的优化

减少压缩网络数据 （XML -> JSON -> ProtoBuf），如果可能建议使用 ProtoBuf。
如果请求的返回数据相同，可以使用 NSCache 进行缓存
使用断点续传，避免因网络失败后要重新下载。

网络不可用的时候，不尝试进行网络请求
长时间的网络请求，要提供可以取消的操作
采取批量传输。下载视频流的时候，尽量一大块一大块的进行下载，广告可以一次下载多个

• 定位层面的优化

如果只是需要快速确定用户位置，最好用 CLLocationManager 的 requestLocation 方法。定位完成后，会自动让定位硬件断电
如果不是导航应用，尽量不要实时更新位置，定位完毕就关掉定位服务
尽量降低定位精度，比如尽量不要使用精度最高的 kCLLocationAccuracyBest

需要后台定位时，尽量设置 pausesLocationUpdatesAutomatically 为 YES，如果用户不太可能移动的时候系统会自动暂停位置更新
尽量不要使用 startMonitoringSignificantLocationChanges，优先考虑 startMonitoringForRegion:

• 硬件检测优化

用户移动、摇晃、倾斜设备时，会产生动作(motion)事件，这些事件由加速度计、陀螺仪、磁力计等硬件检测。在不需要检测的场合，应该及时关闭这些硬件

5.Runloop

1.Runloop 和线程的关系？

一个线程对应一个runloop，主线程的runloop时默认开启的，子线程的runloop以懒加载的形式创建。runloop存储在一个全局的可变字典中，线程是key，runloop是value。

2.RunLoop的运行模式

runloop的运行模式一共有5种，runloop只会运行在一个模式下，要切换模式，就要暂停当前的模式，重新启动一个运行模式

- kCFRunLoopDefaultMode, App的默认运行模式，通常主线程是在这个运行模式下运行

- UITrackingRunLoopMode, 跟踪用户交互事件（用于 ScrollView 追踪触摸滑动，保证界面滑动时不受其他Mode影响）

- kCFRunLoopCommonModes, 伪模式，不是一种真正的运行模式

- UIInitializationRunLoopMode：在刚启动App时第进入的第一个Mode，启动完成后就不再使用

-GSEventReceiveRunLoopMode：接受系统内部事件，通常用不到

3.runloop内部逻辑？

实际上 RunLoop 就是这样一个函数，其内部是一个 do-while 循环。当你调用 CFRunLoopRun() 时，线程就会一直停留在这个循环里；直到超时或被手动停止，该函数才会返回。

image.png

内部逻辑：

• • 如果是 Timer 事件，处理 Timer 并重新启动循环，跳到第 2 步
  • 如果输入源被触发，处理该事件（文档上是 deliver the event）
  • 如果 RunLoop 被手动唤醒但尚未超时，重新启动循环，跳到第 2 步
  • 事件到达基于端口的输入源（port-based input sources）(也就是 Source0)
  • Timer 到时间执行
  • 外部手动唤醒
  • 为 RunLoop 设定的时间超时
• 1. 通知 Observer 已经进入了 RunLoop
  2. 通知 Observer 即将处理 Timer
  3. 通知 Observer 即将处理非基于端口的输入源（即将处理 Source0）
  4. 处理那些准备好的非基于端口的输入源（处理 Source0）
  5. 如果基于端口的输入源准备就绪并等待处理，请立刻处理该事件。转到第 9 步（处理 Source1）
  6. 通知 Observer 线程即将休眠
  7. 将线程置于休眠状态，直到发生以下事件之一
  8. 通知 Observer 线程刚被唤醒（还没处理事件）
  9. 处理待处理事件

• Source1 :基于mach_Port的,来自系统内核或者其他进程或线程的事件，可以主动唤醒休眠中的RunLoop（iOS里进程间通信开发过程中我们一般不主动使用）。mach_port大家就理解成进程间相互发送消息的一种机制就好, 比如屏幕点击, 网络数据的传输都会触发sourse1。
  • Source0 ：非基于Port的 处理事件，什么叫非基于Port的呢？就是说你这个消息不是其他进程或者内核直接发送给你的。一般是APP内部的事件, 比如hitTest:withEvent的处理, performSelectors的事件.

• 简单举个例子：一个APP在前台静止着，此时，用户用手指点击了一下APP界面，那么过程就是下面这样的：

• 我们触摸屏幕,先摸到硬件(屏幕)，屏幕表面的事件会被IOKit先包装成Event,通过mach_Port传给正在活跃的APP , Event先告诉source1（mach_port）,source1唤醒RunLoop, 然后将事件Event分发给source0,然后由source0来处理。

4.autoreleasePool 在何时被释放？

• app启动后，苹果在主线程的runloop中注册了两个observer，其回调都是_wrapRunLoopWithAutoreleasePoolHandler()。
• 第一个observer监听的事件是Entry即将进入loop，其回调内会调用_objc_autoreleasePoolPush()创建自动释放池，其order是-2147483647，优先级最高，保证创建释放池发生在其他所有回调之前。
• 第二个observer监听了两个事件：beforewaiting准备进入休眠时调用_objc_autoreleasePoolPop() 和 _objc_autoreleasePoolPush() 释放旧的释放池病创建新池；Exit即将退出Loop时调用_objc_autoreleasePoolPop() 来释放自动释放池。这个 Observer 的 order 是 2147483647，优先级最低，保证其释放池子发生在其他所有回调之后。
• 在主线程执行的代码，通常是写在诸如事件回调、Timer回调内的。这些回调会被 RunLoop 创建好的 AutoreleasePool 环绕着，所以不会出现内存泄漏，开发者也不必显示创建 Pool 了。

5. GCD 在Runloop中的使用？

• GCD由 子线程 返回到 主线程,只有在这种情况下才会触发 RunLoop。会触发 RunLoop 的 Source 1 事件。

6.AFNetworking 中如何运用 Runloop?

AFURLConnectionOperation 这个类是基于 NSURLConnection 构建的，其希望能在后台线程接收 Delegate 回调。

为此 AFNetworking 单独创建了一个线程，并在这个线程中启动了一个 RunLoop：

+ (void)networkRequestThreadEntryPoint:(id)__unused object {
    @autoreleasepool {
        [[NSThread currentThread] setName:@"AFNetworking"];
        NSRunLoop *runLoop = [NSRunLoop currentRunLoop];
        [runLoop addPort:[NSMachPort port] forMode:NSDefaultRunLoopMode];
        [runLoop run];
    }
}

+ (NSThread *)networkRequestThread {
    static NSThread *_networkRequestThread = nil;
    static dispatch_once_t oncePredicate;
    dispatch_once(&oncePredicate, ^{
        _networkRequestThread = [[NSThread alloc] initWithTarget:self selector:@selector(networkRequestThreadEntryPoint:) object:nil];
        [_networkRequestThread start];
    });
    return _networkRequestThread;
}

runloop启动前内部必须至少有一个 timer、observer、source。所以AFNetworking在runloop run 之前先创建了一个新的NSMachPort添加进去了。

通常情况下，调用者需要持有这个machport并在外部线程通过这个port发送消息到loop内，但此处添加port只是为了让runloop不至于退出，并没有用于实际的发送消息。

当需要这个后台线程执行任务时，AFNetworking通过调用 [NSObject performSelector:onThread:..] 将这个任务扔到了后台线程的 RunLoop 中。

- (void)start {
    [self.lock lock];
    if ([self isCancelled]) {
        [self performSelector:@selector(cancelConnection) onThread:[[self class] networkRequestThread] withObject:nil waitUntilDone:NO modes:[self.runLoopModes allObjects]];
    } else if ([self isReady]) {
        self.state = AFOperationExecutingState;
        [self performSelector:@selector(operationDidStart) onThread:[[self class] networkRequestThread] withObject:nil waitUntilDone:NO modes:[self.runLoopModes allObjects]];
    }
    [self.lock unlock];
}

7. PerformSelector 的实现原理？

• 当调用 NSObject 的 performSelecter:afterDelay: 后，实际上其内部会创建一个 Timer 并添加到当前线程的 RunLoop 中。所以如果当前线程没有 RunLoop，则这个方法会失效。
• 当调用 performSelector:onThread: 时，实际上其会创建一个 Timer 加到对应的线程去，同样的，如果对应线程没有 RunLoop 该方法也会失效。

8.PerformSelector:afterDelay:这个方法在子线程中是否起作用？

• 不起作用，子线程默认没有 Runloop，也就没有 Timer。可以使用 GCD的dispatch_after来实现

9.事件响应的过程？

• 苹果注册了一个 Source1 (基于 mach port 的) 用来接收系统事件，其回调函数为 __IOHIDEventSystemClientQueueCallback()。
• 当一个硬件事件(触摸/锁屏/摇晃等)发生后，首先由 IOKit.framework 生成一个 IOHIDEvent 事件并由 SpringBoard 接收。这个过程的详细情况可以参考这里。SpringBoard 只接收按键(锁屏/静音等)，触摸，加速，接近传感器等几种 Event，随后用 mach port 转发给需要的 App 进程。随后苹果注册的那个 Source1 就会触发回调，并调用 _UIApplicationHandleEventQueue() 进行应用内部的分发。
• _UIApplicationHandleEventQueue() 会把 IOHIDEvent 处理并包装成 UIEvent 进行处理或分发，其中包括识别 UIGesture/处理屏幕旋转/发送给 UIWindow 等。通常事件比如 UIButton 点击、touchesBegin/Move/End/Cancel 事件都是在这个回调中完成的。

10.手势识别的过程？

• 当 _UIApplicationHandleEventQueue() 识别了一个手势时，其首先会调用 Cancel 将当前的 touchesBegin/Move/End 系列回调打断。随后系统将对应的 UIGestureRecognizer 标记为待处理。
• 苹果注册了一个 Observer 监测 BeforeWaiting (Loop即将进入休眠) 事件，这个 Observer 的回调函数是 _UIGestureRecognizerUpdateObserver()，其内部会获取所有刚被标记为待处理的 GestureRecognizer，并执行GestureRecognizer 的回调。
• 当有 UIGestureRecognizer 的变化(创建/销毁/状态改变)时，这个回调都会进行相应处理。

11.CADispalyTimer和Timer哪个更精确？

• iOS设备的屏幕刷新频率是固定的，CADisplayLink在正常情况下会在每次刷新结束都被调用，精确度相当高。
• NSTimer的精确度就显得低了点，比如NSTimer的触发时间到的时候，runloop如果在阻塞状态，触发时间就会推迟到下一个runloop周期。并且 NSTimer新增了tolerance属性，让用户可以设置可以容忍的触发的时间的延迟范围。
• CADisplayLink使用场合相对专一，适合做UI的不停重绘，比如自定义动画引擎或者视频播放的渲染。NSTimer的使用范围要广泛的多，各种需要单次或者循环定时处理的任务都可以使用。
• 在UI相关的动画或者显示内容使用 CADisplayLink比起用NSTimer的好处就是我们不需要在格外关心屏幕的刷新频率了，因为它本身就是跟屏幕刷新同步的。

6.Runtime

1.Category 的实现原理？

• Category 实际上是 Category_t的结构体，在运行时，新添加的方法，都被以倒序插入到原有方法列表的最前面，所以不同的Category，添加了同一个方法，执行的实际上是最后一个。
• Category 在刚刚编译完的时候，和原来的类是分开的，只有在程序运行起来后，通过 Runtime ，Category 和原来的类才会合并到一起。

2.isa指针的理解，对象的isa指针指向哪里？isa指针有哪两种类型？

实例对象的 isa 指向类对象

类对象的 isa 指向元类对象

元类对象的 isa 指向元类的基类

• isa 有两种类型

纯指针，指向内存地址

NON_POINTER_ISA，除了内存地址，还存有一些其他信息

3.Objective-C 如何实现多重继承？

Object-c的类没有多继承,只支持单继承,如果要实现多继承的话，可使用如下几种方式间接实现

• 通过组合实现

A和B组合，作为C类的组件

• 通过协议实现

C类实现A和B类的协议方法

• 消息转发实现

forwardInvocation:方法

4.runtime 如何实现 weak 属性？

weak 此特质表明该属性定义了一种「非拥有关系」(nonowning relationship)。

为这种属性设置新值时，设置方法既不持有新值（新指向的对象），也不释放旧值（原来指向的对象）。

runtime 对注册的类，会进行内存布局，从一个粗粒度的概念上来讲，这时候会有一个 hash 表，这是一个全局表，表中是用 weak 指向的对象内存地址作为 key，用所有指向该对象的 weak 指针表作为 value。

当此对象的引用计数为 0 的时候会 dealloc，假如该对象内存地址是 a，那么就会以 a 为 key，在这个 weak 表中搜索，找到所有以 a 为键的 weak 对象，从而设置为 nil。

runtime 如何实现 weak 属性具体流程大致分为 3 步：

• 1、初始化时：runtime 会调用 objc_initWeak 函数，初始化一个新的 weak 指针指向对象的地址。
• 2、添加引用时：objc_initWeak 函数会调用 objc_storeWeak() 函数，objc_storeWeak() 的作用是更新指针指向（指针可能原来指向着其他对象，这时候需要将该 weak 指针与旧对象解除绑定，会调用到 weak_unregister_no_lock），如果指针指向的新对象非空，则创建对应的弱引用表，将 weak 指针与新对象进行绑定，会调用到 weak_register_no_lock。在这个过程中，为了防止多线程中竞争冲突，会有一些锁的操作。
• 3、释放时：调用 clearDeallocating 函数，clearDeallocating 函数首先根据对象地址获取所有 weak 指针地址的数组，然后遍历这个数组把其中的数据设为 nil，最后把这个 entry 从 weak 表中删除，最后清理对象的记录。

5.讲一下 OC 的消息机制

• OC中的方法调用其实都是转成了objc_msgSend函数的调用，给receiver（方法调用者）发送了一条消息（selector方法名）
• objc_msgSend底层有3大阶段，消息发送（当前类、父类中查找）、动态方法解析、消息转发

6.runtime具体应用

• 利用关联对象（AssociatedObject）给分类添加属性
• 遍历类的所有成员变量（修改textfield的占位文字颜色、字典转模型、自动归档解档）
• 交换方法实现（交换系统的方法）
• 利用消息转发机制解决方法找不到的异常问题
• KVC 字典转模型

7.runtime如何通过selector找到对应的IMP地址？

每一个类对象中都一个对象方法列表（对象方法缓存）

• 类方法列表是存放在类对象中isa指针指向的元类对象中（类方法缓存）。
• 方法列表中每个方法结构体中记录着方法的名称,方法实现,以及参数类型，其实selector本质就是方法名称,通过这个方法名称就可以在方法列表中找到对应的方法实现。
• 当我们发送一个消息给一个NSObject对象时，这条消息会在对象的类对象方法列表里查找。
• 当我们发送一个消息给一个类时，这条消息会在类的Meta Class对象的方法列表里查找。

8.简述下Objective-C中调用方法的过程

Objective-C是动态语言，每个方法在运行时会被动态转为消息发送，即：objc_msgSend(receiver, selector)，整个过程介绍如下：

• objc在向一个对象发送消息时，runtime库会根据对象的isa指针找到该对象实际所属的类

• 然后在该类中的方法列表以及其父类方法列表中寻找方法运行

• 如果，在最顶层的父类（一般也就NSObject）中依然找不到相应的方法时，程序在运行时会挂掉并抛出异常unrecognized selector sent to XXX

• 但是在这之前，objc的运行时会给出三次拯救程序崩溃的机会：

  Method resolution

  objc运行时会调用+resolveInstanceMethod:或者 +resolveClassMethod:，让你有机会提供一个函数实现。如果你添加了函数，那运行时系统就会重新启动一次消息发送的过程，否则 ，运行时就会移到下一步，消息转发（Message Forwarding）。

  Fast forwarding

  如果目标对象实现了-forwardingTargetForSelector:，Runtime 这时就会调用这个方法，给你把这个消息转发给其他对象的机会。 只要这个方法返回的不是nil和self，整个消息发送的过程就会被重启，当然发送的对象会变成你返回的那个对象。否则，就会继续Normal Fowarding。 这里叫Fast，只是为了区别下一步的转发机制。因为这一步不会创建任何新的对象，但下一步转发会创建一个NSInvocation对象，所以相对更快点。

  Normal forwarding

  这一步是Runtime最后一次给你挽救的机会。首先它会发送-methodSignatureForSelector:消息获得函数的参数和返回值类型。如果-methodSignatureForSelector:返回nil，Runtime则会发出-doesNotRecognizeSelector:消息，程序这时也就挂掉了。如果返回了一个函数签名，Runtime就会创建一个NSInvocation对象并发送-forwardInvocation:消息给目标对象。

9.load和initialize的区别？

两者都会自动调用父类的，不需要super操作，且仅会调用一次（不包括外部显示调用).

• load和initialize方法都会在实例化对象之前调用，以main函数为分水岭，前者在main函数之前调用，后者在之后调用。这两个方法会被自动调用，不能手动调用它们。
• load和initialize方法都不用显示的调用父类的方法而是自动调用，即使子类没有initialize方法也会调用父类的方法，而load方法则不会调用父类。
• load方法通常用来进行Method Swizzle，initialize方法一般用于初始化全局变量或静态变量。
• load和initialize方法内部使用了锁，因此它们是线程安全的。实现时要尽可能保持简单，避免阻塞线程，不要再使用锁。

10.怎么理解Objective-C是动态运行时语言？

• 主要是将数据类型的确定由编译时,推迟到了运行时。这个问题其实浅涉及到两个概念,运行时和多态。
• 简单来说, 运行时机制使我们直到运行时才去决定一个对象的类别,以及调用该类别对象指定方法。
• 多态:不同对象以自己的方式响应相同的消息的能力叫做多态。
• 意思就是假设生物类(life)都拥有一个相同的方法-eat;那人类属于生物,猪也属于生物,都继承了life后,实现各自的eat,但是调用是我们只需调用各自的eat方法。

也就是不同的对象以自己的方式响应了相同的消 息(响应了eat这个选择器)。因此也可以说,运行时机制是多态的基础.

KVO怎么用? 实现方式是什么。可不可以多次监控(addObserve)? 可不可以多次移除?? 线程 A 监控，线程 B 改变值， 最终体现在哪个线程

KVO怎么用：对被观察的对象添加观察者，同时被观察者要实现 改变方法的回调。

KVO的实现原理：Apple利用isa-swizzling来实现KVO，当某个类的对象属性第一次被观察时，系统会在运行期间动态的创建该类的派生类，在这个派生类中重写任何被观察属性的setter方法。每个类对象中都有一个isa指针，指向当前类。当一个类对象第一次被观察时，系统就会偷偷将isa指针指向动态生成的派生类，从而在给被监控属性赋值时，实际执行的是派生类的setter方法。键值观察通知依赖于NSObject的两个方法：willChangeValueForKey:和didChangeValueForKey:,在一个被观察属性发生改变之前，willChangeValueForKey:一定会被调用，这就会记录旧的值。而当改变发生后，didChangeValueForKey:会被调用，继而observeValueForKey:ofObject:change:context:也会被调用

可不可以多次监控：可以多次监控，能收到多次回调。

可不可以多次移除：不可以多次移除，添加和移除需要成对出现，只有已经注册了的观察者才可以被移除，否则会报错。

线程 A 监控，线程 B 改变值， 最终体现在哪个线程：体现在线程B，这是由派生类的setter方法来决定的，在哪个线程改变就体现在哪个线程。

7. 内存管理

1.什么情况使用weak关键字，相比assign有什么不同？

在ARC中，在有可能出现循环引用的时候，往往需要让其中一端使用weak来打破循环引用。比如delegate代理属性；当自身已经对某对象进行一次强引用，没必要再强引用一次，此时也会使用weak，比如从图形化界面引入到代码中 IBOutlet控件一般使用weak，当然也可以使用strong。

与assign不同之处在于，weak表明该属性定义了一种非拥有关系 nonowning relationship.为这种属性设置新值时，设置方法既不保留新值，也不释放旧值。此特质与assign类似，不同之处在于 属性所指的对象销毁时，属性值会设置为nil。

assign的设置方法只会执行针对 纯量类型（scalar type，比如 CGFloat或NSInteger等 ）的简单赋值操作。assign可以用非OC对象，而weak必须用于OC对象。

2.如何让自己的类用copy修饰符？如何重写带copy关键字的setter？

如果想让自定义对象具有拷贝功能，需要实现nscoping协议

如果自定义对象分为可变版本与不可变版本，那么需要同时实现NSCopying与NSMutableCopying协议。

首先，声明该类遵守NSCopying协议，实现协议方法：- (id)copyWithZone:(NSZone *)zone;

重写带copy关键字的setter方法

- (void)setName:(NSString *)name {
    //[_name release];
    _name = [name copy];
}

3.深拷贝与浅拷贝分别是什么？

浅拷贝只是对指针的拷贝，拷贝后两个指针指向同一个内存空间，深拷贝是对指针指向的内容进行拷贝，经深拷贝后的指针指向的是两个不同地址的指针。当对象中存在指针成员时，除了在复制对象时需要考虑自定义拷贝构造函数，还应该考虑以下两种情形：

• 当函数的参数为对象时，实参传递给形参的实际上是实参的一个拷贝对象，系统自动通过构造函数实现
• 当函数的返回值为一个对象时，该对象实际上是函数内对象的一个拷贝，用户返回函数调用处
• 一般来说我们倾向于 copy方法是浅拷贝，mutablecopy是深拷贝。但也不必然，这取决于copy协议及可变copy的具体实现的方法

4.@property的本质是什么？ivar、getter、setter是如何生成并添加到这个类中的？

属性的本质是 实例变量 ivar + 存取方法 getter + setter

属性作为oc的一项特性，主要作用在于封装对象中的数据，OC对象通常会把其所需要的数据保存为各种实例变量。实例变量一般通过存取方法来访问，getter用于读取变量的值，而setter用于写入变量的值

ivar、getter、setter是自动合成这个类中，完成属性定义后，编译器会自动编写访问这些属性所需的方法，这个过程叫做自动合成autosynthesis，需要强调的是，这个过程由编译器在编译器执行，所以编辑器里看不到这些合成方法synthesized method的源代码。除了生成方法 getter和setter之外，编译器还要自动向类中添加适当类型的实例变量，并在属性名前加下划线，以此作为实例变量的名字。也可以在类的实现代码里，通过@synthesize语法来制定实例变量的名字。

5.@protocol和category中如何使用@property

• 协议中使用属性只会生成setter和getter方法声明。我们在协议中使用属性的目的，是希望遵守我们协议的对象能够实现该属性。
• 分类使用属性也是只会生成setter和getter方法的声明，如果我们真的要给分类添加属性的实现，需要借助于运行时的两个函数:objc_setAssociatedObject和objc_getAssociatedObject

6.使用CADisplayLink、NSTimer有什么注意点？BAD_ACCESS在什么情况下出现？

CADisplayLink、NSTimer可能会造成循环引用，可以使用YYWeakProxy或者为CADisplayLink、NSTimer添加block来解决循环引用，或者使用GCD的定时器

BAD_ACCESS会在访问野指针时出现，就是说访问了一个已经被释放了的对象会出现。死循环。

7.iOS内存分区情况

• 栈区Stack：栈是向低地址扩展的数据结构，是一块连续的内存空间。内存由编译器自动分配释放；存放函数的参数、局部变量的值等；
• 堆区Heap：堆是向高地址扩展的数据结构，是不连续的内存区域，由程序员负责内存的分配与释放
• 全局区：全局变量和静态变量的存储是放在一块儿的，初始化的全局变量和静态变量在一块儿区域，未初始化的全局变量和未初始化的静态变量在相邻的另一块区域。程序结束后由系统释放。
• 常量区：常量字符串就是放在这里的，程序结束后由系统释放
• 代码区：存放函数体的二进制代码

注意：在iOS中，堆区的内存是应用程序共享的，堆中的内存分配是系统负责的。系统使用一个链表来维护所有已经分配的内存空间(系统紧紧记录，并不管理具体的内容)；变量使用结束后，需要释放内存，OC中是判断引用计数是否为0，如果是就说明没有任何变量使用该空间，那么系统将其回收；当一个app启动后，代码区、常量区、全局区大小就已经固定，因此指向这些区的指针不会产生崩溃性错误。而堆区和栈区是时时刻刻变化的（堆的创建销毁，栈的弹入弹出），所以当使用一个指针指向这个区域里面的内存时，一定要注意内存是否已经被释放，否则会出现野指针报错使程序崩溃。

8.iOS内存管理方式

• Tagged Pointer（小对象）

  tagged pointer 专门用来存储小的对象，例如NSNumber和NSDate。Tagged Pointer 指针的值不再是地址了，而是真正的值，所以，实际上它不再是一个对象了，它只是一个披着对象皮的普通变量而已，所以它的内存并不存储在堆中，也不需要malloc和free。在内存读取上有着3倍的效率，创建时比以前快106倍。obj_msgSend能识别Tagged Pointer，比如NSNumber和intVlaue方法，直接从指针提取数据。使用Tagged Pointer后，指针内存储的数据变成了Tag+Data也就是将数据直接存储在了指针中。NONPOINTER_ISA指针中存放与该对象内存相关的信息。苹果将isa设计成了联合体，在isa中存储了与该对象相关的一些内存信息，原因也如上面所说，并不需要64个二进制位全部用来存储指针。isa的结构如下

  // arm64 架构
  struct {
      uintptr_t nonpointer        : 1;  // 0:普通指针，1:优化过，使用位域存储更多信息
      uintptr_t has_assoc         : 1;  // 对象是否含有或曾经含有关联引用
      uintptr_t has_cxx_dtor      : 1;  // 表示是否有C++析构函数或OC的dealloc
      uintptr_t shiftcls          : 33; // 存放着 Class、Meta-Class 对象的内存地址信息
      uintptr_t magic             : 6;  // 用于在调试时分辨对象是否未完成初始化
      uintptr_t weakly_referenced : 1;  // 是否被弱引用指向
      uintptr_t deallocating      : 1;  // 对象是否正在释放
      uintptr_t has_sidetable_rc  : 1;  // 是否需要使用 sidetable 来存储引用计数
      uintptr_t extra_rc          : 19;  // 引用计数能够用 19 个二进制位存储时，直接存储在这里
  };
  

  这里的has_sidetable_rc和extra_rc，has_sidetable_rc表明该指针是否引用了sidetable散列表，之所以有这个选项，是因为少量的引用计数不会直接存放在sideTables表中的，对象的引用计数会先存放在extra_rc中，当其被存满时，才会存入相应的sidetables散列表中，sidetables中有很多sidetable，每个sidetable也都是一个散列表。而引用计数就包含在sidetable中

  散列表(引用计数表、弱引用表):引用计数要么存放在 isa 的 extra_rc 中，要么存放在引用计数表中，而引用计数表包含在一个叫 SideTable 的结构中，它是一个散列表，也就是哈希表。而 SideTable 又包含在一个全局的 StripeMap 的哈希映射表中，这个表的名字叫 SideTables。

  当一个对象访问sidetables时，首先会取得对象的地址，将地址进行哈希运算，与sidetables中sidetable的个数取余，最后得到的结果就是该对象所要防问的sidetable；在取得sidetable中的refcountmap表中再进行一次hash查找，找到该对象在引用计数表中的位置；如果该位置存在对应的引用计数，则对其进行操作。如果没有则创建一个对应的size_t对象，其实就是一个uint类型的无符号整型；若引用表也是一张hash表的结构，其内部包含了每个对象对应的弱引用表weak_entry_t，而weak_entry_t是一个结构体数组，其中包含的则是每一个弱引用对象所对应的弱引用指针。

9.循环引用

循环引用的实质：多个对象相互之间有强引用，不能释放让系统回收。

如何解决循环引用？

1、避免产生循环引用，通常是将 strong 引用改为 weak 引用。比如在修饰属性时用weak 在block内调用对象方法时，使用其弱引用，这里可以使用两个宏

#define WS(weakSelf) __weak __typeof(&*self)weakSelf = self; // 弱引用
#define ST(strongSelf) __strong __typeof(&*self)strongSelf = weakSelf;

//使用这个要先声明weakSelf 还可以使用__block来修饰变量 在MRC下，__block不会增加其引用计数，避免了循环引用 在ARC下，__block修饰对象会被强引用，无法避免循环引用，需要手动解除。

2、在合适时机去手动断开循环引用。通常我们使用第一种。

• 代理(delegate)循环引用属于相互循环引用

delegate 是iOS中开发中比较常遇到的循环引用，一般在声明delegate的时候都要使用弱引用 weak,或者assign,当然怎么选择使用assign还是weak，MRC的话只能用assign，在ARC的情况下最好使用weak，因为weak修饰的变量在释放后自动指向nil，防止野指针存在

• NSTimer循环引用属于相互循环使用

在控制器内，创建NSTimer作为其属性，由于定时器创建后也会强引用该控制器对象，那么该对象和定时器就相互循环引用了。如何解决呢？这里我们可以使用手动断开循环引用：如果是不重复定时器，在回调方法里将定时器invalidate并置为nil即可。如果是重复定时器，在合适的位置将其invalidate并置为nil即可

3、block循环引用

一个简单的例子：

@property (copy, nonatomic) dispatch_block_t myBlock;
@property (copy, nonatomic) NSString *blockString;

- (void)testBlock {
    self.myBlock = ^() {
        NSLog(@"%@",self.blockString);
    };
}

由于block会对block中的对象进行持有操作,就相当于持有了其中的对象，而如果此时block中的对象又持有了该block，则会造成循环引用。解决方案就是使用__weak修饰self即可

__weak typeof(self) weakSelf = self;

self.myBlock = ^() {
        NSLog(@"%@",weakSelf.blockString);
 };

并不是所有block都会造成循环引用。只有被强引用了的block才会产生循环引用 而比如dispatch_async(dispatch_get_main_queue(), ^{}),[UIView animateWithDuration:1 animations:^{}]这些系统方法等 或者block并不是其属性而是临时变量,即栈block

[self testWithBlock:^{
    NSLog(@"%@",self);
}];

- (void)testWithBlock:(dispatch_block_t)block {
    block();
}

还有一种场景，在block执行开始时self对象还未被释放，而执行过程中，self被释放了，由于是用weak修饰的，那么weakSelf也被释放了，此时在block里访问weakSelf时，就可能会发生错误(向nil对象发消息并不会崩溃，但也没任何效果)。

对于这种场景，应该在block中对 对象使用__strong修饰，使得在block期间对 对象持有，block执行结束后，解除其持有。

__weak typeof(self) weakSelf = self;

self.myBlock = ^() {

        __strong __typeof(self) strongSelf = weakSelf;

        [strongSelf test];
 };

10.ARC 的 retainCount 怎么存储的？

存在64张哈希表中，根据哈希算法去查找所在的位置，无需遍历，十分快捷

散列表（引用计数表、weak表）

• SideTables 表在 非嵌入式的64位系统中，有 64张 SideTable 表
• 每一张 SideTable 主要是由三部分组成。自旋锁、引用计数表、弱引用表。
• 全局的 引用计数 之所以不存在同一张表中，是为了避免资源竞争，解决效率的问题。
• 引用计数表 中引入了 分离锁的概念，将一张表分拆成多个部分，对他们分别加锁，可以实现并发操作，

提升执行效率

• 引用计数表（哈希表）
• 通过指针的地址，查找到引用计数的地址，大大提升查找效率
• 通过 DisguisedPtr(objc_object) 函数存储，同时也通过这个函数查找，这样就避免了循环遍历。

11.ARC 在编译时做了哪些工作？

根据代码执行的上下文语境，在适当的位置插入 retain，release

8.数据结构

1.数据结构的存储一般常用的有几种？各有什么特点？

• 顺序存储：比如数组，存储是按顺序的，再比如栈和队列等
• 链式存储：用一组任意的存储单元存储线性表的数据元素(这组存储单元可以是连续的,也可以是不连续的).它不要求逻辑上相邻的元素在物理位置上也相邻.因此它没有顺序存储结构所具有的弱点,但也同时失去了顺序表可随机存取的优点.

2.集合结构 线性结构 树形结构 图形结构

• 集合结构：一个集合，就是一个圆圈中有很多个元素，元素之间没有任何关系
• 线性结构：一条线上站着很多人，这条线不一定是直的，也可以是弯的。线性结构是n个数据元素的有序（次序）集合，线性结构是一对一关系。比如从a0到aN
• 树形结构：n个节点的有限集，树形结构指的是数据元素之间存在着“一对多”的树形关系的数据结构。树形结构是一对多的关系
• 图形结构：结点之间的结点之间的邻接关系可以是任意的，

3.单向链表 双向链表 循环链表 分别为什么？

• 单向链表：链表的链接方向是单向的，对链表的访问要通过顺序读取从头部开始

image.png

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

image.png

• 循环链表：循环链表是与单向链表一样，是一种链式的存储结构，所不同的是，循环链表的最后一个结点的指针是指向该循环链表的第一个结点或者表头结点，从而构成一个环形的链。

4.数组和链表区别有哪些？

• 数组：数组元素在内存上连续存放，可以通过下标查找元素；插入、删除需要移动大量元素，比较适用于元素很少变化的情况
• 链表：链表中的元素在内存中不是顺序存储，查找慢，插入删除只需要对指针重新赋值，效率高。

5.堆、栈和队列 分别是什么？

• 堆：堆是一种经过排序的树形结构，每一个节点都有一个值，通常我们所说的堆的数据结构是指二叉树。所以堆在数据结构中通常可以被看做是一棵树的数组对象。而且堆需要满足以下两个性质

  • 1 堆中某个节点的值总是不大于或者不小于其父节点的值
  • 2 堆总是一棵完全二叉树

  堆分为两种情况，有最大堆和最小堆。根节点最大的堆叫做最大堆，根节点最小的叫做最小堆。在一个摆放好元素的最小堆中，父节点的元素一定比子节点的元素小，但对于左右节点的大小没有规定谁大谁小。

  堆常用来实现优先队列，堆的存取是随意的，就像在图书馆的书架上取书，虽然书的摆放是有顺序的，但是我们想取任意一本书时不必像栈一样，先取出前面所有的书，书架这种机制不同于箱子，我们可以直接取出我们想要的书。

• 栈：栈是限定仅在表尾进行插入和删除操作的线性表。我们把允许插入和删除的一端称为栈顶，另一端称为栈低，不含任何数据元素的栈称为空栈。栈的特殊之处在于它限制了这个线性表的插入和删除位置，它始终只在栈顶进行。

  栈是一种具有后进先出的数据结构，又称为后进先出线性表，简称LIFO last in first out结构。

  栈中定义了一些操作，最要的是push和pop。push向栈顶压入一个元素，pop在栈顶移除一个元素，并将堆栈的大小减1

  栈的应用：递归

• 队列：队列是只允许在一端进行插入操作而在另一端进行删除操作的线性表。允许插入的一端称为队尾，允许删除的一端称为队头。它是一种特殊 的线性表，特殊在限定插入在队尾，删除在队头。和栈一样，队列是一种操作受限的线性表。

  队列是一种先进先出的数据结构，又称为先进先出数据表，简称FIFO。

6.输入一棵二叉树的根结点，求该树的深度？

二叉树的节点定义如下

struct BinaryTreeNode{
  int m_nValue;
  BinaryTreeNode* m_pLeft;
  BinaryTreeNode* m_pRight;
}

如果一棵树只有一个节点，它的深度为1.如果根节点只有左侧树而没有右侧树，那么树的深度应该是左侧树的深度+1；同样，如果根结点只有右子树而没有左子树，那么树的深度应该是其右子树的深度加1。如果既有左侧树又有右侧树，那该树的深度是左右树深度的较大值再+1

int TreeDepth(TreeNode *pRoot){
  if(pRoot == nullptr) return 0;
  int left = TreeDepth(pRoot->left);
  int right = TreeDepth(pRoot->right);
  return left > right ? left + 1 : right + 1 
}

7.输入一课二叉树的根结点，判断该树是不是平衡二叉树？

• 重复遍历节点

  先求出根节点的左右子树的深度，然后判断他们的深度相差不超过1，如果否则不是平衡二叉树，如果是再用同样的方法判断左右子树是否为平衡二叉树，如果都是则这就是一棵平衡二叉树。

• 遍历一遍节点

  遍历节点的同时记录下该节点的深度，避免重复访问。

  方法1：

  struct TreeNode{
    int val;
    TreeNode* left;
    TreeNode* right;
  };
  int TreeDepth(TreeNode* pRoot){
    if (pRoot == NULL) return 0;
    int left = TreeDepth(pRoot->left);
    int right = TreeDepth(pRoot->right);
    return left>right ? left + 1 : right + 1
  }
  
  bool IsBalanced(TreeNode* pRoot){
    if(pRoot == NULL) return true;
    int left = TreeDepth(pRoot->left);
    int right = TreeDepth(pRoot->right);
    int diff = left - right;
    if (diff > 1 || diff < -1) return flase;
    return IsBalanced(pRoot->left) && IsBalanced(pRoot->right);
  }
  

  方法2：

  bool IsBalanced_1(TreeNode* pRoot, int& depth){
    if (pRoot==NULL){
      depth = 0;
      return true;
    }
    int left,right;
    int diff;
    if (IsBalanced_1(pRoot->left,left) && IsBalanced_1(pRoot->right,right)){
      diff=left-right;
      if(diff < 1 || diff >= -1){
        depth = left > right ? left + 1 : right + 1;
        return true;
      }
    }
    return false;
  }
  
  bool IsBalancedTree(TreeNode* pRoot){
    int depth = 0;
    return IsBalanced_1(pRoot,depth);
  }
  

8.字符匹配 & 字符去重的方法

给你一个仅包含小写字母的字符串，请你去除字符串中重复的字母，使得每个字母只出现一次。需保证返回结果的字典序最小（要求不能打乱其他字符的相对位置）

1.什么叫字典序：26个英文字母的顺序

2.什么叫字符的相对位置，就是你只能删除重复的但是不能左右移动元素

我们来模拟下从第一个元素到最后一个元素的过程算法就出来了：

step1:c

step2:cb

step3:cba

step4:bac

step5:bacd

step6:acdb

按照我们的思维来写算法：定义一个结果集,依次遍历每个元素，结果集不存在就加入，如果存在就判断两个元素之间的元素有没有比当前元素小的，有的话就删掉之前的，比如bacdb，两个b之间有a比b小，所以要删掉之前的b，改成acdb

这里用另一个方法栈+标志来实现

说明：栈中存的元素满足两个条件之一就可以：1.元素都是递增的，2，当前元素在后续不在出现（过了这个村就没这个店了）

public static String removeDuplicateLetters(String s) {
        if (s == null || s.equals("")) {
            return "";
        }
        char[] strArr = s.toCharArray();
        return getResult(strArr);
    }
public static String getResult(char[] strArr) {
    String result = "";
    //记录所有几点的最后一个出现的位置
    Map<Character, Integer> memory = new HashMap<>();
    //记录哪些节点已经放入了栈中
    Map<Character, Boolean> memory2 = new HashMap<>();
    Stack<Character> stack = new Stack();
 
    for (int i = 0; i < strArr.length; i++) {
        memory.put(strArr[i], i);
        memory2.put(strArr[i], false);
    }
    //第一个元素特殊处理下便于理解
    stack.add(strArr[0]);
    memory2.put(strArr[0], true);
 
    for (int i = 1; i < strArr.length; i++) {
        //如果节点没有出现在栈中
        if (!memory2.get(strArr[i])) {
            //如果栈顶节点大于当前节点并且该节点后续还会出现，取出栈顶节点然后继续取栈第二节点继续比较
            while (!stack.isEmpty() && strArr[i] < stack.peek()) {
                if (memory.get(stack.peek()) > i) {
                    memory2.put(stack.peek(), false);
                    stack.pop();
                } else {
                    break;
                }
            }
            //当循环完了后，当前节点肯定大于栈顶元素，入栈，记录该节点已经入栈了
            stack.push(strArr[i]);
            memory2.put(strArr[i], true);
        }
    }
    StringBuilder stringBuilder = new StringBuilder();
    while (!stack.empty()) {
        stringBuilder.insert(0, stack.pop());
    }
    return stringBuilder.toString();
}
 
public static void main(String[] args) {
    String result = removeDuplicateLetters("bacacca");
    System.out.println(result);
}

9.算法

1.时间复杂度 / 空间复杂度

• 时间复杂度

  • 时间频度：一个算法执行所消耗的时间，从理论上是不能算出来的，必须上机运行测试才能知道，但我们不可能也没有必要对每个算法都上机测试。只需要知道哪个算法花费时间最多哪个算法花费时间最少就可以了。并且一个算法花费时间与算法中语句的执行次数成正比。哪个算法中语句执行次数多，它花费时间就多。一个算法中语句执行次数称为语句频度或时间频度，记为T(n)

  • 时间复杂度：一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n),使得当n趋近于无穷大时，T(n)/f(n)的极限值为不等于0的常数，则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n)) 称O(f(n)) 为算法的渐进时间复杂度，简称时间复杂度。在各种不同算法中,若算法中语句执行次数为一个常数,则时间复杂度为O(1),另外,在时间频度不相同时,时间复杂度有可能相同,如T(n)=n2+3n+4与T(n)=4n2+2n+1它们的频度不同,但时间复杂度相同,都为O(n2).

    按数量级递增排列,常见的时间复杂度有：

    O(1)称为常量级，算法的时间复杂度是一个常数。

    O(n)称为线性级，时间复杂度是数据量n的线性函数。

    O(n²)称为平方级，与数据量n的二次多项式函数属于同一数量级。

    O(n³)称为立方级，是n的三次多项式函数。

    O(logn)称为对数级，是n的对数函数。

    O(nlogn)称为介于线性级和平方级之间的一种数量级

    O(2ⁿ)称为指数级，与数据量n的指数函数是一个数量级。

    O(n!)称为阶乘级，与数据量n的阶乘是一个数量级。

    它们之间的关系是：O(1)<O(logn)<O(n)<O(nlogn)<O(n²)<O(n³)<O(2ⁿ)<O(n!)，随着问题规模n的不断增大,上述时间复杂度不断增大,算法的执行效率越低.

• 空间复杂度：评估程序执行所需要的存储空间。可以估算出程序堆计算机内存的使用程度。不包括算法程序代码和所处理的数据本身所占空间部分。通常用所使用额外空间的字节数表示，其算法比较简单，记为 S(n)=O(f(n)),其中n表示问题规模。

2.常用的排序算法有哪些？

常用的排序算法有：选择排序、冒泡排序、插入排序

都将数组分为已排序部分和未排序部分。

选择排序：已排序部分定义在左端，然后选择未排序的最小元素和未排序的第一个元素交互。

冒泡排序：已排序部分定义在右端，在遍历未排序部分的过程中进行交换，将最大元素交换到最右端。

插入排序：已排序部分定义在左端，将未排序部分的第一个元素插入到已排序部分合适的位置。

//选择排序：最值出现在起始端,
void selectSort(int * arr,int length){
  for (int i = 0; i < length -1 ;i++){//趟数
    for (int j = i+1;j < length; j++)//比较次数
    if (arr[i]>arr[j]){
      int temp = arr[i];
      arr[i] = arr[j];
      arr[j] = temp;
    }
  }
}
//冒泡排序：最值出现在末尾，比较的是相邻的元素
void bulletSort(int* arr,int length){
  for(int i = 0; i < length -1; i++){
    for(int j = 0; j< length - i - 1;j++){
      if (arr[j]>arr[j+1]){
        int temp = arr[j];
        arr[j] = arr[j+1];
        arr[j+1] = temp;
      }
    }
  }
}

/**
 *  折半查找：优化查找时间（不用遍历全部数据）
 *
 *  折半查找的原理：
 *   1> 数组必须是有序的
 *   2> 必须已知min和max（知道范围）
 *   3> 动态计算mid的值，取出mid对应的值进行比较
 *   4> 如果mid对应的值大于要查找的值，那么max要变小为mid-1
 *   5> 如果mid对应的值小于要查找的值，那么min要变大为mid+1
 *
 */ 
 
// 已知一个有序数组, 和一个key, 要求从数组中找到key对应的索引位置 
int findKey(int *arr, int length, int key) {
    int min = 0, max = length - 1, mid;
    while (min <= max) {
        mid = (min + max) / 2; //计算中间值
        if (key > arr[mid]) {
            min = mid + 1;
        } else if (key < arr[mid]) {
            max = mid - 1;
        } else {
            return mid;
        }
    }
    return -1;
}

3.字符串反转

void char_reverse (char *cha) {

    // 定义头部指针
    char *begin = cha;
    // 定义尾部指针
    char *end = cha + strlen(cha) -1;
    
    
    while (begin < end) {
        
        char temp = *begin;
        *(begin++) = *end;
        *(end--) = temp;
    }
}

4.链表反转（头差法）

struct Node* reverseList(struct Node *head)
{
    // 定义遍历指针，初始化为头结点
    struct Node *p = head;
    
    // 反转后的链表头部
    struct Node *newH = NULL;
    
    // 遍历链表
    while (p != NULL) {
        
        // 记录下一个结点
        struct Node *temp = p->next;
        // 当前结点的next指向新链表头部
        p->next = newH;
        // 更改新链表头部为当前结点
        newH = p;
        // 移动p指针
        p = temp;
    }
    
    // 返回反转后的链表头结点
    return newH;
}

5.如何查找第一个只出现一次的字符（Hash查找）

char findFirstChar(char* cha)
{
    char result = '\0';
    
    // 定义一个数组 用来存储各个字母出现次数
    int array[256];
    
    // 对数组进行初始化操作
    for (int i=0; i<256; i++) {
        array[i] =0;
    }
    // 定义一个指针 指向当前字符串头部
    char* p = cha;
    // 遍历每个字符
    while (*p != '\0') {
        // 在字母对应存储位置 进行出现次数+1操作
        array[*(p++)]++;
    }
    
    // 将P指针重新指向字符串头部
    p = cha;
    // 遍历每个字母的出现次数
    while (*p != '\0') {
        // 遇到第一个出现次数为1的字符，打印结果
        if (array[*p] == 1)
        {
            result = *p;
            break;
        }
        // 反之继续向后遍历
        p++;
    }
    
    return result;
}

6.如何查找两个子视图的共同父视图？

- (NSArray <UIView *> *)findCommonSuperView:(UIView *)viewOne other:(UIView *)viewOther
{
    NSMutableArray *result = [NSMutableArray array];
    
    // 查找第一个视图的所有父视图
    NSArray *arrayOne = [self findSuperViews:viewOne];
    // 查找第二个视图的所有父视图
    NSArray *arrayOther = [self findSuperViews:viewOther];
    
    int i = 0;
    // 越界限制条件
    while (i < MIN((int)arrayOne.count, (int)arrayOther.count)) {
        // 倒序方式获取各个视图的父视图
        UIView *superOne = [arrayOne objectAtIndex:arrayOne.count - i - 1];
        UIView *superOther = [arrayOther objectAtIndex:arrayOther.count - i - 1];
        
        // 比较如果相等 则为共同父视图
        if (superOne == superOther) {
            [result addObject:superOne];
            i++;
        }
        // 如果不相等，则结束遍历
        else{
            break;
        }
    }
    
    return result;
}

- (NSArray <UIView *> *)findSuperViews:(UIView *)view
{
    // 初始化为第一父视图
    UIView *temp = view.superview;
    // 保存结果的数组
    NSMutableArray *result = [NSMutableArray array];
    while (temp) {
        [result addObject:temp];
        // 顺着superview指针一直向上查找
        temp = temp.superview;
    }
    return result;
}

7.无序数组中的中位数(快排思想)

https://blog.csdn.net/weixin_42109012/article/details/91645051

//求一个无序数组的中位数
int findMedian(int a[], int aLen)
{
    int low = 0;
    int high = aLen - 1;
    
    int mid = (aLen - 1) / 2;
    int div = PartSort(a, low, high);
    
    while (div != mid)
    {
        if (mid < div)
        {
            //左半区间找
            div = PartSort(a, low, div - 1);
        }
        else
        {
            //右半区间找
            div = PartSort(a, div + 1, high);
        }
    }
    //找到了
    return a[mid];
}

int PartSort(int a[], int start, int end)
{
    int low = start;
    int high = end;
    
    //选取关键字
    int key = a[end];
    
    while (low < high)
    {
        //左边找比key大的值
        while (low < high && a[low] <= key)
        {
            ++low;
        }
        
        //右边找比key小的值
        while (low < high && a[high] >= key)
        {
            --high;
        }
        
        if (low < high)
        {
            //找到之后交换左右的值
            int temp = a[low];
            a[low] = a[high];
            a[high] = temp;
        }
    }
    
    int temp = a[high];
    a[high] = a[end];
    a[end] = temp;
    
    return low;
}

8.如何给定一个整数数组和一个目标值，找出数组中和为目标值的两个数。

- (void)viewDidLoad {

    [super viewDidLoad];

    NSArray *oriArray = @[@(2),@(3),@(6),@(7),@(22),@(12)];

    BOOL isHaveNums =  [self twoNumSumWithTarget:9 Array:oriArray];

    NSLog(@"%d",isHaveNums);
}


- (BOOL)twoNumSumWithTarget:(int)target Array:(NSArray<NSNumber *> *)array {
    
    NSMutableArray *finalArray = [NSMutableArray array];
    
    for (int i = 0; i < array.count; i++) {
        
        for (int j = i + 1; j < array.count; j++) {
            
            if ([array[i] intValue] + [array[j] intValue] == target) {
                
                [finalArray addObject:array[i]];
                [finalArray addObject:array[j]];
                NSLog(@"%@",finalArray);
                
                return YES;
            }
        }
    }
    return NO;
}