大纲

1.扎实的基本功：编程语言（熟练掌握1-2门语言），数据结构（栈，队列，链表，哈希，树），算法；

2.高质量的代码：边界条件，特值输入等易忽略问题，必须注重代码的鲁棒性和稳定性；在写代码之前，想好测试用例，把各种可能的用例都先写出来，再进行相应处理；

3.清晰的思路：复杂问题简单化，举例子模拟操作过程，图像化分析；

4.优化效率的能力：多种方法时应当选择最优解，优化时间和空间效率；

5.优秀的综合能力：学习能力，沟通能力，性格，思维发散能力，抽象建模能力；

基础知识

编程语言知识

设计模式

数据结构

数组：C/C++中，数组作为参数传递时会退化为同类型指针；

            面试题3.数组中的重复数组  https://leetcode-cn.com/problems/shu-zu-zhong-zhong-fu-de-shu-zi-lcof/

        考点：对一维数组的编程和理解能力，一维数组在内存中占据连续的空间，可以根据下标定位相应的元素；

考察分析问题的能力，问题相对复杂时，通过具体的实例来找到其中的规律是本题解决的关键所在

考察沟通能力，询问数组是否可以修改？

        扩展：若不能修改数组，则使用什么方法？（二分查找或者新建数组）

           面试题4.二维数组中的查找  https://leetcode-cn.com/problems/er-wei-shu-zu-zhong-de-cha-zhao-lcof/

考点：对二维数组的编程和理解能力，二维数组在内存中占据连续的空间，同一行从左到右存储，整体从上到下存储

考察分析问题的能力，问题相对复杂时，通过具体的实例（右上角，左下角，右下角，左上角等关键位置）来找到其中的规律是本题解决的关键所在

扩展：while(searchScope)和while(row<rows&&col>=0)的区别在哪呢?searchScope=row<rows&&col>=0

字符串：若干字符组成的序列，考察概论非常高,C/C++中以’\0‘作为结尾；"012456789"转换为字符数组则需要11个空间；char[]  ch=new  char[11]; 为了节省内存，C/C++把字符常量放到一个单独的字符区域，当几个指针赋值给相同的字符常量时，实际上指向相同的内存地址；

    面试题5.替换空格  https://leetcode-cn.com/problems/ti-huan-kong-ge-lcof/

考点：对字符串的编程和理解能力；

考察分析时间效率的能力；

考察是否对内存覆盖有警惕性，即字符串能否变长；

考察思维能力，从前往后的思路被否定后，应该想到从后往前；

扩展：合并两个数组或者字符串时，如果从前往后合并需要大量移动，我们可以考虑从后往前合并，减少数字移动次数来提高效率；

链表：由指针把若干个结点链接起来构成线性表；是一种动态数据结构，因为在创建链表时无需知道链表的长度，内存分配不是一次性完成，而是新建结点则分配一次；

     面试题6.从尾到头打印链表  https://leetcode-cn.com/problems/cong-wei-dao-tou-da-yin-lian-biao-lcof/

考点：是否允许修改链表结构？必须询问；

如果使用递归，是否会因为过深而导致栈溢出；

考察对循环，递归， 栈三者关系的掌握；

树：除根以外的结点都只有一个父节点，根节点无父结点，除叶结点以外的结点都有一个或多个子结点，叶结点无子节点，父子之间使用指针链接；

二叉树：树中每个结点最多只能有两个子节点的树；

遍历方式：前序，中序，后序，层序遍历；

    面试题7.重建二叉树  https://leetcode-cn.com/problems/zhong-jian-er-cha-shu-lcof/solution/mian-shi-ti-07-zhong-jian-er-cha-shu-di-gui-fa-qin/

考点：对二叉树的前序遍历和中序遍历的理解程度，前序根在前，中序根前为左子树分支，根后为右子树分支；

考察分析复杂问题的能力，将构建二叉树的大问题分解为左，右子树的小问题，本质上一致，则递归调用；

