头条-最新iOS面试真题总结

关于面试题,可能没那么多时间来总结答案,有什么需要讨论的地方欢迎大家指教。主要记录一下准备过程,和面试的一些总结,希望能帮助到正在面试或者将要面试的同学吧。

头条

一面

1、自我介绍

2、项目相关

3、怎么自定义导航跳转

4、谈谈runtime的理解

5、KVC的用途

6、使用method swizzling要注意什么?(进行版本迭代的时候需要进行一些检验,防止系统库的函数发生了变化)

7、谈对引用计数的理解

8、谈谈runloop的理解

9、runloop有哪些状态

10、autoreleasepool的使用场景

11、TableView优化,怎么减少卡顿

12、copy assign retain weak关键词

13、JSON转Model

14、代码布局

15、多屏幕适配

16、HTTP请求头和响应头

17、Cookie

18、NSCache

19、自己设计一个缓存器

20、怎么实现LRU

21、SDWebImage

22、二叉树先序遍历(递归和非递归)

二面

1、MVC的一些缺点

2、讲一讲其它架构

3、你知道哪些编码方式

4、算法字符串翻转

5、多线程的方式和它们的区别

6、队列和线程的关系

7、一道线程安全的题

8、有哪些锁

9、属性的关键字

10、assign可以用于OC对象吗

11、copy和strong的区别

12、weak如何实现自动赋nil

13、为什么不可变对象要用copy

14、assing可以使用在对象中吗

15、Pod update和pod install的区别

16、layoutIfNeeded和setNeedsLayout的区别

17、抓包工具抓取HTTPS的原理

18、isEquel和hash的关系

19、bitmap的结构

20、可变数组的实现原理

21、如何hook一个对象的方法,而不影响其它对象

22、如何避免if else

23、自旋锁和互斥锁的区别

三面

1、介绍项目,主要介绍自己强项一点的地方

2、数组cop后里面的元素会复制一份新的吗

3、数组的浅拷贝与深拷贝

4、TCP为什么是三次握手和四次挥手

头条一直都是视频面,而且是一条龙服务。总体来说感觉不错,反正主要就是需要基础足够扎实;

快手-最新iOS面试真题总结

背景

面的是快手X3岗位,视频面试,不支持周末,但是可以选择晚上时间。视频面试是通过牛客网进行的,以下是记下来的各轮面试题,对于一些iOS基础知识就不做解答了。

一面

1、用递归写一个算法,计算从1到100的和。

1
2
3
4
5
6
7
8
9
10
11
func sum(value: Int) -> Int {
if value <= 0 {
return 0
}
var number = value
return value + sum(value: number - 1)
}
// 计算过程
let result = sum(value: 100)
print(result)
复制代码

写完算法之后又围绕着问了几个问题,都是算法基础:

  • 算法的时间复杂度是多少
  • 递归会有什么缺点
  • 不用递归能否实现,复杂度能否降到O(1)

2、property的作用是什么,有哪些关键词,分别是什么含义?

3、父类的property是如何查找的?

4、NSArrayNSDictionary应该如何选关键词?

5、copymuteCopy有什么区别,深复制和浅复制是什么意思,如何实现深复制?

6、用runtime做过什么事情?runtime中的方法交换是如何实现的?

7、讲一下对KVC合KVO的了解,KVC是否会调用setter方法?

8、__block有什么作用

9、说一下对GCD的了解,它有那些方法,分别是做什么用的?

10、对二叉树是否了解?

面试官是想接着问这方面的问题的。我当时说了不了解,然后就没有后续了。

二面

1、ARC和MRC的区别,iOS是如何管理引用计数的,什么情况下引用计数加1什么情况引用计数减一?

2、在MRC下执行[object autorelease]会发生什么,autorelease是如何实现的?

3、OC如何实现多继承?

这个当时没有答好。其实借助于消息转发,protocol和类别都可以间接实现多继承。

4、对设计模式有什么了解,讲一下其中一种是如何使用的。

5、有没有哪个开源库让你用的很舒服,讲一下让你舒服的地方。

6、一张100*100,RGBA的png图像解压之后占多大内存空间。

5、算法题

题目:给定一个个数字arr,判断数组arr中是否所有的数字都只出现过一次。

这个并没有要求写出来,说是提供思路就行了。我当时给的方案是在便利数组的时候,用一个字典把便利的元素存起来,如果在后面的便利过程中新元素在字典中存在过就说明,有重复数字出现。时间复杂度是O(n)。

当时也问了有没有办法进行优化,我当时想到了将数组转成Set,然后和原数组比较,两个集合的数量是否变化。

7、因为我跟他介绍自己Swift用的多一些,然后问了些Swift跟OC的区别,各自的优缺点。

8、为什么离职,有什么职业规划。

三面

1、给定一个Int型数组,用里面的元素组成一个最大数,因为数字可能非常大,用字符串输出。

1
2
3
输入: [3,30,34,5,9]
输出: 9534330
复制代码

这个是leetcode的179题,难度中等。面试官让先说思路,再去做题。事先说一下这个题我没有做过。当时的思路是用冒泡法进行排序,排序的前提是将较少位数的数字进行循环补齐,例如3和30的比较,变成33和30的比较,34和4的比较变成34和44的比较,然后将结果从大到小整合成字符串输出。

但是做题是却发现没那么简单,位数的补齐对于2位和3位数的比较还需要求位数的最小公倍数,将他们都转成6位数才能比较。在挣扎了5分钟做了就做罢了。

后来再去做这道题,其实这就是一个排序而已,只不过他的规则是按高位优先级更高的原则,而这一点跟字符串的比较保持一致,如果再加一些Swift的高阶函数,就可以写成:

1
2
3
4
5
6
7
8
9
10
11
12
func largestNumber(_ nums: [Int]) -> String {
let sort = nums.map {"\($0)"}.sorted { (lStr, rStr) -> Bool in
return lStr + rStr > rStr + lStr
}
let result = sort.joined()
if result.prefix(1) == "0" {
return "0"
} else {
return result
}
}
复制代码

2、项目中有这么一个方法func findfile(dir: String suffix: String) -> [String] ,可以通过输入文件夹目录,和后缀检索出所需的文件。

例如需要在某个文件中检索txt文件或者mp4文件,那就传入dir和suffix就行了。现在又有一些需求,例如需要检索utf8格式的txt或者h264编码的mp4,也会有一些例如查找最近一周更新过的文件这样的需求,你如何优化这个类,让它满足这些情况?

我首先想到的是这么多需求不可能一个方法就完成,需要根据不同场景拆出不同的方法,但是这些同属于文件操作,会有一个共同使用的方法就是检索文件。这个方法需要传入文件目录,然后递归的返回当前目录所有文件路径。外部不同场景的调用逻辑就用一个enum完成,不同值对应相同范围的不同种类。

面试官比较关注内部共用的文件检索怎么写,他说子文件如果过多怎么办,如何优化。我有点懵,查找文件至少是要遍历一遍的,子文件过多,这个应该是没法优化的啊。中间卡了一段时间,后来他给了提示说是不是可以用block实现,将文件路径返回出去,由外部决定当前文件是否可用,最终外部的调用类是这个样子。

1
2
3
4
5
//我的方案
//func findDir(_ dir: String) -> [String]
//block方案
func findDir(_ dir: String, block: ((String) -> Bool))
复制代码

我想来确实没毛病,用block返回内容至少不会将该目录的所有文件都由一个对象持有,而前面一堆的铺垫其实也都是为验证block方案的好处。

其实事后想下这个问题没啥难的,这种写法自己也有写过,但当时就是没想起来,可能前面一圈的铺垫给我带偏了吧,说亏也不亏,以后多多努力吧。

总结

整体来看,快手的面试题跟我在别处看到的iOS面试题对比要简单些。一面主要是基础知识,二面考察更全面一些,更多让自己谈一些对技术的理解,三面则是更偏实践一些。

算法虽然三轮都有,但相对比较简单,即使写不出来,有思路也是可以的。当然写出来肯定是加分项,所以大家准备面试时,应该都看一下。算法相关的,排序,数组,二叉树,这几类是重点。

字节跳动-最新iOS面试真题

字节一面内容:

1、  自我介绍

2、  介绍一下简历中的一个项目

3、  面向对象的三个要素

4、  多态?

5、  Java,python,OC运行效率孰高?

6、  Property,其中copy如何?

7、  Property(nonatomatic, copy) NSMutableArray有什么问题

8、  Copy和MutableCopy的区别

9、  解释下类别,原理

10、解释下封装,重载;

11、 OC存在多重继承吗?

12、了解表视图吗,解释一下复用原理

13、说明一下表视图的滑动卡顿的优化方法

14、viewDidLoad和viewDidAppear的调用时机(一次和多次的区别);

15、页面间的传值方式有哪些(公有属性,公有方法和协议,block传值,通知,extern全局变量传值,NSUserDefault简单数据存储传值);

16、通知和delegate的区别?

17、 通知的发送和接收是否在同一线程?

18、HTTP和HTTPS区别?

19、OC中多线程一般有几个方案?

20、了解NSURLConnection和Session吗?

21、说一下NSURLSession具体的实现原理

22、http的头部的几个码。;

23、编程题:实现一个二叉树的倒置。

字节二面内容:

1、老虎吃羊问题。(博弈论,老虎要吃羊,假设所有老虎是理智的,即首先为了生存,其次为了饱腹,老虎吃了羊后会变成羊,同样会被其他老虎吃掉。现在,N只老虎和1只羊,请问N为多少时,老虎们会吃羊。动态规划问题,奇数吃,偶数不吃。)

