ios常用算法

㈠ iOS面试题12-数据结构算法篇

《 2018 iOS面试题系列 》

        这里没有图啊，大家可以抽象一下。

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

        发挥想象力啊。 举个列子。数组。1-2-3-4-5-6-7-8-9-10。这个就是一个顺序存储结构 ，存储是按顺序的 举例说明啊。 栈。做开发的都熟悉。栈是先进后出 ，后进先出的形式 对不对 ？！他的你可以这样理解

        hello world 在栈里面从栈底到栈顶的逻辑依次为 h-e-l-l-o-w-o-r-l-d 这就是顺序存储 再比如 队列 ，队列是先进先出的对吧，从头到尾 h-e-l-l-o-w-o-r-l-d 就是这样排对的

        再次发挥想象力 这个稍微复杂一点 这个图片我一直弄好 ，回头找美工问问，再贴上 例如 还是一个数组

        1-2-3-4-5-6-7-8-9-10 链式存储就不一样了 1(地址)-2(地址)-7(地址)-4(地址)-5(地址)-9(地址)-8(地址)-3(地址)-6(地址)-10(地址)。每个数字后面跟着一个地址 而且存储形式不再是顺序 ，也就说顺序乱了，1（地址） 1后面跟着的这个地址指向的是2，2后面的地址指向的是3，3后面的地址指向是谁你应该清楚了吧。他执行的时候是 1(地址)-2(地址)-3(地址)-4(地址)-5(地址)-6(地址)-7(地址)-8(地址)-9(地址)-10(地址)，但是存储的时候就是完全随机的。明白了？！

        还是举例子。理解最重要。不要去死记硬背 哪些什么。定义啊。逻辑啊。理解才是最重要滴

二叉树有五种表现形式

       二叉树可以转换成森林 树也可以转换成二叉树。这里就不介绍了 你做项目绝对用不到

       数据结构大致介绍这么多吧。理解为主, 别死记，死记没什么用

从现在开始介绍算法啊

       二叉树这个比较麻烦 还有平衡二叉树 有点绕 如果不懂二叉树这一块 你是百分之二百看不懂的

原文链接

㈡ IOS 算法(中级篇) ----- 无重复字符的最长子串

输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

输入: s = ""
输出: 0

题意稍微解释下, 找到给定字符串中 最长 , 不含重复字母 子串
以 "abcabcbb" 举例, 例如:
① "a", "b", "c", "ab", "bc"...连续的都为子串, 像"abb"这种不为子串
② "a", "b", "c", "ab", "bc"为子串, 但都不是最长, 所以不满足罩袭
③ "abca"也为子串, 也很长, 但含重复字母 a , 固也不满足条件
④ "abc", "bca", "cab", 这种物衡兄最长且不含重复字母满足条件

利用 遍历法拦缓 + swift自带函数解题

定义一个容器数组存储每次遍历的字符, 如果包含则删除数组内包含之前所有元素
找当前与之前最大取最大即可

以 "abcabcbb" 举例

那么有

firstIndex:

removeFirst

㈢ iOS-数组排序

首先提供一些排序文章供大家参考学习
常用排序算法总结
iOS-八大基本排序
Sort 各类算前悄卜法和时间复杂度分析

关于iOS中，我们有自己的"sort”尚方宝剑，主要涉及的有NSComparisonResult和compare

NSComparisonResult 是一个枚举类型里面包慧穗含三个值
NSOrderedAscending = -1L,表示两个比较的对象前者小于后置
NSOrderedSame, 表示比较的对象相等
NSOrderedDescending表示两个比较的对象前者大于后者

字符串比较大小的函数，返回NSComparisonResult

数组排序方法（升序）

数组排序方法

数组排序方法（乱序）

单关键字排序

多关键字排序

其中ascending为YES表示升序排列
详细也可看这篇文章分享 iOS浅析排序规运型则描述类: NSSortDescriptor

㈣ ios SKU 组合算法

通俗来讲，一个SKU 就是商品在规格上的一种组合，比如说，一件衣服 有红色 M号的 也有蓝色 L号的 ，不同的组合就是不同的SKU

