type
status
date
slug
summary
tags
category
icon
password
状态
专注质量
预计（分钟）
开始时间
结束时间
文章来源说明
🤔 客户端开发笔试常见知识汇总
目录
🤔 客户端开发笔试常见知识汇总目录选择题和简答题高频题目已知二叉树前序和中序，求后序序列入栈顺序ABCDEFG，则出栈顺序不可能是___排序算法快速排序冒泡排序选择排序插入排序归并排序堆排序希尔排序最后三种结构体所占内存📝算法题C++算法题中常用的api整理（转载知乎用户“好吃的无锡油面筋”）🤗自己积累可能会用上的知识四叉树和八叉树定义应用场景算法过程思考图形学相关渲染管线参考文章
选择题和简答题高频题目
已知二叉树前序和中序，求后序序列
首先知道二叉树的三种序列分别代表什么含义：
- 前序：根左右
- 中序：左根右
- 后序：左右根
因此，如果已知前序，那个第一个节点一定是根节点，然后根据中序序列，就能切出左子树和右子树，一步步递归得到整个序列。这种题目只要花费一定时间，都能推出来，并且最后可以反过来验算，了解方法即可达到100%正确率！
入栈顺序ABCDEFG，则出栈顺序不可能是___
这种序列就看哪一个元素是第一个不按顺序出栈的。
比如ABCDEFG，看似出栈和入栈顺序一样，但是是合理的，因为进去之后马上出栈就可以！
但如果是ADxxxxx，那么你就知道了，B在栈底，C在B上面，此时便会出现出栈序列的矛盾。
排序算法
快速排序
最高频的考点，可以从以下多个方面考察：
- 基础概念
时间复杂度？是否稳定？
- 具体流程
如果选择最后一个元素作为基准元素，那么排序完成一共需要几次比较？
- 手撸实现
理论上只要知道第三条，1、2条的考点也不会被难倒。快排的算法实现就两条，递归和左右指针。一般都是以第一个元素或者最后一个元素为基准，相当于挖了个坑，然后从另一侧找到第一个比基准元素大（或者小）的元素，交换；那么另一侧原来的位置就又多出来个坑，从反面找到第一个比基准元素小（或者大）的元素，交换，重复这个过程知道left==right。此时就能达到左侧都比基准元素大，右侧均比基准元素小的状态了，最后迭代排列两个左右区间。
冒泡排序
从后往前遍历的话，每一轮都能把最大（或者最小）的元素不断交换到最前面。
实现思路非常简单，并且算法稳定。
选择排序
每一轮找到一个最值，放在序列最前面。
是不稳定。
插入排序
数组分为两段，一段为已经排序的，另一段为未排序的。
每次选择未排序序列中的第一个，找到其在有序序列中的位置。
是一种稳定算法
归并排序
不断二分数组，分到不能在分之后，反向递归，合并成有序序列。
比如（54321）需要排成从小到大。
第一次分成543，21
第二次分成54 3 21
第三次分成5 4 3 2 1
第一次归并为45 3 12
第二次归并为345 12
第三次归并为12345
简单的问题，可以问归并算法是否稳定（稳定），时间复杂度。
复杂一点，需要手写代码，但总体来说不难。
堆排序
堆可以用数组实现，因为可以将数组视为一个完全二叉树，那么根节点和子节点在数组中的索引是有规律的，比如根节点数组下标为i，左叶子就是2i，右叶子是2i+1。（如果有的话）
堆排序的流程如下：
- 建堆，从最后一个非叶子节点开始，与其孩子交换，将较大（小）的元素往上调整
- 此时堆顶元素就是最大值，将其与最后一个元素交换，将剩下的堆元素重新调整为堆
- 反复这个过程，知道堆中只剩下一个元素
这是一种不稳定的算法，且时间复杂度为nlogn级别。
希尔排序
没有研究过具体实现，只知道平均复杂度为n的1.3次幂，最坏为n平方，最好为n。
是一种不稳定的排序算法。
最后三种
计数排序、桶排序和箱排序，属于低频考点
结构体所占内存
📝算法题
C++算法题中常用的api整理（转载知乎用户“好吃的无锡油面筋”）
std::vector<T>
- push_back(const T& value): 添加元素至末尾
- pop_back(): 移除末尾元素
- size(): 获取元素数量
- empty(): 检查容器是否为空
- clear(): 清空容器
- begin(), end(): 获取迭代器
std::list<T>
- push_back(const T& value), push_front(const T& value): 添加元素
- pop_back(), pop_front(): 移除元素
- size(), empty(), clear(): 同std::vector
- begin(), end(): 获取迭代器
std::set<T>
- insert(const T& value): 插入元素
- erase(const T& value): 删除元素
- find(const T& value): 查找元素
- size(), empty(), clear(), begin(), end(): 同std::vector
std::map<K, V>, std::unordered_map<K, V>
- insert(std::make_pair(key, value)): 插入键值对
- erase(const K& key): 根据键删除元素
- find(const K& key): 查找键
- size(), empty(), clear(), begin(), end(): 同std::vector
std::queue<T>
- push(const T& value): 添加元素至末尾
- pop(): 移除首元素
- front(): 获取首元素
- size(), empty(): 同std::vector
std::stack<T>
- push(const T& value): 添加元素至顶部
- pop(): 移除顶部元素
- top(): 获取顶部元素
- size(), empty(): 同std::vector
std::priority_queue<T>
- push(const T& value): 插入元素
- pop(): 移除顶部元素
- top(): 获取顶部元素
- size(), empty(): 同std::vector
♥️字符串相关：
getline
std::string line;
std::getline( cin, line ); // 从标准输入读取一整行
stringstream
- str(): 获取或设置流中的字符串内容
- get(): 获取下一个字符
- <<: 插入操作符，将数据插入到流中
- >>: 提取操作符，从流中提取数据
- clear(): 清除流的状态标志
- peek(): 查看下一个字符
"1,234,567"去掉逗号，可以通过以下方法来实现：
字符串相关处理我一般可能会接收之后遍历一次字符串，去掉‘，’，这里的做法明显是一种更好的做法。
其它
构建数组
int arr[][]={0,1,0,-1,1,0,-1,0};
sort函数
可以定义一个返回值为bool的cmp函数作为比较器，在一些题目中很有用
stoi和stof函数
将字符串转为特定类型值
🤗自己积累可能会用上的知识
四叉树和八叉树
定义
一种树型数据结构，分别代表最多有几个子节点。
应用场景
对空间进行分割，方便检测互相之间的碰撞，或者其它需要两两检测的场景。
算法过程
以四叉树为例，其理解逻辑参考堆：
- 第一步是如何构建四叉树，四叉树一般会有一个maxDepth和一个capcity，前者即最深遍历深度，用于控制整体规模，后者用于限制每个树节点存储的孩子个数。在构建时，当超过capcity时，开始对当前空间进行四等分，查询当前节点在哪个区间并添加。如果当前节点处在交叉位置，则需要添加到父节点处，无视capcity的存在
- 第二步是应用，显然，当四叉树已经构建好后，假设当前需要求一个圆A的所有碰撞时，可以快速过滤无用的节点。其父节点以及所有兄弟节点即为它所能接触到的所有可能的节点！
- 另外就是插入和删除，插入跟构建时的步骤一样；删除时需要注意，可能会动态调整树的结构，达到优化目的。
思考
学习一个知识，如果没有深刻实践的话，很难能有深刻理解或者记忆。但复习时也要抓住根本目的，如果是为了找工作，未必面面俱到，对每个领域都有所了解就很好了。
图形学相关
渲染管线
应用阶段—几何阶段—光栅化阶段
顶点着色器出现在几何几段，片元着色器出现在光栅化阶段
参考文章
致谢：
Written by Aryue,editted by Notion AI.
- 作者:Aryue
- 链接:www.aryue.com/article/c59726fc-2456-4bdb-8837-d8b59afccfa9
- 声明:本文采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。