2、青蛙跳格子,斐波拉契数列;青蛙跳格子,斐波拉契数列;

3、熟悉使用什么框架?

4、如果让你自己实现SDWebImage的二级存储机制,你如果实现?

5、@autorelease{ NSString s;}和NSString s;有什么区别?

6、说一下你对autorelease的理解。

7、说一下对于http的理解?

8、http的返回状态码有了解吗?

9、为什么说http是无状态的?

10、为什么不用原生的APNS技术实现呢?

11、了解GCD吗?

12、说一下dispatch_group_t和dispatch_barrier_sync的区别吗?

13、了解NSOperation吗?

14、了解NSOperationQueue吗?

字节三面内容:

1、  算法题:求只有三项元素的数组中的顺序排列,时间复杂度要求O(n);

2、  说一下你对OC程序编译和连接方面的理解?

3、  说一下内存管理相关的操作?

4、  说一下响应链的原理?

5、  追问:hitTest有尝试过重写吗?

6、  http, session和cookie有了解过吗;

7、  线程和队列的关系?

8、  CALayer和UIView了解吗?

大厂常问iOS面试题--视图和图形篇

本篇我们来讲一下 【iOS面试题的视图&图形】相关的问题.

视图&图像相关

主要问题列表如下:

  1. AutoLayout的原理,性能如何
  2. UIView & CALayer的区别
  3. 事件响应链
  4. drawrect & layoutsubviews调用时机
  5. UI的刷新原理
  6. 隐式动画 & 显示动画区别
  7. 什么是离屏渲染
  8. imageName&imageWithContentsOfFile区别
  9. 多个相同的图片,会重复加载吗
  10. 图片是什么时候解码的,如何优化
  11. 图片渲染怎么优化
  12. 如果GPU的刷新率超过了iOS屏幕60Hz刷新率是什么现象,怎么解决

1.AutoLayout的原理,性能如何?

AutoLayout的原理

