引子：小萝卜的例子

希望小萝卜具有自主运动能力。
定位和建图可以看成感知的内外之分：

• 一方面，要明白自身的状态（即位置）；
• 另一方面，也要了解外在的环境（即地图）。

一类传感器是携带于机器人本体上的，测到的通常都是一些间接的物理量而不是直接的位置数据，这种定位方案可适用于未知环境；
另一类是安装于环境中的，限制了机器人的使用范围。
当谈论视觉 SLAM时，主要是指如何用相机解决定位和建图问题。
相机：以一定速率拍摄周围的环境，形成一个连续的视频流。
按照工作方式的不同，可分为：单目相机（Monocular）、双目相机（Stereo）、深度相机（RGB-D）。

本书讲什么

SLAM 是 Simultaneous Localization And Mapping 的缩写，中文译作：同时定位与地图构建。
SLAM 的目的是解决定位与地图构建，希望实时地、在没有先验知识的情况下进行 SLAM。
我们眼中的花草树木、虫鱼鸟兽，在计算机中只是一个个由数字排列而成的矩阵。
与人工智能和机器学习所用的方式——概率学建模是不同的。
与 SLAM 相关的应用点：在许多地方，我们都希望知道自身的位置。
虽然 SLAM 的理论框架基本趋于稳定，但其编程实现仍然较为复杂。
我们会详细地介绍 SLAM 的理论背景、系统架构，以及各个模块的主流做法。
经典书籍：《概率机器人》（Probabilistic robotics）、《计算机视觉中的多视图几何》（Multiple View Geometry in Computer Vision）、《机器人学中的状态估计》（State Estimation for Robotics: A Matrix-Lie-Group Approach）

• 目的在于介绍基础理论，SLAM 只是其应用之一；
• 内容偏重于数学理论，基本不涉及编程实现。

用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 appendTail 和 deleteHead，分别完成在队列尾部插入节点和在队列头部删除节点的功能。

1
2
3
4
5
6
7
8
9
10
11

template<typename T> class CQueue 
{
    public:
        CQueue(void);
        ~CQueue(void);
        void appendTail(const T& node);
        T deleteHead();
    private:
        stack<T> stack1;
        stack<T> stack2;
};

• 操作系统会给每个线程创建一个栈用来存储函数调用时各个函数的参数、返回地址、临时变量等。
• 需要 O(n) 时间，才能找到栈中最大或者最小的元素。
• 考查应聘者写与模板相关的代码的能力。

给定一棵二叉树和其中的一个节点，如何找出中序遍历序列的下一个节点？树中的节点出了有两个分别指向左、右子节点的指针，还有一个指向父节点的指针。

考虑不同位置的节点的下一个节点：

1. 节点有右子树：从右子节点出发一直沿着左指针向下遍历，就能找到下一个节点；
2. 节点没有右子树：
   • 节点是它父节点的左子节点：下一个节点就是它的父节点；
   • 节点是它父节点的右子节点：沿着父指针一直向上遍历，直到找到一个是它父节点的左子节点的节点，这个节点的父节点就是我们要找的下一个节点。反之，则没有下一个节点；

Source Code

输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如，输入前序遍历序列 {1, 2, 4, 7, 3, 5, 6, 8} 和中序遍历序列 {4, 7, 2, 1, 5, 3, 8, 6}，则重建二叉树并输出它的头节点。二叉树节点的定义如下：

1
2
3
4
5
6

struct BinaryTreeNode 
{
    int m_nValue;
    BinaryTreeNode *m_pLeft;
    BinaryTreeNode *m_pRight;
}

• 由于树的操作会涉及大量的指针，因此与树有关的面试题都不太容易。
• 3 种遍历都有递归和循环两种不同的实现方法，递归实现都比循环实现要简洁很多。
• 我们可以平均在 O(logn) 的时间内，根据数值在二叉搜索树中找到一个节点。
• 需要快速找到最大值或最小值的问题都可以用堆来解决。
• 红黑树：把树中的节点定义为红、黑两种颜色，并通过规则确保从根节点到叶节点的最长路径的长度不超过最短路径的两倍。STL 中，set、multiset、map、mutimap 等数据结构都是基于红黑树实现的。
• 考查应聘者分析复杂问题的能力。把构建二叉树的大问题分解成构建左、右子树的两个小问题。确定左、右子树节点的数量，用递归的方法去完成。
  Read more »