栈：栈在计算机领域被广泛应用，例如操作系统会给每个线程创建一个栈来存储函数调用时各个函数的参数，返回地址和临时变量等，栈的特点是先进后厨，最后被push入栈的元素会被第一个pop出栈；栈通常不考虑排序，需要O（N）的时间找到最大或者最小的元素；

    面试题9.用两个栈实现队列  https://leetcode-cn.com/problems/yong-liang-ge-zhan-shi-xian-dui-lie-lcof/

考点：对栈和队列的理解；

考察写模板相关的代码的能力

考察分析问题的能力，通过具体例子分析，结合画图将抽象问题形象化，从而解决该问题；

扩展：用两个队列实现栈；知识点：java里的Stack不推荐使用，因此我们可以使用LinkedList来替代Stack；原因的话是Stack继承了Vector接口，而Vector底层是一个Object[]数组，那么就要考虑空间扩容和移位的问题了。 可以使用LinkedList来做Stack的容器，因为LinkedList实现了Deque接口，所以Stack能做的事LinkedList都能做，其本身结构是个双向链表，扩容消耗少。

算法和数据操作：基于递归的实现方法代码比较简洁，但性能不如基于循环的实现方法，面试时应当根据题目的特点和要求，选择合适的方法；排序和查找是考察算法的重点，着重掌握二分查找，归并排序和快速排序；

考点：二维数组（迷宫或棋盘）上搜索路径，可以尝试采用回溯法，通常回溯用递归实现，或者用栈来实现；

若求某个问题的最优解，且该问题可以分为多个子问题，尝试使用动态规划（最优子问题，重复子结构），自上而下的递归思路去分析动态规划问题随时，会发现子问题之间存在重叠的更小子问题，为避免重复计算，采用自下而上的循环代码实现（如斐波那契数列），将子问题最优解算出并保存，再基于子问题的解来计算大问题的解。

DP的思路之后，如果分解子问题的时候是否存在某个特殊选择，采用此特殊选择一定可得到最优解，那么考虑贪婪算法。

位运算是特殊的算法，一共有，与，或，异或，左移，右移五种；

递归和循环：需要重复地多次 计算相同的问题，则可以选择递归或者循环；递归：在一个函数的内部调用此函数本身，循环：设置计算的初始值及终止条件，在一个范围内重复运算；递归代码简洁但不如循环效率高，原因：每次函数调用需要在内存栈中分配空间以保存参数，返回地址及临时变量，往栈压入数据和弹出数据都需要时间；

递归中很多计算可能重复，对性能将带来很大影响；

递归也可能发生栈溢出；

   面试题10.斐波那契数列  https://leetcode-cn.com/problems/fei-bo-na-qi-shu-lie-lcof/

   青蛙跳台阶问题  https://leetcode-cn.com/problems/qing-wa-tiao-tai-jie-wen-ti-lcof/

考点：不同方法求斐波那契数列的时间效率大不相同，递归只管但效率低，循环实现可以提高时间效率（建立备忘录来减少重复计算，更巧妙的是维护两个变量交替更新）；

考察对递归和循环的理解及编程能力

考察对时间复杂度的分析能力

考察数学建模能力；

查找和排序

面试题11.旋转数组的最小数字https://leetcode-cn.com/problems/xuan-zhuan-shu-zu-de-zui-xiao-shu-zi-lcof/

考点：考察对二分查找的理解；

考察沟通能力和学习能力。需要在很短的时间内学习和理解新概念，在面试过程中，如果面试官提出新概念，应当

主动和面试官沟通，多问问题，弄清概念；

考察应聘者思维的全面性。应当很好地处理这些特例；

回溯法：蛮力法的升级版，从解决问题的每一步的所有肯能选项里系统地选择出一个可行的解决方案，非常适合由多个步骤组成的问题，并且每个步骤都有多个选项；当我们在某一步选择了其中一个选项时，进入下一步，又面临新的选项，如此重复选择，直至到达最终状态；

回溯法解决的问题的所有选项可以形象地用树状结构表示；在某一步有n个可能的选项，则该步骤可以看成树状结构中的一个节点，每个选项看成树中节点连接线，经过这些连接线到达该节点的n个子节点。树的叶节点对应着终结状态，如果在叶节点的状态满足题目的约束要求，则找到了可行的方案；

