3D Vision、SLAM求职宝典 | 程序基础篇（A）

阳光穿透心脏的1/2处 2022-02-02 09:25 157阅读 0赞

这一篇所涉及到的主要是C++语言基础，以及算法与数据结构的考点。实际上这些内容，各大公司都会有考察，无论是笔试还是面试，都离不开算法与数据结构，因为确实是技术岗的基础。 甚至有些公司，例如微软，特别看重手写代码的能力，现场给你一块小黑板，你不得不在短时间内组织好思路并书写，考虑边界、格式、性能等等。 因为SLAM领域中主要以C++语言为主（实时性要求），所以这里我们不提及其他语言了。

如果你的Linux或者C++语言或者数据结构或者算法基础不是很好，那么，赶紧再多看几遍书吧，这里有**新手礼包**相赠——

*  《鸟哥的私房菜》以及官网 [http://cn.linux.vbird.org/][http_cn.linux.vbird.org]
 *  《数据结构：思想与实现（第2版）》 交大本科教材，至少要读一遍
 *  《C++程序设计——思想与方法 慕课版（第3版）》 交大本科教材，至少要读三遍
 *  《算法图解》非常薄的一本书，Python语言
 *  《剑指offer》尤其是应对面试，经典。至少要读三遍 
 *   牛客网。这里有大量的笔试题或者在线编程题以及互联网公司的真题，冲刺阶段必备。 
 *   LeetCode。看你兴趣，如果没时间不看也可以，牛客网上的真题更符合场景，效率更高。当然多多益善。

--------------------

接下来让我们进入正题。

**目录**

1. 多线程的了解

2. stl有什么？

3. vector扩充方式，size与capacity区别

4. 顺序存储结构有哪些？

5. 左值引用与右值引用

6. map与unordered map区别

7. const与static、const在函数前与函数后区别

8. 虚函数与纯虚函数区别，虚函数关键字

9. 函数memcpy 、memset的实现，手撕代码

10. 一行代码求平方根

11. 各种排序时间空间复杂度（快排，归并，桶排，堆排），手撕代码

12. 最长公共子串、最长公共子序列，手撕代码

13. 树的DFS与BFS、树的遍历，手撕代码

14. 对于n个实例的k维数据，建立kd tree的时间复杂度

15. 哈夫曼树带权路径长度、哈夫曼编码

16. 长度为n的list，删除、插入与随机访问的计算复杂度

17. 在有序表中二分查找关键字所需进行的关键字比较次数是多少？

18. 字符串子串数目

19. 三维空间最近邻搜索的常用数据结构（八叉树、kd tree）

20. HashMap和Hashtable的比较

21. 在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数

--------------------

> ### 1. 多线程的了解 ###

为简单起见，以下为多线程入门的一些资料，我们暂时先了解到这。

C++11多线程简介： [https://www.cnblogs.com/zhangbaochong/p/5578701.html][https_www.cnblogs.com_zhangbaochong_p_5578701.html]

C++多线程 | 菜鸟教程 ： [https://www.runoob.com/cplusplus/cpp-multithreading.html][https_www.runoob.com_cplusplus_cpp-multithreading.html]

C++11并发编程基础（一）：并发、并行与C++多线程： [https://www.cnblogs.com/lpxblog/p/5190438.html][https_www.cnblogs.com_lpxblog_p_5190438.html]

**C++11 多线程管理：**[https://www.oschina.net/translate/cplusplus-11-threading-make-your-multitasking-life?print][https_www.oschina.net_translate_cplusplus-11-threading-make-your-multitasking-life_print]

**多线程编程(一) ——初识**：[https://segmentfault.com/a/1190000016171072][https_segmentfault.com_a_1190000016171072]

c++11 线程：让你的多线程任务更轻松:

[https://www.oschina.net/translate/cplusplus-11-threading-make-your-multitasking-life?print][https_www.oschina.net_translate_cplusplus-11-threading-make-your-multitasking-life_print]

\----------------------------------------------------------------------------------------------------------------------------------------

最近又看了一些并发编程的内容，对于新手内容还是不少……这里再补充一波——

C++11 Thread多线程学习心得与问题 [https://www.cnblogs.com/code-wangjun/p/7476559.htm][https_www.cnblogs.com_code-wangjun_p_7476559.htm]

C++11并发之std::thread [https://www.cnblogs.com/lidabo/p/7852033.html][https_www.cnblogs.com_lidabo_p_7852033.html]

C++11中std::mutex的使用 [https://blog.csdn.net/fengbingchun/article/details/73521630][https_blog.csdn.net_fengbingchun_article_details_73521630]

基于C++11并发库的线程池与消息队列多线程框架——std::mutex类 [https://blog.csdn.net/godqiao/article/details/81088860][https_blog.csdn.net_godqiao_article_details_81088860]

\-------------------------------------------------------------------------------------------------------------------------------------------

**一文入门C++多线程编程：**

C++11多线程编程基础入门 [https://blog.csdn.net/krais\_wk/article/details/81095899][https_blog.csdn.net_krais_wk_article_details_81095899]

\--------------------------------------------------------------------------------------------------------------------------------------------

**终极武器： C++ Reference [http://www.cplusplus.com/reference/mutex/][http_www.cplusplus.com_reference_mutex]**

**（强烈建议如果英文没问题，你可以直接跳过以上所有的博客只看C++ Reference网站就够了，权威而且示例清楚）**

多线程编程还是有点晕的，最近楼主在看ORBSLAM中的多线程操作，还没有完全弄懂。

> ### 2. stl有什么？ ###

**STL基本概念与容器——**

C++ STL（标准模板库）是一套功能强大的 C++ 模板类，提供了通用的模板类和函数，这些模板类和函数可以实现多种流行和常用的算法和数据结构，如向量、链表、队列、栈。核心包括三个组件：

<table> 
 <tbody> 
  <tr> 
   <th>组件</th> 
   <th>描述</th> 
  </tr> 
  <tr> 
   <td>容器（Containers）</td> 
   <td>容器是用来管理某一类对象的集合。C++ 提供了各种不同类型的容器，比如 deque、list、vector、map 等。</td> 
  </tr> 
  <tr> 
   <td>算法（Algorithms）</td> 
   <td>算法作用于容器。它们提供了执行各种操作的方式，包括对容器内容执行初始化、排序、搜索和转换等操作。</td> 
  </tr> 
  <tr> 
   <td>迭代器（iterators）</td> 
   <td>迭代器用于遍历对象集合的元素。这些集合可能是容器，也可能是容器的子集。</td> 
  </tr> 
 </tbody> 
</table>

C++中有两种类型的容器：**顺序容器和关联容器**，顺序容器主要有：vector、list、deque等。其中vector表示一段连续的内存地址，基于数组的实现，list表示非连续的内存，基于链表实现。deque（双端队列）与vector类似，但是对于首元素提供删除和插入的双向支持。关联容器主要有map和set。map是key-value形式的，set是单值。map和set只能存放唯一的key值，multimap和multiset可以存放重复key值。 vector 的底层为顺序表（数组），list 的底层为双向链表，deque 的底层为循环队列，set 的底层为红黑树，hash\_set 的底层为哈希表。

**更全面的介绍——**

STL 是 C++ 通用库，基本结构由迭代器、算法、容器、仿函数、配接器和配置器（即内存配置器）组成。目前，STL 中已经提供的容器主要如下：

*  vector <T>：一种向量。
 *  list <T>：一个双向链表容器，完成了标准 C++ 数据结构中链表的所有功能。
 *  queue <T>：一种队列容器，完成了标准 C++ 数据结构中队列的所有功能。
 *  stack <T>：一种栈容器，完成了标准 C++ 数据结构中栈的所有功能。
 *  deque <T>：双端队列容器，完成了标准 C++ 数据结构中栈的所有功能。
 *  priority\_queue <T>：一种按值排序的队列容器。
 *  set <T>：一种集合容器。
 *  multiset <T>：一种允许出现重复元素的集合容器。
 *  map <key, val>：一种关联数组容器。
 *  multimap <key, val>：一种允许出现重复 key 值的关联数组容器。
 *  unordered\_map<key,val>：无序容器，底层基于哈希表。
 *  unordered\_set<key, value>
 *  unordered\_multimap<key, value>
 *  unordered\_multiset<key, value>

STL简介： [http://c.biancheng.net/view/1436.html][http_c.biancheng.net_view_1436.html]

STL查询详细大全： [http://c.biancheng.net/stl/][http_c.biancheng.net_stl]

> ### 3. vector扩充方式，size与capacity区别 ###

**C++ STL 之 vector 的 capacity 和 size 属性区别——**

**size** 是当前 vector 容器真实占用的大小，也就是容器当前拥有多少个容器。

**capacity** 是指在发生 realloc 前能允许的最大元素数，即预分配的内存空间。

当然，这两个属性分别对应两个方法：resize() 和 reserve()。

使用 resize() 容器内的对象内存空间是真正存在的。

使用 reserve() 仅仅只是修改了 capacity 的值，容器内的对象并没有真实的内存空间(空间是"野"的)。

此时切记使用 \[\] 操作符访问容器内的对象，很可能出现数组越界的问题。

下面用例子进行说明：

#include <iostream>
    #include <vector>
    
    using std::vector;
    int main(void)
    {
        vector<int> v;
        std::cout<<"v.size() == " << v.size() << " v.capacity() = " << v.capacity() << std::endl;
        v.reserve(10);
        std::cout<<"v.size() == " << v.size() << " v.capacity() = " << v.capacity() << std::endl;
        v.resize(10);
        v.push_back(0);
        std::cout<<"v.size() == " << v.size() << " v.capacity() = " << v.capacity() << std::endl;
    
        return 0;
    }

运行结果为：(win 10 + VS2010)

![20160417222951238.png][]

**注：** 对于 **reserve(10)** 后接着直接使用 **\[\]** 访问越界报错(内存是野的)，大家可以加一行代码试一下，我这里没有贴出来。

这里直接用**\[\]**访问，vector 退化为数组，不会进行越界的判断。此时推荐使用 at()，会先进行越界检查。

**相关引申——**

针对 capacity 这个属性，STL 中的其他容器，如 list map set deque，由于这些容器的内存是散列分布的，因此不会发生类似 realloc() 的调用情况，因此我们可以认为 capacity 属性针对这些容器是没有意义的，因此设计时这些容器没有该属性。在 STL 中，拥有 capacity 属性的容器只有 vector 和 string。

另，上述介绍中提到了realloc，我们不妨再学习一下：

void \*realloc (void \*ptr, size\_t new\_size )

是C中的函数，相关的还有malloc和free函数。在C++中主要用new和delete了。 realloc可能会改变指针的地址，不建议使用。 realloc函数用于修改一个原先已经分配的内存块的大小，可以使一块内存的扩大或缩小。若nuw\_size > size,即扩大\*ptr所指向的内存空间，如果原先的内存尾部有足够的扩大空间，则直接在原先的内存块尾部新增内存，如果原先的内存尾部空间不足，或原先的内存块无法改变大小，realloc将重新分配另一块nuw\_size大小的内存，并把原先那块内存的内容复制到新的内存块上。

> ### 4. 顺序存储结构有哪些？ ###

存储结构分四类：**顺序存储、链接存储、索引存储 和 散列存储**。[https://blog.csdn.net/wengchen123/article/details/78373000][https_blog.csdn.net_wengchen123_article_details_78373000]

C++中几种常见的顺序存储结构（[https://blog.csdn.net/wonitawonitawonita/article/details/79924068][https_blog.csdn.net_wonitawonitawonita_article_details_79924068]）——

*  vector：支持高效的随机访问和在尾端插入/删除操作
 *  list：非连续存储结构，具有双链表结构，每个元素维护一对前向和后向指针，因此支持前向/后向遍历。支持高效的随机插入/删除操作，但随机访问效率低下，且由于需要额外维护指针，开销也比较大。
 *  deque：deque除了具有vector的所有功能外，还支持高效的首/尾端插入/删除操作
 *  vector与deque的迭代器支持算术运算，list的迭代器只能进行++/--操作，不支持普通的算术运算。

> ### 5. 左值引用与右值引用 ###

左值是表达式结束后依然存在的持久对象；右值是表达式结束时就不再存在的临时对象。根本判断是用取地址符&，左值可以，右值不行。

**左值引用(lvalue reference)：**可以绑定到左值的引用。右值引用(rvalue reference)：指向一个将要销毁的对象的引用。 引用是C++语法做的优化，引用的本质还是靠指针来实现的。引用相当于变量的别名。声明引用的时候必须初始化，且一旦绑定，不可把引用绑定到其他对象；即引用必须初始化，不能对引用重定义；对引用的一切操作，就相当于对原对象的操作。

**左值引用的基本语法：type &引用名 = 左值表达式；**

**右值引用的基本语法type &&引用名 = 右值表达式；**

右值引用主要就是解决一个拷贝效率低下的问题，因为针对于右值，或者打算更改的左值，我们可以采用类似与unique\_ptr的move(移动)操作，大大的提高性能(move semantics)。

**右值引用 (Rvalue Referene)** 是 C++ 新标准 (C++11, 11 代表 2011 年 ) 中引入的新特性 , 它实现了转移语义 (Move Sementics) 和精确传递 (Perfect Forwarding)。详细：C++11 标准新特性: 右值引用与转移语义（[https://www.ibm.com/developerworks/cn/aix/library/1307\_lisl\_c11/][https_www.ibm.com_developerworks_cn_aix_library_1307_lisl_c11]），它的主要目的有两个方面：

*  消除两个对象交互时不必要的对象拷贝，节省运算存储资源，提高效率；
 *  能够更简洁明确地定义泛型函数；

**对于左值引用和右值引用的使用举个例子——**

#include <iostream>
    #include <string>
    #include <utility>
     
    namespace lvalue_rvalue_ {
    
    namespace {
    char& get_val(std::string& str, std::string::size_type ix)
    {
    	return str[ix];
    }
    }
     
    int test_lvalue_rvalue_1()
    {
    {
    	// 赋值运算符的左侧运算对象必须是一个可修改的左值：
    	int i = 0, j = 0, k = 0; // 初始化而非赋值
    	const int ci = i; // 初始化而非赋值
    	// 下面的赋值语句都是非法的
    	//1024 = k; // 错误：字面值是右值
    	//i + j = k; // 错误：算术表达式是右值
    	//ci = k; // 错误：ci是常量(不可修改的)左值
    }
     
    {
    	int i = 0;
    	int& r = i; // 正确：r引用i
    	//int&& rr = i; // 错误：不能将一个右值引用绑定到一个左值上
    	//int& r2 = i * 42; // 错误：i*42是一个右值
    	const int& r3 = i * 42; // 正确：我们可以将一个const的引用绑定到一个右值上
    	int&& rr2 = i * 42; // 正确：将rr2绑定到乘法结果上
    }
     
    {
    	// 不能将一个右值引用绑定到一个右值引用类型的变量上
    	int&& rr1 = 42; // 正确：字面常量是右值
    	//int&& rr2 = rr1; // 错误：表达式rr1是左值
    	//int rr = &&rr1; // 不能将一个右值引用直接绑定到一个左值上
    	int i = 5;
    	int&& rr3 = std::move(i); // C++11,std::move函数是将左值转换为对应的右值引用类型，这一步OK！！！ 
     
    }
     
    	// 调用一个返回引用的函数得到左值，其它返回类型得到右值
    	std::string s{ "a value" };
    	std::cout << s << std::endl; // a value
    	get_val(s, 0) = 'A';
    	std::cout << s << std::endl; // A value
     
    	return 0;

> ### 6. map与unordered map区别 ###

都属于关联容器，存储元素的类型都为Key-Value。也就是pair<key, value>。 map底层基于红黑树实现，排好序的；unordered\_map底层是基于散列表实现，是无序的。 两者的头文件分别是： \#include <map> \#include <unorderd\_map>两者都是不允许重复的key出现的，重复的版本为multimap和unorderd\_multimap.

在C++11中有新出4个关联式容器：unordered\_map/unordered\_set/unordered\_multimap/unordered\_multiset。

**map——**

*  有序性
 *  红黑树 ，插入删除效率比较高
 *  缺点：空间占用率比较高，因为红黑树节点需要保存多余的信息（父子节点和红黑树性质）

**unordered\_map——**

*  哈希表，查找速度非常快
 *  缺点：就是哈希算法的缺点，哈希表的建立耗时，可能发生碰撞，空间占用率高
 *  如果经常用到查找，使用之

因此如果在不涉及顺序并且能够设计出较好的hash算法（碰撞较少）的情况下，unordered\_map是最好的选择。但是如果考虑顺序的因素，仍旧需要选择map。设计动态数据结构的时候（动态插入与删除），红黑树是较好的选择。

> ### 7. const与static、const在函数前与函数后区别 ###

*  变量的作用域决定变量的有效范围，根据变量再计算中的存储位置，可将变量分为：**自动变量（auto），静态变量（static），寄存器变量（register），外部变量（extern）**。 自动变量包括局部变量、形式参数和语句块中变量，存储在内存中的栈区域，函数被调用时系统在栈上分配一块区域叫做帧，调用结束自动回收变量。 全局变量存储在全局变量区，用static修饰的静态变量可以是全局变量也可以是局部变量，静态的全局变量则只有该源文件可以共享某一全局变量，静态局部变量存储在全局变量区，函数结束时变量不消亡，继续上次调用函数时的结果，程序结束时再消亡。 寄存器变量存储在CPU的寄存器中，定义用关键字register修饰，现在的编译器基本上完成了自动的功能。 外部变量一定是全局变量，全局变量的作用域是从定义开始到文件结束，如果在定义之前或者其他源文件也要使用这一变量，则需要在使用前进行extern 外部变量声明。
 *  继续上面的阐述，如果一个函数在定义时前面加上static，该函数只能被本源文件调用。
 *  const修饰常量，作为右值
 *  在类的定义中，如果一个成员函数在函数的后面加关键字 const，说明为常量成员函数，在函数定义时也要加const。 常量成员函数不会修改类的数据成员，任何不修改数据成员的成员函数都应该被声明为const类型，这样如果编写程序时出现相应错误编译器会报错，提高了程序的健壮性。
 *  在成员函数前面加static，则为静态成员函数，静态成员函数用于操作静态数据成员，为类而不是类的对象服务。一般调用用“类名::静态成员函数()” .
 *  特点是没有隐含的this指针，不能访问一般的数据成员，只能访问静态数据成员或者其他静态成员函数。 主要目的就是访问数据成员。 在类外定义时，函数前面不用加static，但是类中的声明不能少static
 *  const加在函数的前面。 修饰函数的返回值，说明返回值是常量，这样的话函数只能被当做常量来使用。

> ### 8. 虚函数与纯虚函数区别，虚函数关键字 ###

*  C++的虚函数主要作用是“运行时多态”，父类中提供虚函数的实现，为子类提供默认的函数实现。子类可以重写父类的虚函数实现子类的特殊化。
 *  在父类函数原型声明中前加virtual，子类中的函数原型必须与父类的中一致，但是关键字virtual可以不写，最好写上。
 *  C++中包含纯虚函数的类，被称为是“抽象类”。抽象类不能使用new出对象，只有实现了这个纯虚函数的子类才能new出对象。
 *  纯虚函数的声明： virtual 返回类型 函数名（参数表）= 0
 *  在父类中没有定义。无法定义抽象类的对象，可以定义指向抽象类的指针
 *  抽象类的作用是保证继承层次的每个类都具有纯虚函数所要求的行为，保证了子类都必须定义该虚函数。

> ### 9. 函数memcpy 、memset的实现，手撕代码 ###

**memcpy——**

头文件：\#include <string.h>

函数原型：void \*memcpy(void \*dest, const void \*src, size\_t n)

功能：将指针src指向的内存空间的n个字节复制到dest指针指向的内存空间

参数：src 为原内容内存的起始地址，dest为复制到目标地址的起始地址

返回值：目标dest内存的起始地址

**注意：1、内存空间不能够有重叠； 2、memcpy对于需要复制的内容没有限制，因此用途更广； 3、很明确的是memcpy是将 n个字节， 虽然memcpy对复制的内容完全没有任何的限制，比如数组，结构体等特殊的结构，如果你想将整个结构体变量的内容复制到dest内存区，最好使用sizeof将要复制的内容的完整大小求出来赋值给n，以保持复制的完整性；**

（ 原文：https://blog.csdn.net/u011118276/article/details/46742341/ ）

void *memCpy(void *dest, const void *src, size_t n)
    {
    	if (NULL == dest || NULL == src || n < 0)
    		return NULL;
    	char *tempDest = (char *)dest;
    	char *tempSrc = (char *)src;
     
    	while (n-- > 0)
    		*tempDest++ = *tempSrc++;
    	return dest;	
    }
    
    
    
    //考虑内存重叠的情况
    void* memcpy2(void* desc, const void * src, size_t size)
    {
    	if(desc == NULL && src == NULL)
    	{
    		return NULL;
    	}
    	unsigned char* desc1 = (unsigned char*)desc;
    	unsigned char* src1 = (unsigned char*)src;
    	//当内存重叠时，从后往前复制
    	if(desc > src && desc1 < (src1 + size))//内存发生重叠
    	{ 
    		for (int i = size - 1; i >= 0; i--)
    		{
    			*desc1++ = *src1++;
    		}
    	}
    	else
    	{
    		for (int i = 0; i < size; i++)
    		{
    			*desc1++ = *src1++;
    		}
    	}
    	return desc;
    }

**memset——**

头文件：\#include <string.h>

函数原型：void \*memset(void \*s, int c, size\_t n)

功能：以s为起始位置的n个字节的内存区域用整数c进行填充

参数：s为内存区域的起始位置，c为要填充的字符，n为要填充多少个字节

返回值：目标s内存的起始地址

**注意： 1、n表示的是字节数，函数是以字节的形式每次赋值给目标地址；2、memset函数也是以字节为单位进行赋值的，所以要想在整形数组中给每一位赋确定的非0值，一般来讲是不可行的；（下方将有对此说明测试的程序）**

void *memSet(void *s, int c, size_t n)
    {
    	if (NULL == s || n < 0)
    		return NULL;
    	char * tmpS = (char *)s;
    	while(n-- > 0)
    		*tmpS++ = c;
    		return s; 
    }

> ### 10. 一行代码求平方根 ###

参考[https://blog.csdn.net/u013146882/article/details/72350873][https_blog.csdn.net_u013146882_article_details_72350873]

三种方法分别是二分法、牛顿法和卡马克算法（本质上也是牛顿法，初始值取得很巧妙）。代码如下：

#include<iostream>
    using namespace std;
    double sqrt_math1(double x) {     //二分法,不断取中间值进行迭代
    	if (x < 0) return -1;
    	double low = (x >= 1 ? 1 : x), high = (x >= 1 ? x : 1), mid = (low + high) / 2;
    	while (abs(mid*mid - x) > 0.000001) {
    		if (mid*mid > x) high = mid;
    		else low = mid;
    		mid = (low + high) / 2;
    	}
    	return mid;
    }
    double sqrt_math2(double x) {   //牛顿法，速度比二分法快
    	if (x < 0) return -1;
    	double pre = x, tem = (pre + x / pre) / 2;
    	while (abs(tem*tem - x) > 0.000001) {
    		tem = (tem + x / tem) / 2;
    	}
    	return tem;
    }
    float sqrt_math3(float x) {      //卡马克快速平方根算法(游戏编程经典算法)，比牛顿法快
    	if (x < 0) return -1;
    	float xhalf = 0.5f*x;
    	int i = *(int*)&x;    // get bits for floating VALUE   
    	i = 0x5f375a86 - (i >> 1);   // gives initial guess y0
    	x = *(float*)&i;   // convert bits BACK to float
    	x = x*(1.5f - xhalf*x*x);  // Newton step, repeating increases accuracy
    	x = x*(1.5f - xhalf*x*x);  // Newton step, repeating increases accuracy
    	x = x*(1.5f - xhalf*x*x);  // Newton step, repeating increases accuracy
    	return 1 / x;
    }
    int main() {
    	double x;
    	cout << "Input the number:";
    	while (cin >> x) {
    		cout << sqrt_math1(x) << endl;
    		cout << sqrt_math2(x) << endl;
    		cout << sqrt_math3(x) << endl;
    	}
            system("pause");
    	return 0;
    }

但是题目中说一行代码求平方根 。。。

改用Python：

*  内置模块： >>import math >>math.sqrt(n)
 *  使用表达式： >> n \*\* 0.5
 *  使用内置函数： >> pow( n, .5 )

> ### 11. 各种排序时间空间复杂度（快排，归并，桶排，堆排），手撕代码 ###

![20180329140709850][]

我的口诀： 不稳定排序的有：**快速直接堆希尔**。

**我们以快速排序为例（来自剑指offer）——**

实现快速排序的核心函数是一个分割函数（Partition），在数组中任意选择一个数index，将数组中的数字分为两部分，比index小的移到左边，大的移到右边。 这个函数的实现（不是一下就能理解，多看几遍）：

int Partition(int data[], int length, int start, int end)  //for example start=0 end=length-1      
    {
        //判断合法输入
        if(data==nullptr || length<=0 || start<=0 || end<=0 )
            throw new exception("Invalid Parameters.");
            
        int index = RandomInRange(start, end); 
        
        int small = start - 1;   //代表比标识小的数   
        Swap(&data[index], &data[end]);   //把标识放在end
        for(int i=start; i<end; ++i) 
        {
            if( data[i] < data[end] )   //用small来计量有几个小于标识的数
            {
                small++;    
                if(samll != i)
                    Swap( &data[small], &data[i] )        
            }    
        
        }
        
        ++small;   //例如small=1 表示data[0] data[1]都是小于的数 现在要把data[1]之后的数与end作交换 
        
        Swap(&data[samll], &data[end]);
        
        return small;    //返回这个标识数的位置 即这个数的最终位置已经排好了 而且前面的数都小于它 后面的数都大于   
    }

Patition这个函数不仅仅是在快速排序中可以用到，有时一些算法题中也可以使用。 接下来，我们看一下快排的主函数：

void QuikSort(int data[], int length, int start, int end)  //因为函数中要用到递归 后面的两个形参不能少   
    {
        if(data == nullptr || length <= 0)  
            throw new std::exception("valid parameters.");
            
        if(satrt == end) 
            return;     
            
        int index = Partition(data, length, start, end);    
        if(start < index)   //start==index 时 前半部分不用排序    
            QuikSort(data, length, start, index-1); 
        if(end > index) 
            QuikSort(data, length, index+1, end);
            
        return;    
    }

OK，关于其他的排序方法这里就不介绍了，如有机会，后面我们再写一篇博客，详细阐述这些排序方法。

> ### 12. 最长公共子串、最长公共子序列，手撕代码 ###

最长公共子串（Longest Common Substring），子串是连续的；

最长公共子序列（Longest Common Subsequences）, 不一定是连续的

**最长公共子序列——**

参考我之前写得一篇博客：[https://blog.csdn.net/weixin\_43795395/article/details/89554031][https_blog.csdn.net_weixin_43795395_article_details_89554031]

“删除最少的字符串使得剩下成为回文串” ：我想掌握了这道题，基本上最长公共子序列方法和代码应该没问题。 这里就简要说一下函数关系式： 不妨设函数参数为m, n，分别表示str1和str2字符串的下标位置。 于是，求函数表达式 L(m, n)！

*  如果str1(m) == str2(n), 则 L(m, n) = L(m-1, n-1)
 *  如果str1(m) != str2(n), 则 L(m, n) = max ( L(m, n-1), L(m-1, n) )

**最长公共子串——**

跟上面有点类似，这里我们直接分析函数关系式 (注意起始状态和上面的不同，而且i = 0 或者j = 0应该指示的是字符串中的下标减1)

*  如果i = 0 或者 j = 0， L(i, j) = 0;
 *  如果 A\[i\] = B\[i\]， L(i, j) = L(i - 1, j - 1) + 1
 *  如果A\[i\] != B\[i\], L(i, j) = 0;

#include<iostream>
    #include<string.h>
    using namespace std;
     
    //dp[i][j]:串(x1,x2,...,xi)与串(y1,y2,...,yj)，
    //d[i][j]表示这两个串结与最长公共子串结尾相同时，最长公共子串的长度
     
    //状态转移方程如下： 
    //若i=0或j=0，则dp[i][j] = 0
    //否则：
    //		若A[i]==B[j]，则dp[i][j] = dp[i-1][j-1] + 1
    //		若A[i]!=B[j]，则dp[i][j] = 0
     
     
    //用于打印的函数，后面才用到 
    void print_substring(string str, int end, int length)
    {
    	int start = end - length + 1;
    	for(int k=start;k<=end;k++)
    		cout << str[k];
    	cout << endl;
    }
     
    int main()
    {
    	string A,B;
    	cin >> A >> B;
    	int x = A.length();
    	int y = B.length();
    	A = " " + A;//特殊处理一下，便于编程 
    	B = " " + B;
    	
    	//回忆一下dp[][]的含义？ 
    	int **dp = new int* [x+1];
    	int i,j;
    	for(i=0;i<=x;i++)
    	{
    		dp[i] = new int[y+1];
    		for(j=0;j<=y;j++)
    			dp[i][j] = 0;
    	}
    	
    	
    	//下面计算dp[i][j]的值并记录最大值 
    	int max_length = 0;
    	for(i=1;i<=x;i++)
    		for(j=1;j<=y;j++)
    			if(A[i]==B[j])
    			{
    				dp[i][j] = dp[i-1][j-1] + 1;
    				if(dp[i][j]>max_length)
    					max_length = dp[i][j];
    			}
    			else
    				dp[i][j] = 0;
     
    	
    	//LCS的长度已经知道了，下面是根据这个最大长度和dp[][]的值，
    	//找到对应的 LCS具体子串， 注意：可能有多个 
    	int const arr_length = (x>y?x:y) + 1;
    	int end_A[arr_length];	//记录LCS在字符串A中结束的位置 
    	int num_max_length = 0;	//记录LCS的个数 
    	
    	for(i=1;i<=x;i++)
    		for(j=1;j<=y;j++)
    			if(dp[i][j] == max_length)
    				end_A[num_max_length++] = i;
    	
    	cout << "the length of LCS(substring) is : " << max_length  << endl << " nums: " << num_max_length << endl << "they are (it is): " << endl;
    	for(int k=0;k<num_max_length;k++)	//输出每个具体的子串 
    		print_substring(A, end_A[k], max_length);
    	
    	return 0;
    }
    
    //来自： https://blog.csdn.net/ten_sory/article/details/79857531

> ### 13. 树的DFS与BFS、树的遍历，手撕代码 ###

BFS和DFS的原理以及代码实践，我在之前的一篇博客中做了较详细的讨论，请见[https://blog.csdn.net/weixin\_43795395/article/details/89399874][https_blog.csdn.net_weixin_43795395_article_details_89399874]。

这里我们主要来看对树用这两种搜索方法。 （参考[https://blog.csdn.net/m0\_37973607/article/details/86290964][https_blog.csdn.net_m0_37973607_article_details_86290964]）

**深度优先搜索(Depth First Search)——**

是沿着树的深度遍历树的节点，尽可能深的搜索树的分支。以下面二叉树为例，深度优先搜索的顺序为：ABDECFG。DFS是先访问根结点，然后遍历左子树接着是遍历右子树，因此我们可以利用堆栈的先进后出的特点，现将右子树压栈，再将左子树压栈，这样左子树就位于栈顶，可以保证结点的左子树先与右子树被遍历。

![805461-20160514164458359-1600906940.png][]

**广度优先搜索(Breadth First Search)——**

又叫宽度优先搜索或横向优先搜索，是从根结点开始沿着树的宽度搜索遍历，上面二叉树的遍历顺序为：ABCDEFG。可以利用队列实现广度优先搜索。

1 #include <vector>
     2 #include <iostream>
     3 #include <stack>
     4 #include <queue>
     5 using namespace std;
     6 
     7 struct BitNode
     8 {
     9     int data;
    10     BitNode *left, *right;
    11     BitNode(int x) :data(x), left(0), right(0){}
    12 };
    13 
    14 void Create(BitNode *&root)
    15 {
    16     int key;
    17     cin >> key;
    18     if (key == -1)
    19         root = NULL;
    20     else
    21     {
    22         root = new BitNode(key);
    23         Create(root->left);
    24         Create(root->right);
    25     }
    26 }
    27 
    28 void PreOrderTraversal(BitNode *root)
    29 {
    30     if (root)
    31     {
    32         cout << root->data << " ";
    33         PreOrderTraversal(root->left);
    34         PreOrderTraversal(root->right);
    35     }
    36 }
    37 
    38 //深度优先搜索
    39 //利用栈，现将右子树压栈再将左子树压栈
    40 void DepthFirstSearch(BitNode *root)
    41 {
    42     stack<BitNode*> nodeStack;
    43     nodeStack.push(root);
    44     while (!nodeStack.empty())
    45     {
    46         BitNode *node = nodeStack.top();
    47         cout << node->data << ' ';
    48         nodeStack.pop();
    49         if (node->right)
    50         {
    51             nodeStack.push(node->right);
    52         }
    53         if (node->left)
    54         {
    55             nodeStack.push(node->left);
    56         }
    57     }
    58 }
    59 
    60 //广度优先搜索
    61 void BreadthFirstSearch(BitNode *root)
    62 {
    63     queue<BitNode*> nodeQueue;
    64     nodeQueue.push(root);
    65     while (!nodeQueue.empty())
    66     {
    67         BitNode *node = nodeQueue.front();
    68         cout << node->data << ' ';
    69         nodeQueue.pop();
    70         if (node->left)
    71         {
    72             nodeQueue.push(node->left);
    73         }
    74         if (node->right)
    75         {
    76             nodeQueue.push(node->right);
    77         }
    78     }
    79 }
    80 
    81 int  main()
    82 {
    83     BitNode *root = NULL;
    84     Create(root);
    85     //前序遍历
    86     PreOrderTraversal(root);
    87     //深度优先遍历
    88     cout << endl << "dfs" << endl;
    89     DepthFirstSearch(root);
    90     //广度优先搜索
    91     cout << endl << "bfs" << endl;
    92     BreadthFirstSearch(root);
    93 }

##  ##

> ### 14. 对于n个实例的k维数据，建立kd tree的时间复杂度 ###

关于Kd树，这里有一篇非常详细的文章，从K近邻算法谈到Kd树，以及Kd树的算法实现。

参考 [https://blog.csdn.net/likika2012/article/details/39619687][https_blog.csdn.net_likika2012_article_details_39619687]

kd树构建的伪代码：

![1353732091_4225.jpg][]

再举一个简单直观的实例来介绍k-d树构建算法。假设有6个二维数据点\{(2,3)，(5,4)，(9,6)，(4,7)，(8,1)，(7,2)\}，数据点位于二维空间内，如下图所示。为了能有效的找到最近邻，k-d树采用分而治之的思想，即将整个空间划分为几个小部分，首先，粗黑线将空间一分为二，然后在两个子空间中，细黑直线又将整个空间划分为四部分，最后虚黑直线将这四部分进一步划分。

![1353405921_3066.jpg][]

6个二维数据点\{(2,3)，(5,4)，(9,6)，(4,7)，(8,1)，(7,2)\}构建kd树的具体步骤为：

1.  确定：split域=x。具体是：6个数据点在x，y维度上的数据方差分别为39，28.63，所以在x轴上[方差][Link 1]更大，故split域值为x；
2.  确定：Node-data = （7,2）。具体是：根据x维上的值将数据排序，6个数据的中值(所谓中值，即中间大小的值)为7，所以Node-data域位数据点（7,2）。这样，该节点的分割超平面就是通过（7,2）并垂直于：split=x轴的直线x=7；
3.  确定：左子空间和右子空间。具体是：分割超平面x=7将整个空间分为两部分：x<=7的部分为左子空间，包含3个节点=\{(2,3),(5,4),(4,7)\}；另一部分为右子空间，包含2个节点=\{(9,6)，(8,1)\}；

如上算法所述，kd树的构建是一个递归过程，我们对左子空间和右子空间内的数据重复根节点的过程就可以得到一级子节点（5,4）和（9,6），同时将空间和数据集进一步细分，如此往复直到空间中只包含一个数据点。

![1353735462_4522.jpg][]

与此同时，经过对上面所示的空间划分之后，我们可以看出，点(7,2)可以为根结点，从根结点出发的两条红粗斜线指向的(5,4)和(9,6)则为根结点的左右子结点，而(2,3)，(4,7)则为(5,4)的左右孩子(通过两条细红斜线相连)，最后，(8,1)为(9,6)的左孩子(通过细红斜线相连)。如此，便形成了下面这样一棵k-d树：

![1353406276_4095.jpg][]![1353404648_2086.jpg][]

也就是说，如之前所述，kd树中，kd代表k-dimension，每个节点即为一个k维的点。每个非叶节点可以想象为一个分割超平面，用垂直于坐标轴的超平面将空间分为两个部分，这样递归的从根节点不停的划分，直到没有实例为止。经典的构造k-d tree的规则如下：

1.  随着树的深度增加，循环的选取坐标轴，作为分割超平面的法向量。对于3-d tree来说，根节点选取x轴，根节点的孩子选取y轴，根节点的孙子选取z轴，根节点的曾孙子选取x轴，这样循环下去。
2.  每次均为所有对应实例的中位数的实例作为切分点，切分点作为父节点，左右两侧为划分的作为左右两子树。

![1353730694_8941.gif][]

**对于n个实例的k维数据来说，建立kd-tree的时间复杂度为O(k\*n\*logn)。**

(构建堆得时间复杂度为O(n), 构建二叉查找树的时间复杂度为 n\*log2n )

> ### 15. 哈夫曼树带权路径长度、哈夫曼编码 ###

**哈夫曼树的构造——**

哈夫曼树在构造时每次从备选节点中挑出两个权值最小的节点进行构造，每次构造完成后会生成新的节点，将构造的节点从备选节点中删除并将新产生的节点加入到备选节点中。新产生的节点权值为参与构造的两个节点权值之和。举例如下：

![872539-20161104194812346-1641453195.png][]

**带权路径长度计算——**

![image][]

(a) WPL = 7x2+5x2+2x2+4x2=36 (b) WPL = 2X1+4X2+7X3+5X3 = 46 (c) WPL = 7x1+5x2+2x3+4x3 = 35

即所有叶节点的带权路径之和为该树的带权路径长度(WPL)。 某个叶节点的带权路径等于该叶节点的深度（根的深度为0）乘以权重，也就是从根到叶节点所走过边的数量。

**哈夫曼树的应用——**

在处理字符串序列时，如果对每个字符串采用相同的二进制位来表示，则称这种编码方式为定长编码。若允许对不同的字符采用不等长的二进制位进行表示，那么这种方式称为可变长编码。可变长编码其特点是对使用频率高的字符采用短编码，而对使用频率低的字符则采用长编码的方式。这样我们就可以减少数据的存储空间，从而起到压缩数据的效果。而通过哈夫曼树形成的哈夫曼编码是一种的有效的数据压缩编码。

如果没有一个编码是另一个编码的前缀，则称这样的编码为前缀编码。如0,101和100是前缀编码。由前缀码形成的序列可以被唯一的组成一个字符串序列。如00101100可以被唯一的分析为0，0，101和100。

示例:　我们对一个字符串进行统计发现a-f出现的频率分别为a:45，b:13，c:12，d:16，e:9，f:5，我们对该字符串进行采用哈夫曼编码进行存储。

![image][image 1]

WPL = 1x45+3x(13+12+16)+4x(5+9)=224

这样算下来使用224二进制位就可以将该字符串存储起来，因为哈夫曼码是前缀码，所以可以唯一的还原出原来的字符序列。如果我们每个字符使用3位进行存储(至少3位),那么需要300bit才能将该字符串存储下。

> ### 16. 长度为n的list，删除、插入与随机访问的计算复杂度 ###

**插入、删除数据效率高，时间复杂度为O(1)，只需更改指针指向即可。**

**随机访问效率低，时间复杂度为O(n)，需要从链头至链尾进行遍历。**

和数组相比，链表的内存空间消耗更大，因为每个存储数据的节点都需要额外的空间存储后继指针。

常见的链表结构有：

*  单链表
 *  循环链表
 *  双向链表
 *  双向循环链表

**数组与链表的对比——　**

数组的缺点

*  若申请内存空间很大，比如100M，但若内存空间没有100M的连续空间时，则会申请失败，尽管内存可用空间超过100M。
 *  大小固定，若存储空间不足，需进行扩容，一旦扩容就要进行数据复制，而这时非常费时的。

链表的缺点

*  内存空间消耗更大，因为需要额外的空间存储指针信息。
 *  对链表进行频繁的插入和删除操作，会导致频繁的内存申请和释放，容易造成内存碎片，如果是Java语言，还可能会造成频繁的GC（自动垃圾回收器）操作。

如何选择链表和数组

*  数组简单易用，在实现上使用连续的内存空间，可以借助CPU的缓冲机制预读数组中的数据，所以访问效率更高。
 *  而链表在内存中并不是连续存储，所以对CPU缓存不友好，没办法预读。
 *  如果代码对内存的使用非常苛刻，那数组就更适合。
 *  可参考 [https://www.cnblogs.com/errornull/p/9790444.html][https_www.cnblogs.com_errornull_p_9790444.html]

> ### 17. 在有序表中二分查找关键字所需进行的关键字比较次数是多少？ ###

举个例子 \{ 12, 24, 36, 48, 60, 72, 84 \} 查找72需要比较的次数 ？

共7个数，下标范围 0 ～ 6. **查找之后的结果有三种，要么找到了，要么low = mid + 1, 要么 high = mid - 1**

二分查找开始：low = 0, high = 6;

第一次查找： mid = low + high / 2 = 3, 数字为48， 不等与72； low = mid + 1 = 4;

第二次查找： mid = low + high / 2 = 4 + 6 / 2 = 5, 数字为72， 成功。 所以一共比较了两次。

**最多比较 log2(N) 向下取整**

> ### 18. 字符串子串数目 ###

想象一个字符串string，子串长度为1的共有n， 子串长度为2的共有n - 1，我就不画图了很容易想象，一直到子串长度为n的有1个。 所有总数 = n + (n - 1) + (n - 2) + ... + 1 = n\*(n - 1) / 2 。

最后空串也算一个，所以子串数目为 n \* (n - 1) / 2 + 1 .

> ### 19. 三维空间最近邻搜索的常用数据结构（八叉树、kd tree） ###

参考《slam十四讲》——

> ### 20. HashMap和Hashtable的比较 ###

这两个数据结构应该主要实在Jave中讲的。。。

[https://blog.csdn.net/qq\_35181209/article/details/74503362][https_blog.csdn.net_qq_35181209_article_details_74503362]

C++中的hashmap跟unordered\_map差不多。

C++中map、hash\_map、unordered\_map、unordered\_set的区别： [https://blog.csdn.net/chen134225/article/details/83106569][https_blog.csdn.net_chen134225_article_details_83106569]

> ### 21. 在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数 ###

这

个就有点简单了，但是主要代码要写的完整准确。 这是来自剑指offer上的一道题，

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc5NTM5NQ_size_16_color_FFFFFF_t_70][]

二维数组中数的查找  
    题目：二维数组中从左到右增序 从上到下增序 实现一个函数输入为一个二维数组和整型数 判断二维数组中是否存在该整数  
    
    bool Find(int* matrix, int rows, int cols, int number)
    {
        bool found = false; 
        
        if(matrix != nullptr rows > 0 && cols > 0)  //判断输入的合法性
        {
            int row = 0; 
            int col = cols -1 ; 
            while(row < rows && col >= 0)   //循环结束的条件是行或者列超标了  
            {
                int tmp = matrix[row*cols + col];     //第row行col列的元素 这里每次循环还要创建局部变量 其实可以不写  直接在括号中做比较  
                if(tmp == number)  
                    found = true;
                    break;   //若存在及时跳出while循环 减小时间 
                //如果不是只有两种可能 比其大 或者比其小 
                else if(tmp > number)
                    --col;
                else 
                    ++row; 
            }
        }
        
        return found;
    }

--------------------

写博不易，您的支持让知识之花绽放得更美丽 ~\_~

![20190514202538815.png][]

[http_cn.linux.vbird.org]: http://cn.linux.vbird.org/
[https_www.cnblogs.com_zhangbaochong_p_5578701.html]: https://www.cnblogs.com/zhangbaochong/p/5578701.html
[https_www.runoob.com_cplusplus_cpp-multithreading.html]: https://www.runoob.com/cplusplus/cpp-multithreading.html
[https_www.cnblogs.com_lpxblog_p_5190438.html]: https://www.cnblogs.com/lpxblog/p/5190438.html
[https_www.oschina.net_translate_cplusplus-11-threading-make-your-multitasking-life_print]: https://www.oschina.net/translate/cplusplus-11-threading-make-your-multitasking-life?print
[https_segmentfault.com_a_1190000016171072]: https://segmentfault.com/a/1190000016171072
[https_www.cnblogs.com_code-wangjun_p_7476559.htm]: https://www.cnblogs.com/code-wangjun/p/7476559.html
[https_www.cnblogs.com_lidabo_p_7852033.html]: https://www.cnblogs.com/lidabo/p/7852033.html
[https_blog.csdn.net_fengbingchun_article_details_73521630]: https://blog.csdn.net/fengbingchun/article/details/73521630
[https_blog.csdn.net_godqiao_article_details_81088860]: https://blog.csdn.net/godqiao/article/details/81088860
[https_blog.csdn.net_krais_wk_article_details_81095899]: https://blog.csdn.net/krais_wk/article/details/81095899
[http_www.cplusplus.com_reference_mutex]: http://www.cplusplus.com/reference/mutex/
[http_c.biancheng.net_view_1436.html]: http://c.biancheng.net/view/1436.html
[http_c.biancheng.net_stl]: http://c.biancheng.net/stl/
[20160417222951238.png]: /images/20220202/f00ce19c8333451388949c6093eedfc5.png
[https_blog.csdn.net_wengchen123_article_details_78373000]: https://blog.csdn.net/wengchen123/article/details/78373000
[https_blog.csdn.net_wonitawonitawonita_article_details_79924068]: https://blog.csdn.net/wonitawonitawonita/article/details/79924068
[https_www.ibm.com_developerworks_cn_aix_library_1307_lisl_c11]: https://www.ibm.com/developerworks/cn/aix/library/1307_lisl_c11/
[https_blog.csdn.net_u013146882_article_details_72350873]: https://blog.csdn.net/u013146882/article/details/72350873
[20180329140709850]: /images/20220202/c9c6afebdc964426b0f923af8c6c1ce0.png
[https_blog.csdn.net_weixin_43795395_article_details_89554031]: https://blog.csdn.net/weixin_43795395/article/details/89554031
[https_blog.csdn.net_weixin_43795395_article_details_89399874]: https://blog.csdn.net/weixin_43795395/article/details/89399874
[https_blog.csdn.net_m0_37973607_article_details_86290964]: https://blog.csdn.net/m0_37973607/article/details/86290964
[805461-20160514164458359-1600906940.png]: /images/20220202/3e4ce75e53024277bfecd81421f73680.png
[https_blog.csdn.net_likika2012_article_details_39619687]: https://blog.csdn.net/likika2012/article/details/39619687
[1353732091_4225.jpg]: https://img-my.csdn.net/uploads/201211/24/1353732091_4225.jpg
[1353405921_3066.jpg]: https://img-my.csdn.net/uploads/201211/20/1353405921_3066.jpg
[Link 1]: http://zh.wikipedia.org/zh/%E6%96%B9%E5%B7%AE
[1353735462_4522.jpg]: https://img-my.csdn.net/uploads/201211/24/1353735462_4522.jpg
[1353406276_4095.jpg]: https://img-my.csdn.net/uploads/201211/20/1353406276_4095.jpg
[1353404648_2086.jpg]: https://img-my.csdn.net/uploads/201211/20/1353404648_2086.jpg
[1353730694_8941.gif]: https://img-my.csdn.net/uploads/201211/24/1353730694_8941.gif
[872539-20161104194812346-1641453195.png]: /images/20220202/ed5772eb1b0a4dacae8b3cc710973b76.png
[image]: /images/20220202/6fd22efe563f40a89b375f5c27a17d29.png
[image 1]: /images/20220202/3e503dc7af094238acac1ee421e840fe.png
[https_www.cnblogs.com_errornull_p_9790444.html]: https://www.cnblogs.com/errornull/p/9790444.html
[https_blog.csdn.net_qq_35181209_article_details_74503362]: https://blog.csdn.net/qq_35181209/article/details/74503362
[https_blog.csdn.net_chen134225_article_details_83106569]: https://blog.csdn.net/chen134225/article/details/83106569
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc5NTM5NQ_size_16_color_FFFFFF_t_70]: /images/20220202/4a9cc9fcd81443349b4ab54d4bdf202e.png
[20190514202538815.png]: /images/20220202/1fc7a5229a94479688f51903be199de9.png