等待异步

有时候执行某个动作，需要等到另一个事件结束，可以用Completer类。

常见的有：

执行某个动作，需要弹窗等待用户选择某条件后再执行后续代码，

//事例

var c = Completer<bool>();
 
Dialogs.tipsCard(title, tip,
  failMsg: '',
  actions: [i18n.ok],
  callback: (index) => c.complete(true),
  dismissCallBack: () {
    if (!c.isCompleted)
      c.complete(false);
  },
);
 
return c.future;

其他：

Completer

Completer允许你做某个异步事情的时候，调用c.complete(value)方法来传入最后要返回的值。最后通过c.future的返回值来得到结果，（注意：宣告完成的complete和completeError方法只能调用一次，不然会报错）。看下面的例子更容易理解。

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

test() async {
   Completer c = new Completer();
   for (var i = 0; i < 1000; i++) {
     if (i == 900 && c.isCompleted == false) {
       c.completeError('error in $i');
     }
     if (i == 800 && c.isCompleted == false) {
       c.complete('complete in $i');
     }
   }

   try {
     String res = await c.future;
     print(res); //得到complete传入的返回值 'complete in 800'
   } catch (e) {
     print(e);//捕获completeError返回的错误
   }
 }

怎么将一个Callback回调转化成Future同步方法（Callback to Future），可以配套async / await去使用呢？

使用场景：dio请求使用call，但外部基本还是习惯使用future方式，为了减少接口的改动，使用callback转future方式。

参考文章：Flutter&Dart Callback转Future

compute

在一个页面中做耗时比较大的运算时，就算用了async / await异步处理， ui页面的动画还是会卡顿，因为还是在这个UI线程中做运算，异步只是说我可以先运行其他的，等我这边有结果再返回，但是，记住，我们的计算仍旧是在这个UI线程，仍会阻塞UI的刷新，异步只是在同一个线程的并发操作。

要解决这个卡顿问题，可以把运算移到另一个线程中，在dart中，这里不是称呼线程，是Isolate，直译叫做隔离，是因为隔离不共享数据，每个隔离中的变量都是不同的，不能相互共享。

Isolate的操作比较复杂，dart中封装了一层简单的实现

1
2

/// package:flutter/foundation.dart
Future<R> Function<Q, R>(FutureOr<R> Function(Q), Q, {debugLabel: String})compute

使用方法

1
2
3
4
5
6
7
8

import 'package:flutter/foundation.dart';

function callback( val ){
  ...
  return res
}
/// `callback` 必须是顶级方法或者是类的静态方法
var res = await compute( callback , val );

简单来讲就是运行var res = await compute( callback , val )函数。callback的传入参数是val, return的数据就是callback的res;

使用场景

• 方法执行在几毫秒或十几毫秒左右的，应使用Future
• 如果一个任务需要几百毫秒或之上的，则建议compute（只有一次返回）或Isolate（用于订阅或有多次返回的）

Flutter/Dart :如何在app启动前等待异步任务？

我在一个dart应用程序上工作，我想获取缓存(SharedPreferences)中存在的数据，然后在应用程序的UI (主屏幕)上显示它。

问题:由于SharedPreferences是一个等待调用，我的主页加载，试图读取数据，应用程序崩溃，因为还没有从SharedPreferences中获取数据，并且应用程序在此之前加载。

其他参考文章：

多任务

dart笔记13：用future实现等待多个任务完成后，再得到所有的执行结果

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

import 'dart:async';

void main() {
  print('start');

  Future task1 = Future(() {
    print('task1');
    return 1;
  });

  Future task2 = Future(() {
    print('task2');
    return 2;
  });

  Future task3 = Future(() {
    print('task3');
    return 3;
  });

  Future future = Future.wait([task1, task2, task3]);

  future.then((value) {
    print(value);
  }).catchError((e){
 
  });


  print('end');

  //执行结果：
  //start
  //end
  //task1
  //task2
  //task3
  //[1, 2, 3]
}

FutureBuilder

Flutter：使用 Completer 实现自定义任务队列

• Flutter：使用 Completer 实现自定义任务队列

环境变量

Mac 配置环境变量

环境变量的设置文件：

非M1类型的Mac：~/.bash_profile

是M1类型的Mac：~/.zshrc

修改方法：

非M1类型的Mac：终端输入open -n ~/.bash_profile

是M1类型的Mac：终端输入open -n ~/.zshrc

编辑完保存并退出

非M1类型的Mac：输入 source ~/.bash_profile 使环境变量生效。

是M1类型的Mac：输入 source ~/.zshrc 使环境变量生效。

• 图论算法——环和有向无环图

  寻找环利用了DFS方法，维护一个递归调用期间已访问的顶点的栈，若(在递归调用期间，通过判断onStack标记数组)两次访问了某个顶点，则说明有环；若DFS递归调用完毕，说明无环。

• 十一、谈谈设计模式

• 十二、如何优化过于臃肿的Controller

• 十三、谈谈性能优化(功耗)

• 十四、UITableView的优化、重用

• 十五、布局 layoutsubview、drawrect等

• 十六、有逼格的代码

