行业知识
Unity游戏开发客户端面经——算法(初级)
前言:记录了���6w字的面经知识点,文章中的知识点若想深入了解,可以点击链接学习。由于文本太多,按类型分开。这一篇是 算法 常问问题总结,有帮助的可以收藏。
1.十大排序
时间复杂度:O(n²) :冒泡排序、选择排序、插入排序
O(nlogn) :堆排序、快速排序、(归并排序)
不稳定的排序:选择排序、快速排序、堆排序、希尔排序。
详细请看: (强烈推荐)https://leetcode.cn/circle/discuss/eBo9UB/#https://leetcode.cn/circle/discuss/eBo9UB/
若基本有序建议用插入排序,不建议用快速排序。
2. 100万的数据选出前1万大的数
利用堆排序、小顶堆实现。
先拿10000个数建堆,然后一次添加剩余元素,如果大于堆顶的数(10000中最小的),将这个数替换堆顶,并调整结构使之仍然是一个最小堆,这样遍历完后,堆中的10000个数就是所需的最大的10000个。建堆时间复杂度是O(mlogm),算法的时间复杂度为O (nmlogm)(n为100,m为10000)。
优化的方法:分治。可以把所有10亿个数据分组存放,比如分别放在1000个文件中。这样处理就可以分别在每个文件的10^6个数据中找出最大的10000个数,合并到一起在再找出1000*10000中的最终的结果。
3. 两个10G 的文件,200m 内存,排序
1.把 10G 大小的文件拆分成 N 个小文件,每个文件 1M 。
2.把每个文件拉倒内存排序,可以并行操作,在内存中直接使用快排,然后写入文件 。
3.对文件做两两合并。
4. A星算法
1.基本原理
避障碍寻路算法有很多,比如:BFS,DFS,Dijkstra等。
对于BFS,它的优点在于可以找到最优的一条路径,缺点是需要遍历整个地图。
对于DFS,它的优点在于不需要遍历整个地图,缺点在于不一定是最优路径。
对于Dijkstar,它的优点在于无差别的遍历当前最短路径,对于查找起始点到任意点的最短路径该算法很有效,缺点是:对于点对点的路径查找很浪费。
对于A*,它能很快的找到一条相对最优的路径,而且搜索的节点比前三个算法都要少。
如果DFS就像一个愣头青,一条路摸到黑的话,那么A*就是一个聪明的愣头青,它虽然也是一条路摸到黑,但是它每一步都会更加逼近终点,而不是像DFS每一步都是随机的。可以理解为A*吸收了DFS和BFS的优点,寻找到的路径优劣程度介于BFS和DFS之间。
简单的说,A*算法就是不停的从起点开始遍历周围的点,找出目前来说消耗最小的点作为新的起点,直到找到终点。
2. 如何找到消耗最小的点
1.F(总代价,走到终点消耗得代价)=G(该点离起点距离)+H(该点离终点距离)。
2.G:从起点到达当前点要走的距离,上下左右都是1,斜边用勾股定理算出约为1.4。
3.H:按照曼哈顿距离计算(d(i,j)=|X1-X2|+|Y1-Y2| )。
4.开启列表open:用来存储可以考虑行进的点,同时存放F、G、H、父对象(从哪个点来)的信息。
5.关闭列表close:用来存储不再考虑的点,存放在关闭列表中的点需要从开启列表移除,同时存放F、G、H、父对象(从哪个点来)的信息。
3. 如何确定路径
1.虽然最优点都在关闭列表中,但是并不能直接使用关闭列表中的点作为路径。
2.而是在关闭列表中从终点开始查找父对象,再查找父对象的父对象。
3.***路:当开启列表为空的时候,说明已经找遍了所有可能的点,寻路失败。
4. 详细流程
1、将起点记录为当前点a。
2、将当前点a放入关闭列表close,并设置父对象为空。
3、将当前点a周围所有能行进的格子放入开启列表,如果周围的点已经在开启列表或者关闭列表中再或者是障碍,就不用管它了。
4、记录当前点a周围所有能行进的格子的F值和父对象(父对象为当前点)。
5、重新在open列表中寻找最优点b(F最小值)将其放入关闭列表,同时在开启列表中移除,每次往关闭列表放点时,要判断该点是否为终点,如果是证明路径已经找完了,结束寻路,如果不是则继续
6、将最优点作为起点b
7、重复上述3、4、5、6步骤,直到找到终点。
8、找到终点,寻路结束,根据终点得父节点返回到起点,为最优路径。
原文链接:读书|杂谈|技术分享-我的编程学习笔记一个分享读书笔记,个人杂谈,技术资源的博客网站https://www.lengyueling.cn/archives/33
A星基础:
A星算法_筱的博客-CSDN博客_a星算法A星算法1.简述A星算法就是试图在地图中找到一条最短路径,但不保证一定存在。任务小猫去找青蛙玩(好TM弱智啊~)条件黑色方块无法通行,每走一个格子小猫消耗的体力都为1。2.如果说你是小猫,你会怎么走?嗯,毫无疑问你肯定这么走。。。很简单的对吧,但是你这么走的时候,真的没经过思考?并非如此吧,你要找最短路径是不是直接连线是最快的?但是连线有障碍物阻挡了,所以逼迫你先往上走出障碍物的区域,然后一路直线当然就是最短路径了。BUT,你所做的思考,都是建立在你脑海里已经有整张地图的概念上,代https://blog.csdn.net/cqs123111/article/details/115303885
A星进阶:
全网最全A*算法优化策略(JPS、HPA)_Wonder-King的博客-CSDN博客_a*算法优化A*算法(A-Star)是一种静态路网中求解最短路径最有效的直接搜索方法,也是解决许多搜索问题的有效算法。算法中的距离估算值与实际值越接近,最终搜索速度越快,是最常用的启发式算法。避障碍寻路算法有很多,比如:BFS,DFS,Dijkstra等。对于BFS,它的优点在于可以找到最优的一条路径,缺点是需要遍历整个地图。对于DFS,它的优点在于不需要遍历整个地图,缺点在于不一定是最优路径。https://blog.csdn.net/qq_42391248/article/details/119727974
优缺点
A*算法优点在于对环境反应迅速,搜索路径直接,是一种直接的搜索算法,因此被广泛应用于路径规划问题。
其缺点是实时性差,每一节点计算量大、运算时间长,而且随着节点数的增多,算法搜索效率降低。
5. A*优化?
1.找到用更合适的OpenList数据结构。
2.在openlist列表用list容器存储,遍历f最小节点元素时间复杂度为O(n),可以用二叉堆实现openlist,获取f最小的节点只需要将堆顶元素拿出来然后使堆重新成为一个二叉堆即可,复杂度是O(lngN)。
3.在f相同的时候,选取h小的节点,减少遍历次数。
4.预先分配必要的内存。
5.缓存和一个节点相邻的节点,因为 A* 需要频繁获取某个节点相邻节点的操作。
6.由计算该节点的4个邻居改为8个邻居等(横向扩展)。
7.如果你想让A*看的更远,可以在扩大A*眼界范围,也可以是周围两圈,三圈等等。当然,眼界越大,就意味着A*要计算的节点也就越多,A*的速度一定会变慢,优点是可以让A*找到更优的路径。
详细请看:【游戏AI-寻路】优化A*的几种方法 - 知乎A*算法在说怎么优化 A* 前,先复习一下A* 算法的基本过程,算法过程可以用下面的伪代码描述: // 初始化起点的信息 pn = pathNodes[startNode.NodeIndex]; pn.parent = startNode; pn.h = CalculateH(); pn.g = 0;…https://zhuanlan.zhihu.com/p/489189483
全网最全A*算法优化策略(JPS、HPA)_Wonder-King的博客-CSDN博客_a*算法优化A*算法(A-Star)是一种静态路网中求解最短路径最有效的直接搜索方法,也是解决许多搜索问题的有效算法。算法中的距离估算值与实际值越接近,最终搜索速度越快,是最常用的启发式算法。避障碍寻路算法有很多,比如:BFS,DFS,Dijkstra等。对于BFS,它的优点在于可以找到最优的一条路径,缺点是需要遍历整个地图。对于DFS,它的优点在于不需要遍历整个地图,缺点在于不一定是最优路径。https://blog.csdn.net/qq_42391248/article/details/119727974
6. A*如何减少斜线两点间的摆头(优化重要点!!)
拉绳算法!
拉绳算法/漏斗算法:即从起点开始,与路径网格的临边的点进行相连,然后依次移动左边界和右边界,判断移动后的夹角变换,如果夹角变小了,说明离终点更近了,合理;继续;如果夹角变大了,说明离终点更远了;则选择另一个边界移动;如果同样变大,则需要进行路径合并了,选择当前边界上的点作为新的起点,并与旧起点相连得到一条路径;从新起点开始刚刚的操作,直到到达终点;
详细请看:Navigation Mesh (NavMesh) 原理讲解(二) 当地块都是三角形时的路径优化 - 知乎上篇讲到NavMesh在找到路径后,由于路径沿地块(网格)中心点连接,因此通常还有优化空间,可以尝试缩短路程。本篇中,将介绍一种如果每个地块都是三角形的情况下进行路径优化的方法。毕竟三角形作为最简单的几何…https://zhuanlan.zhihu.com/p/359393767
5. 快速幂算法
数学公式:Math.Pow(m, n) 【m的n次方】
讲解:利用公式 ,可以直接用底数的平方,指数除以2的方式,这样指数降到0只需要 log(n) 次 ,因此 时间复杂度 仅需要 O(log n) 比朴素的模拟乘方法 O(n) 优秀的多。
递归算法
非递归算法
详细请看:
数据结构与算法:快速幂——求幂运算 O(logN)_正在奋斗中的小志的博客-CSDN博客_数据结构logn快速幂——求幂运算 O(logN)https://blog.csdn.net/Sea3752/article/details/124576488?spm=1001.2014.3001.5502
6. 二分查找
二分模板一共有两个,分别适用于不同情况。
算法思路:假设目标值在闭区间[l, r]中,每次将区间长度缩小一半,当l = r时,我们就找到了目标值。
1.当我们将区间[l, r]划分成[l, mid]和[mid + 1, r]时,其更新操作是r = mid或者l = mid + 1;,计算mid时不需要加1。(常用)
2.当我们将区间[l, r]划分成[l, mid - 1]和[mid, r]时,其更新操作是r = mid - 1或者l = mid;,此时为了防止***循环,计算mid时需要加1。
3.代码里的if语句,若变成一个bool函数带入对应的l,r,mid,array等,在函数里面继续二分查找,即可变成“二分答案”。
7. BFS(广度优先搜索)
BFS从根节点开始搜索,并根据树级别模式探索所有邻居根。它使用队列数据结构来记住下一个节点访问。
1.如果不需要确定当前遍历到了哪一层
2.如果要确定当前遍历到了哪一层,BFS 模板如下。 这里增加了 level 表示当前遍历到二叉树中的哪一层了,也可以理解为在一个图中,现在已经走了多少步了。size 表示在当前遍历层有多少个元素,也就是队列中的元素数,我们把这些元素一次性遍历完,即把当前层的所有元素都向外走了一步。
8. DFS(深度优先搜索)
注意搜索的顺序;当搜到叶子节点(递归结束)时就回溯,回退一步看一步。
DFS从根节点开始搜索,并从根节点尽可能远地探索这些节点。使用堆栈数据结构来记住下一个节点访问。
类似于树的 先序遍历
模板:
详细请看:深度优先搜索与广度优先搜索的本质区别! - 知乎最近在看数据结构中图的相关知识,之前看的很混乱,现在总算是理清了,在此记录一下。 目录: 图的基本知识广度优先搜索(BFS)深度优先搜索(DFS)总结代码实现 一、图的基本知识 日常有很多地方都用到了图,比如…https://zhuanlan.zhihu.com/p/74472146?ivk_sa=1024320u
9. 欧拉筛(解决素数)
详细请看:
数据结构与算法:欧拉筛——查找素数(质数)的最优解算法 O(n)_正在奋斗中的小志的博客-CSDN博客_什么算法最优时是o(n)欧拉筛——查找素数(质数)的最优解算法https://blog.csdn.net/Sea3752/article/details/124572498?spm=1001.2014.3001.5502
10. 斐波拉契数列
0、1、1、2、3、5、8、13、21....
递归:
Int fib (n) { if(n==0) return 0; if(n==1) return 1; if(n>=2){ res= (fib(n-1)+fib(n-2))%(1e9+7); } return res;}; 循环
最优解:矩阵快速幂(longn)
详细请看:
力扣https://leetcode.cn/problems/fei-bo-na-qi-shu-lie-lcof/solution/kuai-su-mi-ju-zhen-kuai-su-mi-bi-ji-by-e-fvt9/
力扣https://leetcode.cn/problems/fei-bo-na-qi-shu-lie-lcof/solution/gong-shui-san-xie-yi-ti-si-jie-dong-tai-9zip0/
11. 背包问题
dp定义
对于背包问题,有一种写法, 是使用二维数组,即dp[i][j] 表示从下标为[0-i]的物品里任意取,放进容量为j的背包,价值总和最大是多少。
1. 01背包
先遍历物品
// weight数组的大小 就是物品个数for(int i = 1; i
上一篇:电脑主机怎么使用网线接口
下一篇:接收邮件服务器地址怎么填?