面试总结

网络基础:

    1. TCP/UDP的特点和区别,以及为什么会有这些特点和区别?如TCP怎么保证传输的安全性.
    2. 详细描述下三次握手和四次分手,为什么建立三次握手四次分手,为什么能保证数据传输的安全性?
    3. DNS解析,以及回车键时,到底进行了哪些操作和数据通信?
    4. Socket是什么?与tcp/udp之间的关系?
    5. HTTP和HTTPS.HTTP是七层架构下的那一层协议?TCP是七层架构下的那一层协议?
    6. Get和Post请求的区别.

TCP:
1. 面向连接:传输之前建立连接,传输结束断开连接.
2. 可靠传输:等值等待协议,无差错传输(超时重传,确认丢失,确认迟到),保证数据的不丢失不重复按序到达
3. 面向字节流:tcp会根据实际情况对数据字节进行划分,分段传输
4. 流量控制:滑动窗口协议,发送窗口的大小,既取决于发送缓存的大小又由接收大小控制.接收窗口的大小,既取决于接收缓存的大小,又由tcp报文首部的窗口值反向制约发送窗口大小来控制速率.
5. 拥塞控制:慢开始,拥塞避免,快恢复,快重传.开始发送报文窗口指数增长即慢开始,直到到达门限值,采用拥塞避免策略线性增长窗口.直到产生拥塞(怎样判断产生拥塞:比如发送报文连续三个确认ACK报文未收到)此时需要采用拥塞避免乘法减小策略.然后重新慢开始.同时减低门限值

UDP:User dataPacker Protocol,用户数据包协议
特点:无连接,尽最大努力交付(不保证可靠传输),面向报文(不合并也不拆分,直接将应用层报文一起封装UDP内传输).
无大报.
UDP:User dataPacker Protocol,用户数据包协议
特点:无连接,尽最大努力交付(不保证可靠传输),面向报文(不合并也不拆分,直接将应用层报文一起封装UDP内传输).
无大报.