如果叶节点的状态不满足约束要求，则回溯到它的上一个节点再尝试其他的选项，如果上一个节点的所有可能都被尝试过，且不能到达满足约束条件的终结状态，则再次回溯到上一个节点，如果所有节点的所有选项都尝试过且无法到达满足约束条件的终结状态，则该问题无解；

通常回溯法适合用递归实现，到我们到达某一个节点时，尝试所有可能的选项并且在满足条件的前提下递归地抵达下一个节点；

面试题12.矩阵中的路径https://leetcode-cn.com/problems/ju-zhen-zhong-de-lu-jing-lcof/

考点：考察对回溯法的理解和掌握；通常在二维矩阵上找路径这类题目都可以使用回溯解决；

考察对数组的编程能力，例如越界处理，标记，回溯还原等；

面试题13.机器人的运动范围https://leetcode-cn.com/problems/ji-qi-ren-de-yun-dong-fan-wei-lcof/

考点：考察对回溯法的理解；通常物体或人在二维方格运动这类问题都可以用回溯法解决；

考察应聘者对数组编程的能力；将矩阵一般看成一个二维数组，只有对数组的特性充分了解，才有可能快速正确地实现回溯法的代码编写；

动态规划与贪婪算法：如果面试题为求一个问题的最优解（通常是求最大值或者最小值），而且该问题能分解成若干个子问题，且子问题之间有重叠的更小的子问题（最优子结构，重复子问题），就可以考虑用动态规划来做；

在应用动态规划之前，分析能否把大问题分解成小问题，分解后的每个小问题也存在最优解；如果把小问题的最优解组合秋来能得到整个问题的最优解，那么使用动态规划解决此问题；从上往下分析题目，从下往上求解题目，此为应用动态规划求解问题的第四个特点；

在应用动态规划的时候，我们每一步都可能面临若干个选择，只好把所有可能都尝试一边，比较得出最优的剪法（面试题14.剪绳子）；即f(n)=max(f(i)×f(n-i));

贪婪算法：当应用贪婪算法解决问题时，每一步都可以做出一个贪婪的选择，基于这个选择，我们确定能得到最优解；为什么这样的贪婪选择能得到最优解？这是我们应用贪婪算法时都需要问的问题，需要用数学方式来证明贪婪选择的正确性；

面试题14.剪绳子https://leetcode-cn.com/problems/jian-sheng-zi-lcof/

考点：考察应聘者的抽象建模能力；应聘者需要把一个具体的场景抽象成一个能用动态规划或者贪婪算法解决的模型；

考察应聘者对动态规划和贪心算法的理解；能够灵活运用动态规划解决问题的关键是：从上到下分析问题，从下到上解决问题的能力，而灵活运用贪婪算法则需要扎实的数学基本功；

位运算：将数字用二进制表示之后，对每一位上0或者1的运算；底层的技术离不开位运算；

理解位运算的第一步是理解二进制；

位运算一共有五种：与，或，异或，左移，右移；

面试题15.二进制中1的个数https://leetcode-cn.com/problems/er-jin-zhi-zhong-1de-ge-shu-lcof/

考点：考察对二进制及位运算的理解；

考察分析，调试代码的能力；如果在面试过程中采用的是第一种思路，则当面试官提示输入负数将出现问题时，面试官期待我们可以找出死循环的原因并加以改进，这要求我们有一定的调试功底；

知识点：把一个整数减去1之后再和原来的整数做位与运算，得到的结果相当于把整数的二进制表示中最右边的1变成0；很多二进制的题都可以这么解决；

高质量的代码

代码的规范性：

清晰的书写；

清晰的布局；

合理的命名；（详解可搜索“命名”关键词博客）

代码的完整性：

考虑问题是否周全；

是否完成了基本功能；

输入边界值是否能得到正确的输出；

是否对各种不合规范的非法输入做出了合理的错误处理；

1.从三个方面确保代码完整性；

