剑指 Offer 学习笔记

工具

网页版微信读书 + Github 题目列表

笔记

面试

能够单元测试。通常面试官出的题目都是要求写函数解决某一问题,如果应聘者能够在定义函数之后,立即对该函数进行全面的单元测试,那就相当于向面试官证明了自己有着专业的软件开发经验。如果应聘者是先写单元测试用例,再写解决问题的函数,我相信面试官定会对你刮目相看,因为能做到测试在前、开发在后的程序员实在是太稀缺了,他会毫不犹豫地抛出绿色的橄榄枝。

基础知识:

  • 编程语言:C++举例。如果写的函数需要传入一个指针,面试官可能会问是否需要为该指针加上 const,把 const 加在指针不同的位置是否有区别;如果写的函数需要传入的参数是一个复杂类型的实例,面试官可能会问传入值参数和传入引用参数有什么区别,什么时候需要为传入的引用参数加上。
  • 数据结构:事先对链表的插入和删除结点了如指掌,对二叉树的各种遍历方法的循环和递归写法都烂熟于胸
  • 算法:各种查找和排序算法的基础上,重点掌握二分查找、归并排序和快速排序

面试官除了希望应聘者的代码能够完成基本的功能之外,还会关注应聘者是否考虑了边界条件、特殊输入(比如NULL 指针,空字符串等)及错误处理。

提问环节:

面试官让应聘者问几个问题,主要是想了解他最关心的问题有哪些,因此应聘者至少要问一两个问题,否则面试官就会觉得你对我们公司、职位等都不感兴趣。

编程语言

《Effective C++》。这本书很适合在面试之前突击C++。这本书列举了使用C++经常出现的问题及解决这些问题的技巧。该书中提到的问题也是面试官很喜欢问的问题。

数据结构

在C/C++中,当数组作为函数的参数进行传递时,数组就自动退化为同类型的指针。因此尽管函数GetSize的参数data被声明为数组,但它会退化为指针,size3的结果仍然是4。

为了节省内存,C/C++把常量字符串放到单独的一个内存区域。当几个指针赋值给相同的常量字符串时,它们实际上会指向相同的内存地址。但用常量内存初始化数组,情况却有所不同。

题4:替换空格

注意要将字符串的结束符 \0 复制过去,否则得到的字符串结尾会多出一个空格。

1
2
char *num = new char[n+1];
num[n]='\0';

链表

我们要特别注意函数的第一个参数 pHead 是一个指向指针的指针。当我们往一个空链表中插入一个结点时,新插入的结点就是链表的头指针。由于此时会改动头指针,因此必须把 pHead 参数设为指向指针的指针,否则出了这个函数pHead仍然是一个空指针。

题5:从尾到头打印链表

当链表非常长的时候,就会导致函数调用的层级很深,从而有可能导致函数调用栈溢出。用栈基于循环实现的代码的鲁棒性要好一些。

题6:重建二叉树

如果两个指针指向同一个数组,它们就可以相减,其结果为两个指针之间的元素数目

vector 的 end() 指向最后一个元素的后一个元素,assign 方法为前闭后开,v2.assign(v1.begin(),v1.end())

题7:两个栈实现队列

stack.pop() 不返回栈顶元素,需要先用 stack.top() 获取。

查找和排序

面试官会经常要求应聘者比较插入排序、冒泡排序、归并排序、快速排序等不同算法的优劣。强烈建议应聘者在准备面试的时候,一定要对各种排序算法的特点烂熟于胸,能够从额外空间消耗、平均时间复杂度和最差时间复杂度等方面去比较它们的优缺点。

题10:二进制中1的个数

把一个整数减去1,再和原整数做与运算,会把该整数最右边一个1变成0。那么一个整数的二进制表示中有多少个1,就可以进行多少次这样的操作

效率更高:用右移运算符代替了除以2,用位与运算符代替了求余运算符(%)来判断一个数是奇数还是偶数

题40:数组中只出现一次的数字

使用异或,用异或结果中不为1的位来将原数组分成两部分

异常处理

超出long long 能够表示的范围,大数问题,需要特殊的数据结构来表示数字,比如用字符串或者数组来表示大的数字,以确保不会溢出。

确保能够正确转换最大的正整数和最小的负整数。

在判断底数base是不是等于0时,不能直接写base==0,这是因为在计算机内表示小数时(包括float和double型小数)都有误差。判断两个小数是否相等,只能判断它们之差的绝对值是不是在一个很小的范围内。如果两个数相差很小,就可以认为它们相等。这就是我们定义函数equal的原因。

