《剑指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)