来历 一般大家都会认为Auto Layout这个东西是苹果自己搞出来的,其实不然,早在1997年Alan Borning, Kim Marriott, Peter Stuckey等人就发布了《Solving Linear Arithmetic Constraints for User Interface Applications》论文(论文地址:http://constraints.cs.washington.edu/solvers/uist97.html)提出了在解决布局问题的Cassowary constraint-solving算法实现,并且将代码发布在他们搭建的Cassowary网站上http://constraints.cs.washington.edu/cassowary/。后来更多开发者用各种语言来写Cassowary,比如说pybee用python写的https://github.com/pybee/cassowary。自从它发布以来JavaScript,.NET,JAVA,Smalltall和C++都有相应的库。2011年苹果将这个算法运用到了自家的布局引擎中,美其名曰Auto Layout。

论文下载链接比较慢,我下载了一份Cassowary原文放到了我的博客 大家可以自由下载.

AutoLayout的原理就是用Cassowary算法来将布局问题抽象成线性不等式,并分解成多个位置间的约束 因为多了计算视图大小frame的过程,所以性能肯定没有指定Frame坐标要快.

详细的原理以及高阶原理请参考戴铭老师的文章 戴铭老师写的 深入剖析Auto Layout,分析iOS各版本新增特性

性能如何?

下面是WWDC2018 High Performance Auto Layout中对比的iOS12和iOS11下分别使用自动布局的性能对比现场.

经过实验得出如下图标结论:

iOS12之前,视图嵌套的数量对性能的影响是呈指数级增长的,而iOS12优化之后对性能的影响是线性增长,对性能消耗不大。

无论如何优化也肯定不如CGRectFrame那样的设置更加直接,性能更好.

2.UIView & CALayer的区别

区别 UIView CALayer
继承父类 UIView:UIResponder:NSObject CALayer:NSObject
用途 可以处理触摸事件 不处理用户的交互,不参与响应事件传递
两者关系 有一个CALayer成员变量 eg: view.layer 是UIView的成员变量
分工 处理交互层事件并包装各种图形的简单设置 底层渲染图形,支持动画

3.事件响应链

下面这篇文章我已经在前几篇将runloop的时候提了不止一次,前列建议阅读,快手的同事大部分都以这个理解为标准

iOS触摸事件全家桶

4. drawrect & layoutsubviews调用时机

layoutSubviews:(相当于layoutSubviews()函数)在以下情况下会被调用:

  1. init初始化不会触发layoutSubviews。
  2. addSubview会触发layoutSubviews。
  3. 设置view的Frame会触发layoutSubviews (frame发生变化触发)。
  4. 滚动一个UIScrollView会触发layoutSubviews。
  5. 旋转Screen会触发父UIView上的layoutSubviews事件。
  6. 改变一个UIView大小的时候也会触发父UIView上的layoutSubviews事件。
  7. 直接调用setLayoutSubviews。

drawrect:(drawrect()函数)在以下情况下会被调用:

  1. drawrect:是在UIViewController的loadView:ViewDidLoad:方法之后调用.
  2. 当我们调用[UIFont的 sizeToFit]后,会触发系统自动调用drawRect:
  3. 当设置UIView的contentMode或者Frame后会立即触发触发系统调用drawRect:
  4. 直接调用setNeedsDisplay设置标记 或setNeedsDisplayInRect:的时候会触发drawRect:

知识点扩充: 当我们操作drawRect方法的时候实际是在操作内存中存放视图的backingStore区域,用于后续图形的渲染操作,如果不理解可以看下UIView的渲染过程.

5.UI的刷新原理

这个问题我不知道问的是不是iOS离屏渲染过程,我来简单的回到一下这个吧

iOS 的MainRunloop 是一个60fps 的回调,也就是说16.7ms(毫秒)会绘制一次屏幕在这过程中要完成以下的工作:

  • view的缓冲区创建
  • view内容的绘制(如果重写了 drawRect)
  • 接收和处理系统的触摸事件

我们看到的UI图形实际上是CPU和GPU不断配合工作的结果.经过UIView的渲染过程 后我们的UI会不间断的接收系统图给我们的事件.

由于主线程的runloop 一直在回调,我们的UI就得到了刷新的窗口,是渲染还是处理事件都是因为runloop不断工作的结果.前几篇我们学过 main线程的runloop默认是启动的.因为我们响应交互.

不知道我这样回答是否满足这个问题的答案.如果回答的不对烦请下方评论区留言 告知我将持续改进.

6.隐式动画 & 显示动画区别

隐式动画一直存在 如需关闭需设置 显式动画是不存在,如需显式 要开启

只需要观察动画执行完成的结果 比如: 一个简单UIView的frame移动 如果从A点移动到B点 移动完成 回到原始位置就是隐式动画

Core Animation 是显式动画.因为它既可以直接对其layer属性做动画,也可以覆盖默认的图层行为.

7.imageName&imageWithContentsOfFile区别

区别 UIView imageWithContentsOfFile
不同点 会图片缓存到内存中 无缓存

8.什么是离屏渲染

iOS离屏渲染的深入研究

9.多个相同的图片,会重复加载吗

不会,GPU有 像素点缓存的mask.

10.图片是什么时候解码的,如何优化

是加载到内存中,从UIImge->CGImage->CGImageSourceCreateWithData(data) 创建ImageSource变成bitmap位图,这些工作都是CoreAnimation在图片被加载到内存中存在在backingStore里,送给GPU流水线处理之前被解码.

如何优化

自己手动操作图片的编码API

CGImageSource开头的哪些,根据合理利用时机和操作系统资源调整出一套缓存小加载快的库.

参考PINRemoteImage或者YYWebImage开源

11.图片渲染怎么优化

可以从阴影,圆角入手.帧率,电量,图片的锯齿等等.

iOS开发-视图渲染与性能优化

12.如果GPU的刷新率超过了iOS屏幕60Hz刷新率是什么现象,怎么解决

现象是 图形清晰,场景逼真,但是一般arm芯片的GPU 刷新超过60Hz一定会超级费电,手机发热导致降频.FPS降低,因为低能耗电量不足,无法支持GPU高刷新率

解决办法只能用xcode自带工具检测,看渲染过程哪里可以优化.

总结

简单回答了一些图形相关的问题,大部分都是iOS离屏渲染,这个地方大家要认真学习.很多资料看起来比较耗时.

大厂常问iOS面试题--通知机制解析篇

简述

本文主要是针对iOS通知机制的全面解析,从接口到原理面面俱到。同时也解决了阿里、字节:一套高效的iOS面试题中关于通知的问题,相信看完此文再也不怕面试官问我任何通知相关问题了

由于苹果没有对相关源码开放,所以以GNUStep源码为基础进行研究,GNUStep虽然不是苹果官方的源码,但很具有参考意义,根据实现原理来猜测和实践,更重要的还可以学习观察者模式的架构设计

问题列表

先把之前的问题列出来,详细读完本文之后,你会找到答案

  1. 实现原理(结构设计、通知如何存储的、name&observer&SEL之间的关系等)
  2. 通知的发送时同步的,还是异步的
  3. NSNotificationCenter接受消息和发送消息是在一个线程里吗?如何异步发送消息
  4. NSNotificationQueue是异步还是同步发送?在哪个线程响应
  5. NSNotificationQueuerunloop的关系
  6. 如何保证通知接收的线程在主线程
  7. 页面销毁时不移除通知会崩溃吗
  8. 多次添加同一个通知会是什么结果?多次移除通知呢
  9. 下面的方式能接收到通知吗?为什么
1
2
3
4
5
// 发送通知
[[NSNotificationCenter defaultCenter] addObserver:self selector:@selector(handleNotification:) name:@"TestNotification" object:@1];
// 接收通知
[NSNotificationCenter.defaultCenter postNotificationName:@"TestNotification" object:nil];
复制代码

关键类结构

NSNotification

用于描述通知的类,一个NSNotification对象就包含了一条通知的信息,所以当创建一个通知时通常包含如下属性:

1
2
3
4
5
6
7
8
9
10
@interface NSNotification : NSObject <NSCopying, NSCoding>
...
/* Querying a Notification Object */

- (NSString*) name; // 通知的name
- (id) object; // 携带的对象
- (NSDictionary*) userInfo; // 配置信息

@end
复制代码

一般用于发送通知时使用,常用api如下:

1
2
- (void)postNotification:(NSNotification *)notification;
复制代码

NSNotificationCenter

这是个单例类,负责管理通知的创建和发送,属于最核心的类了。而NSNotificationCenter类主要负责三件事

  1. 添加通知
  2. 发送通知
  3. 移除通知

核心API如下:

1
2
3
4
5
6
7
8
9
10
// 添加通知
- (void)addObserver:(id)observer selector:(SEL)aSelector name:(nullable NSNotificationName)aName object:(nullable id)anObject;
// 发送通知
- (void)postNotification:(NSNotification *)notification;
- (void)postNotificationName:(NSNotificationName)aName object:(nullable id)anObject;
- (void)postNotificationName:(NSNotificationName)aName object:(nullable id)anObject userInfo:(nullable NSDictionary *)aUserInfo;
// 删除通知
- (void)removeObserver:(id)observer;

复制代码

NSNotificationQueue

功能介绍

通知队列,用于异步发送消息,这个异步并不是开启线程,而是把通知存到双向链表实现的队列里面,等待某个时机触发时调用NSNotificationCenter的发送接口进行发送通知,这么看NSNotificationQueue最终还是调用NSNotificationCenter进行消息的分发

另外NSNotificationQueue是依赖runloop的,所以如果线程的runloop未开启则无效,至于为什么依赖runloop下面会解释

NSNotificationQueue主要做了两件事:

  1. 添加通知到队列
  2. 删除通知

核心API如下:

1
2
3
4
5
6
// 把通知添加到队列中,NSPostingStyle是个枚举,下面会介绍
- (void)enqueueNotification:(NSNotification *)notification postingStyle:(NSPostingStyle)postingStyle;
// 删除通知,把满足合并条件的通知从队列中删除
- (void)dequeueNotificationsMatching:(NSNotification *)notification coalesceMask:(NSUInteger)coalesceMask;

复制代码

队列的合并策略和发送时机

把通知添加到队列等待发送,同时提供了一些附加条件供开发者选择,如:什么时候发送通知、如何合并通知等,系统给了如下定义

1
2
3
4
5
6
7
8
9
10
11
12
13
// 表示通知的发送时机
typedef NS_ENUM(NSUInteger, NSPostingStyle) {
NSPostWhenIdle = 1, // runloop空闲时发送通知
NSPostASAP = 2, // 尽快发送,这种情况稍微复杂,这种时机是穿插在每次事件完成期间来做的
NSPostNow = 3 // 立刻发送或者合并通知完成之后发送
};
// 通知合并的策略,有些时候同名通知只想存在一个,这时候就可以用到它了
typedef NS_OPTIONS(NSUInteger, NSNotificationCoalescing) {
NSNotificationNoCoalescing = 0, // 默认不合并
NSNotificationCoalescingOnName = 1, // 只要name相同,就认为是相同通知
NSNotificationCoalescingOnSender = 2 // object相同
};
复制代码

GSNotificationObserver

这个类是GNUStep源码中定义的,它的作用是代理观察者,主要用来实现接口:addObserverForName:object: queue: usingBlock:时用到,即要实现在指定队列回调block,那么GSNotificationObserver对象保存了queueblock信息,并且作为观察者注册到通知中心,等到接收通知时触发了响应方法,并在响应方法中把block抛到指定queue中执行,定义如下:

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
29
30
31
32
33
@implementation GSNotificationObserver
{
NSOperationQueue *_queue; // 保存传入的队列
GSNotificationBlock _block; // 保存传入的block
}
- (id) initWithQueue: (NSOperationQueue *)queue
block: (GSNotificationBlock)block
{
......初始化操作
}

- (void) dealloc
{
....
}
// 响应接收通知的方法,并在指定队列中执行block
- (void) didReceiveNotification: (NSNotification *)notif
{
if (_queue != nil)
{
GSNotificationBlockOperation *op = [[GSNotificationBlockOperation alloc]
initWithNotification: notif block: _block];

[_queue addOperation: op];
}
else
{
CALL_BLOCK(_block, notif);
}
}

@end
复制代码

存储容器

上面介绍了一些类的功能,但是要想实现通知中心的逻辑必须设计一套合理的存储结构,对于通知的存储基本上围绕下面几个结构体来做(大致了解下,后面章节会用到),后面会详细介绍具体逻辑的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 根容器,NSNotificationCenter持有
typedef struct NCTbl {
Observation *wildcard; /* 链表结构,保存既没有name也没有object的通知 */
GSIMapTable nameless; /* 存储没有name但是有object的通知 */
GSIMapTable named; /* 存储带有name的通知,不管有没有object */
...
} NCTable;

// Observation 存储观察者和响应结构体,基本的存储单元
typedef struct Obs {
id observer; /* 观察者,接收通知的对象 */
SEL selector; /* 响应方法 */
struct Obs *next; /* Next item in linked list. */
...
} Observation;

复制代码

注册通知

正式开始“注册通知”的深入研究,注册通知有几个常用方法,但只需要研究典型的一两个就够了,原理都是一样的

目前只介绍NSNotificationCenter的注册流程,NSNotificationQueue的方式在下面章节单独拎出来解释

接口1

直接看源码(精简版便于理解)

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
/*
observer:观察者,即通知的接收者
selector:接收到通知时的响应方法
name: 通知name
object:携带对象
*/
- (void) addObserver: (id)observer
selector: (SEL)selector
name: (NSString*)name
object: (id)object {
// 前置条件判断
......

// 创建一个observation对象,持有观察者和SEL,下面进行的所有逻辑就是为了存储它
o = obsNew(TABLE, selector, observer);

/*======= case1: 如果name存在 =======*/
if (name) {
//-------- NAMED是个宏,表示名为named字典。以name为key,从named表中获取对应的mapTable
n = GSIMapNodeForKey(NAMED, (GSIMapKey)(id)name);
if (n == 0) { // 不存在,则创建
m = mapNew(TABLE); // 先取缓存,如果缓存没有则新建一个map
GSIMapAddPair(NAMED, (GSIMapKey)(id)name, (GSIMapVal)(void*)m);
...
}
else { // 存在则把值取出来 赋值给m
m = (GSIMapTable)n->value.ptr;
}
//-------- 以object为key,从字典m中取出对应的value,其实value被MapNode的结构包装了一层,这里不追究细节
n = GSIMapNodeForSimpleKey(m, (GSIMapKey)object);
if (n == 0) {// 不存在,则创建
o->next = ENDOBS;
GSIMapAddPair(m, (GSIMapKey)object, (GSIMapVal)o);
}
else {
list = (Observation*)n->value.ptr;
o->next = list->next;
list->next = o;
}
}
/*======= case2:如果name为空,但object不为空 =======*/
else if (object) {
// 以object为key,从nameless字典中取出对应的value,value是个链表结构
n = GSIMapNodeForSimpleKey(NAMELESS, (GSIMapKey)object);
// 不存在则新建链表,并存到map中
if (n == 0) {
o->next = ENDOBS;
GSIMapAddPair(NAMELESS, (GSIMapKey)object, (GSIMapVal)o);
}
else { // 存在 则把值接到链表的节点上
...
}
}
/*======= case3:name 和 object 都为空 则存储到wildcard链表中 =======*/
else {
o->next = WILDCARD;
WILDCARD = o;
}
}
复制代码

逻辑说明

从上面介绍的存储容器中我们了解到NCTable结构体中核心的三个变量以及功能:wildcardnamednameless,在源码中直接用宏定义表示了:WILDCARDNAMELESSNAMED,下面逻辑会用到

建议如果看文字说明觉得复杂不好理解,就看看下节介绍的存储关系图

case1: 存在name(无论object是否存在)

  1. 注册通知,如果通知的name存在,则以name为key从named字典中取出值n(这个n其实被MapNode包装了一层,便于理解这里直接认为没有包装),这个n还是个字典,各种判空新建逻辑不讨论
  2. 然后以object为key,从字典n中取出对应的值,这个值就是Observation类型(后面简称obs)的链表,然后把刚开始创建的obs对象o存储进去

数据结构关系图

这里就回答了上述问题列表的问题1的一部分,现在梳理下存储关系

如果注册通知时传入name,那么会是一个双层的存储结构

  1. 找到NCTable中的named表,这个表存储了还有name的通知
  2. name作为key,找到value,这个value依然是一个map
  3. map的结构是以object作为key,obs对象为value,这个obs对象的结构上面已经解释,主要存储了observer & SEL

case2: 只存在object

  1. object为key,从nameless字典中取出value,此value是个obs类型的链表
  2. 把创建的obs类型的对象o存储到链表中

数据结构关系图

只存在object时存储只有一层,那就是objectobs对象之间的映射

case3: 没有name和object

这种情况直接把obs对象存放在了Observation  *wildcard  链表结构中

接口2

源码

接口功能: 此接口实现的功能是在接收到通知时,在指定队列queue执行block

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 这个api使用频率较低,怎么实现在指定队列回调block的,值得研究
- (id) addObserverForName: (NSString *)name
object: (id)object
queue: (NSOperationQueue *)queue
usingBlock: (GSNotificationBlock)block
{
// 创建一个临时观察者
GSNotificationObserver *observer =
[[GSNotificationObserver alloc] initWithQueue: queue block: block];
// 调用了接口1的注册方法
[self addObserver: observer
selector: @selector(didReceiveNotification:)
name: name
object: object];

return observer;
}
复制代码

逻辑说明

这个接口依赖于接口1,只是多了一层代理观察者GSNotificationObserver,在关键类结构中已经介绍了它,设计思路值得学习

  1. 创建一个GSNotificationObserver类型的对象observer,并把queueblock保存下来
  2. 调用接口1进行通知的注册
  3. 接收到通知时会响应observerdidReceiveNotification:方法,然后在didReceiveNotification:中把block抛给指定的queue去执行

小结

  1. 从上述介绍可以总结,存储是以nameobject为维度的,即判定是不是同一个通知要从nameobject区分,如果他们都相同则认为是同一个通知,后面包括查找逻辑、删除逻辑都是以这两个为维度的,问题列表中的第九题也迎刃而解了
  2. 理解数据结构的设计是整个通知机制的核心,其他功能只是在此基础上扩展了一些逻辑
  3. 存储过程并没有做去重操作,这也解释了为什么同一个通知注册多次则响应多次

发送通知

源码

发送通知的核心逻辑比较简单,基本上就是查找和调用响应方法,核心函数如下

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
// 发送通知
- (void) postNotificationName: (NSString*)name
object: (id)object
userInfo: (NSDictionary*)info
{
// 构造一个GSNotification对象, GSNotification继承了NSNotification
GSNotification *notification;
notification = (id)NSAllocateObject(concrete, 0, NSDefaultMallocZone());
notification->_name = [name copyWithZone: [self zone]];
notification->_object = [object retain];
notification->_info = [info retain];

// 进行发送操作
[self _postAndRelease: notification];
}
//发送通知的核心函数,主要做了三件事:查找通知、发送、释放资源
- (void) _postAndRelease: (NSNotification*)notification {
//step1: 从named、nameless、wildcard表中查找对应的通知
...
//step2:执行发送,即调用performSelector执行响应方法,从这里可以看出是同步的
[o->observer performSelector: o->selector
withObject: notification];
//step3: 释放资源
RELEASE(notification);
}

复制代码

逻辑说明

其实上述代码注释说的很清晰了,主要做了三件事

  1. 通过name & object 查找到所有的obs对象(保存了observersel),放到数组中
  2. 通过performSelector:逐一调用sel,这是个同步操作
  3. 释放notification对象

小结

从源码逻辑可以看出发送过程的概述:从三个存储容器中:namednamelesswildcard去查找对应的obs对象,然后通过performSelector:逐一调用响应方法,这就完成了发送流程

核心点:

  1. 同步发送
  2. 遍历所有列表,即注册多次通知就会响应多次

删除通知

这里源码太长而且基本上都是查找删除逻辑,不一一列举,感兴趣的去下载源码看下吧 要注意的点:

  1. 查找时仍然以nameobject为维度的,再加上observer做区分
  2. 因为查找时做了这个链表的遍历,所以删除时会把重复的通知全都删除掉
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 删除已经注册的通知
- (void) removeObserver: (id)observer
name: (NSString*)name
object: (id)object {
if (name == nil && object == nil && observer == nil)
return;
...
}

- (void) removeObserver: (id)observer
{
if (observer == nil)
return;

[self removeObserver: observer name: nil object: nil];
}
复制代码

异步通知

上面介绍的NSNotificationCenter都是同步发送的,而这里介绍关于NSNotificationQueue的异步发送,从线程的角度看并不是真正的异步发送,或可称为延时发送,它是利用了runloop的时机来触发的

入队

下面为精简版的源码,看源码的注释,基本上能明白大致逻辑

  1. 根据coalesceMask参数判断是否合并通知
  2. 接着根据postingStyle参数,判断通知发送的时机,如果不是立即发送则把通知加入到队列中:_asapQueue_idleQueue

核心点:

  1. 队列是双向链表实现
  2. 当postingStyle值是立即发送时,调用的是NSNotificationCenter进行发送的,所以NSNotificationQueue还是依赖NSNotificationCenter进行发送
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
29
30
31
32
33
34
35
/*
* 把要发送的通知添加到队列,等待发送
* NSPostingStyle 和 coalesceMask在上面的类结构中有介绍
* modes这个就和runloop有关了,指的是runloop的mode
*/
- (void) enqueueNotification: (NSNotification*)notification
postingStyle: (NSPostingStyle)postingStyle
coalesceMask: (NSUInteger)coalesceMask
forModes: (NSArray*)modes
{
......
// 判断是否需要合并通知
if (coalesceMask != NSNotificationNoCoalescing) {
[self dequeueNotificationsMatching: notification
coalesceMask: coalesceMask];
}
switch (postingStyle) {
case NSPostNow: {
...
// 如果是立马发送,则调用NSNotificationCenter进行发送
[_center postNotification: notification];
break;
}
case NSPostASAP:
// 添加到_asapQueue队列,等待发送
add_to_queue(_asapQueue, notification, modes, _zone);
break;

case NSPostWhenIdle:
// 添加到_idleQueue队列,等待发送
add_to_queue(_idleQueue, notification, modes, _zone);
break;
}
}
复制代码

发送通知

这里截取了发送通知的核心代码,这个发送通知逻辑如下:

  1. runloop触发某个时机,调用GSPrivateNotifyASAP()GSPrivateNotifyIdle()方法,这两个方法最终都调用了notify()方法
  2. notify()所做的事情就是调用NSNotificationCenterpostNotification:进行发送通知
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
29
30
31
32
33
static void notify(NSNotificationCenter *center, 
NSNotificationQueueList *list,
NSString *mode, NSZone *zone)
{
......
// 循环遍历发送通知
for (pos = 0; pos < len; pos++)
{
NSNotification *n = (NSNotification*)ptr[pos];

[center postNotification: n];
RELEASE(n);
}
......
}
// 发送_asapQueue中的通知
void GSPrivateNotifyASAP(NSString *mode)
{
notify(item->queue->_center,
item->queue->_asapQueue,
mode,
item->queue->_zone);
}
// 发送_idleQueue中的通知
void GSPrivateNotifyIdle(NSString *mode)
{
notify(item->queue->_center,
item->queue->_idleQueue,
mode,
item->queue->_zone);
}

复制代码

小结

对于NSNotificationQueue总结如下

  1. 依赖runloop,所以如果在其他子线程使用NSNotificationQueue,需要开启runloop
  2. 最终还是通过NSNotificationCenter进行发送通知,所以这个角度讲它还是同步的
  3. 所谓异步,指的是非实时发送而是在合适的时机发送,并没有开启异步线程

主线程响应通知

异步线程发送通知则响应函数也是在异步线程,如果执行UI刷新相关的话就会出问题,那么如何保证在主线程响应通知呢?

其实也是比较常见的问题了,基本上解决方式如下几种:

  1. 使用addObserverForName: object: queue: usingBlock方法注册通知,指定在mainqueue上响应block
  2. 在主线程注册一个machPort,它是用来做线程通信的,当在异步线程收到通知,然后给machPort发送消息,这样肯定是在主线程处理的,具体用法去网上资料很多,苹果官网也有

总结

本文写的内容比较多,以GNUStep源码为基础进行研究,全面阐述了通知的存储、发送、异步发送等原理,对研究学习有很大帮助

大厂常问iOS面试题--Runloop&KVO篇

前言

今天这一篇我们来讲一下 Runloop和KVO

本章的主要回答的问题如下:

Runloop

  • app如何接收到触摸事件的
  • 为什么只有主线程的runloop是开启的
  • 为什么只在主线程刷新UI
  • PerformSelector和runloop的关系
  • 如何使线程保活

KVO

  • 实现原理
  • 如何手动关闭kvo
  • 通过KVC修改属性会触发KVO么
  • 哪些情况下使用kvo会崩溃,怎么防护崩溃
  • kvo的优缺点

Runloop

作为一个合格的iOS开发者必须对runloop有一个更深入的了解,下面我们来回答一下 相关问题

1.app如何接收到触摸事件的

回答这个问题前请认真阅读一下 iOS触摸事件全家桶

通过上图可以看出整个流程就是 我们app启动默认会通过machPort监听端口的方式 来接受IOHIDEvent 来接收和处理触摸事件.

2.为什么只有主线程的runloop是开启的

mian()函数中调用UIApplicationMain,这里会创建一个主线程,用于UI处理,为了让程序可以一直运行并接收事件,所以在主线程中开启一个runloop,让主线程常驻.

3.为什么只在主线程刷新UI

我们所有用到的UI都是来自于UIKit这个基础库.因为objc不是一门线程安全的语言所以存在多线程读写不同步的问题,如果使用加锁的方式操作系统开销很大,会耗费大量的系统资源(内存、时间片轮转、cpu处理速度…),加上上面讲到的系统事件的接收处理都在主线程,如果UI异步线程的话 还会存在 同步处理事件的问题,所以多点触摸手势等一些事件要保持和UI在同一个线程相对是最优解.

另一方面是 屏幕的渲染是 60帧(60Hz/秒), 也就是1秒钟回调60次的频率,(iPad Pro 是120Hz/秒),我们的runloop 理想状态下也会按照时钟周期 回调60次(iPad Pro 120次), 这么高频率的调用是为了 屏幕图像显示能够垂直同步 不卡顿.在异步线程的话是很难保证这个处理过程的同步更新. 即便能保证的话 相对主线程而言 系统资源开销 线程调度等等将会占据大部分资源和在同一个线程只专门干一件事有点得不偿失.

4.PerformSelector和runloop的关系

当调用NSObect的 performSelector:相关的时候,内部会创建一个timer定时器添加到当前线程的runloop中,如果当前线程没有启动runloop,则该方法不会被调用.

开发中遇到最多的问题就是这个performSelector: 导致对象的延迟释放,这里开发过程中注意一下,可以用单次的NSTimer替代.

详细可以参考Runloop与performSelector

5.如何使线程保活?

想要线程保活的话就开启该线程的runloop即可,注意:在NSThread执行的方法中添加while(true){},这样是模拟runloop的运行原理,结合GCD的信号量,在{}代码块中处理任务.

但是注意 开启runloop的方法要正确

如下代码

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
29
30
31
32
33
34
35
36
37
38
39
//测试开启线程
- (void)memoryTest {
for (int i = 0; i < 100000; ++i) {
NSThread *thread = [[NSThread alloc] initWithTarget:self selector:@selector(run) object:nil];
[thread start];
[self performSelector:@selector(stopThread) onThread:thread withObject:nil waitUntilDone:YES];
}
}
//线程停止
- (void)stopThread {
CFRunLoopStop(CFRunLoopGetCurrent());
NSThread *thread = [NSThread currentThread];
[thread cancel];
}
//运行线程的runloop 注意 意添加的那个空port,否则会出现内存泄露
- (void)run {
@autoreleasepool {
NSLog(@"current thread = %@", [NSThread currentThread]);
NSRunLoop *runLoop = [NSRunLoop currentRunLoop];
if (!self.emptyPort) {
self.emptyPort = [NSMachPort port];
}
[runLoop addPort:self.emptyPort forMode:NSDefaultRunLoopMode];
[runLoop runMode:NSRunLoopCommonModes beforeDate:[NSDate distantFuture]];
}
}
//下列代码用于模拟线程内部做的一些耗时任务
- (void)printSomething {
NSLog(@"current thread = %@", [NSThread currentThread]);
[self performSelector:@selector(printSomething) withObject:nil afterDelay:1];
}
//模拟手动点击按钮 让 runloop停掉
- (void)stopButtonDidClicked:(id)sender {
[self performSelector:@selector(stopRunloop) onThread:self.thread withObject:nil waitUntilDone:YES];
}

- (void)stopRunloop {
CFRunLoopStop(CFRunLoopGetCurrent());
}

详细请参考:iOS开发深入研究Runloop与线程保活

KVO

在开发过程中我们经常使用KVO,下面解答一下KVO相关的问题.

KVO的实现原理

通过runtime派生子类的方式 复写相关需要KVO监听的属性,在该属性setter之前和之后调用NSObject的监听方法,这样KVO就实现了属性变换前后的回调.

KVO派生的子类具体格式应该是:NSKVONotifying_+类名的类 eg: NSKVONotifying_Person

下面示例代码为Person类的name添加KVO的模拟实验

1
2
3
4
5
6
7
8
9
10
11
12
13
- (void)setName:(NSString *)name{
_NSSetObjectValueAndNotify();
}

void _NSSetObjectValueAndNotify {
[self willChangeValueForKey:@"name"];
[super setName:name];
[self didChangeValueForKey:@"name"];
}

- (void)didChangeValueForKey:(NSString *)key{
[observe observeValueForKeyPath:key ofObject:self change:nil context:nil];
}

问题来了如何动态创建类呢?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//动态创建XXCustomClass
Class customClass = objc_allocateClassPair([NSObject class], "XXCustomClass", 0);
// 添加实例变量
class_addIvar(customClass, "age", sizeof(int), 0, "i");
// 动态添加方法
class_addMethod(customClass, @selector(hahahha), (IMP)hahahha, "V@:");

//需要实现的方法
void hahahha(id self, SEL _cmd)
{
NSLog(@"hahahha====");
}

- (void)hahahha{

}

//最后注册到运行时环境
objc_registerClassPair(customClass);

V@:表示方法的参数和返回值

具体原理以及自定义实现KVO可以参考KVO详解及底层实现

如何手动关闭KVO?

被观察的对象复写如下方法 返回NO即可关闭KVO

1
2
3
+ (BOOL)automaticallyNotifiesObserversForKey:(NSString *)key {
return NO;
}

如果关闭后还想触发 KVO的话 修改需要手动调用在变量setter的前后 主动调用 willChangeValueForKey:didChangeValueForKey:

通过KVC修改属性会触发KVO么?

会的

哪些情况下使用kvo会崩溃,怎么防护崩溃?

使用不当 会crash,比如:

  • 添加和移出不是成对出现且存在多线程添加KVO的情况,经常遇到的crash是移出 - 内存dealloc的时候 或者对象销毁前没有正确移出Observer

如何防护?

1.注意移出对象 匹配 2.内存野指针问题,一定要在对象销毁前移出观察者 3.可以使用第三方库BlockKit添加KVO,blockkit内部会自动移除Observer避免crash.

KVO的优缺点

优点:

  • 方便两个对象间同步状态(keypath)更加方便,一般都是在A类要观察B类的属性的变化.
  • 非侵入式的得到某内部对象的状态改变并作出响应.(就是在不改变原来对象类的代码情况下即可做出对该对象的状态变化进行监听)
  • 可以嵌入更改前后的两个时机的状态. - 可以通过Keypaths对嵌套对象的监听.

缺点:

  • 需要手动移除观察者,不移除容易造成crash.
  • 注册和移出成对匹配出现.
  • keypath参数的类型String, 如果对象的成员变量被重构而变化字符串不会被编译器识别而报错.
  • 实现观察的方式是复写NSObjec的相关KVO的方法,应该更加面向protocol的方式会更好.

总结

这一篇我们讲了 runloop和KVO相关的内容,这里面最负责的当属runloop如何处理触摸手势事件.建议认真研读相关链接文章.这样才有一个对runloop更深刻的理解。

大厂常问iOS面试题--NSNotification篇

主要内容包含如下:

  • 实现原理(结构设计、通知如何存储的、name&observer&SEL之间的关系等)
  • 通知的发送时同步的,还是异步的
  • NSNotificationCenter接受消息和发送消息是在一个线程里吗?如何异步发送消息
  • NSNotificationQueue是异步还是同步发送?在哪个线程响应
  • NSNotificationQueue和runloop的关系
  • 如何保证通知接收的线程在主线程
  • 页面销毁时不移除通知会崩溃吗
  • 多次添加同一个通知会是什么结果?多次移除通知呢
  • 下面的方式能接收到通知吗?为什么
1
2
3
4
// 发送通知
[[NSNotificationCenter defaultCenter] addObserver:self selector:@selector(handleNotification:) name:@"TestNotification" object:@1];
// 接收通知
[NSNotificationCenter.defaultCenter postNotificationName:@"TestNotification" object:nil];

在解释这些内容之前 强烈建议认真研读一下这篇 一文全解iOS通知机制(经典收藏)文章 了解一下大概 所有的问题就迎刃而解了.

实现原理(结构设计、通知如何存储的、name&observer&SEL之间的关系等

首先通知中心结构大概分为如下几个类

  • NSNotification 通知的模型 name、object、userinfo.
  • NSNotificationCenter通知中心 负责发送NSNotification
  • NSNotificationQueue通知队列 负责在某些时机触发 调用NSNotificationCenter通知中心 post通知

通知是结构体通过双向链表进行数据存储

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 根容器,NSNotificationCenter持有
typedef struct NCTbl {
Observation *wildcard; /* 链表结构,保存既没有name也没有object的通知 */
GSIMapTable nameless; /* 存储没有name但是有object的通知 */
GSIMapTable named; /* 存储带有name的通知,不管有没有object */
...
} NCTable;

// Observation 存储观察者和响应结构体,基本的存储单元
typedef struct Obs {
id observer; /* 观察者,接收通知的对象 */
SEL selector; /* 响应方法 */
struct Obs *next; /* Next item in linked list. */
...
} Observation;

主要是以key value的形式存储,这里需要重点强调一下 通知以 nameobject两个纬度来存储相关通知内容,也就是我们添加通知的时候传入的两个不同的方法. 

简单理解name&observer&SEL之间的关系就是name作为keyobserver作为观察者对象,当合适时机触发就会调用observerSEL.这基本很简单,如果觉得我说的不准确可以看下文章开头的文章.

通知的发送时同步的,还是异步的

同步发送.因为要调用消息转发.所谓异步,指的是非实时发送而是在合适的时机发送,并没有开启异步线程.

NSNotificationCenter接受消息和发送消息是在一个线程里吗?如何异步发送消息

是的, 异步线程发送通知则响应函数也是在异步线程.

异步发送通知可以开启异步线程发送即可.

NSNotificationQueue是异步还是同步发送?在哪个线程响应

1
2
3
4
5
6
// 表示通知的发送时机
typedef NS_ENUM(NSUInteger, NSPostingStyle) {
NSPostWhenIdle = 1, // runloop空闲时发送通知
NSPostASAP = 2, // 尽快发送,这种时机是穿插在每次事件完成期间来做的
NSPostNow = 3 // 立刻发送或者合并通知完成之后发送
};
NSPostWhenIdle NSPostASAP NSPostNow
NSPostingStyle 异步发送 异步发送 同步发送

NSNotificationCenter都是同步发送的,而这里介绍关于NSNotificationQueue的异步发送,从线程的角度看并不是真正的异步发送,或可称为延时发送,它是利用了runloop的时机来触发的.

异步线程发送通知则响应函数也是在异步线程,主线程发送则在主线程.

NSNotificationQueue和runloop的关系

NSNotificationQueue依赖runloop. 因为通知队列要在runloop回调的某个时机调用通知中心发送通知.从下面的枚举值就能看出来

1
2
3
4
5
6
// 表示通知的发送时机
typedef NS_ENUM(NSUInteger, NSPostingStyle) {
NSPostWhenIdle = 1, // runloop空闲时发送通知
NSPostASAP = 2, // 尽快发送,这种时机是穿插在每次事件完成期间来做的
NSPostNow = 3 // 立刻发送或者合并通知完成之后发送
};

如何保证通知接收的线程在主线程

如果想在主线程响应异步通知的话可以用如下两种方式

1.系统接受通知的API指定队列

1
- (id <NSObject>)addObserverForName:(nullable NSNotificationName)name object:(nullable id)obj queue:(nullable NSOperationQueue *)queue usingBlock:(void (^)(NSNotification *note))block

2.NSMachPort的方式 通过在主线程的runloop中添加machPort,设置这个port的delegate,通过这个Port其他线程可以跟主线程通信,在这个port的代理回调中执行的代码肯定在主线程中运行,所以,在这里调用NSNotificationCenter发送通知即可

页面销毁时不移除通知会崩溃吗?

iOS9.0之前,会crash,原因:通知中心对观察者的引用是unsafe_unretained,导致当观察者释放的时候,观察者的指针值并不为nil,出现野指针.

iOS9.0之后,不会crash,原因:通知中心对观察者的引用是weak。

多次添加同一个通知会是什么结果?多次移除通知呢

多次添加同一个通知,会导致发送一次这个通知的时候,响应多次通知回调。 多次移除通知不会产生crash。

下面的方式能接收到通知吗?为什么

1
2
3
4
// 发送通知
[[NSNotificationCenter defaultCenter] addObserver:self selector:@selector(handleNotification:) name:@"TestNotification" object:@1];
// 接收通知
[NSNotificationCenter.defaultCenter postNotificationName:@"TestNotification" object:nil];

不能

首先我们看下通知中心存储通知观察者的结构

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 根容器,NSNotificationCenter持有
typedef struct NCTbl {
Observation *wildcard; /* 链表结构,保存既没有name也没有object的通知 */
GSIMapTable nameless; /* 存储没有name但是有object的通知 */
GSIMapTable named; /* 存储带有name的通知,不管有没有object */
...
} NCTable;

// Observation 存储观察者和响应结构体,基本的存储单元
typedef struct Obs {
id observer; /* 观察者,接收通知的对象 */
SEL selector; /* 响应方法 */
struct Obs *next; /* Next item in linked list. */
...
} Observation;

namelessnamed的具体数据结构如下: 

当添加通知监听的时候,我们传入了nameobject,所以,观察者的存储链表是这样的:

named表:key(name) : value->key(object) : value(Observation)

因此在发送通知的时候,如果只传入name而并没有传入object,是找不到Observation的,也就不能执行观察者回调.

总结

今天又重新认识了iOS中的通知中心,希望大家经常温故而知新.

大厂常问iOS面试题--Block篇

这一篇我们来研究一下objc的block并回答一下面试中的下列问题:

  • 1.block的内部实现,结构体是什么样的
  • 2.block是类吗,有哪些类型
  • 3.一个int变量被 __block 修饰与否的区别?block的变量截获
  • 4.block在修改NSMutableArray,需不需要添加__block
  • 5.怎么进行内存管理的
  • 6.block可以用strong修饰吗
  • 7.解决循环引用时为什么要用__strong__weak修饰
  • 8.block发生copy时机
  • 9.Block访问对象类型的auto变量时,在ARCMRC下有什么区别

在回答所有问题之前我们需要了解一些block背景相关的知识. 如下:

  • 如何查看Block的内部实现,也就是说转换成背后真正的c/c++代码的block是什么样的?以及转换格式或者原理等. -关于变量的作用域

Objective-C 转 C++的方法

下面我写了个示例TestClass.m类其中block代码如下

OC代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
@interface TestClass ()
@end

@implementation TestClass
- (void)testMethods {
void (^blockA)(int a) = ^(int a) {
NSLog(@"%d",a);
};
if (blockA) {
blockA(1990);
}
}
@end

经过上述转换操作我们在TestClass.cpp中最下面发现如下代码

C++代码

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
29
30
31
32
33
34
// @interface TestClass ()
/* @end */


// @implementation TestClass


struct __TestClass__testMethods_block_impl_0 {
struct __block_impl impl;
struct __TestClass__testMethods_block_desc_0* Desc;
__TestClass__testMethods_block_impl_0(void *fp, struct __TestClass__testMethods_block_desc_0 *desc, int flags=0) {
impl.isa = &_NSConcreteStackBlock;
impl.Flags = flags;
impl.FuncPtr = fp;
Desc = desc;
}
};

static void __TestClass__testMethods_block_func_0(struct __TestClass__testMethods_block_impl_0 *__cself, int a) {

NSLog((NSString *)&__NSConstantStringImpl__var_folders_wx_b8tcry0j24dbhr7zlzjq3v340000gn_T_TestClass_ee18d3_mi_0,a);
}

static struct __TestClass__testMethods_block_desc_0 {
size_t reserved;
size_t Block_size;
} __TestClass__testMethods_block_desc_0_DATA = { 0, sizeof(struct __TestClass__testMethods_block_impl_0)};

static void _I_TestClass_testMethods(TestClass * self, SEL _cmd) {
void (*blockA)(int a) = ((void (*)(int))&__TestClass__testMethods_block_impl_0((void *)__TestClass__testMethods_block_func_0, &__TestClass__testMethods_block_desc_0_DATA));
if (blockA) {
((void (*)(__block_impl *, int))((__block_impl *)blockA)->FuncPtr)((__block_impl *)blockA, 1990);
}
}

上面的代码生成是通过如下操作:

打开终端,cd到TestClass.m所在文件夹,使用如下命令

1
clang -rewrite-objc TestClass.m

就会在当前文件夹内自动生成对应的TestClass.cpp文件

注意: 如果提示clang没有的话 需要安装, 输入如下

1
2
3
4
5
brew install clang-format
或者
brew link clang-forma
然后输入 下面命令测试是否好使
clang-format --help

通过上述代码我们发现Block的其实是一个结构体类型

底层实现 会根据 __类名__方法名_block_impl_下标 (0代表这个方法或者这个类中第0个block 下面如果还有将会 第1个block 第2个…)

1
struct __类名__方法名_block_impl_下标

关于变量的作用域

c语言的函数中可能使用的参数变量种类

  • 参数类型
  • 自动变量(局部变量)
  • 静态变量(静态局部变量)
  • 静态全局变量
  • 全局变量

由于存储区域特殊,这其中有三种变量是可以在任何时候以任何状态调用的.

  • 静态变量
  • 静态全局变量
  • 全局变量

而其他两种,则是有各自相应的作用域,超过作用域后,会被销毁.


1.block的内部实现,结构体是什么样的

看了上面的背景知识我们来回到一下这个问题

block的内部实现如下:

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
29
30
31
32
33
34
struct __TestClass__testMethods_block_impl_0 {
struct __block_impl impl; //成员变量
struct __TestClass__testMethods_block_desc_0* Desc; //desc 结构体声明
// 构造函数
// fp 函数指针
// desc 静态全局变量初始化的 __main_block_desc_ 结构体实例指针
// flags block 的负载信息(引用计数和类型信息),按位存储.
__TestClass__testMethods_block_impl_0(void *fp, struct __TestClass__testMethods_block_desc_0 *desc, int flags=0) {
impl.isa = &_NSConcreteStackBlock;
impl.Flags = flags;
impl.FuncPtr = fp;
Desc = desc;
}
};
//将来被调用的block内部的代码:block值被转换为C的函数代码
//这里,*__cself 是指向Block的值的指针,也就相当于是Block的值它自己(相当于C++里的this,
OC里的self)
//__cself 是指向__TestClass__testMethods_block_impl_0结构体实现的指针
//Block结构体就是__TestClass__testMethods_block_impl_0结构体.Block的值就是通过__TestClass__testMethods_block_impl_0构造出来的
static void __TestClass__testMethods_block_func_0(struct __TestClass__testMethods_block_impl_0 *__cself, int a) {
NSLog((NSString *)&__NSConstantStringImpl__var_folders_wx_b8tcry0j24dbhr7zlzjq3v340000gn_T_TestClass_9f58f7_mi_0,a);
}

static struct __TestClass__testMethods_block_desc_0 {
size_t reserved;
size_t Block_size;
} __TestClass__testMethods_block_desc_0_DATA = { 0, sizeof(struct __TestClass__testMethods_block_impl_0)};

static void _I_TestClass_testMethods(TestClass * self, SEL _cmd) {
void (*blockA)(int a) = ((void (*)(int))&__TestClass__testMethods_block_impl_0((void *)__TestClass__testMethods_block_func_0, &__TestClass__testMethods_block_desc_0_DATA));
if (blockA) {
((void (*)(__block_impl *, int))((__block_impl *)blockA)->FuncPtr)((__block_impl *)blockA, 1990);
}
}

可以看得出来__TestClass__testMethods_block_impl_0有3个部分组成

  • impl 函数指针指向__TestClass__testMethods_block_impl_0
1
2
3
4
5
6
struct __block_impl {
void *isa;
int Flags;
int Reserved; //今后版本升级所需的区域
void *FuncPtr; //函数指针
};
  • Desc 指向__TestClass__testMethods_block_impl_0的Desc指针,用于描述当前这个block的附加信息的,包括结构体的大小等等信息.
1
2
3
4
static struct __TestClass__testMethods_block_desc_0 {
size_t reserved; //今后升级版本所需区域
size_t Block_size; //block的大小
} __TestClass__testMethods_block_desc_0_DATA = { 0, sizeof(struct __TestClass__testMethods_block_impl_0)};
  • __TestClass__testMethods_block_impl_0()构造函数,也就是该block的具体实现
1
2
3
4
5
6
__TestClass__testMethods_block_impl_0(void *fp, struct __TestClass__testMethods_block_desc_0 *desc, int flags=0) {
impl.isa = &_NSConcreteStackBlock;
impl.Flags = flags;
impl.FuncPtr = fp;
Desc = desc;
}

此结构体中

  • isa指针保持这所属类的结构体的实例的指针.
  • struct __TestClass__testMethods_block_impl_0相当于Objective-C类对象的结构体
  • _NSConcreteStackBlock相当于Block的结构体实例,也就是说block其实就是Objective-C对于闭包的对象实现

讲到这里block的内部实现你看懂了吗?结构体是什么样的你记住了吗? 其实看着繁琐 细心观察代码会发现还是比较简单的.

2.block是类吗,有哪些类型?

block也算是个类,因为它有isa指针,block.isa的类型包括

  • _NSConcreteGlobalBlock 跟全局变量一样,设置在程序的数据区域(.data)中
  • _NSConcreteStackBlock栈上(前面讲的都是栈上的 block)
  • _NSConcreteMallocBlock 堆上

这个isa可以按位运算

3.一个int变量被 __block 修饰与否的区别?block的变量截获

__block 修饰与否的区别

用一段示例代码来解答这个问题吧:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
__block int a = 10;
int b = 20;

PrintTwoIntBlock block = ^(){
a -= 10;
printf("%d, %d\n",a,b);
};

block();//0 20

a += 20;
b += 30;

printf("%d, %d\n",a,b);//20 50

block();/10 20

通过__block修饰int a,block体中对这个变量的引用是指针拷贝,它会作为block结构体构造参数传入到结构体中且复制这个变量的指针引用,从而达到可以修改变量的作用.

int b没有被__block修饰,block内部对b是值copy.所以在block内部修改b不影响外部b的变化.

block的变量截获

通过如下代码我们来观察要一下变量的捕获

1
2
3
4
5
6
7
8
9
10
11
blk_t blk;
{
id array = [NSMutableArray new];
blk = [^(id object){
[array addObject:object];
NSLog(@"array count = %ld",[array count]);
} copy];
}
blk([NSObject new]);
blk([NSObject new]);
blk([NSObject new]);

输出打印

1
2
3
block_demo[28963:1629127] array count = 1
block_demo[28963:1629127] array count = 2
block_demo[28963:1629127] array count = 3

我们把上面的代码翻译成C++看下

1
2
3
4
5
6
7
8
9
10
11
struct __main_block_impl_0 {
struct __block_impl impl;
struct __main_block_desc_0* Desc;
id array;//截获的对象
__main_block_impl_0(void *fp, struct __main_block_desc_0 *desc, id _array, int flags=0) : array(_array) {
impl.isa = &_NSConcreteStackBlock;
impl.Flags = flags;
impl.FuncPtr = fp;
Desc = desc;
}
};

在Objc中,C结构体里不能含有被__strong修饰的变量,因为编译器不知道应该何时初始化和废弃C结构体。但是Objc的运行时库能够准确把握Block从栈复制到堆,以及堆上的block被废弃的时机,在实现上是通过__TestClass__testMethods_block_copy_0函数和__TestClass__testMethods_block_dispose_0函数进行的

1
2
3
4
5
6
static void __TestClass__testMethods_block_copy_0(struct __TestClass__testMethods_block_impl_0*dst, struct __TestClass__testMethods_block_impl_0*src) {
_Block_object_assign((void*)&dst->array, (void*)src->array, 3/*BLOCK_FIELD_IS_OBJECT*/);
}
static void __TestClass__testMethods_block_dispose_0(struct __TestClass__testMethods_block_impl_0*src) {
_Block_object_dispose((void*)src->array, 3/*BLOCK_FIELD_IS_OBJECT*/);
}
  • _Block_object_assign相当于retain操作,将对象赋值在对象类型的结构体成员变量中.

  • _Block_object_dispose相当于release操作.

这两个函数调用的时机是在什么时候呢?

函数 被调用时机
__TestClass__testMethods_block_copy_0 从栈复制到堆时
__TestClass__testMethods_block_dispose_0 堆上的Block被废弃时
什么时候栈上的Block会被复制到堆呢?
  • 调用block的copy函数时。

  • Block作为函数返回值返回时。

  • 将Block赋值给附有__strong修饰符id类型的类或者Block类型成员变量时。

  • 方法中含有usingBlock的Cocoa框架方法或者GCD的API中传递Block时。

什么时候Block被废弃呢?
  • 堆上的Block被释放后,谁都不再持有Block时调用dispose函数。

以上就是变量被block捕获的内容


4.block在修改NSMutableArray,需不需要添加__block

  • 如修改NSMutableArray的存储内容的话,是不需要添加__block修饰的。
  • 如修改NSMutableArray对象的本身,那必须添加__block修饰。

5.怎么进行内存管理的?

在上面Block的构造函数__TestClass__testMethods_block_impl_0中的isa指针指向的是&_NSConcreteStackBlock,它表示当前的Block位于栈区中.

block内存操作 存储域/存储位置 copy操作的影响
_NSConcreteGlobalBlock 程序的数据区域 什么也不做
_NSConcreteStackBlock 从栈拷贝到堆
_NSConcreteMallocBlock 引用计数增加
  • 全局Block:_NSConcreteGlobalBlock的结构体实例设置在程序的数据存储区,所以可以在程序的任意位置通过指针来访问,它的产生条件:

    • 记述全局变量的地方有block语法时.
    • block不截获的自动变量.

    以上两个条件只要满足一个就可以产生全局Block. 参考

  • 栈Block:_NSConcreteStackBlock在生成Block以后,如果这个Block不是全局Block,那它就是栈Block,生命周期在其所属的变量作用域内.(也就是说如果销毁取决于所属的变量作用域).如果Block变量和__block变量复制到了堆上以后,则不再会受到变量作用域结束的影响了,因为它变成了堆Block.

  • 堆Block:_NSConcreteMallocBlock将栈block复制到堆以后,block结构体的isa成员变量变成了_NSConcreteMallocBlock

6.block可以用strong修饰吗?

在ARC中可以,因为在ARC环境中的block只能在堆内存或全局内存中,因此不涉及到从栈拷贝到堆中的操作.

在MRC中不行,因为要有拷贝过程.如果执行copy用strong的话会crash, strong是ARC中引入的关键字.如果使用retain相当于忽视了block的copy过程.

7.解决循环引用时为什么要用__strong__weak修饰?

首先因为block捕获变量的时候 结构体构造时传入了self,造成了默认的引用关系,所以一般在block外部对操作对象会加上__weak,在Block内部使用__strong修饰符的对象类型的自动变量,那么当Block从栈复制到堆的时候,该对象就会被Block所持有,但是持有的是我们上面加了__weak所以行程了比消此长的链条,刚好能解决block延迟销毁的时候对外部对象生命周期造成的影响.如果不这样做很容易造成循环引用.

8.block发生copy时机?

在ARC中,编译器将创建在栈中的block会自动拷贝到堆内存中,而block作为方法或函数的参数传递时,编译器不会做copy操作.

  • 调用block的copy函数时。

  • Block作为函数返回值返回时。

  • 将Block赋值给附有__strong修饰符id类型的类或者Block类型成员变量时。

  • 方法中含有usingBlock的Cocoa框架方法或者GCD的API中传递Block时。

9.Block访问对象类型的auto变量时,在ARC和MRC下有什么区别?

ARC下会对这个对象强引用,MRC下不会

大厂常问iOS面试题--数据结构篇

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

数据结构的存储一般常用的有两种 顺序存储结构 和 链式存储结构

  • 顺序存储结构:

    比如,数组,1-2-3-4-5-6-7-8-9-10,存储是按顺序的。再比如栈和队列等

  • 链式存储结构:

    比如,数组,1-2-3-4-5-6-7-8-9-10,链式存储就不一样了 1(地址)-2(地址)-7(地址)-4(地址)-5(地址)-9(地址)-8(地址)-3(地址)-6(地址)-10(地址)。每个数字后面跟着一个地址 而且存储形式不再是顺序

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

  • 集合结构

    一个集合,就是一个圆圈中有很多个元素,元素与元素之间没有任何关系 这个很简单

  • 线性结构

    一个条线上站着很多个人。 这条线不一定是直的。也可以是弯的。也可以是值的 相当于一条线被分成了好几段的样子 (发挥你的想象力)。 线性结构是一对一的关系

  • 树形结构

    做开发的肯定或多或少的知道xml 解析 树形结构跟他非常类似。也可以想象成一个金字塔。树形结构是一对多的关系

  • 图形结构

    这个就比较复杂了。他呢 无穷。无边 无向(没有方向)图形机构 你可以理解为多对多 类似于我们人的交集关系

3.单向链表 双向链表 循环链表

  • 单向链表 A->B->C->D->E->F->G->H. 这就是单向链表 H 是头 A 是尾 像一个只有一个头的火车一样 只能一个头拉着跑 单向链表

  • 双向链表 双向链表

  • 循环链表

    循环链表是与单向链表一样,是一种链式的存储结构,所不同的是,循环链表的最后一个结点的指针是指向该循环链表的第一个结点或者表头结点,从而构成一个环形的链。发挥想象力 A->B->C->D->E->F->G->H->A. 绕成一个圈。就像蛇吃自己的这就是循环 不需要去死记硬背哪些理论知识。

4.数组和链表区别

  • 数组

    数组元素在内存上连续存放,可以通过下标查找元素;插入、删除需要移动大量元素,比较适用于元素很少变化的情况

  • 链表

    链表中的元素在内存中不是顺序存储的,查找慢,插入、删除只需要对元素指针重新赋值,效率高

5.堆、栈和队列

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

    1)堆中某个节点的值总是不大于或不小于其父节点的值;

    2)堆总是一棵完全二叉树。

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

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

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

  • 栈是一种具有后进先出的数据结构,又称为后进先出的线性表,简称 LIFO(Last In First Out)结构。也就是说后存放的先取,先存放的后取,这就类似于我们要在取放在箱子底部的东西(放进去比较早的物体),我们首先要移开压在它上面的物体(放进去比较晚的物体)。

  • 堆栈中定义了一些操作。两个最重要的是PUSH和POP。PUSH操作在堆栈的顶部加入一个元素。POP操作相反,在堆栈顶部移去一个元素,并将堆栈的大小减一。

  • 栈的应用—递归

