0，常考常错常忘 链接到标题

时间/空间复杂度 链接到标题

空间复杂度指的是随着输入规模 n 的增长，程序额外占用的内存大小的增长趋势。

只考虑与输入规模 n 有关的额外内存。

常数个额外变量（无论有几个）都算作 O(1)

eg.

vector<int> nums(n);

该段代码创建了一个大小为 n 的数组，所以空间复杂度是 n

该代码初始化所有元素的操作相当于一个隐性的 for 循环，所以时间复杂度是O(n)

数据元素的存储结构 链接到标题

逻辑结构是数据元素之间的关系，存储结构是数据元素及其关系在计算机中的存储方式。

存储结构有顺序、链式、索引、散列四种，逻辑结构有线性和非线性结构。

二叉树是逻辑结构，树属于逻辑结构中的非线性结构。

双向链表、哈希表、循环队列都是存储结构分别属于链式、散列和**顺序**。

数组的存取 链接到标题

数组的存取 ≠ 插入/删除，存取速度与下标数值无关，存就是给 a[i]赋值，取就是读出 a[i]的值，永远是 O(1)

在二维数组行序为主序存储时,元素在内存中按照先行后列的顺序连续存储。对于 A[i][j],其地址计算公式为:

基地址 + (i-1)*n + (j-1)

队列的各种情况判定 链接到标题

在循环队列中,正确判断队满的条件是(rear+1)%n == front。

因为循环队列需要牺牲一个存储空间来区分队空和队满状态,当队列满时,队尾指针 rear 再前进一个位置就会与队头指针 front 重合。

判断队空的条件是 rear%n == front

队列中只有一个元素时，(front+1)%n == rear

rear = (front + 队列中元素个数) % 数组长度

enqueue 将元素（item）插入队列的末尾，dequeue 将队列的第一个元素（即最先插入队列的元素）移除并返回其值

在使用链表实现的队列中，入队和出队操作的平均时间复杂度分别是多少？

输出受限的双向队列 链接到标题

(牛客队列原题)已知输入序列为 abcd 经过输出受限的双向队列后能得到的输出序列有()

此处的输出受限的双向队列指：可以在两端输入，只能在一端输出

常见排序算法的稳定性 链接到标题

不稳定：

堆排序，快速排序，希尔排序，直接选择排序

稳定：

基数排序，冒泡排序，直接插入排序，折半插入排序，归并排序

有序数组合并时间复杂度 链接到标题

合并 m 个长度为 n 的有序数组的最优时间复杂度确实是 O(mn(logm))

二叉树相关概念 链接到标题

结点的度：一个节点的子树的个数

叶节点：度为 0 的结点

二叉树最小深度：dmin​=⌈log2​(n+1)⌉ (⌈x⌉表示向上取整)

深度为 k 的二叉树至多有 2^k-1 个结点

树的节点数=度*对应结点个数+根节点

二叉树的不同形态 链接到标题

哈夫曼树：给定 N 个权值作为 N 个叶子结点，构造一棵二叉树，若该树的带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman Tree)。

给定 n 个带权结点，其 Huffman 树的结构不是唯一的

在哈夫曼编码中,要满足前缀编码的要求,即任何一个字符的编码都不能是另一个字符编码的前缀。同时,哈夫曼树是一个满二叉树,所有的字符编码都是叶子节点。

哈夫曼树带权路径计算有两种方式：1，按 Huffman（最小对合并）逐步合并

2，权 × 深度

平衡二叉树：它的左子树和右子树的深度之差(平衡因子)的绝对值不超过 1，且它的左子树和右子树都是一颗平衡二叉树。

满二叉树：如果一个二叉树的层数为 k，结点总数是(2^k)-1 ，它就是满二叉树。

完全二叉树：与满二叉树相似，但最后一行相比满二叉树并不完整

二叉搜索树：非空左子树的所有键值小于其根结点的键值；非空右子树的所有键值大于其根结点的键值；左、右子树都是二叉搜索树

堆/栈/队列 链接到标题

堆是一种特殊的完全二叉树

栈中有 n 个元素时，这几个元素能组成的出栈序列有 个

队列状况判定条件

队空:front=rear