近段时间，刚好遇到要在商品详情页购买商品的时候，实现选择不同规格组合的sku，预判无库存sku选项置灰，减少客户不必要sku的选择。

网上搜寻了一大批有关sku选择算法的文章，然后被各路大神的一顿操作秀得一脸懵逼，简单来说就是没看懂。。。

当然基于以上参考得到的灵感，终于总结出来了一种简单易用通俗易懂的sku选择算法，思路简单，唯一的bug是sku数据有n多层的时候，计算量大耗内存。当然现在手机的运算能力都是杠杠的，正常来说商品的sku也不会有几十上百层那么夸张。

接下来我先捋一下思路吧！

Tips： sku 有三种状态，可选（正常），不可选（置灰），已选中（高亮），

一，sku算法初版：计算所有sku的组合 与 有库存sku的组合的交集，交集里面的sku为可选项，反之其他sku为不可选。

 1.计算所有sku的组合-->集合A

A = ["34,61,66"  , "34,61,67"  , ......]

2.计算有库存的sku的组合 -->集合B

一般是从后台服务器返回的 eg：

3. 计算集合A与集合B的交集，交集里面的所有元素就是初始时所有可选sku ID ，反之其他sku ID就是置灰（无库存不可选状态）

4.以上三步就是简易的sku算法核心思路，弹出规格框时，计算集合A和集合B的交集，得到初步赛选结果，告诉客户，哪些sku无库存不可选置灰显示，可选的为正常状态显示,减少客户做不必要的选择操作。

5.当然，细心的你很快就会发现这样的sku算法会导致无法判断出，已选sku的兄弟节点是否可选的bug。

二，优化兄弟节点的可选状态判断bug

1.如上图 已选Platform 属性的 34，长度属性的 62 ， 我们要判断的已选sku兄弟节点属性分别是Platform 属性的 35，长度属性的 61。 

2.即：

要判断 长度属性的 61是否为可选，就要判断，34，61这样的组合是否属于有库存组合里面子集，是：可选，不是： 不可选。

同理：

要判断 Platform 属性的 35是否为可选，就要判断，35，62这样的组合是否属于有库存组合里面子集，是：可选，不是： 不可选。

3.细心的你肯定发现了规律，34，61 或者 35，62 这样的组合都有一个共同点

即：包含n个已选skuID，n = 已选sku个数-1 .

三,计算兄弟节点是否可选

1,计算已选sku ID 同类属性的组合 ==集合C  即：计算Platform 属性和长度属性的组合

集合C = ["34,61","34,62","35,61","35,61","35,62"]

2.计算已选skuID的子集 ==集合D 即：计算 [34，62]的子集 

集合D = ["34","62","34,62"]

3.从集合D里面筛选出，含有n个已选skuID的子集（n = 已选sku个数-1 ）==集合E

集合E = ["34","62"]

4.最后计算可选兄弟节点组合，集合C里面的组合只要是含有集合E里面的元素都是可选兄弟节点组合

可选兄弟节点组合F = 【集合C里面的组合只要是含有集合E里面的元素】

5. 

兄弟节点可选skuID =  【（集合A与集合B的交集的skuID集合）再与 集合F 的并集 】

四，整理

1.筛选有库存的sku组合为可选sku 其余为不可选sku

2.计算兄弟节点可选sku

3.可选sku正常显示，不可选sku置灰，已选sku高亮

附Demo： sku算法demo

五，拓展一下

㈤ IOS 算法(中级篇) ----- 无重复字符串的排列组合

例:
给定: s = "qwe"
返回：["qwe", "qew", "wqe", "weq", "ewq", "eqw"]

给定: s = "ab"
返回：["ab", "ba"]

解题思路

这个题目蔽旁比较好的地方是规定了 字符串每个字符均不相同, 减少了我们很多判断处理
全排列+交换法, 交换位置之后再递归回溯

例如 初始字符串 qwe, 我们定义一个index = 0, 初始数组, [qwe]

第一轮，数组每个元素用index 0以上的，跟0做交换，得到：
wqe, eqw 加上初始qwe, 我们得到这样一个侍埋数组 [qwe, wqe, eqw]