• 十七、单元测试

• 十八、APP审核

• 常见笔试/面试题

• END

• iOS进阶–App功耗优化看这篇就够了
• iOS耗电量检测与优化

UITableView的优化、重用

< 返回目录

布局 layoutsubview、drawrect等

< 返回目录

有逼格的代码

typedef NSString * NSRunLoopMode NS_EXTENSIBLE_STRING_ENUM;
提升自己逼格的编程之美之代码规范
iOS开发细节 | 通知怎么写？
实现NS_ENUM的自定义反射

单元测试

< 返回目录

APP审核

< 返回目录

1、如何使用一个for循环输出九九乘法表

NSJSONSerialization

1
2

NSData *data = [operation.responseString dataUsingEncoding:NSUTF8StringEncoding];
    NSMutableDictionary *responseObject_dic = [NSJSONSerialization JSONObjectWithData:data options:NSJSONReadingMutableContainers | NSJSONReadingMutableLeaves error:nil];

//NSJSONReadingMutableContainers的作用: http://blog.csdn.net/chenyong05314/article/details/45691041

1
2
3

NSJSONReadingMutableContainers：返回可变容器，NSMutableDictionary或NSMutableArray。
NSJSONReadingMutableLeaves：返回的JSON对象中字符串的值为NSMutableString
NSJSONReadingAllowFragments：允许JSON字符串最外层既不是NSArray也不是NSDictionary，但必须是有效的JSON Fragment。例如使用这个选项可以解析 @“123” 这样的字符串。

iOS中常见Crash总结

• iOS中常见Crash总结
• iOS开发之调试技巧Xcode7中你一定要知道的炸裂调试神技、Address Sanitizer EXC_BAD_ACCESS

• iOS App 签名的原理 （非常好，非常详细的文章）

1. CertificateSigningRequest：本地公钥。
2. p12：本地私钥，可以导入到其他电脑。
3. 证书：内容是公钥或私钥，由其他机构对其签名组成的数据包。
4. Entitlements：包含了 App 权限开关列表。
5. Provisioning Profile：包含了 证书 / Entitlements 等数据，并由苹果后台私钥签名的数据包。

概览

四种方式安装一个APP的方式

1. 从 AppStore 下载
2. 开发 App 时可以直接把开发中的应用安装进手机进行调试。
3. In-House 企业内部分发，可以直接安装企业证书签名后的 APP。
4. AD-Hoc 相当于企业分发的限制版，限制安装设备数量，较少用。

区别：

App Store 下载的是Apple后台用私钥A对其进行重签名，

而其他的是用Xcode配置的对应该证书的本地私钥L对app进行签名。

一、App Store 下载的签名机制（最简单的签名）

当App 提交审核通过后，Apple会对App重签名，所以从App Store下载的app都是苹果的官方签名。

流程如下：

1、Apple 官方有自己固定的一对公钥和私钥，私钥A存在Apple后台，公钥A存在iOS设备

2、app审核通过后，Apple后台用私钥A对其进行重签名

3、app下载到iOS设备后，iOS设备内置的公钥A会对app的签名进行验证

4、如果验证通过，则可运行，否则不能

当然除了这个方式，还有一下三种方式安装一个app：

1. 开发时，直接通过USB将应用安装到手机进行调试；
2. In-House 企业内部分发，可直接安装企业证书签名的App；
3. Ad-Hoc 相当于企业分发的限制版，限制安装设备数量。

①、KeyChain 里的“从证书颁发机构请求证书”，本地生成一对公私钥。（其中：公钥L是保存的CertificateSigningRequest(CSR)，而私钥L保存在电脑本地，可以导出为p12）

附：Apple 官方也有自己固定的一对公钥和私钥，私钥A存在Apple后台，公钥A内置在iOS设备

（因为这里的这个私钥是本地Mac持有，所以团队开发时，可在KeyChain导出私钥，存为.p12文件，其他Mac即可导入这个私钥）

2、在Member Center把CertificateSigningRequest上传到苹果后台生成证书（即上传之后Apple后台用Apple 官方自己固定的私钥A对我们上传的公钥L进行签名，将得到的签名+公钥L打包起来，称为证书），下载到本地。

Apple 官方有自己固定的一对公钥和私钥，私钥A存在Apple后台，公钥A内置在iOS设备

3、在Member Center配置AppID、添加设备UUID／Entitlements, 生成app对应的 Provisioning Profile 文件，并下载到本地
4、在XCode中配置好证书，打包编译时，**用Xcode配置的对应该证书的本地私钥L对app进行签名，并把 Provisioning Profile 文件一起打包进App去(文件名为 embedded.mobileprovision)**。这里对App的签名数据分两部分，Mach-O 可执行文件把签名直接写进这个文件，其他资源文件则保存在_CodeSignature目录下

5、安装APP到手机上时，iOS设备内置的公钥A(指Apple官方自己固定的公钥)对embedded.mobileprovision的数字签名进行验证，同时对里面的证书的签名也会验证
如果验证通过，确保了embedded.mobileprovision的数据是苹果授权后，再取出里面数据做各种验证，包括公钥L对app签名进行验证，验证设备ID，AppID，权限开关。