a.功能测试：尽量突破常规思维的限制，比如打印从1道最大的n位数；最大的三位数是999，最大的四位数是9999，那么超出int范围的应该使用long，超出long表示的范围，即任意大的数字应该使用字符串或数组来保存大数，确保不会溢出；

b.边界测试；如果基于循环，则测试循环条件是否正确？如果基于递归，那么递归终止的边界值是否正确？

c.负面测试；考虑各种可能的错误输入；所写函数除了顺利地完成要求的功能，当输入不符合要求的时候还要能做出合理的错误处理；

在写代码时，能将未来需求可能的变化考虑进去，在需求发生变化时能尽量减少代码改动的风险，那么就展现了对程序的可扩展性合可维护性的理解；

2.三种错误处理方式；

a.函数使用返回值来告知调用者是否出错；（使用不便，函数不能直接将计算结果返回给其他变量，也不能把这个函数计算的结果直接作为参数传递地给其他函数）

b.当错误发生时，设置一个全局变量；调用者可以直接把返回值赋值给其他变量或者作为参数传递给其他函数；（安全隐患：调用者容易忘记检查全局变量，在调用出错时忘记进行相应的错误处理，从而留下安全隐患）

c.异常；当函数运行出错时，抛出一个异常，还可以根据不同的出错原因定义不同的异常类型；调用者根据异常的类型就能知道出错的原因，从而做出相应的处理；（抛出异常会打乱正常的顺序，对程序的性能有较大影响）

面试题16.数值的整数次方https://leetcode-cn.com/problems/shu-zhi-de-zheng-shu-ci-fang-lcof/

考点：考察应聘者思维的全面性；如底数为0而指数为负数时的错误处理；

对效率要求比较高的面试官还会考察应聘者快速做乘方的能力；

面试题17.打印从1道最大的n位数https://leetcode-cn.com/problems/da-yin-cong-1dao-zui-da-de-nwei-shu-lcof/

考点：考察解决大数问题的能力，选择合适的数据表示方式来解决大数问题；

考虑是否会考虑用户的使用习惯；（使用PrintNumber去掉前面的0字符）

面试小提示：如果是关于n位的整数并且没有限定n的取值范围，或者输入任意大小的整数，那么这道题很有可能需要考虑大数问题；

面试题18.删除链表的节点https://leetcode-cn.com/problems/shan-chu-lian-biao-de-jie-dian-lcof/

考点：考察对链表的编程能力；

考察创新思维能力；即当我们想删除一个节点时，不一定要删除这个节点本身，可以把下一个节点的内容复制覆盖到此节点，再删除下一个节点即可；

考察思维的全面性，即删除的节点位于头部，尾部，及输入的链表只有一个节点时的特殊情况；

面试题21.调整数组顺序，使得奇数位于数组前半部分，偶数位于数组后半部分https://leetcode-cn.com/problems/diao-zheng-shu-zu-shun-xu-shi-qi-shu-wei-yu-ou-shu-qian-mian-lcof/

考点：考察快速思维能力；

考察对扩展性的理解，要求写出的代码具有可重用性；

代码的鲁棒性：

又称健壮性；指程序能够判断输入是否合乎规范要求，对不符合要求的输入予以合理的处理；

容错性是鲁棒性的重要体现；

提高代码的鲁棒性的有效途径是：进行防御式编程，指遇见什么地方可能会出现什么问题，并为这些可能出现的问题指定处理方式；如：打开文件发现文件不存在时，提示用户检查文件名和路径，服务器连接不上时，提示用户更换连接线路等；

最简单最实用的防御式编程：再函数入口添加代码以验证用户输入是否符合要求；如指针为空，字符串为空，数组为空等，提前考虑道并进行相应处理；

多问：如果？？？那么？？？（比如22.链表中倒数第K个节点，如果K大于链表节点数怎么办）？提前思考能帮助发现潜在问题并解决，从而写出鲁棒性高的软件或代码；

面试题22.链表中倒数第K个节点https://leetcode-cn.com/problems/lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof/

考点：考察对链表的理解；

考察所写代码的鲁棒性，鲁棒性是解决此题的关键；例如K过大，head为空，K=0；

