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]，而需要分上述三种括号进行一一配对；②当存在闭括号，但栈为空或者栈顶元素并不是配对的开括号，已经能够证明输入表达式括号不匹配了，此时可以跳出循环。

　　本文介绍 JPEG 编解码过程（附简单的cpp实现）。JPEG 中常用到的熵编码是变长编码：Huffman 编码，本文也对算术编码（附cpp实现）、LZW 编码（附py实现）两种熵编码进行介绍。

　　加密方法可以分为两大类：一类是对称密码体制，又称单钥或私钥密码体制（private key cryptography）；还有一类是非对称密码体制，也称双钥或公开密钥体制（public key cryptography）。前者的加密和解密过程都用同一套密码，后者的加密和解密过程用的是两套密码。
　　在单钥加密的情况下，密钥只有一把，所以密钥的保存变得很重要，一旦秘钥泄露，密文也就被破解了；在双钥加密的情况下，秘钥有两把，一把是公开的公钥，还有一把是不公开的私钥，公钥与私钥是一一对应的关系，有一把公钥就必然有一把与之对应的、独一无二的私钥，反之亦成立。此外，①同时生成公钥和私钥应该是相对比较容易的：所有的公钥、私钥对都不同，用公钥可以解开私钥加密的信息，反之用私钥也可以解开公钥加密的信息；但是②从公钥推算出私钥，应该是很困难或者是不可能的。
　　目前，通用的单钥加密算法有 DES（Data Encryption Standard），通用的双钥加密算法为 RSA（Rivest-Shamir-Adleman），本文主要介绍三种常用的单钥加密算法：DES、3DES（Triple DES） 以及 AES（Advanced Encryption Standard）。

　一些计算机程序设计中常用的线性数据结构：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)$。