iOS ------ 消息传递和消息转发

一,消息传递

在OC中,传递消息就是在对象上调用方法

相对于C语言的方法就“静态绑定”的函数,在编译器就决定了运行时所要调用的函数。在OC中,如果向某对象传递消息,就会使用动态绑定机制来决定需要调用那个方法。调用那个方法完全取决于运行期决定,甚至可以在程序运行时改变。编译时并不能确定方法有没有对应的实现,没有写方法的具体实现也不会报错。

给对象发送消息可以这样来写:

id returnValue = [someObject messageName:parameter];

本例中,someObject叫做“接收者”(receiver),messageName叫做“选择子”(selector)。选择子与参数合起来称作“消息”(message)。编译器将其转换为C语言函数调用objc_msgSend

id returnValue = objc_msgSend(someObject, @selector(messageName:), parameter);

这个函数将消息接受者,选择子和参数作为主要参数,其原型如下:

objc_msgSend(receiver, selector)                    // 不带参数
objc_msgSend(receiver, selector, arg1, arg2,...)    // 带参数

消息传递的关键在于objc_class结构体有两个关键的字段:

  • isa 指向父类的指针
  • methodLists 类的方法分发表(dispatch table)

其中对象的isa指针让对象可以访问类和类的继承链。

消息传递的过程:

  • 当消息传递给一个对象时,首先从运行时系统缓存objc_cache中进行查找。如果找到则执行,否则执行下面的步骤
  • objc_msgSend通过isa指针获取类的结构体,然后通过选择子作为“键”在方法分发表methodLists查找应该执行的方法,实际上查找的就是相应方法的IMP函数指针,Dispatch table 是一张SELIMP的对应表。也就是说方法编号SEL最后还要通过Dispatch table表找到对应的IMPIMP是一个函数指针,然后去执行这个方法
  • 如果未找到,通过isa找到父类并在父类的分发表中查找,一直沿着类的继承链找到NSObject类,一旦找到则传入相应的参数来执行方法的具体实现,并将该方法加入到本类的方法缓存objc_cache。如果一直未找到方法的实现那么消息发送阶段结束,进入动态解析阶段,解析到就结束。如果未解析到,则会进入消息转发流程。

在这里插入图片描述

消息传递分为三个阶段:

  • 消息发送阶段
  • 动态解析阶段
  • 消息转发阶段

方法查找的核心函数就是 _class_lookupMethodAndLoadCache3 函数,接下来重点分析 _class_lookupMethodAndLoadCache3 函数内的源码。

IMP _class_lookupMethodAndLoadCache3(id obj, SEL sel, Class cls)
{return lookUpImpOrForward(cls, sel, obj, YES/*initialize*/, NO/*cache*/, YES/*resolver*/);
}

lookUpImpOrForward 函数