前言：你真的懂isEqual与hash？

参考文章：

• iOS开发 之 不要告诉我你真的懂isEqual与hash!
• 哈希算法详解（附带 iOS 开发中实际应用）
• iOS weak关键字实现原理

eg：

1
2

1、NSMutableSet/NSSet中添加对象的时候，就会调用- (NSUInteger)hash方法。
2、NSMutableSet/NSSet中添加 obj2 对象的时候，如果NSMutableSet/NSSet 中之前就已经存在 obj1 对象，且 obj1 对象的 - (NSUInteger)hash 返回值和当前要添加的 obj2 的- (NSUInteger)hash 返回值相等, 则 obj2 会继续调用- (BOOL)isEqual:方法，其中此方法以 obj1 为参数；否则不等, 继续下一个元素判断。

通过重写isEqual，我们可以做到对象的判等可以完全由您决定, 即使两个完全不同的对象。

一、基础

1、nil, Nil,NULL 与 NSNull 的区别

• nil 指向一个对象的指针为空,在objc.h 的定义如下: NSString *name = nil;
• Nil 指向一个类的指针为空,定义如下: Class aClass = Nil;
• NULL 指向C类型的指针为空, 例如: int*pInt = NULL;
• NSNull 在Objective-C中是一个类,只是名字中有个Null，多用于集合(NSArray,NSDictionary)中值为空的对象

2、==、 isEqualToString、isEqual

2.1、背景：为什么要有isEqual方法?

答：判断两个对象是否相等（而不是判断两个对象的地址是否相等）。

对于基本类型, ==运算符比较的是值;
对于对象类型, ==运算符比较的是对象的地址(即是否为同一对象)

1
2
3
4
5
6
7
8

UIColor *color1 = [UIColor colorWithRed:0.5 green:0.5 blue:0.5 alpha:1.0];
UIColor *color2 = [UIColor colorWithRed:0.5 green:0.5 blue:0.5 alpha:1.0];
NSLog(@"color1 == color2 = %@", color1 == color2 ? @"YES" : @"NO");
NSLog(@"[color1 isEqual:color2] = %@", [color1 isEqual:color2] ? @"YES" : @"NO");

// 打印结果如下：
color1 == color2 = NO
[color1 isEqual:color2] = YES

总结：

1、==
判断指针指向的地址，即指针值，是否相等
①对于基本类型, ==运算符比较的是值;
②对于对象类型, ==运算符比较的是对象的地址(即是否为同一对象)）

2、isEqualToString
直接判断字符串内容是否相等

3、isEqual
先判断两个对象的地址是否相同，再判断类型是否一致，然后再判断对象的具体内容是否一致
//情况①：地址相同则肯定相等；
//情况②：地址不同时候，如果类型一致且里面的内容相等，则也算相等

2.1、苹果官方重写isEqual 的demo

isEqual：先判断两个对象的地址是否相同(采用==)，再判断类型是否一致(采用isKindOfClass)，然后再判断对象的具体内容是否一致

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

- (BOOL)isEqual:(id)object {
    if (self == object) {
        return YES;
    }

    if (![object isKindOfClass:[Person class]]) {
        return NO;
    }

    return [self isEqualToPerson:(Person *)object];
}

- (BOOL)isEqualToPerson:(Person *)person {
    if (!person) {
        return NO;
    }

    BOOL haveEqualNames = (!self.name && !person.name) || 
      										[self.name isEqualToString:person.name];
    BOOL haveEqualBirthdays = (!self.birthday && !person.birthday) || 
      										[self.birthday isEqualToDate:person.birthday];

    return haveEqualNames && haveEqualBirthdays;
}

附：通过重写isEqual，我们可以做到对象的判等可以完全由您决定, 即使两个完全不同的对象。

2.2、==、 isEqualToString、isEqual验证示例

四、weak

以下内容来自： iOS weak关键字实现原理

• 1、weak关键字修饰对象的【初始化及重新赋值】实现原理
• 2、weak关键字是如何保证在weak对象执行语句时内存对象不被释放的呢？
• 3、当weak对象指向的内存对象被释放后，weak对象自动置为nil。原理是怎样？

1、weak关键字修饰对象初始化及重新赋值实现原理

objc_initWeak：当初始化一个weak对象并将内存对象赋值给该weak对象时会调用该方法。

objc_storeWeak：当为一个weak对象赋新值时会调用该方法。

1
2
3
4
5
6
7
8
9
10
11
12

objc_initWeak(id *location, id newObj)
{
    //对内存对象进行非nil判断
    if (!newObj) {
        *location = nil;
        return nil;
    }
    
    //调用storeWeak方法，三个参数的意义在storeWeak方法中描述
    return storeWeak<false/*old*/, true/*new*/, true/*crash*/>
        (location, (objc_object*)newObj);
}

1
2
3
4
5
6

objc_storeWeak(id *location, id newObj)
{
    //调用storeWeak方法，三个参数的意义在storeWeak方法中描述
    return storeWeak<true/*old*/, true/*new*/, true/*crash*/>
        (location, (objc_object *)newObj);
}

