剑指offer | 认识面试
“老实说，《剑指offer》我是最近才开始看的，觉得晚了。为什么怎么说呢，因为千羽之前遇到很多面试，发现面试官问的问题大部分是从这里出来的。推荐刚入职的小伙伴都看一下这本书
面试这东西，第一印象很重要，你前面答的好，后面的问题就问的少，如果你回答的含糊不清，后面就会问的多。具体可以看这篇文章《我踩坑了》
“Github: https://github.com/nateshao/leetcode/blob/main/algo-notes/src/main/java/com/nateshao/sword_offer/topic_00/ListNode.java
面试这东西
有的的员工中有面试发挥很好但工作平平的，也有面试一般但工作优秀的。对于追求职业发展的人来说，通过面试只是迈过一一个门槛而不是目的，真正的较量是在入职后的成长。就像学钓鱼，你可能在有经验的垂钓者的指导下能钓到几条鱼，但如果没有学到垂钓的真谛，离开了指导者你可能就很难钓到很多鱼。我希望读这本书的朋友不要只学一些技巧来对付面试，而是通过学习如何解决面试中的难题来提高自己的编程和解决问题的能力，进而提高自信心，在职场中能迅速成长。
一、面试官谈面试（了解）
““对于初级程序员，我一般会偏向考查算法和数据结构，看应聘者的基本功;对于高级程序员，我会多关注专业技能和项目经验。何幸杰(SAP, 高级工程师)
““应聘者要事先做好准备，对公司近况、项目情况有所了解，对所应聘的工作真的很有热情。另外，应聘者还要准备好合适的问题问面试官。” 韩伟东(盛大，高级研究员)
““应聘者在面试过程首先需要放松，不要过于紧张，这有助于后面解决问题时开拓思路。其次不要急于编写代码，应该先了解清楚所要解决的问题。这时候最好先和面试官多做沟通，然后开始做一些整体的设计和规划，这有助于编写高质量和高可读性的代码。写完代码后不要马上交，最好自己review并借助一些测试用例来走几遍代码，找出可!能出现的错误。” 尧敏(淘宝，资深经理)
““‘神马’ 都是浮云，应聘技术岗位就是要踏实写程序。田超(微软，SDE II)
1.1 面试的三种形式
注意：
- 他的口型，这对应聘者的听力提出了更高的要求。如果应聘者在面试的时候没有听清楚或者听懂面试官的问题，千万不要不懂装懂、答非所问，这是面试的大忌。当不确定面试官的问题的时候，应聘者--定要大胆地向面试官多提问，直到弄清楚面试官的意图为止。
- 思考清楚再开始编码、良好的代码命名和缩进对齐习惯、能够单元测试。
- 现场面试
- 规划好路线并且估算时间
- 准备好得体的衣服（男生有领子的衣服）
- 注意面试邀请里的面试流程
- 准备几个问题
1.2 面试的三个环节
通常面试官会把每一轮面试分为三个环节(如图下图 所示):
- 首先是行为面试，面试官参照简历了解应聘者的过往经验;
- 然后是技术面试，这一环节很有可能会要求应聘者现场写代码;
- 最后一个环节是应聘者问几个自己最感兴趣的问题。
1.2.1 行为面试环节
面试开始的5~10分钟通常是行为面试的时间。在行为面试这个环节里，面试官会注意应聘者的性格特点，深入地了解简历中列举的项目经历。由于这一环节一般不会 问技术难题，因此也是一个暖场的过程，应聘者可以利用这几分钟时间调整自己的情绪，进入面试的状态。
不少面试官会让应聘者做一个简短的自我介绍。由于面试官手中拿着应聘者的简历，而那里有应聘者的详细信息，因此此时的自我介绍不用花很多时间，用30秒到1分钟的时间介绍自己的主要学习、工作经历就即可。 如果面试官对你的某一段经历或者参与的某一个项目很感兴趣，他会有针对性地提几个问题详细了解。
1. 应聘者的项目经验
应聘者自我介绍之后，面试官接着会对照应聘者的简历去详细了解他感兴趣的项目。应聘者在准备简历的时候，建议用如图1.3所示的STAR模型描述自己经历过的每一个项目。
- Situation：简短的项目背景。 比如项目的规模,开发的软件的功能、目标用户等。
- Task：自己完成的任务。 这个要写详细，要让面试官对自己的工作一目了然。在用词上要注意区分**“参与”和“负责”**。如果只是加入某-一个开发团队写了几行代码就用“负责”，那就很危险。面试官看到简历上应聘者“负责”了某个项目，他可能就会问项目的总体框架设计、核心算法、团队合作等问题。这些问题对于只是简单“参与”的人来说，是很难回答的，会让面试官认为你不诚实，印象分会减去很多。
- Action：为了完成任务自己做了哪些工作，是怎么做的。 这里可以详细介绍。做系统设计的，可以介绍系统架构的特点;做软件开发的，可以写基于什么工具在哪个平台下应用了哪些技术;做软件测试的，可以写是手工测试还是自动化测试，是白盒测试还是黑盒测试等。
- Result：Result:自己的贡献。这方面的信息可以写得具体些，最好能用数字加以说明。如果是参与功能开发，可以说按时完成了多少功能;如果做优化，可以说性能提高的百分比是多少:如果是维护，可以说修改了多少个Bug。
举个例子。
笔者用下面一段话介绍自己在微软Winforms项目组的经历: Winforms是微软.NET中的一个成熟的UI平台(Situation)。本人的工作是在添加少量新功能之外主要负责维护已有的功能(Task)。新的功能主要是让Winforms的控件的风格和Vista、Windows 7的风格保持一致。在维护方面，对于较难的问题我用WinDbg 等工具进行调试(Action)。在过去两年中我总共修改了超过200个Bug (Result)。
如果在应聘者的简历中上述4类信息还不够清晰，面试官可能会追问相关的问题。除此之外，面试官针对项目经验最常问的问题还包括如下几个类型:
- 你在该项目中碰到的最大的问题是什么，你是怎么解决的?
- 从这个项目 中你学到了什么?
- 什么时候会和其他团队成员(包括开发人员、测试人员、设计人员、 项目经理等)有什么样的冲突，你们是怎么解决冲突的?
2.应聘者掌握的技能
“不会的东西千万不要写上去！！！
除了应聘者参与过的项目之外，面试官对应聘者掌握的技能也很感兴趣，他有可能针对简历上提到的技能提出问题。和描述项目时要注意“参与”和“负责" 一样，描述技能掌握程度时也要注意“了解”、“熟悉”和“精通”的区别。（简历上不要写精通）
“了解”。指对某一个技术只是上过课或者看过书，但没有做过实际的项目。通常不建议在简历中列出只是肤浅地了解一点的技能，除非这项技术应聘的职位的确需要。比如某学生读本科的时候学过《计算机图形学》这门课程，但一直没有开发过与图形绘制相关的项目,那就只能算是了解。如果他去应聘Autodesk 公司，那他可以在简历上提一下 他了解图形学。Autodesk是-一个 开发三维设计软件的公司，有很多职位或多或少都会与图形学有关系，那么了解图形学的总比完全不了解的要适合一些。但如果他是去应聘Oracle,那就没有必要提这一点了 ,因为开发数据库系统的Oracle公司大部分职位与图形学没有什么关系。
简历中我们描述技能的掌握程度大部分应该是 “熟悉”。如果我们在实际项目中使用某一项技术已经有较长的时间，通过查阅相关的文档可以独立解决大部分问题，我们就熟悉它了。对应届毕业生而言，他毕业设计所用到的技能，可以用 “熟悉” ;对已经工作过的，在项目开发过程中所用到的技能，也可以用“熟悉”。
如果我们对一项技术使用得得心应手， 在项目开发过程中当同学或同事向我们请教这个领域的问题我们都有信心也有能力解决，这个时候我们就可以说自己精通了这项技术。应聘者不要试图在简历中把自己修饰成“高人”而轻易使用“精通”，除非自己能够很轻松地回答这个领域里的绝大多数问题，否则就会适得其反。通常如果应聘者在简历中说自己精通某-项技术，面试官就会对他有很高的期望值，因此会挑-些比较难的问题来问。这也是越装高手就越容易露馅的原因。曾经碰到一个在简历中说自己精通C++的应聘者，连成员变量的初始化顺序这样的问题都被问得一-头雾水，那最终的结果也就可想而知了。
3.回答"为什么跳槽"
在面试已经有工作经验的应聘者的时候，面试官总喜欢问为什么打算跳槽。每个人都有自己的跳槽动机和原因，因此面试官也不会期待一个标准答案。面试官只是想通过这个问题来了解应聘者的性格，因此应聘者可以大胆地根据自己的真实想法来回答这个问题。但是，应聘者也不要想说什么就说什么，以免给面试官留下负面的印象。
在回答这个问题时不要抱怨，也不要流露出负面的情绪。 负面的情绪通常是能够传染的，当应聘者总是在抱怨的时候，面试官就会担心如果把他招进来的话他将成为团队负面情绪的传染源，从而影响整个团队的士气。应聘者应尽量避免以下4个原因:
- 老板太苛刻。 如果面试官就是当前招聘的职位的老板，他听到应聘者抱怨现在的老板苛刻时,他肯定会想要是把这个人招进来,接下来他就会抱怨我也苛刻了。
- 同事太难相处。 如果应聘者说他周围有很多很难相处的同事,面试官很有可能会觉得这个人他本身就很难相处。
- 加班太频繁。 对于大部分It企业来说，加班是家常便饭。如果正在面试的公司也需要经常加班,那等于应聘者说他不想进这家公司。
- 工资太低。 现在的工资太低的确是大部分人跳槽的真实原因，但不建议在面试的时候对面试官抱怨。面试的目的是拿到offer, 我们要尽量给面试官留下好印象。现在假设你是面试官，有两个人来面试: 一个人一开口就说现在工资太低了，希望新工作能加多少多少工资;另一个说我只管努力干活，工资公司看着给，相信公司不会亏待勤奋的员工。你更喜欢哪个?这里不是说工资不重要,但我们要清楚面试不是谈工资的时候。等完成技术面试之后谈offer 的时候，再和HR谈工资也不迟。通过面试之后我们就掌握主动了，想怎么谈就怎么谈，如果工资真的开高了HR会和你很客气地商量。
笔者在面试的时候，通常给出的答案是**:现在的工作做了一段时间，已经没有太多的激情了，因此希望寻找一份更有挑战的工作。然后具体论述为什么有些厌倦现在的职位，以及面试的职位我为什么会有兴趣。**笔者自己跳过两次槽，第一次从Autodesk跳槽到微软，第二次从微软跳槽到现在的思科。从面试的结果来看，这样的回答都让面试官很满意，最终也都拿到了offer.当时在微软面试被问到为什么要跳槽时,笔者的回答是:我在Autodesk开发的软件Civil 3D是一款面向土木行业的设计软件。如果我想在现在的职位上得到提升，就必须加强士木行业的学习，可我对诸如计算土方量、道路设计等没有太多兴趣，因此出来寻找机会。在微软工作两年半之后去思科面试的时候，
笔者的回答是:我在微软的主要工作是开发和维护.NET的UI平台Winforms.由于Winforms已经非常成熟，不需要添加多少新功能，因此我的大部分工作都是维护和修改BUG。两年下来，调试的能力得到了很大的提高，但长期如此自己的软件开发和设计能力将不能得到提高，因此想出来寻找可以设计和开发系统的职位。同时，我在过去几年里的工作都是开发桌面软件，对网络了解甚少，因此希望下一个工作能与网络相关。众所周知，思科是个网络公司，这里的软件和系统或多或少都离不开网络，因此我对思科的职位很感兴趣。
1.3.2 技术面试环节
面试官在通过简历及行为面试大致了解应聘者的背景之后，接下来就要开始技术面试了。一轮1小时的面试，通常技术面试会占据40~50分钟。这是面试的重头戏，对面试的结果起决定性作用。虽然不同公司里不同面试官的背景、性格各不相同，但总体来说他们都会关注应聘者5种素质:
- 扎实的基础知识、
- 能写高质量的代码、
- 分析问题时思路清晰、
- 能优化时间效率和空间效率，
- 以及学习沟通等各方面的能力(如图所示)。
应聘者在面试之前需要做足准备，对编程语言、数据结构和算法等基础知识有全面的了解。面试的时候如果遇到简单的问题，应聘者一定要注重细节，写出完整、鲁棒的代码。如果遇到复杂的问题，应聘者可以 通过画图、举具体例子分析和分解复杂问题等方法先理清思路再动手编程。 除此之外，应聘者还应该不断优化时间效率和空间效率，力求找到最优的解法。在面试过程中，应聘者还应该主动提问，以弄清楚题目的要求，表现自己的沟通能力。当面试官前后问的两个问题有相关性的时候，尽量把解决前面问题的思路迁移到后面的问题中去，展示自己良好的学习能力。如果能做到这么几点，那么通过面试获得心仪的职位将是水到渠成的事情。
1.扎实的基础知识
扎实的基本功是成为优秀程序员的前提条件，因此面试官首要关注的应聘者素质就是是否具备扎实的基础知识。通常基本功在编程面试环节体现在3个方面:编程语言、数据结构和算法。
**首先，每个程序员至少要掌握一两门编程语言。**面试官从应聘者在面试过程中写的代码及跟进的提问中，能看出其编程语言掌握的熟练程度。以大部分公司面试要求的C++举例。如果写的函数需要传入一个指针，面试官可能会问是否需要为该指针加上const,把const加在指针不同的位置是否有区别;如果写的函数需要传入的参数是一个复杂类型的实例，面试官可能会问传入值参数和传入引用参数有什么区别，什么时候需要为传入的引用参数加上const.
**其次，数据结构通常是编程面试过程中考查的重点。**在参加面试之前，应聘者需要熟练掌握链表、树、栈、队列和哈希表等数据结构，以及它们的操作。如果我们留意各大公司的面试题，就会发现链表和二叉树相关的问题是很多面试官喜欢问的问题。这方面的问题看似比较简单，但要真正掌握也不容易，特别适合在这么短的面试时间内检验应聘者的基本功。如果应聘者事先对链表的插入和删除结点了如指掌，对二叉树的各种遍历方法的循环和递归写法都烂熟于胸，那么真正到了面试的时候也就游刃有余了。
最后，大部分公司都会注重考查查找、排序等算法。 应聘者可以在了解各种查找和排序算法的基础上，重点掌握二分查找、归并排序和快速排序 ，因为很多面试题都只是这些算法的变体而己。比如面试题8“旋转数组的最小数字”和面试题38“数字在排序数组中出现的次数”的本质是考查二分查找，而面试题36“数组中的逆序对”实际上是考查归并排序。少数对算法很重视的公司比如谷歌或者百度，还会要求应聘者熟练掌握动态规划和贪婪算法。如果应聘者对动态规划算法很熟悉，那么他就能很轻松地解决面试题31 "连续子数组的最大和”。
2，高质量的代码
只有注重质量的程序员，才能写出鲁棒稳定的大型软件。在面试过程中，面试官总会格外关注边界条件、特殊输入等看似细枝末节但实质至关重要的地方，以考查应聘者是否注重代码质量。很多时候，面试官发现应聘者写出来的代码只能完成最基本的功能，一旦输入特殊的边界条件参数就会错误百出甚至程序崩溃。
通常越是简单的问题，面试官的期望值就会越高。如果题目很简单，面试官就会期待应聘者能够很完整地解决问题，除了完成基本功能之外,还要考虑到边界条件、错误处理等各个方面。比如这道题，面试官不仅仅是期待你能完成把字符串转换成整数这个最起码的要求，而且希望你能考虑到各种特殊的输入。面试官至少会期待应聘者能够在不需要提示的情况下，考虑到输入的字符串中有非数字字符和正负号，要考虑到最大的正整数和最小的负整数以及溢出。同时面试官还期待应聘者能够考虑到当输入的字符串不能转换成整数时，应该如何做错误处理。当把这个问题的方方面面都考虑到的时候，我们就不会再认为这道题简单了。
除了问题考虑不全面之外，还有一个面试官不能容忍的错误就是程序不够鲁棒。以前面的那段代码为例，只要输入-一个空指针，程序立即崩溃。这样的代码如果加入到软件当中，将是灾难。因此当面试官看到代码中对空指针没有判断并加以特殊处理的时候，通常他连往下看的兴趣都没有。
要想很好地解决前面的问题，最好的办法是在动手写代码之后想好测试用例。只有把各种可能的输入事先都想好了，才能在写代码的时候把各种情况都做相应的处理。写完代码之后，也不要立刻给面试官检查，而是先在心里默默地运行。 当输入之前想好的所有测试用例都能得到合理的输出时，再把代码交给面试官。做到了这一步，通过面试拿到Offer就是顺理成章的事情了。
3.清晰的思路
“有的算法，你手写不了，但是你思路得有。所以，好的思路是最重要的。
只有思路清晰，应聘者才有可能在面试过程中解决复杂的问题。有些时候面试官会有意出一些比较复杂的问题,以考查应聘者能否在短时间内形成清晰的思路并解决问题。对于确实很复杂的问题，面试官甚至不期待应聘者能在面试不到一个小时的时间里给出完整的答案,他更看重的可能还是应聘者是否有清晰的思路。面试官通常不喜欢应聘者在没有形成清晰思路之前就草率地开始写代码，这样写出来的代码容易逻辑混乱、错误百出。
应聘者可以用几个简单的方法帮助自己形成清晰的思路。首先是举几个简单的具体例子让自己理解问题。当我们一眼看不出问题中隐藏的规律的时候，可以试着用一两个具体的例子模拟操作的过程，这样说不定就能通过具体的例子找到抽象的规律。其次可以试着用图形表示抽象的数据结构。像分析与链表、二叉树相关的题目，我们都可以画出它们的结构来简化题目。最后可以试着把复杂的问题分解成若千个简单的子问题，再一 一解决。很多基于递归的思路，包括分治法和动态规划，都是把复杂的问题分解成-一个或者多个简单的子问题。
比如把二叉搜索树转换成排序的双向链表这个问题就很复杂。遇到这个问题，我们不妨先画出一两个具体的二叉搜索树，直观地感受二叉搜索树和排序的双向链表有哪些联系。如果一下 子找不出转换的规律，我们可以把整个二叉树看成3个部分:根结点、左子树和右子树。当我们递归地把转换左右子树这两个子问题解决之后，再把转换左右子树得到的链表和根结点链接起来，整个问题也就解决了
4.优化效率的能力
优秀的程序员对时间和内存的消耗锱铢必较，他们很有激情地不断优化自己的代码。当面试官出的题目有多种解法的时候，通常他会期待应聘者最终能够找到最优解。当面试官提示还有更好的解法的时候，应聘者不能放弃思考，而应该努力寻找在时间消耗或者空间消耗上可以优化的地方。
要想优化时间或者空间效率，首先要知道如何分析效率。即使是同一个算法，用不同方法实现的效率可能也会大不相同，我们要能够分析出算法及其代码实现的效率。例如求斐波那契数列，很多人喜欢用递归公式f(n)=f(n-1)+f(n- -2)求解。如果分析它的递归调用树，我们就会发现有大量的计算是重复的，时间复杂度以n的指数增加。但如果我们先求f(1)、f(2),再根据f(1)和f(2)求出f(3),接下来根据f(2)、f(3)求出f(4),并以此类推用一个循环求出f(n),这种计算方法的时间效率就只有O(n),比前面递归的方法要好得多。
要想优化代码的效率，我们还要熟知各种数据结构的优缺点，并能选择合适的数据结构解决问题。我们在数组中根据下标可以用0(1)时间完成查找。数组的这个特征可以用来实现简单的哈希表解决很多问题，比如面试题35“第一个只出现一次的字符”。为了解决面试题30“最小的k个数”，我们需要一个数据容器来存储k个数字。在这个数据容器中，我们希望能够快速地找到最大值并且能快速地替换其中的数字。经过权衡，我们发现二叉树比如最大堆或者红黑树都是实现这个数据容器的不错选择。
要想优化代码的效率，我们也要熟练掌握常用的算法。面试中最常用的算法是查找和排序。如果从头到尾顺序扫描一个数组，我们需要O(n)时间才能完成查找操作。但如果数组是排序的，应用二分查找算法就能把时间才能完成查找操作。但如果数组是排序的，应用二分查找算法就能把时间复杂度降低到O(logn) (如面试题8“旋转数组的最小值"和面试题38“数字在排序数组中出现的次数”)。排序算法除了能够给数组排序之外，还能用来解决其他问题。比如快速排序算法中的Partition 函数能够用来在n个数里查找第k大的数字，从而解决面试题29“数组中出现次数超过一半的数字”和面试题30“最小的k个数”。归并排序算法能够实现在O(nlogn)时间统计n个数字中的逆序对数目(面试题36“数组中的逆序对”)。
5.优秀的综合能力
在面试过程中，应聘者除了展示自己的编程能力和技术功底之外，还需要展示自己的软技能(Soft Skills),诸如自己的沟通能力和学习能力。随着软件系统的规模越来越大，软件开发已经告别了单打独斗的年代，程序员与他人的沟通变得越来越重要。在面试过程中，面试官会观察应聘者在介绍项目经验或者算法思路时是否观点明确、逻辑清晰，并以此判断其沟通能力的强弱。另外，面试官也会从应聘者说话的神态和语气来判断他是否有团队合作的意识。通常面试官不会喜欢高傲或者轻视合作者的人。
IT行业知识更新很快，因此程序员只有具备很好的学习能力才能跟上知识更替的步伐。通常面试官有两种办法考查应聘者的学习能力。面试官的第一-种方法 是询问应聘者最近在看什么书、从中学到了哪些新技术。面试官可以用这个问题了解应聘者的学习愿望和学习能力。面试官的第二种方法是抛出一个新概念，接下来他会观察应聘者能不能在较短时间内理解这个新概念并解决相关的问题。比如面试官要求应聘者计算第1500个丑数。很多人都没有听说过丑数这个概念。这个时候面试官就会观察应聘者面对丑数这个新概念时，能不能经过提问、思考、再提问的过程，最终找出丑数的规律从而找到解决方案(详见面试题34“丑数”)。
1.3.3 应聘者提问环节
在结束面试前的5到10分钟，面试官会给应聘者机会问几个问题，应聘者的问题的质量对面试的结果也有一定的影响。有些人的沟通能力很强，马上就能想到有意思的问题。但对于大多数人而言，在经受了面试官将近一小时的拷问之后可能已经精疲力竭，再迅速想出几个问题难度很大。因此建议应聘者不妨在面试之前做些功课，为每一轮面试准备2~3个问题，这样到提问环节的时候就游刃有余了。
面试官让应聘者问几个问题，主要是想了解他最关心的问题有哪些，因此应聘者至少要问一“两个问题， 否则面试官就会觉得你对我们公司、职位等都不感兴趣，那你来面试做什么?但是也不是什么问题都可以在这个时候问。如果问题问得比较合适，对应聘者来说是个加分的好机会;但如果问的问题不太合适，面试官对他的印象就会大打折扣。
有些问题是不适合在技术面试这个环节里问的。首先是不要问和自己的职位没有关系的问题，比如问“公司未来五年的发展战略是什么”。如果应聘的职位是CTO,而面试官是CEO，这倒是个合适的问题。如果应聘的只是在一线开发的职位，那这个问题离我们就太远了，与我们的切身利益没有多少关系。另外，坐在对面的面试官很有可能也只是-一个在一线开发的程序员，他该怎么回答这个关系公司发展战略的问题呢?
其次是不要问薪水。 技术面试不是谈薪水的时候，要谈工资要等通过面试之后和HR谈。而且让面试官觉得你最关心的问题就是薪水，给面试官留下的印象也不好。再次是不要立即打听面试结果，比如问“您觉得我能拿到Offer吗”之类的问题。现在大部分公司的面试都有好几轮，最终决定应聘者能不能通过面试，是要把所有面试官的评价综合起来的。问这个问题相当于白问，因为问了面试官也不可能告诉应聘者结果，还会让面试官觉得他没有自我评估的能力。
最后推荐问的问题是与招聘的职位或者项目相关的问题。 如果这种类型的问题问得很到位，那么面试官就会觉得你对应聘的职位很有兴趣。不过要问好这种类型的问题也不容易，因为首先对应聘的职位或者项目的背景要有一定的了解。我们可以从两方面去了解相关的信息:一是面试前做足功课，到网上去收集一些相关的信息，做到对公司成立时间、主要业务、职位要求等都了然于胸;二是面试过程中留心面试官说过的话。有不少面试官在面试之前会简单介绍与招聘职位相关的项目，其中会包含其他渠道 无法得到的信息，比如项目进展情况等。应聘者可以从中找出一两个点，然后向面试官提问。
《剑指offer》刷题笔记
定义链表
“Github:https://github.com/nateshao/leetcode/blob/main/algo-notes/src/main/java/com/nateshao/sword_offer/topic_00/ListNode.java
public class ListNode {
int val; // 数据
ListNode next; //下一个节点
ListNode before;
public ListNode(){ //创建一个无参数构造方法，用于初始化
}
ListNode(int val) { // 创建一个有参数构造方法，便于给结点传数据
this.val = val;
}
}
定义二叉树
public class TreeNode {
int val;
TreeNode left; // 左孩子
TreeNode right; // 右孩子
TreeNode(int x) {
val = x;
}
}
《剑指offer》面试题1：赋值运算符函数 P13
“题目: 如下为类型CMyString的声明，请为该类型添加赋值运算符函数。
思路：
- 将返回值类型声明为该类型的引用
- 把传入的参数类型声明为常量引用
- 释放实例自身已有的内存
- 判断传入的参数和当前的实例是不是同一个实例
class CMyString
{
public:
CMyString(char* pData = NULL) { m_pData = pData; }
CMyString(const CMyString& str);
CMyString& operator=(const CMyString& str);
~CMyString() {}
private:
char* m_pData;
};
当面试官要求应聘者定义一个赋值运算符函数时,他会在检查应聘者写出的代码时关注如下几点:
- 是否把返回值的类型声明为该类型的引用,并在函数结束前返回实例自身的引用(即*this)。只有返回一个引用,才可以允许连续赋值。否则如果函数的返回值是void,应用该赋值运算符将不能做连续赋值。假设有3个CMyString的对象: str1、 str2和str3,在程序中语句strl=str2=str3将不能通过编译。
- 是否把传入的参数的类型声明为常量引用。如果传入的参数不是引用而是实例,那么从形参到实参会调用一次拷贝构造函数。把参数声明为引用可以避免这样的无谓消耗,能提高代码的效率。同时,我们在赋值运算符函数内不会改变传入的实例的状态,因此应该为传入的引用参数加上const关键字。
- 是否释放实例自身已有的内存。如果我们忘记在分配新内存之前释放自身已有的空间,程序将出现内存泄露。
- 是否判断传入的参数和当前的实例(*this)是不是同一个实例。如果是同一个,则不进行赋值操作,直接返回。如果事先不判断就进行赋值,那么在释放实例自身的内存的时候就会导致严重的问题:当 *this和传入的参数是同一个实例时,那么一旦释放了自身的内存,传入的参数的内存也同时被释放了,因此再也找不到需要赋值的内容了。
经典的解法，适用于初级程序员
当我们完整地考虑了上述4个方面之后,我们可以写出如下的代码:
//赋值运算函数
CMyString& CMyString::operator=(const CMyString& str)
{
//①检查自赋值
if(this == &str) return *this;
//②释放原有资源
delete [] m_pData;
//③分配新内存资源
m_pData = new char(strlen(str.m_pData) + 1);
strcpy_s(m_pData, strlen(str.m_pData) + 1, str.m_pData);
//④返回本对象的引用
return *this;
}
//注：③过程可能会出现内存不足分配失败，m_pData成为空指针，程序崩溃
这是一般C教材上提供的参考代码。如果接受面试的是应届毕业生或者C++初级程序员,能全面地考虑到前面四点并完整地写出代码,面试官可能会让他通过这轮面试。但如果面试的是C++高级程序员,面试官可能会提出更高的要求。
考虑异常安全性的解法,高级程序员必备
在前面的函数中,我们在分配内存之前先用delete释放了实例mpData的内存。如果此时内存不足导致new char抛出异常, mpData将是一个空指针,这样非常容易导致程序崩溃。也就是说一旦在赋值运算符函数内部抛出一个异常, CMyString的实例不再保持有效的状态,这就违背了异常安全性(Exception Safety)原则。
要想在赋值运算符函数中实现异常安全性,我们有两种方法。一个简单的办法是我们先用new分配新内容再用delete释放已有的内容。这样只在分配内容成功之后再释放原来的内容,也就是当分配内存失败时我们能确保CMyString的实例不会被修改。我们还有一个更好的办法是先创建一个临时实例,再交换临时实例和原来的实例。下面是这种思路的参考代码:
CMyString& CMyString::operator=(const CMyString& str)
{
if (this != &str) //①检查自赋值
{
CMyString tmp(str); //②拷贝构造临时变量
//③交换当前对象与临时对象的数据。
char* p = tmp.m_pData;
tmp.m_pData = this->m_pData;
this->m_pData = p;
}
return *this;
}
在这个函数中,我们先创建一个临时实例tmp,接着把 tnp.mpData和实例自身的m_pData做交换。由于tmp是一个局部变量,但程序运行到if的外面时也就出了该变量的作用域,就会自动调用 tmp的析构函数,把 tmp.m pData所指向的内存释放掉。由于 tmp.m_pData指向的内存就是实例之前mpData的内存,这就相当于自动调用析构函数释放实例的内存。在新的代码中,我们在CMyString的构造函数里用new分配内存。如果由于内存不足抛出诸如bad_alloc等异常,我们还没有修改原来实例的状态,因此实例的状态还是有效的,这也就保证了异常安全性。如果应聘者在面试的时候能够考虑到这个层面,面试官就会觉得他对代码的异常安全性有很深的理解,那么他自然也就能通过这轮面试了。
总结
这篇文章还是有一点水的，不过主要是和大家一起认识一下面试的形式、过程、以及面试官想要的是什么。我们就应该往这方面去准备。而不是一头雾水，像只苍蝇一样乱撞哦。
参考链接：
- https://blog.csdn.net/weixin_43919932/article/details/103016158
革命尚未成功，同志仍需努力，冲冲冲
腾讯云开发者
