IMG_2141.JPG
前言：在现在的面试中，算法问题越来越常见。而ios同学在工作中应用算法的场景又比较少，所以为了广大iOS同学的福祉。写了此文。各位同学在看答案前，最好先自己先试着写写，这样印象会更深。
我作为面试官的时候 不一定非要写出来，通常让面试者答对思路即可，毕竟过于苛刻也很难找到合格的面试者。iOS人要学要会的还有很多（oc，xib，swift，macos，swiftUI，算法）。
一、链表
链表问题是面试中最常见的问题。因为链表是计算机中最为常用的一种数据结构
1.定义
链表是一种物理存储单元上非连续、非顺序的存储结构，由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。
一般分为单链表和双向链表
单链表
单链表.png
双向链表
双向链表.png
2.常见算法
①链表反转
②链表实现队列功能（方法： 入队，出队 队列的特点是先入先出）
③链表实现栈功能（方法：入栈，出栈 栈的特点是 先入后出，后进先出）
④链表相加问题（比较有难度）
⑤链表有环
提高：
题目：给一个环形链表，请你将他三等分（前提链表%3==0）
答案：在GitHub
链表问题考察的本质其实不是算法，就是考察你最近有没有在刷链表的题。练过就会 没练过可能就不会。
二、二叉树
1.定义
二叉树（Binary tree）是树形结构的一个重要类型。许多实际问题抽象出来的数据结构往往是二叉树形式，即使是一般的树也能简单地转换为二叉树，而且二叉树的存储结构及其算法都较为简单，因此二叉树显得特别重要。二叉树特点是每个节点最多只能有两棵子树，且有左右之分
二叉树的五种形态
1、 空二叉树（什么都没有，nothing）
2、 只有一个根节点的二叉树（左右子树为空）
3、 右子树为空的二叉树（右腿断了）
4、 左子树为空的二叉树（左腿断了）
5、 满二叉树
二叉树.png
2.常见算法
①求二叉树的深度
②二叉树镜像
③提高： 寻找最低的共同节点（我在github 上面写了2种方式方便大家理解）
答案：在GitHub
二叉树主要考察 你对二叉树形态的理解和二叉树相关算法的运用。
三、经典岛问题
岛问题是算法培训里面必须培训的问题，由岛可以延伸出很多算法题。
给定一个由 '1'（陆地）和 '0'（水）组成的的二维网格，计算岛屿的数量。一个岛被水包围，并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设网格的四个边均被水包围。
示例 1:
输入:
11110
11010
11000
00000 输出: 1
示例 2:
输入:
11000
11000
00100
00011 输出: 3
经典思路： 拿出先决条件，然后找个地方储存，然后用另一个方法递归。
答案：在GitHub
四、排序问题
排序问题.png
冒泡排序：将相邻的两个元素两两比较，根据大小来交换元素的位置
选择排序：就是先找出数组中最小的，然后依次找出数据并排序
快速排序：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
插入排序法：是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据，算法适用于少量数据的排序
堆排序 就是利用堆(假设利用大堆顶)进行排序的方法。它的基本思想是，将待排序的序列构成一个大顶堆。此时，整个序列的最大值就是堆顶的根节点。将它移走(其实就是将其与堆数组的末尾元素交换，此时末尾元素就是最大值)，然后将剩余的n-1个序列重新构造成一个堆，这样就会得到n个元素中的次小值。如此反复执行，便能得到一个有序序列了。
二分查找： （这里假设数组元素呈升序排列）将n个元素分成个数大致相同的两半，取a[n/2]与欲查找的x作比较，如果x=a[n/2]则找到x，算法终止；如 果x<a[n/2]，则我们只要在数组a的左半部继续搜索x；如果x>a[n/2]，则我们只要在数组a的右 半部继续搜索x。
二分查找思路：定义 两个指针动态取值范围，然后比较中间值。
答案：在GitHub
排序问题属于算法启蒙问题了，面试中偶尔也会问到。
五、斐波那契数列
定义
斐波那契数列（Fibonacci sequence），又称黄金分割数列，因数学家莱昂纳多·斐波那契（Leonardo Fibonacci）以[兔]子繁殖为例子而引入，故又称为“兔子数列”，指的是这样一个数列：1、1、2、3、5、8、13、21、34、……在数学上，斐波那契数列以如下被以递推的方法定义：F(0)=1，F(1)=1, F(n)=F(n - 1)+F(n - 2)（*n ≥ 2，n ∈ N）在现代物理、准[晶体结构]、化学等领域，斐波那契数列都有直接的应用。
1题 求：最长斐波那契数列
/*输入: [1,2,3,4,5,6,7,8]
输出: 5
原因: 最长斐波那契数列: [1,2,3,5,8]
输入: [1,3,7,11,12,14,18]
输出: 3
原因: [1,11,12],[3,11,14],[7,11,18]*/
/*
2题 求：第N个斐波那契数列的值
3题 数组里的斐波那契数列下标
输入: [7,3,4] 11
输出: [0,2]
输入: [3,3] 6
输出: [0,1]
输入： [20,70,110,150], 90
输出: [0,1]
答案：在GitHub
斐波那契数列也是面试比较常见的问题，考察面试者对斐波那契数列的理解和循环的应用
六、动态规划问题（困难）
题目：谷歌扔鸡蛋问题
给你 k 枚相同的鸡蛋，并可以使用一栋从第 1 层到第 n 层共有 n 层楼的建筑。
已知存在楼层 f ，满足 0 <= f <= n ，任何从 高于 f 的楼层落下的鸡蛋都会碎，从 f 楼层或比它低的楼层落下的鸡蛋都不会破。
每次操作，你可以取一枚没有碎的鸡蛋并把它从任一楼层 x 扔下（满足 1 <= x <= n）。如果鸡蛋碎了，你就不能再次使用它。如果某枚鸡蛋扔下后没有摔碎，则可以在之后的操作中 重复使用 这枚鸡蛋。
请你计算并返回要确定 f 确切的值 的 最小操作次数 是多少？
输入：k = 2, n = 6
输出：3
输入：k = 2, n = 100
输出：14
分析：这是一个动态规划题，考察的并不是让你应用哪种具体算法，而是根据要求动态规划得出方程式，然后根据方程式动态求解。考察的是面对需求的分析能力。
分析题目本身，给定了2个参数 k鸡蛋的数量，n楼层的高度。这种题先从边缘情况分析
- 当鸡蛋只有一个的时候 最少次数肯定为n
- 当楼层为1层的时候 肯定为1
3.当楼层为2层的时候 就转化为 在1层扔或者2层扔
情况分为1层碎了或者1层没碎 1层碎了就其实就是1次 没碎还需要再扔1次 就为2.
图1
1.png
截屏2.png
总结公式为 dp(k−1,x−1)和dp(k,n−x) x为扔的楼层
因为2种情况都有可能发生，取最大值 max(dp(k−1,x−1),dp(k,n−x) ）在加1。
因为 不同的楼层返回的值有大有小，题目告诉我们取最小的可能min
所以推出方程式dp(k,n)=1+ min(max(dp(k−1,x−1),dp(k,n−x))) 1≤x≤n
然后套用方程式，写满 图1 这个二维数组即可。
答案：在GitHub
题目：01背包问题
有N件物品和一个可以承受W重量的背包，物品的属性有重量和价值。约束条件为，在给定的一组物品中，和一个固定承重为W的背包，动态算出可以装载的最大价值。即
输入：w = 6, n =4,[(v:6,w:3),(v:10,w:1),(v:5,w:2),(v:10,w:4)]
输出：21
输入：w = 6, n =4,[(v:3,w:1),(v:8,w:5),(v:5,w:1),(v:10,w:1)]
输出：18
背包问题.png
公式： f[w][n]=max{f[w][n-1],f[w-w1][n-1]+w1}
思路也是放入和没放的动态调试。
答案：在GitHub
七、零散的算法问题
1.8位截取问题
/*输入一个字符串，请按长度为8拆分每个输入字符串并进行输出；
长度不是8整数倍的字符串请在后面补数字0，空字符串不处理。
输入： abc
输出： abc00000
*/
2.打印二进制整数问题
思路：先取余 再除2
func printIntNumber(no : Int) -> String
{
if no == 0{
print("二进制：00")
return "00"
}
if no == 1{
print("二进制：01")
return"01"
}
var i = no
var string : String = ""
while i>0{
let last = String(i%2) //取余
i = i/2 //关键 十进制转二进制就是不断的除2
string.insert(contentsOf: last, at: string.startIndex)
}
print("\(no)二进制: \(string)")
return string
}
3.局部最小值问题
/*
无序数组，任意两个相邻的数不等，找到存在局部最小的位置
0位置比1位置小，则0位置是局部最小，n-2位置比n-1位置小，返回n-1位置
中间位置i，需满足 i 比左边小也比右边小，则i位置是局部最小
局部最小位置存在即可返回，不用返回所有的位置
*/
答案：在GitHub 会持续更新
网友评论