由官方文档可知，无论是初始化weak对象还是为weak对象赋值，最终都会调用到 storeWeak方法，不同点在于，二者传入三个模板值不同。

如果weak对象与旧内存对象的关联，则先调用weak_unregister_no_lock，将weak对象与旧内存对象解除指向关系。

然后在将weak对象与旧内存对象的关联解除后，就调用 weak_register_no_lock方法将weak对象与新内存对象进行关联

至此，weak关键字修饰对象的初始化和重新赋值流程就完成了。

2、weak关键字是如何保证在weak对象执行语句时内存对象不被释放的呢？

问：weak关键字是如何保证【在weak对象执行语句时】内存对象【不被释放】的呢？

答：其实很简单，就是对内存对象进行计数增加。

每次在使用weak对象时，都相当于调用一次 objc_loadWeak。

在weak对象执行的语句中，weak对象所指向的内存对象计数会+1，这样就保证在语句中不会发生执行一半而释放内存对象的问题。

3、当weak对象指向的内存对象被释放后，weak对象自动置为nil。原理是怎样？

当内存对象释放时，会调用到一个叫weak_claer_no_lock的方法。在 weak_claer_no_lock方法中，会进行对weak对象的置空操作。

4、Weak-Strong搭配使用的误解

在使用Block时，我们可以使用weak关键字来避免外部变量被Block强引用而导致的循环引用，同时为了Block中的代码能够正常执行，许多开发者提出了Weak-Strong搭配使用的方式，类似如下：

1
2
3
4
5
6
7
8

{
    __weak typeof(self) weakSelf = self;
    self.block = ^{
        __strong typeof(weakSelf) strongSelf = weakSelf;
        [strongSelf test1];
        [strongSelf test2];
    };
}

以上代码相对于单独使用weak来说还是有好处的，使用Weak-Strong搭配的方式的话，可以保证在执行 [strongSelf test1]和 [strongSelf test2]时，是向同一对象发送消息。

为什么这么说呢？当开始执行Block语句时，若self还存在，那么strongSelf可以保证在整个Block代码块中不会被释放，即使Block中调用无数次strongSelf，strongSelf也不会因为多线程而在半途被释放；若开始执行Block时，self已经被释放，那么之后所有的消息都会被发送至nil。所以Weak-Strong搭配可以保证Block中语句被处理为一个事务。

1
2
3
4
5
6
7

{
    __weak typeof(self) weakSelf = self;
    self.block = ^{
        [weakSelf test1];	// 可能这时候self还没释放，有值。
        [weakSelf test2];	// 而到这时候self刚好释放，为ni。导致Block中语句不是被发送给同一对象去处理。
    };
}

所以说，Weak-Strong并不能保证Block中语句一定会被执行，它只能保证Block中语句作为一个事务被发送到同一对象处。只要理解了weak实现原理，我们就能明白何时单独使用weak也能完成代码功能，而何时必须使用Weak-Strong来保证代码事务能力。

5、weak关键字涉及到的数据结构

略。请查看 iOS weak关键字实现原理

1、SideTables

SideTables本质上是一个全局的 StripedMap。而StripedMap本质是一个数组。

在 SideTables中， Item类型为 SideTable

2、SideTable

SideTable中包含三个元素，分别是 1.自旋锁 2.记录对象引用计数的字典 3.记录对象弱引用信息的数据结构 weak_table_t。

3、weak_table_t

weak_table_t本质上是一个数组，其中每个Item为 weak_entry_t。

4、weak_entry_t

weak_entry_t就比较有意思了，它本质上是个字典。其中的key值为对象，而value对应为一个数组，数组中保存的值均为 weak_referrer_t类型的数据。

5、weak_referrer_t

weak_referrer_t本质上是 objc_object **，即Objective-C对象的地址。

所以，weak_entry_tvalue数组中，每一个Item均为一个地址，即weak对象的地址。

在项目中有某个功能需要用到多个delegate对象，这就需要把delegate放到容器中，但又只能弱引用weak保存delegate，否则会导致delegate对象不能被释放。所以，我们的需求就是希望能在容器中只保存弱引用的delegate对象。

在OC中Foundation框架中的常用容器类（NSSet，NSDictionary，NSArray）及其可变子类在加入元素时，均会对元素进行强引用。有的时候（比如持有多个Delegate对象时），希望有对应的弱引用容器使用。

支持弱引用的容器类，有如下：

[NSHashTable weakObjectsHashTable]

[NSPointerArray weakObjectsPointerArray]

[NSPointerArray pointerArrayWithOptions:]

详见：YYKit学习笔记之NSHashTable与NSMapTable

其他参考：

• OC弱引用容器实现方案总结

• iOS如何在容器类中使用弱引用(weak reference)

• 数组或字典如何弱引用对象

• iOS - 如何实现弱引用字典

*在iOS项目开发过程中，我们经常会使用到NSSet、NSArray、NSDictionary三个类，它们为我们设计较友好的数据结构时提供了很方便的方法*

