iOS开发之一数据结构与算法

1、 数据结构 其实就是数据和结构，就是一堆数据在内存中以什么样的形式存在。

10年专注成都网站制作，成都定制网站，个人网站制作服务，为大家分享网站制作知识、方案，网站设计流程、步骤,成功服务上千家企业。为您提供网站建设,网站制作,网页设计及定制高端网站建设服务,专注于成都定制网站,高端网页制作,对成都三轮搅拌车等多个方面，拥有丰富的网站制作经验。

2、 数据 在内存中的结构分为 逻辑结构 和 物理结构 。

数据在内存中有4种：集合结构， 线性结构，树型结构，图形结构。

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 算法(中级篇) ----- 最小路径和

例如:

输入:

[

[1,2,3],

[4,5,6],

[7,8,9]

]

输出: 21

解释: 因为路径 1→2→3→6→9 的总和最小。

输入:

[

[1,0,3],

[4,2,1],

[3,2,2]

]

输出: 6

解释: 因为路径 1→0→2→1→2 的总和最小。

解题思路

这道题题意思很好理解, 但一些实际动手操作的话也是有点难度

因为有几个很难下手点:

每行最小怎么找到?

最小路径怎么选取?

怎么判断处理拐点?

因为题目描述是"一条从左上角到右下角的路径", 所以针对当前单元格(i, j),只用考虑3种情况

左边界单元格只能从上方单元格移来

上边界单元格只能从左边单元格移来

其他情况(i, j) 只能从左边单元格(i-1, j)或上方单元格(i, j-1)移到

接下来我们做的是, 把原来数组值替换, 替换到达这里面的最小值

可以看到

i = 0, j = 0 起点值不变

i ≠ 0, j = 0 左边界, cgrid[i][j] = cgrid[i-1][j] + cgrid[i][j]

i = 0, j ≠ 0 上边界, cgrid[i][j] = cgrid[i][j-1] + cgrid[i][j]

i ≠ 0, j ≠ 0 其余情况, 我们取左边一个单元格, 上面的单元格 两者之中的最小值

即: cgrid[i][j] = cgrid[i-1][j] cgrid[i][j-1] ?

cgrid[i-1][j] + cgrid[i][j] : cgrid[i][j-1] + cgrid[i][j]

IOS 算法合集地址

iOS开发面试拿offer攻略之数据结构与算法篇附加安全加密

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

1.1、集合结构 说白了就是一个集合，就是一个圆圈中有很多个元素，元素与元素之间没有任何关系 这个很简单

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

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

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

数据结构的存储

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

2.1 顺序存储结构

发挥想象力啊。 举个列子。数组。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 就是这样排对的

2.2 链式存储结构

再次发挥想象力 这个稍微复杂一点 这个图片我一直弄好 ，回头找美工问问，再贴上 例如 还是一个数组 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(地址)，但是存储的时候就是完全随机的。明白了？

单向链表\双向链表\循环链表

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

3.1 单向链表

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

3.2 双向链表

数组和链表区别：

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

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

3.3 循环链表

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

二叉树／平衡二叉树

4.1 什么是二叉树

树形结构下,两个节点以内 都称之为二叉树 不存在大于 2 的节点 分为左子树 右子树 有顺序 不能颠倒 ，懵逼了吧，你肯定会想这是什么玩意，什么左子树右子树 ，都什么跟什么鬼？ 现在我以普通话再讲一遍，你把二叉树看成一个人 ，人的头呢就是树的根 ，左子树就是左手，右子树就是右手，左右手可以都没有（残疾嘛，声明一下，绝非歧视残疾朋友，勿怪，勿怪就是举个例子， I am very sorry ） , 左右手呢可以有一个，就是不能颠倒。这样讲应该明白了吧

二叉树有五种表现形式

1.空的树（没有节点）可以理解为什么都没 像空气一样

2.只有根节点。 （理解一个人只有一个头 其他的什么都没，说的有点恐怖）

3.只有左子树 （一个头 一个左手 感觉越来越写不下去了）

4.只有右子树

5.左右子树都有

二叉树可以转换成森林 树也可以转换成二叉树。这里就不介绍了 你做项目绝对用不到数据结构大致介绍这么多吧。理解为主, 别死记，死记没什么用

1、不用中间变量,用两种方法交换 A 和 B 的值

2、****求最大公约数

3、模拟栈操作

栈是一种数据结构，特点：先进后出 -

练习：使用全局变量模拟栈的操作

#include stdio.h

#include stdbool.h

#include assert.h

//保护全局变量：在全局变量前加 static 后，这个全局变量就只能在本文件中使用 static int data[1024] ;//栈最多能保存 1024 个数据

static int count = 0 ;//目前已经放了多少个数(相当于栈顶位置)

4、排序算法

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

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

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

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

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

4.1、选择排序

【选择排序】：最值出现在起始端

第 1 趟：在 n 个数中找到最小(大)数与第一个数交换位置

第 2 趟：在剩下 n-1 个数中找到最小(大)数与第二个数交换位置

