

数据结构是指相互之间存在着一种或多种关系的数据元素的集合和该集合中数据元素之间的关系组成 。 常用的数据结构有:数组,栈,链表,队列,树,图,堆,散列表等。
数组是可以再内存中连续存储多个元素的结构,在内存中的分配也是连续的,数组中的元素通过数组下标进行访问,数组下标从0开始。例如下面这段代码就是将数组的第一个元素赋值为 1。 int[] data = new int[100];data[0] = 1;
优点:
a. 按照索引查询元素速度快
b. 按照索引遍历数组方便
缺点:
a. 数组的大小固定后就无法扩容了
b. 数组只能存储一种类型的数据
c. 添加,删除的操作慢,因为要移动其他的元素
适用场景: 频繁查询,对存储空间要求不大,很少增加和删除的情况。
有序的对象列表,属于数据结构的一种:顺序结构。 泛型集合类,引入System.Collections.Generic命名空间,常用操作有Count属性查看长度,Add()添加,Remove()去除,AddRange()添加集合,Clear()清空集合。
数组在C#中最早出现的。在内存中是连续存储的,所以它的索引速度非常快,而且赋值与修改元素也很简单。数组存在一些不足的地方。在数组的两个数据间插入数据是很麻烦的,而且在声明数组的时候必须指定数组的长度,数组的长度过长,会造成内存浪费,过段会造成数据溢出的错误。如果在声明数组时我们不清楚数组的长度,就会变得很麻烦。List是集合,集合元素的数量可以动态变化。增加、插入、删除元素很方便。
栈是一种特殊的线性表,仅能在线性表的一端操作,栈顶允许操作,栈底不允许操作。 栈的特点是:先进后出,或者说是后进先出,从栈顶放入元素的操作叫入栈,取出元素叫出栈。 栈的结构就像一个集装箱,越先放进去的东西越晚才能拿出来,所以,栈常应用于实现递归功能方面的场景,例如斐波那契数列。
队列与栈一样,也是一种线性表,不同的是,队列可以在一端添加元素,在另一端取出元素,也就是:先进先出。从一端放入元素的操作称为入队,取出元素为出队。使用场景:因为队列先进先出的特点,在多线程阻塞队列管理中非常适用。
链表是物理存储单元上非连续的、非顺序的存储结构,数据元素的逻辑顺序是通过链表的指针地址实现,每个元素包含两个结点,一个是存储元素的数据域 (内存空间),另一个是指向下一个结点地址的指针域。根据指针的指向,链表能形成不同的结构,例如单链表,双向链表,循环链表等。
优点:
a. 链表是很常用的一种数据结构,不需要初始化容量,可以任意加减元素;
b. 添加或者删除元素时只需要改变前后两个元素结点的指针域指向地址即可,所以添加,删除很快;
缺点:
a. 因为含有大量的指针域,占用空间较大;
b. 查找元素需要遍历链表来查找,非常耗时。
适用场景:
数据量较小,需要频繁增加,删除操作的场景
树是一种数据结构,它是由n(n>=1)个有限节点组成一个具有层次关系的集合。把它叫做 “树” 是因为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的。
它具有以下的特点:
在日常的应用中,我们讨论和用的更多的是树的其中一种结构,就是二叉树。二叉树是树的特殊一种,具有如下特点:
散列表,也叫哈希表,是根据关键码和值 (key和value) 直接进行访问的数据结构,通过key和value来映射到集合中的一个位置,这样就可以很快找到集合中的对应元素。哈希表的应用场景很多,当然也有很多问题要考虑,比如哈希冲突的问题,如果处理的不好会浪费大量的时间,导致应用崩溃。
堆是一种比较特殊的数据结构,可以被看做一棵树的数组对象,具有以下的性质:
a. 堆中某个节点的值总是不大于或不小于其父节点的值;
b. 堆总是一棵完全二叉树;
c. 将根节点最大的堆叫做最大堆或大根堆,根节点最小的堆叫做最小堆或小根堆。常见的堆有二叉堆、斐波那契堆等。
因为堆有序的特点,一般用来做数组中的排序,称为堆排序。
图是由结点的有穷集合V和边的集合E组成。其中,为了与树形结构加以区别,在图结构中常常将结点称为顶点,边是顶点的有序偶对,若两个顶点之间存在一条边,就表示这两个顶点具有相邻关系。 按照顶点指向的方向可分为无向图和有向图: 图是一种比较复杂的数据结构,在存储数据上有着比较复杂和高效的算法,分别有邻接矩阵 、邻接表、十字链表、邻接多重表、边集数组等存储结构。
前序遍历,先访问根节点在访问左节点在访问右节点。
中序遍历,先访问左节点在访问根节点在访问右节点。
后序遍历,先访问左节点在访问右节点在访问根节点。
前中后代表的是访问根节点的时序。采用递归方式和非递归方式。前者优点是直观,编写起来简单,缺点是但其开销也比较大。非递归形式开销小,但编写复杂。
主要使用:工厂模式、代理模式、策略模式、观察者模式、单例模式等
a. 单一职责原则 (The Single Responsiblity Principle,简称 SRP):一个类,最好只做一件事,只有一个引起它的变化。
b. 开放-封闭原则 (The Open-Close Principle,简称 OCP):对于扩展是开放的,对于更改是封闭的
c. Liskov 替换原则(The Liskov Substitution Principle,简称 LSP):子类必须能够替换其基类。
d. 依赖倒置原则 (The Dependency Inversion Pricinple, 简称 DIP):依赖于抽象
e. 接口隔离原则 (The Interface Segregation Principle,简称 ISP):使用多个小的专门的接口,而不要使用一个大的总接口。
观察者模式:一对多的关系,当被观察这发生改变时会通知所有观察者。让双方都依赖于抽象,使得各自变化不会影响另一方。
用一种业务逻辑、数据、界面显示分离的方法组织代码,将业务逻辑聚集到一个部件里面,在改进和个性化定制界面及用户交互的同时,不需要重新编写业务逻辑。经典MVC模式中,M是指业务模型,V是指用户界面,C则是控制器,使用MVC的目的是将M和V的实现代码分离,从而使同一个程序可以使用不同的表现形式。其中,View的定义比较清晰,就是用户界面。
想锻炼算法相关内容注意推荐去刷题网站勤加练习,如力扣、牛客网等。
十种常见排序算法可以分为两大类:



常规答案
与2取余,若为0则是偶数,否则为奇数。
public static bool IsEven(int number) { return ((number % 2) == 0); } 进阶答案
检测数字的二进制最低位是否为0。将最低位和1相与,如果结果为0,则为偶数,否则为奇数。
如奇数3和1位与,实际上是 00000000 00000000 00000000 00000011 & 00000000 00000000 00000000 00000001 --------------------------------------------- 00000000 00000000 00000000 00000001 再比如偶数6和1位与,实际上是 00000000 00000000 00000000 00000110 & 00000000 00000000 00000000 00000001 --------------------------------------------- 00000000 00000000 00000000 00000000 判断一个整数是奇数还是偶数 /** /// 判断一个整数是否是偶数 /// /// 传入的整数 /// 如果是偶数,返回true,否则为false public static bool IsEven(int number) { return ((number & 1) == 0); } /** /// 判断一个整数是否是奇数 /// /// 传入的整数 /// 如果是奇数,返回true,否则为false public static bool IsOdd(int number) { return !IsEven(number); } 常规答案
利用位运算进行判断,将一个数通过不断位右移,最终结果若为1则为true,否则为false。
判断一个整数是否是2的n次方 public static bool IsPower(int number) { if (number <= 0) { return false; } while (true) { if (number == 1) { return true; } //如果是奇数 if ((number & 1) == 1) { return false; } //右移一位 number >>= 1; } } 进阶答案
2的n次方其二进制表示只有1个1,如整数8,其二进制表示形式是00001000,减去1后为00000111,让这两者进行位与的结果刚好是0则为true,否则就是falsez。
判断一个整数是否是2的n次方 public static bool IsPower(int number) { if (number <= 0) { return false; } if ((number & (number - 1)) == 0) { return true; } return false; } 代码 private static int GetCountGroupByOne(int data) { int count = 0; if (data == 0) { } else if (data > 0) { while (data > 0) { data &= (data - 1); count++; } } else { int minValue = -0x40000001; while (data > minValue) { data &= (data - 1); count++; } count++; } return count; } 利用堆排序、小顶堆实现。
先拿10000个数建堆,然后一次添加剩余元素,如果大于堆顶的数(10000中最小的),将这个数替换堆顶,并调整结构使之仍然是一个最小堆,这样遍历完后,堆中的10000个数就是所需的最大的10000个。建堆时间复杂度是O(mlogm),算法的时间复杂度为O (nmlogm)(n为100,m为10000)。
优化的方法:分治。可以把所有10亿个数据分组存放,比如分别放在1000个文件中。这样处理就可以分别在每个文件的10^6个数据中找出最大的10000个数,合并到一起在再找出1000*10000中的最终的结果。
算法思路:假设目标值在闭区间[l, r]中,每次将区间长度缩小一半,当l = r时,我们就找到了目标值。
1.当我们将区间[l, r]划分成[l, mid]和[mid + 1, r]时,其更新操作是r = mid或者l = mid + 1;,计算mid时不需要加1。(常用)
int bsearch_1(int 1, int r) { While (l int mid = l +r >> 1; if(check(mid)) r = mid; else l = mid + 1; } return l; } 2.当我们将区间[l, r]划分成[l, mid - 1]和[mid, r]时,其更新操作是r = mid - 1或者l = mid;,此时为了防止死循环,计算mid时需要加1。
int bsearch_2(int 1, int r) { While (l int mid = l + r +1 >> 1; if(check(mid)) l = mid; else r = mid - 1; } return l; } 3.代码里的if语句,若变成一个bool函数带入对应的l,r,mid,array等,在函数里面继续二分查找,即可变成“二分答案”。
BFS从根节点开始搜索,并根据树级别模式探索所有邻居根。它使用队列数据结构来记住下一个节点访问。
1.如果不需要确定当前遍历到了哪一层
while queue 不空: cur = queue.pop() for 节点 in cur的所有相邻节点: if 该节点有效且未访问过: queue.push(该节点) 2.如果要确定当前遍历到了哪一层,BFS 模板如下。 这里增加了 level 表示当前遍历到二叉树中的哪一层了,也可以理解为在一个图中,现在已经走了多少步了。size 表示在当前遍历层有多少个元素,也就是队列中的元素数,我们把这些元素一次性遍历完,即把当前层的所有元素都向外走了一步。
level = 0 while queue 不空: size = queue.size() while (size --) { cur = queue.pop() for 节点 in cur的所有相邻节点: if 该节点有效且未访问过: queue.push(该节点) } level++; 注意搜索的顺序;当搜到叶子节点(递归结束)时就回溯,回退一步看一步。
DFS从根节点开始搜索,并从根节点尽可能远地探索这些节点。使用堆栈数据结构来记住下一个节点访问。
类似于树的 先序遍历

static int Fn(int n) { if (n <= 0) { throw new ArgumentOutOfRangeException(); } if (n == 1||n==2) { return 1; } return checked(Fn(n - 1) + Fn(n - 2)); // when n>46 memory will overflow } string a = new string("abc"); a = (a.ToUpper() +"123").Substring(0,2); 实在C#中第⼀⾏是会出错的(Java中倒是可⾏)。
应该这样初始化:
string b = new string(new char[] {'a','b','c'}); 三个临时对象:abc、ABC、AB
已知点P(x,y),以及直线上的两点A(x1,y1)、B(x2,y2),可以通过计算向量AP与向量AB的叉乘是否等于0来计算点P是否在直线AB上。
知识点:叉乘
/// /// 2D叉乘 /// /// 点1 /// 点2 /// public static float CrossProduct2D(Vector2 v1,Vector2 v2) { //叉乘运算公式 x1*y2 - x2*y1 return v1.x * v2.y - v2.x * v1.y; } /// /// 点是否在直线上 /// /// /// /// /// public static bool IsPointOnLine(Vector2 point, Vector2 lineStart, Vector2 lineEnd) { float value = CrossProduct2D(point - lineStart, lineEnd - lineStart); return Mathf.Abs(value) <0.0003 /* 使用 Mathf.Approximately(value,0) 方式,在斜线上好像无法趋近为0*/; } 已知点P(x,y),以及线段A(x1,y1),B(x2,y2)。
1)方法一
可以进行下面两部来判断点P是否在线段AB上:
(1)点是否在线段AB所在的直线上(点是否在直线上)
(2)点是否在以线段AB为对角线的矩形上,来忽略点在线段AB延长线上
/// /// 2D叉乘 /// /// 点1 /// 点2 /// public static float CrossProduct2D(Vector2 v1,Vector2 v2) { //叉乘运算公式 x1*y2 - x2*y1 return v1.x * v2.y - v2.x * v1.y; } /// /// 点是否在直线上 /// /// /// /// /// public static bool IsPointOnLine(Vector2 point, Vector2 lineStart, Vector2 lineEnd) { float value = CrossProduct2D(point - lineStart, lineEnd - lineStart); return Mathf.Abs(value) <0.0003 /* 使用 Mathf.Approximately(value,0) 方式,在斜线上好像无法趋近为0*/; } /// /// 点是否在线段上 /// /// /// /// /// public static bool IsPointOnSegment(Vector2 point, Vector2 lineStart, Vector2 lineEnd) { //1.先通过向量的叉乘确定点是否在直线上 //2.在拍段点是否在指定线段的矩形范围内 if (IsPointOnLine(point,lineStart,lineEnd)) { //点的x值大于最小,小于最大x值 以及y值大于最小,小于最大 if (point.x >= Mathf.Min(lineStart.x, lineEnd.x) && point.x <= Mathf.Max(lineStart.x, lineEnd.x) && point.y >= Mathf.Min(lineStart.y, lineEnd.y) && point.y <= Mathf.Max(lineStart.y, lineEnd.y)) return true; } return false; } Unity性能优化 面试题都在这里了,希望本篇文章能够让你在面试关卡如鱼得水得到自己想要的工作。
资料白嫖,技术互助
🎬 博客主页:https://xiaoy.blog.csdn.net
🎥 本文由 呆呆敲代码的小Y 原创 🙉
🎄 学习专栏推荐:Unity系统学习专栏
🌲 游戏制作专栏推荐:游戏制作
🌲Unity实战100例专栏推荐:Unity 实战100例 教程
🏅 欢迎点赞 👍 收藏 ⭐留言 📝 如有错误敬请指正!
📆 未来很长,值得我们全力奔赴更美好的生活✨
------------------❤️分割线❤️-------------------------
| 学习路线指引(点击解锁) | 知识定位 | 人群定位 |
|---|---|---|
| 🧡 Unity系统学习专栏 🧡 | 入门级 | 本专栏从Unity入门开始学习,快速达到Unity的入门水平 |
| 💛 Unity实战类项目 💛 | 进阶级 | 计划制作Unity的 100个实战案例!助你进入Unity世界,争取做最全的Unity原创博客大全。 |
| ❤️ 游戏制作专栏 ❤️ | 难度偏高 | 分享学习一些Unity成品的游戏Demo和其他语言的小游戏! |
| 💚 游戏爱好者万人社区💚 | 互助/吹水 | 数万人游戏爱好者社区,聊天互助,白嫖奖品 |
| 💙 Unity100个实用技能💙 | Unity查漏补缺 | 针对一些Unity中经常用到的一些小知识和技能进行学习介绍,核心目的就是让我们能够快速学习Unity的知识以达到查漏补缺 |