对于NSSet来说，object是强引用的，和NSDictionary中的value是一样的。而NSDictionary中的key则是copy的，因此当开发者想要使NSSet的objects或者NSDictionary的values为weak，或者NSDictionary使用没有实现协议的对象作为key时，比较麻烦（需要使用NSValue的方法valueWithNonretainedObject）。
还好苹果为我们提供了相对于NSSet和NSDictionary更通用的两个类NSHashTable和NSMapTable。

关联对象实现原理

iOS底层原理总结 - 关联对象实现原理

关联对象并不是存储在被关联对象本身内存中，而是存储在全局的统一的一个AssociationsManager中，如果设置关联对象为nil，就相当于是移除关联对象。

回过头来看objc_AssociationPolicy policy 参数: 属性以什么形式保存的策略。

1
2
3
4
5
6
7
8

typedef OBJC_ENUM(uintptr_t, objc_AssociationPolicy) {
    OBJC_ASSOCIATION_ASSIGN = 0,  // 指定一个弱引用相关联的对象
    OBJC_ASSOCIATION_RETAIN_NONATOMIC = 1, // 指定相关对象的强引用，非原子性
    OBJC_ASSOCIATION_COPY_NONATOMIC = 3,  // 指定相关的对象被复制，非原子性
    OBJC_ASSOCIATION_RETAIN = 01401,  // 指定相关对象的强引用，原子性
    OBJC_ASSOCIATION_COPY = 01403     // 指定相关的对象被复制，原子性   
};
复制代码

我们会发现其中只有RETAIN和COPY而为什么没有weak呢？

NSPointerArray

1、NSPointerArray

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

- (instancetype)init {
  if (self = [super init]) {
    _delegates = [NSPointerArray weakObjectsPointerArray];
  }
  return self;
}

// 添加对象指针
- (void)addDelegate:(id)delegate {
  [_delegates addPointer:(__bridge void*)delegate];
}
// 和 NSArray在概念上不一样的地方是，NSPointerArray需要添加的是对象的指针地址，尽管他俩都是在操作指针。所以在添加对象时，需要将其转换为指针类型，__bridge转换十分具有 CoreFoundation特色


// 移除对象指针
- (void)removeDelegate:(id)delegate {
  NSUInteger index = [self indexOfDelegate:delegate];
  if (index != NSNotFound) {
    [_delegates removePointerAtIndex:index];
  }
  [_delegates compact];
}

- (NSUInteger)indexOfDelegate:(id)delegate {
  for (NSUInteger i = 0; i < _delegates.count; i += 1) {
    if ([_delegates pointerAtIndex:i] == (__bridge void*)delegate) {
      return i;
    }
  }
  return NSNotFound;
}

Here are main question we will ask during interview:
1.Data Structure:
a.linked lists
b.Stacks
c.Queues
d.binary trees
e.hash tables
2.Algorithms:
a.Sort (like quick sort and merge sort), binary search, greedy algorithms.
b.Binary tree(like traversal, construction, manipulation..)
You can find more to do exercises on https://leetcode.com/

1
2
3
4
5
6
7
8
9
10
11
12
13
14

以下是我们在面试中要问的主要问题：

1.数据结构：
a、 链接列表
b、 堆栈
c、 队列
d、 二叉树
e、 哈希表

2.算法：
a、 排序（像快速排序和合并排序），二进制搜索，贪婪算法。
b、 二叉树（比如遍历、构造、操作…）

你可以找到更多的练习https://leetcode.com/

一、二叉树

二叉树（binary tree）是指树中节点的度不大于2的有序树，它是一种最简单且最重要的树。

在二叉树中，一个元素也称作一个结点。

节点:二叉树中每个元素都称为节点。

叶子结点：就是出度为0的结点，就是没有子结点的结点。

二、几种二叉树

满二叉树、完全二叉树、平衡二叉树、最优二叉树

1、完全二叉树

若设二叉树的深度为k，除第 k 层外，其它各层 (1～k-1) 的结点数都达到最大个数，第k 层所有的结点都连续集中在最左边，这就是完全二叉树。

2、满二叉树

一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。

也就是说，如果一个二叉树的层数为K，且结点总数是(2^k) -1 ，则它就是满二叉树。

满二叉树的第i层上有2

个结点 (i≥1)。

满二叉树肯定是完全二叉树，而完全二叉树不一定是满二叉树。

3、平衡二叉树

一文读懂平衡二叉树｜技术头条

二叉搜索树（Binary Search Tree），又叫二叉排序树，简单而言就是左子树上所有节点的值均小于根节点的值，而右子树上所有结点的值均大于根节点的值，左小右大，并不是乱序，因此得名二叉排序树。

二叉搜索树的结构与值的插入顺序有关，同一组数，若其元素的插入顺序不同，二叉搜索树的结构是千差万别的。

为了避免二叉搜索树变成“链表”，我们引入了平衡二叉树(平衡二叉树必须是二叉搜索树)，即让树的结构看起来尽量“均匀”，左右子树的节点数尽量一样多。

举例：给出一组数[1,3,5,8,9,13]。假设我们就按[1,3,5,8,9,13]这样的顺序插入，其流程是这样的：