重复这样的操作...依次与第三个、第四个...数交换位置

第 n-1 趟，最终可实现数据的升序（降序）排列。

4.2、冒泡排序

【冒泡排序】：相邻元素两两比较，比较完一趟，最值出现在末尾

第 1 趟：依次比较相邻的两个数，不断交换（小数放前，大数放后）逐个推进，最值最后出现在第 n 个元素位置

第 2 趟：依次比较相邻的两个数，不断交换（小数放前，大数放后）逐个推进，最值最后出现在第 n-1 个元素位置

…… ……

第 n-1 趟：依次比较相邻的两个数，不断交换（小数放前，大数放后）逐个推进，最值最后出现在第 2 个元素位置

5、折半查找（二分查找）

折半查找：优化查找时间（不用遍历全部数据） 折半查找的原理：

1.数组必须是有序的

2.必须已知 min 和 max （知道范围）

// 已知一个有序数组, 和一个 key , 要求从数组中找到 key 对应的索引位置

字符串反转

给定字符串 " hello,world ",实现将其反转。输出结果： dlrow , olleh

序数组合并

将有序数组 {1,4,6,7,9} 和 {2,3,5,6,8,9,10,11,12} 合并为{1,2,3,4,5,6,6,7,8,9,9,10,11,12}

HASH 算法

哈希表

例：给定值是字母 a ，对应 ASCII 码值是 97，数组索引下标为 97。

这里的 ASCII 码，就算是一种哈希函数，存储和查找都通过该函数，有效地提高查找效率。

在一个字符串中找到第一个只出现一次的字符。如输入" abaccdeff "，输出' b '字符( char )是一个长度为 8 的数据类型，因此总共有 256 种可能。每个字母根据其 ASCII 码值作为数组下标对应数组种的一个数字。数组中存储的是每个字符出现的次数。

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

思路:分别记录两个子视图的所有父视图并保存到数组中，然后倒序寻找,直至找到第一个不一样的父视图。

求无序数组中的中位数

中位数：当数组个数 n 为奇数时，为 (n + 1)/2 ，即是最中间那个数字；当 n 为偶数时，为 (n/2 + (n/2 + 1))/2 , 即是中间两个数字的平均数。

首先要先去了解一些几种排序算法: iOS 排序算法

思路:

1.排序算法+中位数

首先用冒泡排序、快速排序、堆排序、希尔排序等排序算法将所给数组排序，然后取出其中位数即可。

2.利用快排思想

1、简述 SSL 加密的过程用了哪些加密方法，为何这么作？

SSL 加密的过程之前有些过，此处不再赘述。

SSL 加密，在过程中实际使用了 对称加密 和 非对称加密 的结合。

主要的考虑是先使用 非对称加密 进行连接，这样做是为了避免中间人攻击秘钥被劫持，但是 非对称加密的效率比较低。所以一旦建立了安全的连接之后，就可以使用轻量的 对称加密。

2、RSA 非对称加密

对称加密[算法]在加密和解密时使用的是同一个秘钥；而[非对称加密算法]需要两个[密钥]来进行加密和解密，这两个秘钥是[公开密钥]（ public key ，简称公钥）和私有密钥（ private key ，简称私钥）。

RSA 加密

与对称加密[算法]不同，[非对称加密算法]需要两个[密钥]：[公开密钥]（ publickey ）和私有密钥（ privatekey ）。公开密钥与私有密钥是一对，如果用公开密钥对数据进行加密，只有用对应的私有密钥才能解密；如果用私有密钥对数据进行加密，那么只有用对应的公开密钥才能解密。因为加密和解密使用的是两个不同的[密钥]，所以这种算法叫作[非对称加密算法]。

RSA**** 加密原理

RSA 是常用的加密模式，其加密原理可用以下的例子进行简要的论述。

随机取两个质数

以上就是本篇所整理的，感谢观看！

介绍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解密:

解密网站:

为了让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; i24; 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; i24; i++) { string=[md5Str substringWithRange:NSMakeRange(8, 16)]; } return string;}@end

iOS：常用排序算法

冒泡排序是相邻数据进行两两比较，假设升序排序，则一趟排序下来，就会有一个最大数产生在数组最末端。因为有 n 个数据需要进行比较，而每一趟排序需要遍历n个数据，所以时间复杂度为O(n^2)

快速排序是定下一个基准数（一般默认定义最左侧数据为基准数，可以理解为参照数），每一趟排序都需要从左（角标 i）右（角标 j）两侧开始像中间进行排序，因为基准数定义在左侧，一般先从右侧开始向左侧移动，j--；遇到小于基准数的暂停，左侧开始向右移动，i++；遇到大于基准数的暂停；然后交换i 和 j 所对应的数据。当i和j相遇的时候，则将相遇值与基准数进行交换，一趟排序结束。时间复杂度是O(log2 n)

当前文章：iOS开发iOS算法,ios数据结构和算法
网站网址：http://kswjz.com/article/dsegjhc.html