知识点：当用一个指针遍历链表不能解决问题时，可以尝试两个指针遍历链表，比如快慢指针或者首位指针；

面试题23.链表中环的入口

考点：对链表的理解；

代码的鲁棒性；

分析问题的能力；把一个问题分解成几个简单的步骤，是一种常用的解决复杂问题的方法；环入口此题可分解为三个步骤：判断有无环并且找出环中任意一个节点；得到环中节点的个数；找到环的入口；

面试题24.反转链表https://leetcode-cn.com/problems/fan-zhuan-lian-biao-lcof

考点：与链表相关的问题总有大量的指针操作，而指针操作的代码容易出催哦；为避免出错，变成前先进性全面分析，写出鲁棒的代码；

考察对链表，指针的编程能力；

考察思维的全面性及代码的鲁棒性；

面试题25.合并两个排序的链表https://leetcode-cn.com/problems/he-bing-liang-ge-pai-xu-de-lian-biao-lcof/

考点：分析问题的能力，解决此问题需要大量指针操作；

考察鲁棒性，应当考虑指针的安全，如处理空指针；

面试题26.树的子结构https://leetcode-cn.com/problems/he-bing-liang-ge-pai-xu-de-lian-biao-lcof/

考点：先序遍历递归搜索;分两部分：1.搜索判断起点    2.开始判断；

考察对空指针的检查，即边界检查；

知识点：在计算机内表示小数（float和double）时有误差，只能判断它们之差的绝对值是不是在一个很小的范围内，如果两个数相差很小，则可以认为它们相等；

考察对递归的编程能力；

考察代码的鲁棒性，含有大量指针操作，应采用防御式编程的方式，每次访问指针地址之前都要考虑此指针是否为nullptr;

解决面试题的思路

画图让抽象问题形象化

面试题27.二叉树的镜像https://leetcode-cn.com/problems/er-cha-shu-de-jing-xiang-lcof/comments/

考点：考察对二叉树的理解，实质上用树的遍历算法来解决；

考察思维能力；树的镜像是抽象概念，我们需要在短时间内想清楚求镜像的步骤并转化成代码；使用画图的方法将抽象问题形象化，有助于快速找到解题思路；

面试题28.对称的二叉树https://leetcode-cn.com/problems/dui-cheng-de-er-cha-shu-lcof/

考点：对二叉树的理解，实质上用树的遍历算法来解决；

考察思维能力，树的对称是抽象概念，需要在短时间内想清楚对称的步骤并转换为代码；可以画图把抽象问题形象化，有助快速找i到解题思路；

面试题29.顺时针打印矩阵

面试题30.包含min函数的栈https://leetcode-cn.com/problems/bao-han-minhan-shu-de-zhan-lcof/

考点：考察分析复杂问题的思维能力，辅助栈；

考察对栈的理解和编程能力；

面试题31.从上到下打印二叉树https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-lcof/

考点：对层序遍历的编程和思考能力；

考察对队列Queue继承于LinkedList，ArrayList的声明规则；

考察思维能力，二叉树从上到下可借助队列；

考察对二叉树及队列的理解；

知识点：从上到下按层遍历二叉树，从本质上来说就是广度优先遍历二叉树；树是图的一种特殊退化形式；

面试题32.分行从上到下打印二叉树https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-ii-lcof/

考点：对层序遍历的编程和思考能力；

考察对队列Queue继承于LinkedList，ArrayList的声明规则；

考察思维能力，二叉树从上到下可借助队列；

考察对二叉树及队列的理解；

面试题32.之字形打印二叉树https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-iii-lcof/solution/

考点：双端队列LinkedList的使用，addLast，addfirst,以及使用每层队列的size（）%2==1来确定奇偶层数；

考点：对层序遍历的编程和思考能力；

考察对队列Queue继承于LinkedList，ArrayList的声明规则；

考察思维能力，二叉树从上到下可借助队列；

考察对二叉树及队列的理解；

面试题33.二叉搜索树的后序遍历https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-hou-xu-bian-li-xu-lie-lcof/