第二宏谈橡轮，新数组每个元素用index 1以上的，跟1做交换，得到：
qew, weq, ewq, 加上之前那些 得到 [qwe, wqe, eqw, qew, weq, ewq]

为了便于理解我们再看个例子 初始字符串 JQKA, index = 0, [JQKA]

第一轮，index 0以上的，跟0做交换，得到：
QJKA, KQJA, AQKJ
数组: [JQKA, QJKA, KQJA, AQKJ]

第二轮，index 1以上的，跟1做交换，得到：
JKQA, JAKQ, QKJA, QAKJ, KJQA, KAJQ, AKQJ, AJKQ

数组: [JQKA, QJKA, KQJA, AQKJ, JKQA, JAKQ, QKJA, QAKJ, KJQA, KAJQ, AKQJ, AJKQ]

第三轮，index 2以上的，跟2做交换，得到：
JQAK QJAK KQAJ
AQJK JKAQ JAQK
QKAJ QAJK KJAQ
KAQJ AKJQ AJQK

数组: [JQKA, QJKA, KQJA, AQKJ, JKQA, JAKQ, QKJA, QAKJ, KJQA, KAJQ, AKQJ, AJKQ, JQAK QJAK KQAJ, AQJK JKAQ JAQK, QKAJ QAJK KJAQ, KAQJ AKJQ AJQK]

完成返回

按着这个思路我们可写算法

㈥ iOS算法系列（二）- 八大排序算法

排序算法也算是老生常谈了，如果你大学专业是计算机或软件，甚至你参加过国二国三都会学到排序算法，如果我没猜错的话你接触的第一个算法是冒泡。
排序算法老生常谈，但确实多少大厂面试题中的必考题。
废话不多说，开始正题
常见的八种排序算法他们的关系如下：

递归的最底部情形，是数列的大小是零或一，也就是永远都已经被排序好了。虽然一直递归下去，但是这个算法总会退出，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。

希尔排序是基于插入排序的以下两点性质而提出改进方法的：
插入排序在对几乎已经排好序的数据操作时， 效率高， 即可以达到线性排序的效率
但插入排序一般来说是低效的， 因为插入排序每次只能将数据移动一位

希尔排序的基本思想是：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行依次直接插入排序。

说基数排序之前，我们简单介绍桶排序：
算法思想：是将阵列分到有限数量的桶子里。每个桶子再个别排序（有可能再使用别的排序算法或是以递回方式继续使 用桶排序进行排序）。桶排序是鸽巢排序的一种归纳结果。当要被排序的阵列内的数值是均匀分配的时候，桶排序使用线性时间（Θ（n））。但桶排序并不是 比较排序，他不受到 O(n log n) 下限的影响。
简单来说，就是把数据分组，放在一个个的桶中，然后对每个桶里面的在进行排序。
例如要对大小为[1..1000]范围内的n个整数A[1..n]排序

各种排序的稳定性，时间复杂度、空间复杂度、稳定性总结如下图：

㈦ IOS AES加密

AES加密有四种工作模式：ECB、CBC、CFB和OFB，其中IOS支持ECB（kCCOptionPKCS7Padding 对应Java中的kCCOptionPKCS5Padding）和CBC（kCCOptionECBMode）

AES是开发中常用的加密算法之一。然而由于前后端开发使用的语言不统一，导致经常出现前端加密而后端不能解密的情况出现。然而无论什么语言系统，AES的算法总是相同的， 因此导致结果不一致的原因在于 加密设置的参数不一致 。于是先来看看在两个平台使用AES加密时需要统一的几个参数。

参考： https://welkinx.com/2016/07/30/10/

ios中使用AES128位 ECB模式加密 结果转换16进制

https://tieba..com/p/4581819586

与服务器通讯的时候，除了确定密钥外，加密模式和填充方式也要确定。第一个例子中，就是使用了kCCOptionPKCS7Padding加密模式，并且有IV(初始向量)，而第二个例子中使用了ECB(没有补码方式)。

此外也要注意转码后的密文是转成16进制，还是base64编码。

参考链接：
http://blog.51cto.com/ciphertext/1420338
https://welkinx.com/2016/07/30/10/
https://tieba..com/p/4581819586