队列

  • 队列是只允许在一端进行插入操作、而在另一端进行删除操作的线性表。允许插入的一端称为队尾,允许删除的一端称为队头。它是一种特殊的线性表,特殊之处在于它只允许在表的前端进行删除操作,而在表的后端进行插入操作,和栈一样,队列是一种操作受限制的线性表。

  • 队列是一种先进先出的数据结构,又称为先进先出的线性表,简称 FIFO(First In First Out)结构。也就是说先放的先取,后放的后取,就如同行李过安检的时候,先放进去的行李在另一端总是先出来,后放入的行李会在最后面出来。

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

二叉树的结点定义如下:

1
2
3
4
5
6
struct BinaryTreeNode
{
int m_nValue ;
BinaryTreeNode* m_pLeft;
BinarvTreeNode* m_pRight ;
}
  • 如果一棵树只有一个结点,它的深度为1。
  • 如果根结点只有左子树而没有右子树,那么树的深度应该是其左子树的深度加1;同样如果根结点只有右子树而没有左子树,那么树的深度应该是其右子树的深度加1。
  • 如果既有右子树又有左子树,那该树的深度就是其左、右子树深度的较大值再加1。
1
2
3
4
5
6
7
8
9
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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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 false;
return IsBalanced(pRoot->left) && IsBalanced(pRoot->right);
}

