Technology Math - chaolunner/CloudNotes GitHub Wiki
有2n+1个数，其中有n个数出现过两次，找出其中只出现一次的数
-
解析：任何数异或0值不变，任何数与自己异或值为0。 因此一个数两次异或同一个数，值不变。
-
算法实现：
public void FindSingle() { int[] arr = {1, 2, 3, 4, 5, 4, 3, 2, 1}; int t = 0 for (int i = 0; i < arr.Length; i++) { t ^= arr[i]; } Debug.Log("single = " + t); }
一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写出程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。
-
解析：将所有元素异或（即为2个不同元素的异或），找到第一个为1的位，然后根据该位是1还是0将数组分成2组（这两个数字必然在不同组中），最后对这2组所有元素进行异或。
-
算法实现：
public void FindTwoDiffNum(int[] arr) { int t = 0; for (int i = 0; i < arr.Length; i++) { t ^= arr[i]; } int count = 0; while ((t & 0x01) == 0) { t >> 1; count++; } int leftResult = 0, rightResult = 0; for (int i = 0; i < arr.Length; i++) { if (((arr[i] >> count) & 0x01) == 0) { leftResult ^= arr[i]; } else { rightResult ^= arr[i]; } } Debug.Log(leftResult + "," + rightResult); }
-
定义：斐波那契数列指的是这样一个数列 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233，377，610，987，1597，2584，4181，6765，10946，17711，28657，46368........ 这个数列从第3项开始，每一项都等于前两项之和。
-
算法实现：
private void Start() { // 输出第十位的数字 print(Foo(10)); } private int Foo(int a) { if (a <= 0) { return 0; } else if (a > 0 && a <= 2) { return 1; } else { return Foo(a - 1) + Foo(a - 2); } }
-
定义：二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。
-
算法实现：
static int BinSearch(int[] array, int key) { int low = 0; int high = array.Length; while (low <= high) { int middle = (low + high) / 2; if (key == array[middle]) { return middle; } else if (key > array[middle]) { low = middle + 1; } else if (key < array[middle]) { high = middle - 1; } } return -1; }
- 前序遍历：先访问根节点，然后前序遍历左子树，再前序遍历右子树。如下图所示，前序遍历结果为：ABDFECGHI
- 中序遍历：中序遍历根节点的左子树，然后访问根节点，最后中序遍历右子树。如下图所示，中序遍历结果为：DBEFAGHCI
- 后序遍历：从左到右先叶子后节点的方式遍历访问左右子树，最后访问根节点。如下图所示，后序遍历结果为：DEFBHGICA
- 层序遍历：从根节点从上往下逐层遍历，在同一层，按从左到右的顺序对节点逐个访问。
Binary Search Tree，BST的中序遍历必定是严格递增的。
性质：
- 若它的左子树不为空，则左子树上所有结点的值均小于它的根结点的值。
- 若它的右子树不为空，则右子树上所有结点的值均大于它的根结点的值。
- 它的左、右子树也分别为二叉查找树。
Red-Black Tree 自平衡二叉树。
性质：
- 节点是红色或黑色。
- 根节点是黑色的。
- 叶子节点是黑色的。
- 红色节点的子节点是黑色的（红色节点不能相邻）。
- 从根节点到任意一个叶子节点的路径上，黑色节点的个数必须相等（这个个数就称为黑高度）。也就是说黑高度必须相等。
kd-tree（k-dimensional树的简称），是一种分割k维数据空间的数据结构。主要应用于多维空间关键数据的搜索（如：范围搜索和最近邻搜索）。K-D树是二进制空间分割树的特殊的情况。
创建k-d树：
- 建立根节点。
- 选取方差最大的坐标轴作为分割轴，数据方差大说明沿该坐标轴方向上数据点分散的比较开。在这个方向上，进行数据分割可以获得最好的平衡。
- 选择该坐标轴的中位数作为分割点。
- 遍历数据，小于中位数的传递给根节点的左子树，大于中位数的传递给根节点的右子树。
- 递归执行步骤2-4，直到所有数据都被建立到KD Tree的节点上为止。
最邻近搜索：
- 从根节点开始，递归的往下移。往左还是往右的决定方法与插入元素的方法一样(如果输入点在分区面的左边则进入左子节点，在右边则进入右子节点)。
- 一旦移动到叶节点，将该节点当作当前最佳点。
- 解开递归，并对每个经过的节点运行下列步骤：
- 如果当前所在点比当前最佳点更靠近输入点，则将其变为当前最佳点。
- 检查另一边子树有没有更近的点，如果有则从该节点往下找。
- 当根节点搜索完毕后完成最邻近搜索。
典型的单源最短路径算法，用于计算一个节点到其他节点的最短路径。它的主要特点是以起始点为中心向外层层扩展(广度优先搜索思想)，直到扩展到终点为止。
给出一个无向图，用Dijkstra算法找出以A为起点的单源最短路径步骤如下：
算法描述：
设G=(V,E)是一个带权有向图，把图中顶点集合V分成两组，第一组为已求出最短路径的顶点集合（用S表示，初始时S中只有一个源点，以后每求得一条最短路径 , 就将加入到集合S中，直到全部顶点都加入到S中，算法就结束了），第二组为其余未确定最短路径的顶点集合（用U表示），按最短路径长度的递增次序依次把第二组的顶点加入S中。在加入的过程中，总保持从源点v到S中各顶点的最短路径长度不大于从源点v到U中任何顶点的最短路径长度。此外，每个顶点对应一个距离，S中的顶点的距离就是从v到此顶点的最短路径长度，U中的顶点的距离，是从v到此顶点只包括S中的顶点为中间顶点的当前最短路径长度。
宽度优先搜索算法（又称广度优先搜索,其英文全称是Breadth First Search）是最简便的图的搜索算法之一，这一算法也是很多重要的图的算法的原型。Dijkstra单源最短路径算法和Prim最小生成树算法都采用了和宽度优先搜索类似的思想。属于一种盲目搜寻法，目的是系统地展开并检查图中的所有节点，以找寻结果。换句话说，它并不考虑结果的可能位置，彻底地搜索整张图，直到找到结果为止。
广度优先搜索使用队列（queue）来实现，整个过程可以看做一个倒立的树形：
- 把根节点放到队列的末尾。
- 每次从队列的头部取出一个元素，查看这个元素所有的下一级元素，把它们放到队列的末尾。并把这个元素记为它下一级元素的前驱。
- 找到所要找的元素时结束程序。
- 如果遍历整个树还没有找到，结束程序。
深度优先搜索属于图算法的一种，是一个针对图和树的遍历算法，英文缩写为DFS即Depth First Search。
其过程简要来说是对每一个可能的分支路径深入到不能再深入为止，而且每个节点只能访问一次。
深度优先搜索用栈（stack）来实现，整个过程可以想象成一个倒立的树形：
- 把根节点压入栈中。
- 每次从栈中弹出一个元素，搜索所有在它下一级的元素，把这些元素压入栈中。并把这个元素记为它下一级元素的前驱。
- 找到所要找的元素时结束程序。
- 如果遍历整个树还没有找到，结束程序。
-
定义：几何剖分技术是一种能将场景中的几何物体通过层次性机制组织，使用时可以快速剔除层次树的整个分支，从而加快索引几何体的过程。四叉树（quad tree）和八叉树（octree）是一种常用的空间剖分方法，它将已知的空间分成四/八个子空间作为节点，每个节点又划分成四/八个子空间，依此递归，直到达到指定深度。
-
定义：A* （A-Star)算法是一种静态路网中求解最短路径最有效的直接搜索方法，也是许多其他问题的常用启发式算法。注意——是最有效的直接搜索算法，之后涌现了很多预处理算法（如ALT，CH，HL等等），在线查询效率是A*算法的数千甚至上万倍。
-
过程：
- 将起点A添加到open列表中（A没有计算花费F是因为当前open列表只有这一个节点）。
- 检查open列表，选取花费F最小的节点M（检查M如果为终点时则结束寻路，如果open列表为空则寻路失败，直接结束）。
- 遍历与M相邻的每一节点N：
- 如果N是障碍物，那么不管它。
- 如果N在closed列表中，那么不管它。
- 如果N不在open列表中：添加它然后计算出它的花费F(n) = G + H。
- 如果N已在open列表中：检查F花费是否更小。如果是，更新它的花费F和它的父节点（即设置N的父节点为M）。
- 将节点M从open列表中移除并加入到closed列表中。
- 重复2，3，4步。
-
G = 从起点A移动到N的移动代价，使用N的父节点的G值 + 估值函数（N的父节点，N节点）求得。
H = 从N移动到终点B的估算成本，使用估值函数（N节点，终点B）求得。
估值函数：max(dx, dy)、sqrt(dx * dx, dy * dy)、min(dx, dy) * 0.414 + max(dx + dy)，这些算法都可以。
保证估值恒小于实际路径长，A*就是成立的。这也是为什么不能直接使用曼哈顿算法 dx + dy 的原因。
你甚至可以取一个常数0，这样A*就退化为广搜了。
如下图中，横向和纵向的移动代价为 10，对角线的移动代价为 14。
之所以使用这些数据，是因为实际的对角移动距离是 2 的平方根，或者是近似的 1.414 倍的横向或纵向移动代价。
使用 10 和 14 就是为了保证估值恒小于实际路径长并避免浮点计算，优化性能。
-
算法实现：
using System.Collections; using System.Collections.Generic; using UnityEngine; using UnityEngine.UI; /// <summary> /// A*算法寻路 /// </summary> public class AstarFind : MonoBehaviour { AstarGrid grid; void Start() { grid = GetComponent<AstarGrid>(); FindPath(grid.startPos, grid.endPos); } /// <summary> /// 使用A*算法寻路 /// </summary> /// <param name="start"></param> /// <param name="end"></param> void FindPath(Vector2 start,Vector2 end) { //和A*算法无关，只是为了显示使用 int showFindNum=1; //开启列表 List<Cell> openLs = new List<Cell>(); //关闭列表 List<Cell> closeLs = new List<Cell>(); //起点 Cell startCell = grid.GetCell(start); //终点 Cell endCell = grid.GetCell(end); Debug.LogFormat("寻路开始,start({0}),end({1})!",start,end); //将起点作为待处理的点放入开启列表， openLs.Add(startCell); //如果开启列表没有待处理点表示寻路失败，此路不通 while(openLs.Count>0) { //遍历开启列表，找到消费最小的点作为检查点 Cell cur = openLs[0]; for (int i = 0; i < openLs.Count; i++) { if(openLs[i].fCost<cur.fCost&&openLs[i].hCost<cur.hCost) { cur = openLs[i]; } } Debug.Log("当前检查点：" + cur.ToString()+" 编号："+showFindNum+" open列表节点数量："+openLs.Count); //显示在界面，和A*算法无关 cur.obj.transform.Find("Num").GetComponent<Text>().text=showFindNum.ToString(); showFindNum++; //从开启列表中删除检查点，把它加入到一个“关闭列表”，列表中保存所有不需要再次检查的方格。 openLs.Remove(cur); closeLs.Add(cur); //检查是否找到终点 if(cur==endCell) { Debug.Log("寻路结束!"); grid.CreatePath(cur); return; } //根据检查点来找到周围可行走的点 //1.如果是墙或者在关闭列表中则跳过 //2.如果点不在开启列表中则添加 //3.如果点在开启列表中且当前的总花费比之前的总花费小，则更新该点信息 List<Cell> aroundCells = GetAllAroundCells(cur); foreach (var cell in aroundCells) { if (cell.isWall || closeLs.Contains(cell)) continue; int cost= cur.gCost+ GetDistanceCost(cell, cur); if(cost<cell.gCost||!openLs.Contains(cell)) { cell.gCost = cost; cell.hCost = GetDistanceCost(cell,endCell); cell.parent = cur; Debug.Log("cell:" + cell.ToString() + " parent:" + cur.ToString() + " " + cell.PrintCost()); if(!openLs.Contains(cell)) { openLs.Add(cell); } //显示在界面，和A*算法无关 cell.obj.transform.Find("Cost").GetComponent<Text>().text = cell.fCost.ToString(); } } } Debug.Log("寻路失败!"); } // 取得周围的节点 public List<Cell> GetAllAroundCells(Cell cell) { List<Cell> list = new List<Cell>(); for (int i = -1; i <= 1; i++) { for (int j = -1; j <= 1; j++) { // 如果是自己，则跳过 if (i == 0 && j == 0) continue; int x = cell.x + i; int y = cell.y + j; // 判断是否越界，如果没有，加到列表中 if (x < grid.gridSize && x >= 0 && y < grid.gridSize && y >= 0) { list.Add(grid.GetCell(new Vector2(x,y))); } } } return list; } /// <summary> /// 估价函数，启发函数 /// A*本身不限制H使用的估计算法，如max(dx,dy)、sqrt(dx*dx,dy*dy)、min(dx,dy)*(0.414)+max(dx+dy)这些都可以（可惜曼哈顿算法dx+dy不在此列）， /// 记住一点，只要你能保证H值恒小于实际路径长，A*就是成立的。你甚至可以取一个常数0，这样A*就退化为广搜了。 /// </summary> /// <param name="a"></param> /// <param name="b"></param> /// <returns></returns> int GetDistanceCost(Cell a, Cell b) { int cntX = Mathf.Abs(a.x - b.x); int cntY = Mathf.Abs(a.y - b.y); // 判断到底是那个轴相差的距离更远 if (cntX > cntY) { return 14 * cntY + 10 * (cntX - cntY); } else { return 14 * cntX + 10 * (cntY - cntX); } } }using System.Collections; using System.Collections.Generic; using UnityEngine; using UnityEngine.UI; /// <summary> /// 单独的格子 /// </summary> public class Cell { public int x; public int y; public bool isWall; // 与起点的长度 public int gCost; // 与目标点的长度 public int hCost; // 总的路径长度 public int fCost { get { return gCost + hCost; } } // 父节点 public Cell parent=null; public GameObject obj; public Cell(int x,int y,bool isWall,GameObject obj) { this.x = x; this.y = y; this.isWall = isWall; this.obj = obj; } public override string ToString() { return "("+x+","+y+")"; } public string PrintCost() { return "{ fCost:" + fCost + ",hCost:" + hCost + "}"; } } /// <summary> /// 地面的格子构建 /// 这里只是简单的demo，没有优化也没有调整，只是纯展示A*算法 /// </summary> public class AstarGrid : MonoBehaviour { public GameObject CellAsset; public GameObject PointAsset; public int gridSize = 10; int cellSize = 50; List<string> wallList = new List<string>() { "5_5", "5_6", "5_7" }; public List<Cell> cells = new List<Cell>(); public Vector2 startPos = new Vector2 (3,6); public Vector2 endPos = new Vector2 (7,6); void Awake () { CreateGrid(); } void CreateGrid() { //创建格子； for (int i = 0; i < gridSize; i++) { for (int j = 0; j < gridSize; j++) { GameObject obj= GameObject.Instantiate<GameObject>(CellAsset, transform); RectTransform trans = obj.transform as RectTransform; trans.anchoredPosition = new Vector2(i,j) * cellSize; bool isWall=false; trans.Find("Text").GetComponent<Text>().text = i + "," + j; if(wallList.Contains( i+"_"+j)) { isWall = true; obj.GetComponent<Image>().color=Color.black; } Cell cell = new Cell(i, j, isWall, obj); cells.Add(cell); } } //创建起点 GameObject obj1 = GameObject.Instantiate<GameObject>(PointAsset, transform); RectTransform trans1 = obj1.transform as RectTransform; trans1.anchoredPosition = startPos * cellSize; obj1.GetComponent<Image>().color = Color.red; trans1.localScale = Vector3.one * 1.2f; obj1.name = "start"; //创建终点 GameObject obj2 = GameObject.Instantiate<GameObject>(PointAsset, transform); RectTransform trans2 = obj2.transform as RectTransform; trans2.anchoredPosition = endPos * cellSize; obj2.GetComponent<Image>().color = Color.green; trans2.localScale = Vector3.one * 1.2f; obj2.name = "end"; } public Cell GetCell(Vector2 pos) { return cells.Find((c) => { return c.x == (int)pos.x && c.y == (int)pos.y; }); } public void CreatePath(Cell endPos) { Cell cell = endPos; while(cell!=null) { GameObject obj1 = GameObject.Instantiate<GameObject>(PointAsset, transform); RectTransform trans1 = obj1.transform as RectTransform; trans1.anchoredPosition = cellSize*new Vector2(cell.x,cell.y); obj1.GetComponent<Image>().color = new Color(Color.blue.r, Color.blue.g, Color.blue.b,0.5f); cell = cell.parent; } } }