最小二乘拟合 是一种数学上的近似和优化，利用已知的数据得出一条直线或者曲线，使之在坐标系上与已知数据之间的距离的平方和最小。

ICP 算法简介

• 由点云配准 说起

  　Point cloud registration, is the process of finding a spatial transformation that aligns two point clouds. The purpose is to merge point clouds of multiple views into a globally consistent model.
  　Iterative Closest Points (ICP) is an algorithm employed to minimize the difference between two clouds of points. In the algorithm, target point cloud, is kept fixed, while the other one, the source, is transformed to best match the reference (the target). The algorithm iteratively revises the transformation (combination of translation and rotation) needed to minimize the distance from the source to the reference point cloud.

　　昨晚华为在线笔试，三道编程题，结果倒在第二题上，刷了两题半，没能 AK。

第一题

　第一题是括号（“(”、“[”、“{”）匹配，想法也比较简单，就通过栈stack模拟，遇到开括号推入堆栈，每当遇到闭括号（“)”、“]”、“}”），就进行配对，满足配对就将栈顶的开括号弹出。假如最终的栈是空的，说明输入表达式不存在括号或者括号能够完全匹配。
　需要注意的是：①满足配对并不是stack.top()==inputStr[currentIdx]，而需要分上述三种括号进行一一配对；②当存在闭括号，但栈为空或者栈顶元素并不是配对的开括号，已经能够证明输入表达式括号不匹配了，此时可以跳出循环。

　一些计算机程序设计中常用的线性数据结构：Array、ArrayList、LinkedList、List、Stack、Queue、Hashtable 和Dictionary。为了更高效的进行数据的查找和访问，例如避免普通数据查找的 $O(N)$ 线性时间复杂度，常用树这种数据结构保存数据。
　树（Tree）是由多个节点（Node）的集合组成，每个节点又有多个与其关联的子节点（Child Node）；子节点就是直接处于节点之下的节点，而父节点（Parent Node）则位于节点直接关联的上方；树的根（Root）指的是一个没有父节点的单独的节点。所有的树都呈现了一些共有的性质：①只有一个根节点；②除了根节点，所有节点都有且只有一个父节点；③无环。将任意一个节点作为起始节点，都不存在任何回到该起始节点的路径（正是前两个性质保证了无环的成立）。
　更高效同时也相对更加复杂的树型数据结构包括 BST（二叉查找树）、R-B Tree（红黑树）、AVL Tree（平衡二叉树：父节点的左子树和右子树的高度之差不能大于1）、Treap（树堆：满足①二叉查找树的性质；满足②堆的性质）、Splay Tree（伸展树：在一次搜索后，会对树进行一些特殊的操作，这些操作的理念与AVL树有些类似，即通过旋转，来改变树节点的分布，并减小树的深度；伸展树并没有AVL树的平衡要求，任意节点的左右子树可以相差任意深度）、B-Tree（B树：多叉平衡查找树，B$^{+}$-Tree（B+树）是B树的变体）等。
　本文主要介绍基础的 BST（二叉查找树）以及提升搜索效率的更高级的数据结构：R-B Tree（红黑树）。

如何对 vector 初始化

• 大小为size的一维向量，二位向量

1
2

vector<what-type> var-name(what-size);
vector<vector<what-type>> var-name(rowSize, vector<what-type>(colSize));

• 数组转 vector

1
2
3
4
5
6
7
8
9
10
11
12

int rowSize = ?;
int colSize = ?;
what-type A_[rowSize][colSize] = {
  {element1, elment2, ..., element},
  {},
  ...
  {}
};
vector<vector<what-type>> A(rowSize, vector<what-type>(colSize));
for(int row=0; row<rowSize; row++) {
  A[row].assign(A_[row], A_[row] + colSize);
}

有向图 vs 无向图

• 有向图强调出入度的概念；无向图，其邻接矩阵 是一个对称矩阵。
• 无向图边的两端是对称的，无向图讲究连通这个概念，没有方向，没有拓扑。

判断图是否连通？（一个图有几个连通分量）

• 从一个指定的点开始，通过不同的策略去遍历这个图，有深度遍历和广度遍历。
• 每次经过一个节点的时候，首先判断一下这个节点是否已经访问过了，如果没有访问过，则这个节点可以作为下一次继续遍历的候选。
• 如果这个图是连通的话，这种方法最终会覆盖到整个图。所以可以采用一种计数统计的方式来实现。
  • 比如说每次访问一个以前没有遍历的节点，则将对应的计数加一。这样当最后遍历结束后，如果统计的节点和图本身的节点一样的话，表示这个图是连通的，否则表示不连通。
• 这种方法用来判断整个图是否为连通的时候，实际上只要给定一个点，然后按照给定的步骤可以把该点所连接的所有点都涵盖到。如果有其它分隔的部分则不会再处理了，所以，通过这种办法我们在图不是连通的情况下，它只需要涵盖图的一部分就执行结束了。最坏的情况时间复杂度也就是$O(V+E)$。

何为贪心？

• 贪心算法在解决问题的策略上目光短浅，只根据当前已有的信息就作出选择（下一步的选择总是在当前看来收敛最快和效果最明显的那一个），而且一旦做出了选择，不管将来有什么结果，这个选择策略都不会改变（以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为规模更小的子问题）。
• 贪心算法并不是从整体最优考虑，它所做出的选择只是在某种意义上的局部最优。
• 贪心算法对于大部分的优化问题都能产生最优解（如单源最短路径问题，最小生成树等），但不能总获得整体最优解，通常可以获得近似最优解。
• 贪心策略一旦经过证明成立后，它就是一种高效的算法。

基本概念？

• 点连通度（图的连通度）：对应一个图 $G$，对于所有点集 $U \subset V_G$，也就是 $V_G$ 的子集中，使得 $G-U$（在图 $G$ 中删去 $U$ 和与 $U$ 关联的边）要么是一个非连通图，要么就是一个平凡图，其中最小的集合 $U$ 的大小 $|U|$ 就是图 $G$ 的点连通度（有时候也直接称为图的连通度）。