方法2:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
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);
}

大厂常问iOS面试题--算法篇

1.时间复杂度

  • 时间频度

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

  • 时间复杂度

    一般情况下,算法中基本操作重复执行的次数是问题规模n的某个函数,用T(n)表示,若有某个辅助函数f(n),使得当n趋近于无穷大时,T(n)/f(n)的极限值为不等于零的常数,则称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的不断增大,上述时间复杂度不断增大,算法的执行效率越低.

2.空间复杂度

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

3.常用的排序算法

  • 选择排序、冒泡排序、插入排序三种排序算法可以总结为如下:

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

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

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

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

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
/** 
* 【选择排序】:最值出现在起始端
*
* 第1趟:在n个数中找到最小(大)数与第一个数交换位置
* 第2趟:在剩下n-1个数中找到最小(大)数与第二个数交换位置
* 重复这样的操作...依次与第三个、第四个...数交换位置
* 第n-1趟,最终可实现数据的升序(降序)排列。
*
*/
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;
}
}
}
}

/**
* 【冒泡排序】:相邻元素两两比较,比较完一趟,最值出现在末尾
* 第1趟:依次比较相邻的两个数,不断交换(小数放前,大数放后)逐个推进,最值最后出现在第n个元素位置
* 第2趟:依次比较相邻的两个数,不断交换(小数放前,大数放后)逐个推进,最值最后出现在第n-1个元素位置
* …… ……
* 第n-1趟:依次比较相邻的两个数,不断交换(小数放前,大数放后)逐个推进,最值最后出现在第2个元素位置
*/
void bublleSort(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;
}