4、最优二叉树（哈夫曼树）

漫画：什么是 “哈夫曼树”？

在介绍哈弗曼树之前，我们必须先弄清楚和树相关的四个概念。

概念1：什么是路径？

在一棵树中，从一个结点到另一个结点所经过的所有结点，被我们称为两个结点之间的路径。

概念2：什么是路径长度？

在一棵树中，从一个结点到另一个结点所经过的“边”的数量，被我们称为两个结点之间的路径长度。

概念3：什么是结点的带权路径长度？

结点的带权路径长度，是指树的【根结点到该结点的路径长度】和【该结点权重】的【乘积】。

概念4：什么是树的带权路径长度？

在一棵树中，【所有】【叶子结点】的带权路径长度之和，被称为树的带权路径长度，也被简称为WPL。

哈夫曼树（Huffman Tree）是在叶子结点和权重确定的情况下，带权路径长度最小的二叉树，也被称为最优二叉树。

问：怎样构建二叉树，才能保证其带权路径长度最小？

答：原则上，我们应该让权重小的叶子结点远离树根，权重大的叶子结点靠近树根。

例：下图左侧的这棵树就是一颗哈夫曼树，它的WPL是46，小于之前例子当中的53。

1*3+3*3+4*2+6*2+8*2=48 （3+6)*3+（1+4+8）*2=27+26=53

需要注意的是，同样叶子结点所构成的哈夫曼树可能不止一颗，下面这几棵树都是哈夫曼树

问：怎么利用给定的结点和权重，构建哈弗曼树？

答：想看 漫画：什么是 “哈夫曼树”？ 还是很好理解的。

二叉树遍历

遍历是对树的一种最基本的运算，所谓遍历二叉树，就是按一定的规则和顺序走遍二叉树的所有结点，使每一个结点都被访问一次，而且只被访问一次。由于二叉树是非线性结构，因此，树的遍历实质上是将二叉树的各个结点转换成为一个线性序列来表示。

参考文章：二叉树的遍历（前序、中序、后序、已知前中序求后序、已知中后序求前序）

前序遍历：根节点->左子树->右子树（根->左->右）

中序遍历：左子树->根节点->右子树（左->根->右）

后序遍历：左子树->右子树->根节点（左->右->根）

• 前序遍历结果：GDAFEMHZ
• 中序遍历结果：ADEFGHMZ
• 后序遍历结果：AEFDHZMG

进入正题，已知两种遍历结果求另一种遍历结果（其实就是重构二叉树）

1、前序遍历的第一元素是整个二叉树的根节点

2、中序遍历中根节点的左边的元素是左子树，根节点右边的元素是右子树

3、后序遍历的最后一个元素是整个二叉树的根节点

一、Stack

stack翻译为栈，时STL中实现的一个后进先出的容器。

一、单链表

• 算法面试题：如何判断单链表中是否存在环

我们都知道单链表中结点都是一个结点指向下一个结点这样一个一个链接起来的，直到尾结点的指针域没有指向，单链表就到此结束了。

题目：已知下列是一个有环的单链表，请问如何判断单链表是否存在环

分析：把环想象成操作。

则我们通过使用快慢指针判断单链表是否存在环。
使用slow、fast 2个指针，slow慢指针每次向前走1步，fast快指针每次向前走2步，
若存在环的话，必定存在某个时候 slow = fast 快慢指针相遇。
list 带头结点的单链表
返回值 >0:存在环返回环的位置 0:不存在环

在相遇点，由于两个指针继续一个走一步，一个走两步，当再次相遇时，走一步的指针所走过的节点数记为环/操场的长度。

*那么问题来了，既然知道该单链表是代码单链表，那么我怎样将其还原为正常单链表呢？*

带环单链表去掉环

我们只需要将尾结点的next指针域置为NULL就还原为正常单链表了。我们怎样找到尾结点呢？请看代码。

1. 去掉单链表中的环，将尾结点的next域置位空。
2. 环位置结点之后的结点，判断其next域是否为环结点，如果是环节点，说明是尾结点

稳定与不稳定：如果a原本在b的前面并且a=b，排序之后a仍然在b的前面那就是稳定排序，如果排序之后a可能会出现在b的后面则是不稳定排序。所以冒泡排序是稳定的。选择排序可能不稳定。

空间复杂度：是指算法在计算机内执行时所需的存储空间与n的规模之间的关系。

时间复杂度：排序的的总操作次数，与n的规模之间的关系。

以下是我们在面试中要问的主要问题：

1.数据结构：
a、 链表
b、 堆叠
c、 排队
d、 二叉树
e、 哈希表

2.算法：
a、 排序（像快速排序和归并排序），二分搜索法，贪婪算法。
b、 二叉树（比如遍历、构造、操作…）

iOS 开发中常用的排序（冒泡、选择、快速、插入、希尔、归并、基数）算法

因为冒泡和选择排序都是原地排序算法，不需要额外的存储空间。所以其空间复杂度都是O(1)。

归并排序需要额外的空间来存储合并过程中的临时数组，其空间复杂度O(n)。

11.5.3 快速排序为什么快