㈧ IOS 算法(基础篇) ----- 两个数组的交集

例子：

输入派闭行：nums1 = [1,2,3,4], nums2 = [2,2]
输出：[2]

输入：nums1 = [7,9,8], nums2 = [9,4,9,8,4,5,10]
输出：[9,8]

1.先Set方法去重num1, 减少循环, let set1 = Set(nums1)
(Set和Array的区别在于，Set是无尘哗序的，且Set中不能存在重态毕复的元素)
2.遍历set1, 如果num2包含 , result就插入

/// Returns a new set with the elements that are common to both this set and
/// the given sequence.
///
/// In the following example, the bothNeighborsAndEmployees set is made up
/// of the elements that are in both the employees and neighbors sets.
/// Elements that are in only one or the other are left out of the result of
/// the intersection.
///
/// let employees: Set = ["Alicia", "Bethany", "Chris", "Diana", "Eric"]
/// let neighbors: Set = ["Bethany", "Eric", "Forlani", "Greta"]
/// let bothNeighborsAndEmployees = employees.intersection(neighbors)
/// print(bothNeighborsAndEmployees)
/// // Prints "["Bethany", "Eric"]"

㈨ 介绍iOS中MD5加密算法的使用

前言

软件开发过程中，对数据进行加密是保证数据安全的重要手段，常见的加密有Base64加密和MD5加密。Base64加密是可逆的，MD5加密目前来说一般是不可逆的。

MD5生成的是固定的128bit，即128个0和1的二进制位，而在实际应用开发中，通常是以16进制输出的，所以正好就是32位的16进制，说白了也就是32个16进制的数字。

MD5主要特点是 不可逆，相同数据的MD5值肯定一样，不同数据的MD5值不一样（也不是绝对的，但基本是不能一样的）。

MD5算法还具有以下性质：

1、压缩性：任意长度的数据，算出的MD5值长度都是固定的。

2、容易计算：从原数据计算出MD5值很容易。

3、抗修改性：对原数据进行任何改动，哪怕只修改1个字节，所得到的MD5值都有很大区别。

4、弱抗碰撞：已知原数据和其MD5值，想找到一个具有相同MD5值的数据（即伪造数据）是非常困难的。

5、强抗碰撞：想找到两个不同的数据，使它们具有相同的MD5值，是非常困难的。

6、MD5加密是不可解密的，但是网上有一些解析MD5的，那个相当于一个大型的数据库，通过匹配MD5去找到原密码。所以，只要在要加密的字符串前面加上一些字母数字符号或者多次MD5加密，这样出来的结果一般是解析不出来的。

MD5的应用:

由于MD5加密算法具有较好的安全性，而且免费，因此该加密算法被广泛使用

大多数的'登录功能向后台提交密码时都会使用到这种算法

注意点:

（1）一定要和后台开发人员约定好，MD5加密的位数是16位还是32位(大多数都是32位的)，16位的可以通过32位的转换得到。

（2）MD5加密区分 大小写，使用时要和后台约定好。

MD5解密:

解密网站:http://www.cmd5.com/

为了让MD5码更加安全 涌现了很多其他方法 如加盐。 盐要足够长足够乱 得到的MD5码就很难查到。

终端代码：$ echo -n abc|openssl md5 给字符串abc加密、

苹果包装了MD5加密的方法，使用起来十分的方便。

#import@interface MD5Encrypt : NSObject// MD5加密/**由于MD5加密是不可逆的,多用来进行验证*/// 32位小写+(NSString *)MD5ForLower32Bate:(NSString *)str;// 32位大写+(NSString *)MD5ForUpper32Bate:(NSString *)str;// 16为大写+(NSString *)MD5ForUpper16Bate:(NSString *)str;// 16位小写+(NSString *)MD5ForLower16Bate:(NSString *)str;@end