4.字符串反转

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void char_reverse (char *cha) {

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

while (begin < end) {

char temp = *begin;
*(begin++) = *end;
*(end--) = temp;
}
}

5.链表反转(头差法)

.h声明文件

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#import <Foundation/Foundation.h>

// 定义一个链表
struct Node {
int data;
struct Node *next;
};

@interface ReverseList : NSObject

// 链表反转
struct Node* reverseList(struct Node *head);

// 构造一个链表
struct Node* constructList(void);

// 打印链表中的数据
void printList(struct Node *head);

@end

.m实现文件

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#import "ReverseList.h"

@implementation ReverseList

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;
}

struct Node* constructList(void)
{
// 头结点定义
struct Node *head = NULL;
// 记录当前尾结点
struct Node *cur = NULL;

for (int i = 1; i < 5; i++) {
struct Node *node = malloc(sizeof(struct Node));
node->data = i;

// 头结点为空,新结点即为头结点
if (head == NULL) {
head = node;
}
// 当前结点的next为新结点
else{
cur->next = node;
}

// 设置当前结点为新结点
cur = node;
}

return head;
}

void printList(struct Node *head)
{
struct Node* temp = head;
while (temp != NULL) {
printf("node is %d \n", temp->data);
temp = temp->next;
}
}

@end