在Object-C中学习数据结构与算法之排序算法

二分搜索法，是一种【在有序数组中】查找某一特定元素的搜索算法。

iOS查找算法之二分查找

漫画：五分钟学会贪心算法

有一个背包，最多能承载150斤的重量，现在有7个物品，
重量分别为[35, 30, 60, 50, 40, 10, 25]，
价值分别为[10, 40, 30, 50, 35, 40, 30]，
应该如何选择才能使得我们的背包背走最多价值的物品？

局部最优解

1、每次都尽量选择当前【价值最高】的物品
重量分别为[35, 30🚗, 60, 50🚗, 40🚗, 10🚗, 25]， 130
价值分别为[10, 40②✅, 30, 50①✅, 35④✅, 40③✅, 30]， 165

2、每次都尽量选择当前【重量最小】的物品
重量分别为[35④, 30③, 60, 50, 40⑤, 10①, 25②]， 140
价值分别为[10✅,40✅, 30, 50, 35✅, 40✅, 30✅]， 155

3、每次都尽量选择当前【价值密度最高】的物品
重量分别为[35🚗, 30🚗, 60, 50🚗, 40, 10🚗, 25🚗]， 150
价值分别为[10✅, 40✅, 30, 50✅, 35, 40✅, 30✅]， 170
价值密度 [0.285⑤, 1.333②, 0.5, 1.0④, 0.875, 4.0①, 1.2③]

想象一下下列场景：

1. 从通讯录中寻找某个联系人
2. 从一大堆文件中寻找某个文件
3. 到了影厅之后，寻找电影票上指定的座位

如果以上情况中，联系人、文件、影厅座位这些“数据”没有按照需要的顺序组织，如何找到想要的特定“数据”呢？会非常麻烦！所以说，对于需要搜索的数据，往往应该先排个序！

排序比较 & 对比归并排序与快速排序

前言

1
2
3
4
5
6

// 交换数组中的两个元素
void swap(NSMutableArray *array, NSInteger i, NSInteger j) {
    NSNumber *temp = array[i];
    array[i] = array[j];
    array[j] = temp;
}

算法图解

《034-Data-AlgorithmCollect-iOS》

一、冒泡排序

实现一个冒泡排序或者快速排序

从小到大排序：

1
2
3
4
5
6
7
8
9
10
11
12
13

假设45132，按从小到大排序
i = 0 的时候，j的相邻两个位置都要比较排一下位置：
         j = 0 的时候：arr_M = 45132(a[0]和a[1]比得到的结果)
         j = 1 的时候：arr_M = 41532(a[1]和a[2]比得到的结果)
         j = 2 的时候：arr_M = 41352(a[2]和a[3]比得到的结果)
         j = 3 的时候：arr_M = 41325(a[3]和a[4]比得到的结果)
i=0已经将第一个最大的值放到最后了。

i = 1 的时候，j的相邻两个位置都要比较排一下位置：
         j = 0 的时候：arr_M = 14325
         j = 1 的时候：arr_M = 13425
         j = 2 的时候：arr_M = 13245
i=1已经将第二个最大的值放到最后了。

冒泡排序代码实现

二、选择排序

**从数组的第a[i+1]个元素开始到第n个元素，寻找最小的元素(的位置)**。（具体过程为:先设最小位置为i=0，从该位置往后逐一比较，若遇到比之小的则记下该最小值的位置，结束后交换）；

先为a[0]取到最小值，再为a[1]取到最小值，再继续…..

从小到大排序：

1
2
3
4
5
6
7
8
9
10
11
12
13

假设45132，按从小到大排序
i = 0 的时候，j的相邻两个位置都要比较排一下位置：
     j = i+1=1 的时候：arr_M = 45132(此时a[0]的4和a[1]的5比较：得到的结果)
         j = 2 的时候：arr_M = 15432(此时a[0]的4和a[2]的1比较：得到的结果)
         j = 3 的时候：arr_M = 15432(此时a[0]的1和a[3]的3比较：得到的结果)
         j = 4 的时候：arr_M = 15432(此时a[0]的1和a[4]的2比较：得到的结果)
i=0已经将第一个最小的值放到第一位了。

i = 1 的时候，j的相邻两个位置都要比较排一下位置：
         j = 2 的时候：arr_M = 14532(a[1]和a[2]比得到的结果)
         j = 3 的时候：arr_M = 13542(a[1]和a[3]比得到的结果)
         j = 4 的时候：arr_M = 12543(a[1]和a[4]比得到的结果)
i=1已经将第二个最小的值放到最第二位了。

选择排序代码实现

三、快速排序

漫画：什么是快速排序？（完整版）

快速排序（Quicksort）是对冒泡排序的一种改进。

同冒泡排序一样，快速排序也属于交换排序，通过元素之间的比较和交换位置来达到排序的目的。

不同的是，冒泡排序在每一轮只把一个元素冒泡到数列的一端，而快速排序在每一轮挑选一个基准元素，并让其他比它大的元素移动到数列一边，比它小的元素移动到数列的另一边，从而把数列拆解成了两个部分。这种思路就叫做分治法。