#import "MD5Encrypt.h"#import@implementation MD5Encrypt#pragma mark - 32位 小写+(NSString *)MD5ForLower32Bate:(NSString *)str{ //要进行UTF8的转码 const char* input = [str UTF8String]; unsigned char result[CC_MD5_DIGEST_LENGTH]; CC_MD5(input, (CC_LONG)strlen(input), result); NSMutableString *digest = [NSMutableString stringWithCapacity:CC_MD5_DIGEST_LENGTH * 2]; for (NSInteger i = 0; i < CC_MD5_DIGEST_LENGTH; i++) { [digest appendFormat:@"%02x", result[i]]; } return digest;}#pragma mark - 32位 大写+(NSString *)MD5ForUpper32Bate:(NSString *)str{ //要进行UTF8的转码 const char* input = [str UTF8String]; unsigned char result[CC_MD5_DIGEST_LENGTH]; CC_MD5(input, (CC_LONG)strlen(input), result); NSMutableString *digest = [NSMutableString stringWithCapacity:CC_MD5_DIGEST_LENGTH * 2]; for (NSInteger i = 0; i < CC_MD5_DIGEST_LENGTH; i++) { [digest appendFormat:@"%02X", result[i]]; } return digest;}#pragma mark - 16位 大写+(NSString *)MD5ForUpper16Bate:(NSString *)str{ NSString *md5Str = [self MD5ForUpper32Bate:str]; NSString *string; for (int i=0; i<24; i++) { string=[md5Str substringWithRange:NSMakeRange(8, 16)]; } return string;}#pragma mark - 16位 小写+(NSString *)MD5ForLower16Bate:(NSString *)str{ NSString *md5Str = [self MD5ForLower32Bate:str]; NSString *string; for (int i=0; i<24; i++) { string=[md5Str substringWithRange:NSMakeRange(8, 16)]; } return string;}@end

㈩ iOS中的哈希表

哈希表也叫散列表，是根据键值(Key value)而直接进行访问的数据结构。也就是说，它通过把键(Key)映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做哈希函数，映射函数得出的值叫哈希值或哈希码，存放记录的数组叫做哈希表。哈希表中存放数据占总空间比例叫做装填因子（负载因子）。

哈希函数的设计要达到输出值的平均分布化，这样能尽可能降低哈希冲突的概率。

一般情况下，哈希函数中输入值与输出值具有 N对1 关系。

哈希函数具有的特点：如果两个哈希码不同，则它们的键(Key)也一定不同。

该特点常用于优化比较两个对象是否相同，先判断hash码是否相同，若hash码不同则不需要进行对象比较。

哈希表优点：查找效率高，插入删除和查找时间复杂度为O(1)。

哈希表缺点：占用空间大，需要预留一定空间，否则哈希冲突概率会很大。哈希表无法记录插入顺序。

哈希函数因为会N对1的关系，会触发哈希冲突。哈希冲突常见解决方式有有以下几种：

1. 开放寻址法

线性探测（偏移1，2，3..）

可能会导致数据堆积一起，降低插入删除和查找效率。

二次方探测（偏移1*1，2*2，3*3..）

相比线性探测不容易造成数据堆积，但当装填因子比较大时，可能会造成一次查询肢升/插入中，同一位置多次被探测。

2. 拉链法

使用数组+链表解决哈希冲突问题。

开放寻址法缺点：

开放寻址法的缺点是在删除元素时，不能真的删除，否则会引起查找失败。需要在删除元素位置做个标记，代表该索引位置可以插入，但是搜索路过时不能中断搜索。

另一方面，开放寻址法因为在冲突时会占用其它哈希索引空间，所以扩容时装填因子不能太大。

哈希表扩容与缩容