6.有序数组合并

.h声明文件

1
2
3
4
5
6
7
#import <Foundation/Foundation.h>

@interface MergeSortedList : NSObject
// 将有序数组a和b的值合并到一个数组result当中,且仍然保持有序
void mergeList(int a[], int aLen, int b[], int bLen, int result[]);

@end

.m实现文件

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#import "MergeSortedList.h"

@implementation MergeSortedList

void mergeList(int a[], int aLen, int b[], int bLen, int result[])
{
int p = 0; // 遍历数组a的指针
int q = 0; // 遍历数组b的指针
int i = 0; // 记录当前存储位置

// 任一数组没有到达边界则进行遍历
while (p < aLen && q < bLen) {
// 如果a数组对应位置的值小于b数组对应位置的值
if (a[p] <= b[q]) {
// 存储a数组的值
result[i] = a[p];
// 移动a数组的遍历指针
p++;
}
else{
// 存储b数组的值
result[i] = b[q];
// 移动b数组的遍历指针
q++;
}
// 指向合并结果的下一个存储位置
i++;
}

// 如果a数组有剩余
while (p < aLen) {
// 将a数组剩余部分拼接到合并结果的后面
result[i] = a[p++];
i++;
}

// 如果b数组有剩余
while (q < bLen) {
// 将b数组剩余部分拼接到合并结果的后面
result[i] = b[q++];
i++;
}
}

