《剑指Offer》题目总结（持续更新）

首先说明：这篇文章并不是解析每一道题，而是做一个规律性的总结. 如需详细题解还请移步力扣. 以下仅供读者自查.

技术面试，除了良好的情商外，需要注意的有以下的几点：

• 扎实的基础知识
• 高质量的代码
• 清晰的思路（画图让抽象问题形象化，举例让抽象问题具体化，分解使复杂问题简单化）、
• 优化效率的能力
• 优秀的综合能力

反问环节推荐话题：与应聘职位或者项目相关的问题，需要事先对应聘的岗位和或者项目的背景有一定的了解，或者是临场发挥，从面试官刚才的话题中抽出问题提问.

高质量的代码

题67 将字符串转化为整数. 这道题看上去不费吹灰之力就可以完成，但本题的主要考察点在于：能否预判空指针或空串（这也是其他题目经常要进行判断的步骤），以及各种非法的输入. 故而测试者在测试代码的时候，应该自己构造出一些测试样例，不要过快提交，避免草率. 测试者在测试代码时，通常可以从功能测试、边界值测试和特殊输入测试入手. 一边心中默念这三种测试类型，一边构建相应的测试样例，结果不会差很远. 但要提防的一点是：改了某一处bug，导致原本正确的测试样例出了问题，这种情况下推荐综合测试.

题68 树中两个节点的最低公共祖先. 这道题看上去就存在一些疑点，首先，是什么树，要和面试官沟通好. 如果是二叉搜索树，是一种情况. 如果不是二叉树，那么是否节点之间存在特殊指针，例如从子节点指向父节点的指针，还是没有？这些都是要综合考虑的问题，思考好这些问题，有的时候也会给我们带来不错的idea，例如知识迁移的idea .

从二叉树中找到指定节点的路径：

// 小trick：温馨提示，做递归类型题时，从宏观上把握，避免陷入细节无法自拔. 

struct node {
    node* left;
    node* right;
    int val;
};

// 寻找到target节点的路径，保存在引用类型vector中
bool findPath(vector<node*>& path, node* currentNode, int targetVal) {
    if (currentNode == nullptr) {
        return false;
    }
    // 先将当前节点压入vector
    path.push_back(currentNode);
    // 如果当前已经找到target节点，则返回true
    if (currentNode->val == targetVal) {
        return true;
    }
    // 如果当前节点不是target节点，则递归搜寻其左子树和右子树
    if (findPath(currentNode->left) || findPath(currentNode->right)) {
        return true;
    }
    // 都找不到
    path.pop_back();
    return false;
}

要关注 代码是否完成了基本的功能，输入边界值能否得到正确的输出，是否对各种不规范的非法输入做了合理的错误处理.

O(1) 时间内删除单链表节点 这里基于节点已经在链表中的假设，通过值覆盖，删除后续节点，来达到等价的效果. 需要注意删除节点的位置.

（基础）语言特性、数据结构、算法

题1 以C++为例，需要熟练掌握构造函数、析构函数、继承、多态、模板、重载等语言特性的使用. 这里需要各位回顾大学低年级学习的知识，时间太久难免生疏.

题2 要了解基础的设计模式，特别单例模式，代码量不大很好考，常见的有单线程的单例模式，以及多线程下单例模式的懒汉式、饿汉式、DCL锁模式的书写.

题 有时还要准备一下多线程编程，例如生产者-消费者模式. 这里就牵涉到wait，notify等线程通信的用法.

题3、题4 数组、二维数组的访问规律性把握

题6 关于链表的题，画图 yyds

题7 由二叉树前中序遍历求出树结构，本题适合自上而下的递归求解 (这里我再次强调，写递归时不要钻到细节里面去，从宏观把握，更不容易出问题，且AC的可能性更大，做题速度更快，检查递归的时候可以深入一两层，但也不宜多，干嘛和自己过不去呢).

题8 深入考察二叉树的中序遍历结构特征，将一个问题进行归类，分解为若干小问题求解，在此也需要各位注意一下二叉树的非递归遍历.

题9 用两个栈实现队列，栈无非就是先入后出，而队列是先进先出，通过简单的举例可以将该问题具体化，进而找到求解策略.

延伸 吾日三省吾身，快速幂掌握了否，回溯递归理解了否，动规贪心明白了否？

位运算 求二进制中1的个数（注意负数的情况，推荐左移）;

题29 顺时针打印矩阵

题30 包含min函数的栈

链表经典题目

链表中倒数第k个节点 考虑范围、空指针、乃至数据类型引发的鲁棒性问题

链表中环的入口节点 从链表是否有环进行迁移.

反转链表

合并两个排序链表

树经典题目

二叉搜索树的后续遍历序列 将大问题分解为小问题进行求解，这是递归分治的精髓所在.

二叉树中和为某一值的路径 转化为树的遍历问题.

博主持续更新中…

如有错误，欢迎批评指正！