当装填因子过大，会增大哈希冲突概率，需要对哈希表进行扩容，因此哈希表一般使用二级指针实现(iOS底层使用DisguisedPtr<void *>）。扩容时需要对所有数据进行重新映射（重哈希），一般每次空间*2。

当装填因子太小，且空间占用比较大，比如：if (装填因子 < 0.1 && num >1024) {缩容}。

哈希算法本质是一类安全性较高的哈希函数。Hash算法还具有一个特点，就是很难找到逆向规律。

哈希算法常用于密码安全领域，哈希算法中输入值与输出值具有 N对1 关系，常见的哈希算法包括MD5，SHA，CRC16，CRC32。

SideTables是个全局变量，是StripedMap（哈希表）类型。

StripedMap重载了[]，可通过下标的方式快速存取。

StripedMap事实上不是个常规的哈希表，我认为它可以叫做只读哈希表。它在创建之初就会以模版类型初始化满所有存储空间，且不支持修改和扩容。因此，模版类型传递指针是没有意义的。一般模版都设置为结构体，后续操作针对该结构体改值。

SideTables的哈希Key是对象地址addr，哈希函数是((addr >>4) ^ (addr >>9)) %StripeCount，Value是SideTable结构体。因此，SideTables存储着对象地址与SideTable的 N-1 关系。这样可以把对象信息分散到不同SideTable中，提升查找效率。

每个SideTable中存储一堆对象的弱引用表和引用计数表。

weak_table_t的哈希Key是对象地址，哈希函数如下：

Value是weak_entry_t。weak_table_t可以通过对象指针快速找到对象存储的weak_entry_t。

weak_table_t可进行扩容与缩容。历瞎老

当出现哈希冲突时，与weak_table_t配套的函数使用线性探测法查找。

每个weak_table_t中神蠢存储一堆对象的弱引用表。

weak_entry_t只有当装载数据超过一定长度才会启用哈希表存储功能，out_of_line()返回是否启用哈希表。weak_entry_t的哈希Key是弱指针地址，value也是弱指针地址。哈希函数与weak_table_t相同。

weak_entry_t可进行扩容，不会进行缩容。

当出现哈希冲突时，与weak_entry_t配套的函数使用线性探测法查找。

每个weak_entry_t存储指向一个对象的所有弱指针地址（二级指针）。

RefcountMap本质是DenseMap类按照指定模版typedef的类型。

RefcountMap的哈希Key是对象地址，Value是引用计数。

当value为0时，RefcountMap会自动清除这条记录。

当出现哈希冲突时，RefcountMap使用二次方探测法查找。

每个RefcountMap中存储一堆对象的引用计数。

sDataLists是存储所有@synchronized锁的全局哈希表，key是@synchronized的参数。

PropertyLocks是存储所有atomic锁的全局哈希表，key是属性生成的成员变量地址。

类对象的方法缓存cache_t使用哈希表存储bucket_t（sel+imp)，使用逆序线性探测（Index-1)解决哈希冲突。

cache_t扩容时会将所有方法缓存清空。

static objc::ExplicitInitDenseSet<const char *> namedSelectors;

namedSelectors是个全局变量，存储所有的方法名SEL，内部结构是哈希表DenseMap。

typedef DenseMap<DisguisedPtr<objc_object>, ObjectAssociationMap> AssociationsHashMap;

AssociationsHashMap是AssociationsManager中存储所有关联对象的哈希表，内部结构是DenseMap。

NSObject默认的hash方法是对象地址，即默认没有做优化。

还有个方法isEqual:方法，NSObject默认实现返回该对象与参数对象指针地址是否相同。

hash方法的本质是该对象的哈希函数，需要子类去实现。hash方法主要有两个作用，这两个作用在NSDictionary和NSSet中体现出来。

1. 与isEqual:配合，优化比较

先调用hash方法进行比较，若值相同才调用isEqualTo:进行比较。这依赖于hash的 N-1 关系。

从CF源码中可以找到CFString的源码，即可以看到NSString内部重写的hash方法。

这句话的大意是：这个字符串的大小如果小于等于96，则保证哈希的安全；如果大小大于96，则会大幅度增加哈希冲突的概率。

2. 与哈希表配合，hash方法对应哈希表的哈希函数，但返回值需要经过转换对应存储索引（一般通过取余）。此时hash方法的设计就非常重要，应做到输出哈希码的平均分散化，否则会导致数据堆叠，增大哈希冲突概率。

常见的NSDictionary和NSSet内部就是哈希表，NSDictionary会使用Key作为哈希表的Key，NSSet使用元素作为Key。它们会对Key对象调用hash方法获得初步的哈希码，然后经过转变成为存储区域的索引（下标）。

NSDictionary和NSSet因为都使用哈希表存储，因此存储元素都是无序的。

NSDictionary和NSSet在插入新元素时具体步骤如下：