@end

7.查找第一个只出现一次的字符(Hash查找)

.h声明文件

1
2
3
4
5
6
7
8
#import <Foundation/Foundation.h>

@interface HashFind : NSObject

// 查找第一个只出现一次的字符
char findFirstChar(char* cha);

@end

.m实现文件

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
29
30
31
32
33
34
35
36
37
38
39
40
41
#import "HashFind.h"

@implementation HashFind

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;
}

@end

8.查找两个子视图的共同父视图

.h声明文件

1
2
3
4
5
6
7
8
#import <Foundation/Foundation.h>
#import <UIKit/UIKit.h>
@interface CommonSuperFind : NSObject

// 查找两个视图的共同父视图
- (NSArray<UIView *> *)findCommonSuperView:(UIView *)view other:(UIView *)viewOther;

@end

.m实现文件

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#import "CommonSuperFind.h"

@implementation CommonSuperFind

- (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;
}

@end

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

.h声明文件

1
2
3
4
5
6
7
8
#import <Foundation/Foundation.h>

@interface MedianFind : NSObject

// 无序数组中位数查找
int findMedian(int a[], int aLen);

@end
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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
.m实现文件
#import "MedianFind.h"

@implementation MedianFind

//求一个无序数组的中位数
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;
}

@end

10.给定一个整数数组和一个目标值,找出数组中和为目标值的两个数。

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
29
30
31
- (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;
}