IMP lookUpImpOrForward(Class cls, SEL sel, id inst, bool initialize, bool cache, bool resolver)
{// initialize = YES , cache = NO , resolver = YESIMP imp = nil;bool triedResolver = NO;runtimeLock.assertUnlocked();// 缓存查找, 因为cache传入的为NO, 这里不会进行缓存查找, 因为在汇编语言中CacheLookup已经查找过// Optimistic cache lookupif (cache) {imp = cache_getImp(cls, sel);if (imp) return imp;}// runtimeLock is held during isRealized and isInitialized checking// to prevent races against concurrent realization.// runtimeLock is held during method search to make// method-lookup + cache-fill atomic with respect to method addition.// Otherwise, a category could be added but ignored indefinitely because// the cache was re-filled with the old value after the cache flush on// behalf of the category.runtimeLock.lock();checkIsKnownClass(cls);if (!cls->isRealized()) {realizeClass(cls);}if (initialize  &&  !cls->isInitialized()) {runtimeLock.unlock();_class_initialize (_class_getNonMetaClass(cls, inst));runtimeLock.lock();// If sel == initialize, _class_initialize will send +initialize and // then the messenger will send +initialize again after this // procedure finishes. Of course, if this is not being called // from the messenger then it won't happen. 2778172}retry:    runtimeLock.assertLocked();// Try this class's cache.// 防止动态添加方法,缓存会变化,再次查找缓存。imp = cache_getImp(cls, sel);// 如果查找到imp, 直接调用done, 返回方法地址if (imp) goto done;// 查找方法列表, 传入类对象和方法名// Try this class's method lists.{// 根据sel去类对象里面查找方法Method meth = getMethodNoSuper_nolock(cls, sel);if (meth) {// 如果方法存在,则缓存方法log_and_fill_cache(cls, meth->imp, sel, inst, cls);// 方法缓存之后, 取出imp, 调用done返回impimp = meth->imp;goto done;}}// 如果类方法列表中没有找到, 则去父类的缓存中或方法列表中查找方法// Try superclass caches and method lists.{unsigned attempts = unreasonableClassCount();for (Class curClass = cls->superclass;curClass != nil;curClass = curClass->superclass){// Halt if there is a cycle in the superclass chain.if (--attempts == 0) {_objc_fatal("Memory corruption in class list.");}// 查找父类的缓存// Superclass cache.imp = cache_getImp(curClass, sel);if (imp) {if (imp != (IMP)_objc_msgForward_impcache) {// 在父类中找到方法, 在本类中缓存方法, 注意这里传入的是cls, 将方法缓存在本类缓存列表中, 而非父类中// Found the method in a superclass. Cache it in this class.					log_and_fill_cache(cls, imp, sel, inst, curClass);goto done;}else {// Found a forward:: entry in a superclass.// Stop searching, but don't cache yet; call method // resolver for this class first.break;}}// 查找父类的方法列表// Superclass method list.Method meth = getMethodNoSuper_nolock(curClass, sel);if (meth) {// 同样拿到方法, 在本类进行缓存log_and_fill_cache(cls, meth->imp, sel, inst, curClass);imp = meth->imp;goto done;}}}// ---------------- 消息发送阶段完成 ---------------------// ---------------- 进入动态解析阶段 ---------------------// 上述列表中都没有找到方法实现, 则尝试解析方法// No implementation found. Try method resolver once.if (resolver  &&  !triedResolver) {runtimeLock.unlock();_class_resolveMethod(cls, sel, inst);runtimeLock.lock();// Don't cache the result; we don't hold the lock so it may have // changed already. Re-do the search from scratch instead.triedResolver = YES;goto retry;}// ---------------- 动态解析阶段完成 ---------------------// ---------------- 进入消息转发阶段 ---------------------// No implementation found, and method resolver didn't help. // Use forwarding.imp = (IMP)_objc_msgForward_impcache;cache_fill(cls, sel, imp, inst);done:runtimeLock.unlock();return imp;
} 

方法缓存

在进行查找时,OC会运行时会利用缓存机制来提高查找的速度,在方法查找中,他会将最近使用过的方法实现存储在缓存中下次调用相同的方法就可以直接在缓存中获取实现,避免了反复查找的过程。

类缓存(objc_cache)

struct objc_cache {unsigned int mask /* total = mask + 1 */                 OBJC2_UNAVAILABLE;unsigned int occupied                                    OBJC2_UNAVAILABLE;Method _Nullable buckets[1]                              OBJC2_UNAVAILABLE;
};
  • mask: 指定分配的缓存 bucket 的总数。,所以缓存的 size(total)是 mask+1。

  • occupied: 指定实际占用的缓存bucket的总数。

  • buckets: 指向 Method 数据结构指针的数组。

为了加速消息分发, 系统会对方法和对应的地址进行缓存,就放在 objc_cache 中,所以在实际运行中,大部分常用的方法都是会被缓存起来的。

SEL和IMP

IMP是OC方法实现代码块的地址,可以通过它像C语言函数一样直接调用方法实现。

typedef id (&IMP)(id,SEL,...);

IMP是一个函数指针,这个被指向的函数包含一个接搜消息的对象id(self指针),调用方法的选择子SEL(方法名),以及不定个数的方法参数,并返回一个id.

SEL是OC中表示方法名的数据类型,在运行时有编译器生成的唯一标识符用于在对象查找并调用相应的方法。

/// An opaque type that represents a method selector.
typedef struct objc_selector *SEL;

OC编译时会根据方法的名字包括参数序列,生成区分这个方法的唯一ID,不管是子类还是父类,只要方法的名字包括参数序列相同,它们的ID就相同。

二,消息转发

当一个对象能够接收一个消息时,会走完正常的消息传递过程。弱无法接受会发生什么呢?

  • 默认情况下,如果以[object message] 的形式调用方法,如果object无法响应message消息时,编译器会报错
  • 如果是以performselector 的形式调用方法,则需要等到运行时才能确定object是否能接受message消息,则程序崩溃