1
2
3
4
5
6
7
8

// 快速排序函数 quickSort(array, 0, [array count] - 1);
void quickSort(NSMutableArray *array, NSInteger left, NSInteger right) {
    if (left < right) {
        NSInteger pivotIndex = partition(array, left, right);
        quickSort(array, left, pivotIndex - 1);
        quickSort(array, pivotIndex + 1, right);
    }
}

快速排序代码实现

1、排序原理：

设要排序的数组是A[0]……A[N-1]，首先任意选取一个数据（通常选用数组的第一个数）作为关键数据，

快排图

然后将所有比它小的数都放到它左边，所有比它大的数都放到它右边，这个过程称为一趟快速排序。

2、排序流程

快速排序算法通过多次比较和交换来实现排序，其排序流程如下：

(1)首先设定一个分界值，通过该分界值将数组分成左右两部分。

(2)将大于或等于分界值的数据集中到数组右边，小于分界值的数据集中到数组的左边。此时，左边部分中各元素都小于或等于分界值，而右边部分中各元素都大于或等于分界值。

(3)然后，左边和右边的数据可以独立排序。对于左侧的数组数据，又可以取一个分界值，将该部分数据分成左右两部分，同样在左边放置较小值，右边放置较大值。右侧的数组数据也可以做类似处理。

(4)重复上述过程，可以看出，这是一个递归定义。通过递归将左侧部分排好序后，再递归排好右侧部分的顺序。当左、右两个部分各数据排序完成后，整个数组的排序也就完成了。

四、归并排序

Hello 算法 11.6 归并排序

图解排序算法(四)之归并排序

1、划分阶段：通过递归不断地将数组从中点处分开（以把序列分成元素尽可能相等的两半），将长数组的排序问题转换为短数组的排序问题。当子数组长度为 1 时终止划分，开始合并。

归并排序思路简单，速度仅次于快速排序，为稳定排序算法，一般用于对总体无序，但是各子项相对有序的数列。

2、合并阶段：持续地将左右两个较短的有序数组合并为一个较长的有序数组，直至结束。

归并排序的合并过程如下：

1. 初始化：创建两个指针，分别指向两个已排序数组的起始位置。
2. 比较元素：比较两个指针所指向的元素。
3. 选择较小元素：将较小的元素放入临时数组，并移动该元素所在数组的指针。
4. 重复比较：重复步骤2和3，直到其中一个数组的所有元素都被比较过。
5. 复制剩余元素：如果一个数组的所有元素都已经被比较并复制到临时数组中，将另一个数组中剩余的元素直接复制到临时数组的末尾。
6. 返回临时数组：临时数组现在是一个合并后的有序数组。

示例：要将[4,5,7,8]和[1,2,3,6]两个已经有序的子序列，合并为最终序列[1,2,3,4,5,6,7,8]，来看下实现步骤。

附：深度优先遍历(DFS)和广度优先遍历(BFS)

深度优先遍历(Depth First Search, 简称 DFS)

广度优先遍历（Breath First Search, 简称 BFS） 也叫层序遍历，指的是从图的一个未遍历的节点出发，先遍历这个节点的相邻节点，再依次遍历每个相邻节点的相邻节点。

BFS 一般是解决最短路径问题。

iOS算法篇-leetcode题目记录

• iOS算法篇-leetcode题目记录

附：排序算法代码

1、冒泡排序代码实现

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

- (void)methodMaopao {
  int array[5] = {4, 5, 1, 3, 2};
    
  for (int i = 0; i < 5-1; i++) { //需要比较几遍
      for(int j = 0; j < 5-1-i; j++) { //每一遍都从0开始到倒数第-i个
          if (array[j] > array [j + 1]){
              int temp = array[j];
              array[j] = array[j + 1];
              array[j + 1] = temp;
          }
      }
  }

  for(int i = 0; i < 5; i++) {
      printf("%d\n",array[i]);
  }
}

2、选择排序代码实现

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

func sort(items: Array<Int>) -> Array<Int> {
    var list = items
    for i in 0..<list.count {
    		//记录当前最小的数，比较i+1后更大的数进行记录
        var minIndex = i
        for j in i+1..<list.count {
            if list[j] < list[minIndex] {
                minIndex = j
            }
        }
        // 交换
        let temp = list[minIndex]
        list[minIndex] = list[i]
        list[i] = temp
    }
    return list
}

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

//单趟 快速排序挖坑法
int PartSort2(int* a, int left, int right)
{
	if (left >= right) return left;
 
  int begin = left;
	int end = right;
	int key = a[left]; //保存要排序的值
	while (begin < end) //当左右指针相遇时结束
	{
    // begin是坑，从后往前找比key小的值填到坑里
		while (begin < end && a[end] >= key) {
			end--;
		}
		a[begin] = a[end];
    
    // 此时end位置是坑，从前往后比key大的值填到坑中
		while (begin < end && a[begin] <= key) {
			begin++;
		}
		a[end] = a[begin];
	}
 
	//begin和end相遇的地方是key对应的位置
	a[end] = key;
	return end; //返回排好位置的元素的下标
}

END

< 返回目录