队满:(front=(rear+1)modmaxSize)

最大有效元素个数:maxSize - 1

LIFO 与 FILO , LILO 与 FIFO 链接到标题

LIFO (Last In, First Out)

“后进先出” → 最后放进去的元素最先出来。

👉 常用在栈 (stack) 的描述里。

FILO (First In, Last Out)

“先进后出” → 最先放进去的元素最后出来。

👉 和 LIFO 是同一个规则，只是从“第一个进去的元素”的角度来描述。

同理得

FIFO 先进先出(队列)

LILO 后进后出

大根堆/小根堆 链接到标题

可参考:【堆 - 专题】堆排序，大根堆，小根堆

子节点均大于等于根节点的堆叫做小根堆，反之为大根堆

将关键字依次插入小根堆中，按层序从左至右插入，遇到结点值比根节点小时上浮即可

Linux 中的查找 链接到标题

(牛客查找原题)

Linux 中，有文本文件 file.txt，想要查找出包含 “test” 或 “taste” 两个单词的行并显示对应行号，下面命令正确的是(grep -n ’t[ae]st’ file.txt)

for 循环和 foreach 循环 链接到标题

for 循环遍历速度快于 foreach 循环

不建议在 Unity 中的 Update() 函数中使用 foreach 循环，容易遗留内存垃圾

foreach 是只读的,在 foreach 中修改数据会报错

C# 中常用的容器类 链接到标题

List(列表)，HashTable(哈希表)，Dictionary(字典)，Stack(栈)，Queue(队列)

1，小数点精度设置 链接到标题

cout<<fixed<<setprecision(n);

设置输出精度为小数点后 n 位（四舍五入），该设置会对此后的所有 cout 输出产生影响

如果需要直接截断小数点后 n 位，并不四舍五入，可采用以下方式：

float count;
cout<<trunc(count*1e9)/1e9;

trunc 函数只能截断小数部分保留整数部分，此处将 count 的小数点后 9 位转为整数，截断后再将数值缩回原位，从而达成直接截断的效果

2，二叉树编号 链接到标题

(牛客二叉树专项练习)将一颗有 100 个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点进行编号，根节点编号为 1 ，求编号为 98 的节点的父节点编号

在完全二叉树中,对于任意一个编号为 n 的节点:

• 其左子节点的编号为 2n

• 其右子节点的编号为 2n+1

• 其父节点的编号为⌊n/2⌋(向下取整)

3，前中后缀表达式 链接到标题

前缀表达式 链接到标题

前缀表达式是运算符在前操作符在后的式子，实际上类似于二叉树的先序遍历 (eg.*+ab+cd)

中缀表达式 链接到标题

中缀表达式的格式和我们平时所写所看的表达式格式相同，同时也类似于二叉树的中序遍历

后缀表达式 链接到标题

后缀表达式的运算符放在两个操作符的后面，类似于二叉树的后续遍历 (eg.ab+cd+*)

4， C# 小知识 链接到标题

C# 各类修饰符 链接到标题

访问修饰符 链接到标题

Public:公有的，对其访问没有限制

Internal:内部的，同一个程序集中的所有类都可以访问

Private:私有的，只有在声明它们的类或结构中才能访问

Protected:受保护的，只能在它的类和派生类中访问

类修饰符 链接到标题

abstract:可以被指示一个类只能作为其它类的基类

sealed:指示一个类不能被继承

static：修饰类时表示该类是静态类，不能够实例化该类的对象,该类的成员为静态

成员修饰符 链接到标题

abstract:指示该方法或属性没有实现

const:指定域或局部变量的值不能被改动

event:声明一个事件

extern:指示方法在外部实现

override:对由基类继承成员的新实现

readonly:指示一个域只能在声明时以及相同类的内部被赋值

Partial：在整个同一程序集中定义分部类和结构

Virtual：用于修饰方法、属性、索引器或事件声明，并且允许在派生类中重写这些对象

New：作修饰符，隐藏从基类成员继承的成员，在不使用 new 修饰符的情况下隐藏成员是允许的，但会生成警告。作运算符，用于创建对象和调用构造函数

C# 中的 GC 机制 链接到标题

参考:

【Unity 面试篇】Unity 面试题总结甄选 ｜ C#基础篇 | ❤️ 持续更新 ❤️

C#垃圾回收机制(GC)基础到进阶

GC (垃圾回收机制，Garbage Collection) 是.net 框架中负责自动管理和内存释放的重要特性，将不再使用的对象所占的内存资源回收

C# 内部有两个内存管理池:堆内存和栈内存

然而 GC 操作容易引起性能问题

栈由编译器自动管理，GC 不管栈，GC 只管理托管堆内存

C# 装箱与拆箱 链接到标题

C# 中的数据类型主要分为值类型和引用类型(值类型:整数/浮点数/布尔等 引用类型:类/数组/字符串等)

装箱：值类型转换为对象类型

拆箱：之前由值类型转换而来的对象类型再转回值类型

只有装过箱的数据才能拆箱

装箱拆箱会带来性能问题，应尽量避免装箱拆箱操作

参考:

C# 装箱和拆箱

C# 程序设计基础之 - 装箱与拆箱

C# ref 与 out 链接到标题

可参考:【唐老狮】C#——ref 和 out

ref 和 out 的功能是将参数按引用传递

ref 要求参数在调用前初始化

out 要求方法体内为参数赋值

ref 和 out 类似于 C++ 中的引用

C# Console 输出 链接到标题

        Console.WriteLine($"键1的值是{myDict[1]}");

        Console.WriteLine("键1的值是"+myDict[1]);

        //两种写法的输出结果相同，$ 是 C# 中的一个语法糖，表示插值字符串
        //它允许字符串中直接嵌入变量或表达式，语法格式为 $"文本 {变量或表达式} 文本"

5，Unity 小知识 链接到标题

Unity C# 线程与协程 链接到标题

Unity 中除了负责绘制 UI /获取游戏对象等的主线程以外，还有多线程与协程

协程是伪异步，并不是真正的异步执行，属于生命周期的一部分，同一时间只会有一个协程运行，其余协程按顺序开启，也就是与生命周期并发执行

线程是真异步，与脚本生命周期并行运行，一个 CPU 在同一时刻只能运行一个线程，但是多个 CPU 在同一时刻就可以运行多个线程。

错题回顾：在 OnDestroy() 内启动协程，协程会怎样？

当对象正在被销毁时，它的 MonoBehaviour 生命周期已结束，此时 Unity 不会启动新的协程（即便调用 StartCoroutine()，也不会执行）。

参考

Unity 协程和线程的区别深入理解(附实验展示)

Unity 的 PlayerPrefs 类 链接到标题

PlayerPrefs 类是 U3d 自带的一个用于本地数据持久化保存的类，可存储整型/浮点型/字符串数据

//存储整型数据
//(数据被存入内存中，当游戏正常关闭时，Unity会自动将数据存储在硬盘中)
//(未正常关闭游戏时数据会丢失)
PlayerPrefs.SetInt("intKey",999);

//读取整型数据
int intVal = PlayerPrefs.GetInt("intKey");

//删除所有存储数据
PlayerPrefs.DeleteAll();

//根据名字删除单个存储数据
PlayerPrefs.DeleteKey("intKey");

//根据名字查找单个存储数据
bool exist = PlayerPrefs.HasKey("intKey")

//即时存储数据，马上将数据存储到硬盘中
PlayerPrefs.Save();

参考

【Unity 数据持久化】PlayerPrefs 的 存、读、删

Unity 本地持久化类 Playerprefs 使用详解

Unity 中 Image 和 RawImage 的区别 链接到标题

省流:做没有额外图像处理的背景之类的用 RawImage

localPosition 与 position 链接到标题

子物体的 localPosition 是相对于父物体的，而 position 是世界坐标

Unity 生命周期 链接到标题

Script Execution Order 是 Unity 唯一允许开发者显式控制生命周期顺序的入口。

对象池 链接到标题

对象池适合管理生命周期短但需要重复出现的对象，可以有效减少 GC (垃圾回收) 的触发

值/引用类型的存放位置 链接到标题

【值类型是否在栈上】取决于它被放在哪

【引用类型的内容】一定在堆上，但引用本身可能在栈上

方法中的局部变量默认存放在栈上