《剑指offer学习笔记-第二章：面试需要的基础知识》

面试题对应的答案在我的文章https://mp.****.net/mdeditor/87880918#，答案都是自己编写并通过编译的，可能不是最优的解法，后面慢慢优化。

2.2 编程语言
面试过程中面试官要么直接问语言语法，要么让应聘者编写代码解决一个问题，以此判断对语言掌握程度。
（1） C++
通常语言面试有三种类型：
a. 直接问对C++概念的理解，如对关键字的理解。
b. 面试官拿出准备好的代码，让你分析代码运行结果。
c. 要求写一个类型或者实现类型中的一个成员函数。
（2） C#
略

2.3 数据结构
大多数面试题围绕数组、字符串、链表、树、栈、队列这些常见数据结构展开。

（1） 数组
数组占据一块连续的内存并按照顺序储存数据，由于它的内存连续，可以在O(1)时间读写任何元素，可以用来实现简单的哈希表。它的缺点是空间效率不高，常有空闲区域，vector解决了这个问题。
数组和指针是两个相关联又有区别的两个概念，数组名也是一个指向数组首元素的指针，可以通过指针访问数组。
在32位系统对任意指针求sizeof，结果都是4。当数组做函数参数传递时，数组退化为同类型的指针。

**面试题3：**在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。
例如，如果输入长度为7的数组{2,3,1,0,2,5,3}，那么对应的输出是第一个重复的数字2。

思路：
a.先把数组排序（排序长度为n的数组需要O(nlogn)的时间），再遍历一遍数组就可找出是否有重复数字。
b.从头到尾扫描数组，同时将数字存入哈希表，当存入数字时可以判断该哈希表是否已包含了该数字，时间复杂度为O(n),但需要一个大小为O(n)的哈希表，当数组中出现较大的数字时，会浪费很多空间。
c. 从头到尾扫描数组，当扫到下表为i的数字m，首先比较该数字m是否等于i,如果是则扫描下一个数字
增加题目要求：不能修改数组找出重复的数字。
思路：
a.创建一个辅助数组，再根据原数组元素值移到对应下标处，同时判断对应下标是否已经有值，该方案需要O(n)的辅助空间。

b.对数组中的数进行二分查找，比如数组长度为8，就查数组中1-4的个数，超过4个说明有重复数字，否则重复数字在5-8中，然后继续二分查找剩余的数，直到查到最后两个数中的一个。

**面试题4：**在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

思路：从数组右上角开始，当前数字和查找数相等则返回true并退出，大于查找数列号减一，小于查找数行号加1，超出边界值返回false并退出。

图来自（https://blog.****.net/qq_38277033/article/details/81127816）

（2） 字符串
字符串是由若干字符组成的序列，C/C++中每个字符串都以字符‘\0’结尾，这样就能方便找到尾部，因此每个字符串都会多一个字符，需要注意字符串越界，如：

char str[3];
strcopy(str,”abc”);//实际字符串“abc”大小为4

为了节省内存，C/C++把常量字符串放到单独的一个内存区域，当指针赋值给相同的常量字符串时，它们会指向同一内存地址，但用常量内存初始化数组却不同，数组会新分配空间然后将字符串内容复制过去，所以地址会不同。

面试题5：请实现一个函数，将一个字符串中的每个空格替换成“%20”。例如，当字符串为We Are
Happy.则经过替换之后的字符串为We%20Are%20Happy。

思路：首先应该考虑到替换空格之后整个字符串会变长，然后考虑题目对时间复杂度和空间复杂度的要求。先遍历一次字符串，统计出字符串中空格数，推算出替换后字符串总长度。从字符串的后面开始复制和替换，准备两个指针，P1指向原始字符串末尾，P2指向替换后的字符串的头部，然后将原始字符串从尾部开始往后移动，遇到空格则替换，直到P1=P2,此时空格已替换完。
（3）