当不确定一个对象是否能接受某个消息时,可以调用respondsToSelector:来进行判断

if ([self respondsToSelector:@selector(method)]) {[self performSelector:@selector(method)];
}

当一个对象无法接受莫哥消息时,就会启动“消息转发”机制。通过学习转发机制可以告诉对象如何处理未知的消息。

消息转发机制分为三个阶段:

  • 动态方法解析
  • 备用接受者
  • 完整消息转发

在这里插入图片描述

1,动态方法解析

// No implementation found. Try method resolver once.
//未找到实现。尝试一次方法解析器if (slowpath(behavior & LOOKUP_RESOLVER)) {behavior ^= LOOKUP_RESOLVER;return resolveMethod_locked(inst, sel, cls, behavior);}

如果没找到方法则尝试调用resolveMethod_locked动态解析,只会执行一次:

/***********************************************************************
* resolveMethod_locked
* Call +resolveClassMethod or +resolveInstanceMethod.
*
* Called with the runtimeLock held to avoid pressure in the caller
* Tail calls into lookUpImpOrForward, also to avoid pressure in the callerb
**********************************************************************/
static NEVER_INLINE IMP
resolveMethod_locked(id inst, SEL sel, Class cls, int behavior)
{lockdebug::assert_locked(&runtimeLock);ASSERT(cls->isRealized());runtimeLock.unlock();//判断是不是元类if (! cls->isMetaClass()) {// try [cls resolveInstanceMethod:sel]resolveInstanceMethod(inst, sel, cls);}else {// try [nonMetaClass resolveClassMethod:sel]// and [cls resolveInstanceMethod:sel]resolveClassMethod(inst, sel, cls);if (!lookUpImpOrNilTryCache(inst, sel, cls)) {resolveInstanceMethod(inst, sel, cls);}}// chances are that calling the resolver have populated the cache// so attempt using itreturn lookUpImpOrForwardTryCache(inst, sel, cls, behavior);
}

主要用的的方法如下

// 类方法未找到时调起,可以在此添加方法实现
+ (BOOL)resolveClassMethod:(SEL)sel;
// 对象方法未找到时调起,可以在此添加方法实现
+ (BOOL)resolveInstanceMethod:(SEL)sel;
//其中参数sel为未处理的方法

上述代码的大致流程:

  • 先检查进行解析的是否是元类
  • 如果不是元类,则调用resolveInstanceMethod:进行对象方法动态调用
  • 如果是元类,则调用resolveClassMethod:进行类方法动态解析,完成类方法动态解析后,再次查询cls中的imp,如果没有找到,则进行一次对象方法动态解析

两个方法resolveInstanceMethodresolveClassMethod则称为方法的动态决议。

执行完上述代码后返回lookUpImpOrForwardTryCache

IMP lookUpImpOrForwardTryCache(id inst, SEL sel, Class cls, int behavior)
{return _lookUpImpTryCache(inst, sel, cls, behavior);
}

这个方法调用的是_lookUpImpTryCache方法:

ALWAYS_INLINE
static IMP _lookUpImpTryCache(id inst, SEL sel, Class cls, int behavior)
{lockdebug::assert_unlocked(&runtimeLock);if (slowpath(!cls->isInitialized())) {// see comment in lookUpImpOrForwardreturn lookUpImpOrForward(inst, sel, cls, behavior);}IMP imp = cache_getImp(cls, sel);if (imp != NULL) goto done;
#if CONFIG_USE_PREOPT_CACHESif (fastpath(cls->cache.isConstantOptimizedCache(/* strict */true))) {imp = cache_getImp(cls->cache.preoptFallbackClass(), sel);}
#endifif (slowpath(imp == NULL)) {return lookUpImpOrForward(inst, sel, cls, behavior);}done:if ((behavior & LOOKUP_NIL) && imp == (IMP)_objc_msgForward_impcache) {return nil;}return imp;
}

可以看到这里有cache_getImp;也就是说在进行一次动态决议之后,还会通过cache_getImp从cache里找一遍方法的sel。

#endifif (slowpath(imp == NULL)) {return lookUpImpOrForward(inst, sel, cls, behavior);}

如果还是没找到(imp == NULL),也就是无法通过动态添加方法的话,还会执行一次lookUpImpOrForward,这时候进lookUpImpOrForward方法,这里behavior传的值会发生变化。

第二次进入lookUpImpOrForward方法后,执行到if (slowpath(behavior & LOOKUP_RESOLVER))这个判断时

// 这里就是消息转发机制第一层的入口if (slowpath(behavior & LOOKUP_RESOLVER)) {behavior ^= LOOKUP_RESOLVER;return resolveMethod_locked(inst, sel, cls, behavior);}

根据变化后的behavior值和LOOKUP_RESOLVER值之间的关系导致该if语句内部只能进入第一次。解释了为什么开头说的该动态解析resolveMethod_locked为什么只执行一次次

具体实现

+(BOOL)resolveInstanceMethod:(SEL)sel {if ([NSStringFromSelector(sel) isEqualToString:@"instanceMethodTest:"]) {Method method = class_getInstanceMethod([self class], @selector(addDynamicInstanceMethod:));IMP methodIMP = method_getImplementation(method);const char * types = method_getTypeEncoding(method);class_addMethod([self class], sel, methodIMP, types);return YES;}return [super resolveInstanceMethod:sel];
}+(BOOL)resolveClassMethod:(SEL)sel {if ([NSStringFromSelector(sel) isEqualToString:@"classMethodTest:"]) {// 类方法都是存在元类中,所以添加方法需要往元类上添加Class metaClass = object_getClass([self class]);Method method = class_getClassMethod([self class], @selector(addDynamicClassMethod:));IMP methodIMP = method_getImplementation(method);const char * types = method_getTypeEncoding(method);class_addMethod(metaClass, sel, methodIMP, types);return YES;}return [super resolveClassMethod:sel];
}-(void)addDynamicInstanceMethod:(NSString *)value {NSLog(@"addDynamicInstanceMethod value = %@",value);
}+(void)addDynamicClassMethod:(NSString *)value {NSLog(@"addDynamicClassMethod value = %@",value);
}

2,备用接受者(快速转发)

当cache中没有找到imp,猎类的继承链里的方法列表都没有找到imp,并且resolve InstanceMethod / resolveClassMethod返回NO就进入快速消息转发。也就是本类没有能力去处理这个消息,那么就交给其他类去处理。

done:if ((behavior & LOOKUP_NIL) && imp == (IMP)_objc_msgForward_impcache) {return nil;}return imp;

从imp == (IMP)_objc_msgForward_impcache进入消息转发机制。
查看一下这个方法:
竟然是汇编实现的这就又印证了汇编速度更快的结论

	STATIC_ENTRY __objc_msgForward_impcache// No stret specialization.b	__objc_msgForwardEND_ENTRY __objc_msgForward_impcacheENTRY __objc_msgForwardadrp	x17, __objc_forward_handler@PAGEldr	p17, [x17, __objc_forward_handler@PAGEOFF]TailCallFunctionPointer x17END_ENTRY __objc_msgForward

具体实现

-(id)forwardingTargetForSelector:(SEL)aSelector {if ([NSStringFromSelector(aSelector) isEqualToString:@"instanceMethodTestFastForwarding:"]) {SubFromView * subFromView = [[SubFromView alloc]init];if ([subFromView respondsToSelector:aSelector]) {return  subFromView;}}return [super forwardingTargetForSelector:aSelector];
}+(id)forwardingTargetForSelector:(SEL)aSelector {if ([NSStringFromSelector(aSelector) isEqualToString:@"classMethodTestFastForwarding:"]) {if ([SubFromView respondsToSelector:aSelector]) {return  [SubFromView class];}}return [super forwardingTargetForSelector:aSelector];
}

我们在新建的SubFromView完成相应方法的实现,然后就将消息最终转发给了su bFromview实现。

3,完整消息转发(慢速转发)

//封装方法
- (NSMethodSignature *)methodSignatureForSelector:(SEL)aSelector {NSString *method = NSStringFromSelector(aSelector);if ([method isEqualToString:@"sendMessage:"]) {//把这个方法存起来return [NSMethodSignature signatureWithObjCTypes:"v@:@"];}return [super methodSignatureForSelector:aSelector];}- (void)forwardInvocation:(NSInvocation *)anInvocation {//获得方法编号SEL sel = [anInvocation selector];//还来找备胎SpareWheel *sp = [SpareWheel new];//判断能否响应方法if ([sp respondsToSelector:sel]) {anInvocation.target = sp;}else {[super forwardInvocation:anInvocation];}
}

慢速转发需要同时实现methodSignatureForSelector和forwardInvocation两个函数,相当于是重新给该消息进行签名,然后调用forwardInvocation转发。[NSMethodSignature signatureWithObjCTypes:“v@😡”];,这里的"v@😡"是苹果官方的类型定义,

快速转发和慢速转发都会将消息转发给别的对象,它们的区别是什么?

  • 慢速转发可以转发给多个对象,而快速转发最多只能转发一个
  • 快速转发需要实现forwardingTargetForSelector这个方法,但是慢速必须同时实现methodSignatureForSelectorforwardInvocation方法。
  • 块速转发必须指定转发对象或者进行快速转发,而慢速转发作为最终步骤,可以不指定转发对象,也可以控制是否调用doesNotRecognizeSelector来控制抛异常。所以慢速转发可以避免闪退,如果最终没有可转发的对象,可以进行错误提示,提高用户体验。

总结:

  • 动态方法解析不处理,会进入消息转发流程

  • 消息转发流程有快速转发和慢速转发

  • 如果消息转发阶段,快速转发和慢速转发不处理,就进入doesNotRecognizeSelector默认抛出异常信息

在这里插入图片描述

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/378663.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

【操作系统】定时器(Timer)的实现

这里写目录标题 定时器一、定时器是什么二、标准库中的定时器三、实现定时器 定时器 一、定时器是什么 定时器也是软件开发中的⼀个重要组件.类似于⼀个"闹钟".达到⼀个设定的时间之后,就执行某个指定 好的代码. 定时器是⼀种实际开发中⾮常常用的组件. ⽐如⽹络通…

浅谈C嘎嘎类与对象

本篇文章与大家浅谈一下C嘎嘎的类与对象知识点 类的定义 关键字:class 语法格式: class 类名 { };//这里的分号不能少 此外,class有三个属性分别是private、public、protected,这三个属性是干啥的,相…

FPGA CFGBVS 管脚接法

说明 新设计了1个KU040 FPGA板子,回来之后接上JTAG FPGA不识别。做如下检查: 1、电源测试点均正常; 2、查看贴片是否有漏焊,检查无异常,设计上NC的才NC; 3、反复检查JTAG接线是否异常,贴片是…

【BUG】已解决:ValueError: Expected 2D array, got 1D array instead

已解决:ValueError: Expected 2D array, got 1D array instead 欢迎来到英杰社区https://bbs.csdn.net/topics/617804998 欢迎来到我的主页,我是博主英杰,211科班出身,就职于医疗科技公司,热衷分享知识,武汉…

本地多模态看图说话-llava

其中图片为bast64转码,方便json序列化。 其中模型llava为本地ollama运行的模型,如:ollama run llava 还有其它的模型如:llava-phi3,通过phi3微调过的版本。 实际测试下来,发现本地多模型的性能不佳&…

音视频入门基础:H.264专题(13)——FFmpeg源码中通过SPS属性获取视频色彩格式的实现

一、引言 通过FFmpeg命令可以获取到H.264裸流文件的色彩格式(又译作色度采样结构、像素格式): 在vlc中也可以获取到色彩格式(vlc底层也使用了FFmpeg进行解码): 这个色彩格式就是之前的文章《音视频入门基础…

【unity实战】使用unity制作一个红点系统

前言 注意,本文是本人的学习笔记记录,这里先记录基本的代码,后面用到了再回来进行实现和整理 素材 https://assetstore.unity.com/packages/2d/gui/icons/2d-simple-ui-pack-218050 框架: RedPointSystem.cs using System.…

入职前回顾一下git-01

git安装 Linux上安装git 在linux上建议用二进制的方式来安装git,可以使用发行版包含的基础软件包管理工具来安装。 红帽系 sudo yum install gitDebian系 sudo apt install gitWindows上安装git 去官网下载和操作系统位数相同的安装包.或者可以直接安装GitHub…

MAVSDK动态库与静态库及mavsdk_server程序macOS平台编译与安装

1.克隆mavsdk: git clone https://github.com/mavlink/MAVSDK.git --recursive 2.编译静态库 cmake -Bbuild/default -H. -DCMAKE_BUILD_TYPE=Release -DBUILD_SHARED_LIBS=OFF 生成makefile 生成成功,开始编译 cmake --build build/default -j8 成功生成libmavsdk.a 开…

谷歌邮箱被停用,开发者账号也要完犊子了?还能申诉回来?怎么申诉

当谷歌邮箱突然被停用,不少开发者可能会感到一阵心慌。大家最担心的是,这会不会影响到自己用这个邮箱注册的开发者账号?自己的APP还能不能顺利通过审核?毕竟,邮箱一旦“歇菜”,可能就意味着和它绑定的开发者…

VAE论文阅读

在网上看到的VAE解释,发现有两种版本: 按照原来论文中的公式纯数学推导,一般都是了解生成问题的人写的,对小白很不友好。按照实操版本的,非常简单易懂,比如苏神的。但是却忽略了论文中的公式推导&#xff…

几何相关计算

目录 一、判断两个矩形是否相交 二、判断两条线段是否相交 三、判断点是否在多边形内 四、垂足计算 五、贝塞尔曲线 六、判断多边形顺时针还是逆时针 七、判断凹多边形 一、判断两个矩形是否相交 当矩形1的最大值比矩形2的最小值都小,那矩形1和矩形2一定不相…

SpringBoot开发的AI导航站技术架构剖析 —— 技术如何选型 - 第520篇

历史文章(文章累计520) 《国内最全的Spring Boot系列之一》 《国内最全的Spring Boot系列之二》 《国内最全的Spring Boot系列之三》 《国内最全的Spring Boot系列之四》 《国内最全的Spring Boot系列之五》 《国内最全的Spring Boot系列之六》 《…

鸿蒙模拟器(HarmonyOS Emulator)Beta申请审核流程

文 | Promise Sun 一.背景: 鸿蒙项目开发需要使用模拟器进行开发测试,但目前想在DevEco Studio开发工具中使用模拟器就必须到华为官网进行报名申请,参加“鸿蒙模拟器(HarmonyOS Emulator)Beta活动申请”。 申请审核通…

Hi3861 OpenHarmony嵌入式应用入门--华为 IoTDA 设备接入

华为云物联网平台(IoT 设备接入云服务)提供海量设备的接入和管理能力,可以将自己的 IoT 设备 联接到华为云,支撑设备数据采集上云和云端下发命令给设备进行远程控制,配合华为云物联网平台的服 务实现设备与设备之间的控…

微信小程序---npm 支持

一、构建 npm 目前小程序已经支持使用 npm 安装第三方包,但是这些 npm 包在小程序中不能够直接使用,必须得使用小程序开发者工具进行构建后才可以使用。 为什么得使用小程序开发者工具需要构建呢❓ 因为 node_modules 目录下的包,不会参与…

【学习笔记】无人机(UAV)在3GPP系统中的增强支持(十一)-无人机服务可用性用例需求

引言 本文是3GPP TR 22.829 V17.1.0技术报告,专注于无人机(UAV)在3GPP系统中的增强支持。文章提出了多个无人机应用场景,分析了相应的能力要求,并建议了新的服务级别要求和关键性能指标(KPIs)。…

Study--Oracle-07-ASM自动存储管理(二)

一、ASM安装准备条件 1、ASM支持存储类型 本地祼设备(本地的磁盘和分区) 网络附加存储(NAS) 存储区域网络(SAN) 2、ASM使用本地裸设备,要点: 已经被挂载到操作系统上或者已经做了分区 映射裸设备为文件名 设置正确的权限(针对grid用户和asmadmin组,权限为660) 二、OR…

快速排序及归并排序的实现与排序的稳定性

目录 快速排序 一. 快速排序递归的实现方法 1. 左右指针法 步骤思路 为什么要让end先走? 2. 挖坑法 步骤思路 3. 前后指针法 步骤思路 二. 快速排序的时间和空间复杂度 1. 时间复杂度 2. 空间复杂度 三. 快速排序的优化方法 1. 三数取中优化 2. 小区…

贪心算法(2024/7/16)

1合并区间 以数组 intervals 表示若干个区间的集合,其中单个区间为 intervals[i] [starti, endi] 。请你合并所有重叠的区间,并返回 一个不重叠的区间数组,该数组需恰好覆盖输入中的所有区间 。 示例 1: 输入:inter…