1
(num1-num2>-0.000000001) && (num1-num2<0.000000001)

链表

删除节点O(1)方法:把下一个结点的内容复制到需要删除的结点上覆盖原有的内容,再把下一个结点删除。如果要删除的结点位于链表的尾部,那么它就没有下一个结点,怎么办?我们仍然从链表的头结点开始,顺序遍历得到该结点的前序结点,并完成删除操作。如果链表中只有一个结点,而我们又要删除链表的头结点(也是尾结点),此时我们在删除结点之后,还需要把链表的头结点设置为NULL。

new/delete、new[]/delete[] 要配套使用。delete一个指针之后,只是回收指针指向位置的空间,而指针本身的值不变(也就是说还是指向那个地址的)。你需要手工将其赋值为NULL。

1
2
int *pia = new int[10];
delete []pia;

解题常用方法:定义两个指针,(求中间节点、环形链表)一个指针一次走一步,另一个指针一次走两步。(求倒数第k个)一个指针先走k-1步;

指针

指针(*)、取地址 (&)、解引用(*)与引用(&)。 定义指针时与使用时的*意义不同。

int *p,p 是指向的地址,&p 是自己的地址,*p 是指向的地址里的值。指针的指针,解引用就是指向的指针的值(指向的指针的指向地址)

int *p定义了一个指向int类型指针p(我们使用*符号把p声明为指针),并初始化p使其指向int类型的变量num,这里&num中的&是取地址操作符,当&作用于一个对象上时,它返回了该对象的地址。

*p = 100 这里的 *操作符为解引用操作符,它返回指针p所指的对象(左值)。

作用在引用上的所有操作事实上都是作用在该引用所绑定的对象上。在传参的时候,使用指针传参,编译器需要给指针另行分配存储单元,存储一个该指针的副本,在函数中对这个副本进行操作;而使用引用传参,编译器就不需要分配存储空间和保存副本了,函数将直接对实参进行操作。所以使用引用使得程序的运行速度更快,执行效率更高。

题26:复杂链表的复制

创建一遍结点并接到原结点的后面

空间时间

C/C++程序员要养成采用引用(或指针)传递复杂类型参数的习惯。如果采用值传递的方式,从形参到实参会产生一次复制操作。这样的复制是多余的操作,我们应该尽量避免

题29:数组中出现次数超过一半的数字 / 题30:最小的k个数

两个题目类似,O(n):基于 Partition 函数来解决。基于数组的第 k 个数字来调整,使得比第k 个数字小的所有数字都位于数组的左边,比第k个数字大的所有数字都位于数组的右边。

O(nlogk):考虑面向海量数据的情况,题30可用红黑树来维护k个数字,进行插入、删除最大值操作

1
multiset<int,greater<int>>::reverse_iterator it; //greater从大到小排列,倒序遍历(rbegin(),rend())

Partition 函数

TODO: 2.4.1 节

sort 函数

1
sort(str.begin(),str.end(),comp); // return a > b 是降序

comp 函数定义在类内需要声明为 static,定义在类外则不需要;https://taifua.com/cpp-sort-problem.html

类的静态成员(变量和方法)属于类本身,在类加载的时候就会分配内存,可以通过类名直接去访问;非静态成员(变量和方法)属于类的对象,所以只有在类的对象产生(创建类的实例)时才会分配内存,然后通过类的对象(实例)去访问。静态成员函数不接受隐含的this自变量。所以,它就无法访问自己类的非静态成员。

哈希表

如果需要判断多个字符是不是在某个字符串里出现过或者统计多个字符在某个字符串中出现的次数,我们可以考虑基于数组创建一个简单的哈希表。这样可以用很小的空间消耗换来时间效率的提升。

C++的STL中,set、multiset、map、multimap等数据结构都是基于红黑树实现的。

前序、中序、后序的递归、循环写法,较多题目会用到

Leetcode

9. Palindrome Number

注意 int 范围,正序不超过时倒序可能超出

只需要比较到一半数字即可,也不会超出interger

-2147483648 ~ +2147483647 (4 Bytes)

单引号和双引号区别

‘a’表示是一个字符,”a”表示一个字符串相当于’a’+’\0’;

Switch 函数

switch 中仅支持 int 或者 char 等(必须是一个整型或枚举类型,或者是一个 class 类型,其中 class 有一个单一的转换函数将其转换为整型或枚举类型。)

0%