数据通信三次握手四次分手具体:
SYN(同步报文):synchronization同步单词,
ACK :(Acknowledge character）即是确认字符
Fin :终止报文
建立连接:
1. 客服端发送SYN同步报文到Server端
2. Server返回ACK+SYN报文
3. 客户端返回ACK确认报文
发送数据
断开连接:
1. 客户发送Fin终止报文到Server端
2. Server返回ACK确认报文(此时断开单项连接)
3. Server发送Fin+ACK确认终止报文
4. 客户端发送ACK确认报文(断开双向连接)
为什么启动三次握手四次分手?
客服端发送建立连接请求SYN同步报文后,如果出现网络等其他因素发生超时,客户端会启动超时重传策略,再次发送SYN同步报文,此时Server端返回SYN+ACK确认报文,第三次客户端的ACK确认报文只会发送一次.确认需要建立哪次连接.以避免此处超时.

输入网址回车键时,到底进行了哪些操作和数据通信?
1. DNS解析(客户端会将域名通过DNS解析服务器解析返回对应的IP地址和端口号,再由IP服务器发送网络请求),DNS也是使用UDP协议通信
2. 发送TCP三次握手,建立TCP连接
3. 服务器响应请求,进行数据通信,得到HTML代码
4. 浏览器解析HTML代码.请求资源
5. 浏览器渲染UI

什么是Socket?
Socket是对TCP/IP协议的封装,我们可以通过它更加方便的调用api,我们可以基于此封装自己的通信协议.
Socket连接:sockt连接即所谓的长连接.客户端和服务端一旦建立连接就不会主动断掉.心跳检测:服务端或者客户端会每隔一段时间发送一个心跳包用来检测连接状态.
HTTP连接:http连接就是所谓的短连接,客户端向服务端发送一次网络请求,服务器端响应连接后会断开连接.

HTTP和HTTPS?
HTTP:超文本传输协议是应用层协议.是基于TCP连接的.
HTTPS:安全性高的超文本传输协议,基于SSL/TSL非对称加密算法建立连接.传输过程还是使用对称加密算法.

GET和POST请求的区别?

  1. GET直接拼接参数在url之后
  2. GET参数长度一般较小
  3. GET安全性较低.

设计模式?你知道哪些设计模式,日常开发中是怎么应用的?

1. 设计模式?你知道哪些设计模式,日常开发中是怎么应用
  1. MVC设计模式,model和view相互隔离互不干扰,通过controller来进行数据通信
  1. 单例设计模式的使用
    1. 常见share方法实现内,alloc,init创建对象.
    2. 重写allocWithZone方法,dispact_once保证一次创建,并且加锁@ synchronized互斥锁保证多线程环境下创建安全.
    3. 重写init,copyWithZone,mutableCopyWithZone方法此三个方法内部直接调用allocWithZone保证对象仅会创建一次.
  1. 代理设计模式(UItableView,自定义代理传值)手写单例代码
  1. 观察者模式
    1. 系统通知
    2. KVO(手动实现KVO)

git的使用和日常开发中的问题处理?

1. git的使用和日常开发中的问题处理?
  1. 分支的使用,创建分支.合并分支时需要先到主分支再合并子分支代码.
  1. git暂存:git stash
    场景:
    1. 当前任务为完成但是需要修复紧急bug,再回头处理当前任务,暂存任务,切换到其他分支工作.
    2. 用于自己的任务未完成不提交到服务器但是拉取服务器上其他开发人员代码.
  1. 打tag,标记上线版本

iOS相关:

多线程

多线程:
串行并行，异步同步的区别？
并行,并发的区别?
进程和线程的关系和区别?
多线程的几种实现方式以及优缺点
1. 准确说出多线程的几种实现方式以及特点.
2. GCD怎么实现并发数的控制.
3. 多线程多读单写的实现?
4. 异步组队列调用?
5. NSOperation的有几种状态?怎么用NSOperation实现串行队列?并发队列?怎么实现任务依赖?
6. NSThread内部实现?怎么实现一个常驻线程?
7. 锁的概念,你知道哪些锁?以及开发中看具体使用?

什么是同步?什么是异步?

1. 同步:在当前线程中执行任务,不具备开启新线程的能力主线程同步进行耗时操作会阻塞主线程需要使用异步处理(sync)
2. 异步:在新的线程中执行任务,具备开启新线程的能力.(async)
例子:

什么是串行访问?什么是并发访问?串行/并发 全局队列,主队列

1. 串行队列:一个任务结束以后,在执行下一个任务(串串)
2. 并发队列:多个任务可以同时进行.
3. 主队列:永远在主线程上工作的串行队列.
4. 全局队列:和并发队列,执行效果一样,只是说,并发队列,需要我们程序员,自己创建.而全局队列,是由于系统提供

在主队列中同步串行访问?会造成什么问题?为什么?在自定义的串行队列会有问题吗?

GCD

NSOperation(AFNetworking)

NSThread(常驻线程)

多线程与锁.

- (void)viewDidLoad {
    [super viewDidLoad];
    dispatch_sync(dispatch_get_main_queue(), ^{
        [self doSomething];
    });
}

原因:死锁,由队列引起的循环等待.
流程:主队列执行viewDidLoad任务,又提交了一个block任务.都需要分配到主线程中去执行,主队列的特点又是先进先出,就是第一个任务执行完成后才能执行第二个任务.此时block任务在viewDidLoad内.block的任务开始依赖viewDidload的任务完成.所以产生队列引起的循环等待.

自定义的串行队列:不会产生问题,首先主队列执行viewDidLoad任务,过程中同步执行block任务,但是是在自定义的串行队列上执行(也是在主线程上执行),执行完成以后再在主队列上执行viewDidLoad后续操作.不会产生问题,因为没有在一个队列上进行,不用遵循一个队列的先进先出原则.

全局队列同步执行任务

- (void)viewDidLoad {
    [super viewDidLoad];
    dispatch_queue_t global_queue = dispatch_get_global_queue(0, 0);
    NSLog(@"1");
    dispatch_sync(global_queue, ^{
        NSLog(@"2");
        dispatch_sync(global_queue, ^{
            NSLog(@"3");
        });
        NSLog(@"4");
    });
    NSLog(@"5");
    
}

打印结果12345.

流程:首先执行1,同步并发队列执行任务2,再在里面同步并发处理任务3(因为是并发操作可以执行,同步又是在当前线程处理),在执行任务4,最后5.

- (void)viewDidLoad {
    [super viewDidLoad];
    dispatch_queue_t global_queue = dispatch_get_global_queue(0, 0);
    dispatch_async(global_queue, ^{
        NSLog(@"1");
        [self performSelector:@selector(printLog) withObject:self afterDelay:0];
        NSLog(@"3");
    });
    
}
- (void)printLog {
    NSLog(@"2");
}
打印结果:13
2不打印.

知识点:asyn开启子线程,子线程RunLoop默认是不开启的,performSelector:withObject:afterDelay方法是NSTimer内部方法,需要提交任务到RunLoop因为RunLoop不开启所以不会执行.

多读单写的实现?
读者读者并发,读者和写者互斥.写者和写者互斥.

异步栅栏调用.(形象理解)

//1. 创建全局并发队列
current_queue = dispatch_queue_create("read_write_queue", DISPATCH_QUEUE_CONCURRENT);

- (id)objectForKey:(NSString *)key {
    __block id obj;
    //2. 并发队列中同步执行读取操作
    dispatch_sync(current_queue, ^{
        obj = [userCenterDic objectForKey:key];
    });
    return obj;
}
- (void)setObject:(id)obj ForKey:(NSString *)key {
    //3. 异步栅栏调用内写入操作
    dispatch_barrier_async(current_queue, ^{
        [self->userCenterDic setObject:obj forKey:key];
    });
    
}
步骤:
1. 创建全局并发队列
2. 并发队列中同步执行读取操作
3. 异步栅栏调用内写入操作

网络下载多张图片全部完成后拼接成一张图片?
异步组队列调用

//1. 创建全局并发队列
current_queue = dispatch_queue_create("read_write_queue", DISPATCH_QUEUE_CONCURRENT);
//2. 创建group
dispatch_group_t group = dispatch_group_create();
    for (NSURL *url in urls) {
        //3. dispatch_group_asyn异步组队列执行多任务
        dispatch_group_async(group, current_queue, ^{
            NSLog(@"拿到url获取图片 %@",url);
        });
    }
// 4. dispatch_group_notify监听组内任务执行完毕,开始执行其他任务.
dispatch_group_notify(group, current_queue, ^{
        NSLog(@"所有图片下载完成,拼接图片");
    });

1. 创建全局并发队列
2. 创建group
3. dispatch_group_asyn异步组队列执行多任务
4. dispatch_group_notify监听组内任务执行完毕,开始执行其他任务.

NSOperation相关

NSOperation(任务)和NSOperationQueue(操作队列).
1. 任务依赖(怎么实现?),a任务依赖b任务的执行,方便的控制操作之间的执行先后顺序.
2. 任务状态控制
3. 最大并发量

面试点:
1. NSOperation子类重写start方法会怎么样?重写mian方法会怎么样?
2. NSOperation怎么实现一个串行队列怎么实现一个并发队列?
3. NSOperationQueue有几种创建方式?
4. NSOperation怎么添加任务依赖?作用是什么?
  1. NSOperation子类重写main方法系统会控制状态的实现.
    NSOperation子类重写start方法需要自行控制任务状态实现.
    源码分析.通过kvo的方法监听状态.实现一系列操作.
    显示start方法.内部会实现当前任务状态的具体逻辑
    重写start方法.相当于系统的默认实现都被覆盖掉了.
    重写main是在start函数内部,以及实现了任务状态.
  2. 通过控制NSOperationQueue最大并发数来控制,maxConcurrentOperationCount来控制,为1就是串行队列,大于1就是并发队列
  3. 两种创建方法1. 主操作队列(运行在主线程上的队列) 2 . 自定义操作队列
1. 主队列
NSOperationQueue *queue = [NSOperationQueue mainQueue];
2. 自定义队列
NSOperationQueue *queue = [[NSOperationQueue alloc] init];


//添加任务依赖
[operation addDependency:operation1];
//移除任务依赖
[operation removeDependency:operation1];


//添加任务到操作队列中
[queue addOperation:operation];


//模拟异步耗时主线程刷新UI操作
//1.创建队列
    NSOperationQueue *queue = [[NSOperationQueue alloc]init];
    [queue addOperationWithBlock:^{
        //2. 添加耗时操作
        for (int i = 0; i < 2; i++) {
            [NSThread sleepForTimeInterval:2]; // 模拟耗时操作
            NSLog(@"模拟耗时操作%@", [NSThread currentThread]); // 打印当前线程
        }
        //3. 回到主线程
        [[NSOperationQueue mainQueue]addOperationWithBlock:^{
            NSLog(@"刷新UI");
        }];
    }];

1. 创建队列
2. 添加操作
3. 回到主线程刷新UI


监听操作的四种状态:准备执行完成取消
isReady
isExcuting
isFinished
isCancel

NSThread相关

1. NSThread启动流程?
2. 如何实现一个常驻线程?
  1. 首先执行start方法,然后执行main方法内部执行[target performSelect]方法.最后执行exit方法退出线程
  1. 常驻现成的实现
    1.懒加载NSThread.内部@selector方法开启runLoop
    2.获取当前runLoop开启
    3.在此thread执行相应方法
//1. 懒加载
- (NSThread *)thread{
    
    if(!_thread){
        _thread = [[NSThread alloc] initWithTarget:self selector:@selector(threadRunloopPoint:) object:nil];
        [_thread start];
    }
    return _thread;
}
//2. 获取当前runloop(此时在子线程默认是不开启的),开启runLoop
- (void)threadRunloopPoint:(id)__unused object{
    NSLog(@"%@",NSStringFromSelector(_cmd));
    @autoreleasepool {
        [[NSThread currentThread] setName:@"changzhuThread"];
        NSRunLoop *runLoop = [NSRunLoop currentRunLoop];
        //// 这里主要是监听某个 port，目的是让这个 Thread 不会回收
        [runLoop addPort:[NSMachPort port] forMode:NSDefaultRunLoopMode];
        [runLoop run];
    }
}
//3.  [self performSelector:@selector(run) onThread:self.thread withObject:nil waitUntilDone:NO modes:@[NSDefaultRunLoopMode]];

- (void)run {
    NSLog(@"task1----%@",[NSThread currentThread]);
    NSLog(@"run");
    
    NSRunLoop *loop = [NSRunLoop currentRunLoop];
    [loop addPort:[NSPort port] forMode:NSDefaultRunLoopMode];
    [loop run];
    
}

1. 懒加载NSThread创建子线程保证创建同一个子线程@selector执行runLoop开启的方法
2. 获取当前runloop(此时在子线程默认是不开启的),开启runLoop
3. 执行要执行的事件.

锁的概念?在日常开发过程中都使用过哪些锁?具体使用场景

  1. @synchronized
  2. atomic
  3. OSSpinLock
  4. NSLock,NSRecursiveLock
  5. dispatch_semaphore_t(信号量)
1. @synchronized一般创建单例对象的时候使用,保证多线程环境下创建对象是唯一的.
2. atomic原子性:此属性修饰的对象,读写是安全的,使用是不安全的,具体是在set和get方法内,保证了线程的安全.但是如可变数组等对象,进行添加操作(add)是无法保证线程安全的
3. NSSpinLock:自旋锁,循环等待询问,不释放当前资源.具体使用场景,系统引用计数+1,-1操作.
4. NSLock.线程同步问题,保证互斥.加锁内部再加锁会造成死锁,需使用NSRecursiveLock递归锁.

[lock lock]加锁
[lock unlock]解锁
5. dispatch_semaphore_t:信号量,线程同步共享资源互斥访问.可以控制线程的最大并发数
1. create创建信号量
2. wait等待线程
3. signal唤醒线程.
//创建结构体semaphore
dispatch_semaphore_create(1);
//阻塞线层,主动行为
dispatch_semaphore_wait(dispatch_semaphore_create(1), DISPATCH_TIME_FOREVER);
//唤醒线程,被动行为
dispatch_semaphore_signal(dispatch_semaphore_create(1));

-(void)dispatchSignal{
    //crate的value表示，最多几个资源可访问
    dispatch_semaphore_t semaphore = dispatch_semaphore_create(2);
    dispatch_queue_t quene = dispatch_get_global_queue(DISPATCH_QUEUE_PRIORITY_DEFAULT, 0);
     
    //任务1
    dispatch_async(quene, ^{
        dispatch_semaphore_wait(semaphore, DISPATCH_TIME_FOREVER);
        NSLog(@"run task 1");
        sleep(1);
        NSLog(@"complete task 1");
        dispatch_semaphore_signal(semaphore);
    });
    //任务2
    dispatch_async(quene, ^{
        dispatch_semaphore_wait(semaphore, DISPATCH_TIME_FOREVER);
        NSLog(@"run task 2");
        sleep(1);
        NSLog(@"complete task 2");
        dispatch_semaphore_signal(semaphore);
    });
    //任务3
    dispatch_async(quene, ^{
        dispatch_semaphore_wait(semaphore, DISPATCH_TIME_FOREVER);
        NSLog(@"run task 3");
        sleep(1);
        NSLog(@"complete task 3");
        dispatch_semaphore_signal(semaphore);
    });
}
打印结果:先执行两个,此两个任务是随机的执行完以后在执行第三个任务
run task 2
run task 3
complete task 2
complete task 3
run task 1
complete task 1

此段代码的意思是:首先创建信号量2,只能开启两个线程执行任务.代码内dispatch_semaphore_wait(semaphore, DISPATCH_TIME_FOREVER);代表主动阻塞线程,等待任务能够被访问.可以访问时被动signal执行任务操作.所以会先完成两个任务.完成后才能处理第三个任务.

RunTime和RunLoop

RunLoop

RunLoop面试:

1. 什么是RunLoop以及RunLoop的实现机制?
2. 什么是事件循环机制?
3. RunLoop和NSTimer之间的关系.
4. RunLoop和多线程之间的关系.
5. RunLoop有多少种mode作用是什么?
6 你是否使用过commonMode以及对他的理解?
7. Source0和Source1的区别?
8. 当一个处于休眠状态的RunLoop我们可以通过哪些方式将其唤醒?
9. 滑动tableview时.banner条无法自动滚动的原因和解决办法?怎么保证子线程数据更新UI的时候不打断用户的滑动操作?
10. 第一次我们点击一个app图标.运行到最终退出app进行了哪些过程?系统都发生了什么?
11. RunLoop和线程是样的一个关系?子线程上的RunLoop使用需要注意什么?

RunLoop:
通过内部维护的事件循环来对事件/消息进行管理的一个对象.

什么是事件循环?
没有消息/事件处理时,休眠以避免资源浪费,有消息处理时,立刻被唤醒.发生了用户态和内核态状态的相互切换.

main函数为什么能保证程序的不退出?
main函数内部维护了一个RunLoop运行循环.

RunLoop的数据结构:
CFRunLoop的结构:

1. pthread:一一对应为什么说RunLoop和线程是一一对应的?从CFRunLoop的底层源码中,我们可以发现,里面包含了一个pthread机构,可以解释为什么一一对应.
2. currentMode类型CFRunLoopMode
3. modes:是一个集合NSMutableSet<CFRunLoopMode *>
4. commonModes:是一个集合NSMutableSet<NSString *>特殊性:不是实际存在的模式.和DefaultMode是不一样的.是同步source/Timer/Observer到多个Mode中的一种技术方法.
5. commonModeItems:里面包含observes,sources,timers.

CFRunLoopMode的结构:

1. name:如NSDefaultRunLoopMode.
2. sources0:NSMutableSet无序的
3. sources1:NSMutableSet无序的
4. observers:NSMutableArray有序的
5. timers:NSMutableArray有序的

CFRunLoopSource结构:

source0:需要手动唤醒线程.处理点击事件等.
source1::具备唤醒线程的能力:捕获事件交给source0处理.

CFRunLoopTimer:
基于事件的定时器.

CFRunLoopObserver:我们可以监听RunLoop的哪些时间点呢?
进入,timer事件之前,sources事件之前,休眠状态之前,准备唤醒,退出

1. Entry:runLoop的入口时机
2. BeforeTimers:将要对timer的一些事件进行处理
3. BeforeSources:将要对source进行处理
4. BeforeWaiting:将要进入休眠状态.
5. AfterWaiting:
6. Exit:退出

RunLoop的Mode:有哪些Mode?为什么会有多个mode?如何将Timer添加到两个mode中?
如果当前运行在mode1我们只能处理mode1上面的source1,observers,timers事件处理,无法接收到Mode2上面的事件进行处理.

1. NSDefaultRunLoopMode:点击,消息等事件处理
2. UITrackingRunLoopMode:滑动事件

事件循环的实现机制:

1. RunLoop启动之后,首先发送一个通知,告知观察者即将启动.
2. 将要处理timer/Source0事件的通知发送
3. 处理Source0事件
    1. 如果有Source1事件要处理,处理唤醒时收到的消息
    2. 如果没有Source1事件要处理,线程将要进入休眠.发送通知
        1. 正式进入休眠(用户态到内核态的切换)
        2. 休眠状态1. Source1,Timer回调,外部手动唤醒 此时唤醒线程
        3. 线程刚被唤醒,发送通知.
        4. 继续循环处理步骤2中的事件.

滚动tableView定时器事件无法滚动的原因:

1. RunLoop默认只能处理一个Mode下的事件的.滑动tableView的时候,会从DefaultMode下切换到UITrackingMode上,此时timer是在DefaultMode模式下是无法进行事件处理的.
解决办法:
1. 将banner中的timer通过相应api添加到commonMode下.注意此时coomonMode并不是实际的Mode,他只是将当前mode打上commonMode标记,此时我们可以将事件源同步到多个mode中相应集合中.
怎么保证子线程数据更新UI的时候不打断用户的滑动操作?
首先数据更具在子线程,我们刷新时需要在主线程更新,我们滑动操作是此时处于UITrackingMode模式下,我们需要将更新UI的操作封装放在DefaultMode模式下,此时不会影响滑动的MOde下的事件处理.

点击一个app图标:

1. 属于冷启动.此时第一步dyld动态链接器.
2. RunTime时期.
3. main函数时期,启动主线程RunLoop.开始处理事件处理完成进入休眠状态.当我们点击内部收到Source1,RunLoop被唤醒重现Source0开始处理事件.
4. app杀死,RunLoop退出,发送即将退出RunLoop通知,退出程序.

RunLoop和线程

1. RunLoop和线程是一一对应的,系统默认只开启主线程的RunLoop
2. 子线程的RunLoop默认是不开启的.需要手动开启.不然无效

RunTime

1. RunTime能做哪些事情,KVO的实现原理?Notification的实现原理?以及数据结构?
2. RunLoop是什么,数据结构是怎么样的?有几种模式,以及作用?能做什么事情?
3. 滑动事件导致NSTimer无法继续响应有什么解决办法和思路?

OC基础:
1. OC中对象的类型?数据结构?对象的基本特点.isa,superClass?指针指向?
2. 事件的响应链条?
3. 消息的传递机制,以及消息转发流程?面试题:一个对象发送消息,发生了什么?
4. @synthesize 和 @dynamic 分别有什么作用？
5. category实现，底层实现与原理?
内存管理相关?
1. strong和copy的区别?
2. 怎样让一个类能实现copy操作?为什么这样就可以?
3. 对weak属性的理解?

循环引用:

block:
什么是block,为什么block说是一个对象?block的循环引用?

UItableView的性能优化

1. 谈谈你对UITableView的性能优化
  1. cell的重用(UITableView的重用池),创建当前屏幕所显示的cell,移出屏幕的cell放在缓存池中需要用到直接从缓存池中取.
    2.cell的高度计算
  2. 图像的显示原理层面方向

图像的显示原理?

1. 以及UI卡顿的优化?以及怎么检测卡顿?

检测卡顿:通过添加Observer到主线程RunLoop状态切换的耗时来达到检测卡顿的目的.

Switf相关:

swift和OC相比有哪些特点?
struct和class区别?
什么是尾随闭包?什么是逃逸闭包?

编程方式

1. 什么是函数式编程?
2. 什么是链式编程?
3. 怎么实现链式编程?
4. 什么是响应式编程,你对响应式编程有哪些了解?

第三方框架

1. SDWebImage实现原理?
2. AFNetWoring实现原理?
3. FMDB的实现原理?

APP整体面试:

1. APP的启动速度优化方案?

2. APP瘦身?以及代码优化处理?
  1. main函数之前进行过哪些操作?怎么优化启动速度?

3. APP耗电量怎么优化?
  1. 有哪些地方可能存在电量消耗过大的问题?怎么处理?

APP架构

MVC和MVVM的特点?区别?iOSAPP怎么设计架构,复杂的页面怎么设计架构?怎么实现原生代码动态更换文字和图片等内容.

开发中你有遇到过什么问题?是怎么解决的?

数据结构和算法:

目标:了解基本数据结构
递归算法?斐波那契数列.
objc的数据机构?
冒泡排序思路以及实现代码?
插入排序思路以及实现代码?
选择排序思路以及实现代码?

常用数据结构

  1. 数组:有序集合,连续存放,可以直接通过下标取值,查询效率高
    必须实现定义固定长度,不能适应动态数据.
  2. 链表(单项链表和双向链表):链表中的元素在内存中不是顺序储存的,而是通过元素中的指针联系到一起的.
    链表动态的进行储存分配,但是链表需要第一个元素开始一直找到需要的元素位置.查询效率低
  3. 堆:先进先出,iOS堆区内存需要手动管理.例如block的循环引用就是在堆区新开辟内存空间
  4. 线性表(栈:特殊的线性表):先进后出的原则,oc中的控制器push.pop栈顶控制器先释放.
  5. 散列表(哈希表),字典集合 1. 折中数组和链表的优缺点,既方便查找也不用申请固定内存空间.但是不能存储相同key.
  6. 二叉树.(掌握二叉树的遍历,先序遍历,中序遍历,后序遍历)

遍历是对树的一种最基本的运算，所谓遍历二叉树，就是按一定的规则和顺序走遍二叉树的所有结点，使每一个结点都被访问一次，而且只被访问一次。由于二叉树是非线性结构，因此，树的遍历实质上是将二叉树的各个结点转换成为一个线性序列来表示。
设L、D、R分别表示遍历左子树、访问根结点和遍历右子树， 则对一棵二叉树的遍历有三种情况：DLR（称为先根次序遍历），LDR（称为中根次序遍历），LRD （称为后根次序遍历）


先序遍历:
void XXBL(tree *root){
    //DoSomethingwithroot
    if(root->lchild!=NULL)
        XXBL(root->lchild);
    if(root->rchild!=NULL)
        XXBL(root->rchild);
}
中序遍历
void ZXBL(tree *root)
{
    if(root->lchild!=NULL)
        ZXBL(root->lchild);
        //Do something with root
    if(root->rchild!=NULL)
        ZXBL(root->rchild);
}
后序遍历
void HXBL(tree *root){
    if(root->lchild!=NULL)
        HXBL(root->lchild);
    if(root->rchild!=NULL)
        HXBL(root->rchild);
        //Do something with root
}

找到现在问题定位,不是学习更多新的东西,是把已经掌握的东西记得滚瓜烂熟.才能更好的完成面试.

最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 206,214评论 6赞 481
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 88,307评论 2赞 382
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 152,543评论 0赞 341
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 55,221评论 1赞 279
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 64,224评论 5赞 371
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 49,007评论 1赞 284
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 38,313评论 3赞 399
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 36,956评论 0赞 259
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 43,441评论 1赞 300
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,925评论 2赞 323
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 38,018评论 1赞 333
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 33,685评论 4赞 322
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 39,234评论 3赞 307
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 30,240评论 0赞 19
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,464评论 1赞 261
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 45,467评论 2赞 352
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 42,762评论 2赞 345