跳转至

剑指 Offer

参考资料

  • 剑指 Offer

面试的流程

略

面试需要的基础知识

面试题 1: 赋值运算符函数

  • 返回类型为该类型的引用, 并返回 *this
  • 传入参数为 const T&
  • 先判断是否是自赋值, 如果是则直接返回 *this
  • 否则先释放原有的内存, 再分配新的内存, 最后复制数据
// 这本书的标准答案
class T {
public:
    T& operator=(const T& other) {
        if(this != &other) {
            // 调用拷贝构造函数
            T temp(other); // 如果在这里失败, 则不会执行下面的代码
                           // 保证异常安全

            // 交换数据
            int* tempData = temp.data;
            temp.data = data;
            data = tempData;
        }
        return *this;
        // temp 是一个临时对象, 会在函数结束时自动析构
    }
private:
    int* data;
    int size;
};

面试题 2: 实现 Singleton 模式

  • 需求: 全局唯一实例, 懒加载, 线程安全, 禁止拷贝
  • 错误的实现
    • 将构造函数设为私有, 提供一个用于获取实例的静态方法, 一个静态指针指向唯一实例
      • 只适用单线程环境, 通过判断指针是否为空来判断是否需要创建实例, 可能会出现线程安全问题
    • 加一把同步锁, 可以但是效率低, 因为后续实例化的尝试也需要加锁才能判断是否需要创建实例
  • 勉强的实现
    • 加锁,前后判断指针是否为空
  • 最佳实现
    • 静态方法的静态局部变量 (进程生命周期)
    • C++ 11 保证静态局部变量的初始化是线程安全的, 且只会执行一次
    • 会自动调用析构函数, 不会内存泄漏
#include <iostream>

class Singleton {
public:
    // 获取单例引用的静态方法
    static Singleton& getInstance() {
        // C++11 保证: 静态局部变量的初始化是线程安全的
        // 且只会执行一次
        static Singleton instance; 
        return instance;
    }

    // 禁止拷贝构造
    Singleton(const Singleton&) = delete;
    // 禁止赋值操作
    Singleton& operator=(const Singleton&) = delete;

    // 示例业务方法
    void doSomething() {
        std::cout << "Singleton is doing something." << std::endl;
    }

private:
    // 私有化构造函数
    Singleton() {
        std::cout << "Singleton Construct" << std::endl;
    }

    // 私有化析构函数 (可选, 根据需求)
    ~Singleton() {
        std::cout << "Singleton Destruct" << std::endl;
    }
};

int main() {
    // 调用时才会初始化
    Singleton::getInstance().doSomething();
    return 0;
}

面试题 3: 二维数组中的查找

在一个二维数组中, 每一行都按照从左到右递增的顺序排序, 一列都按照从上到下递增的顺序排序, 请完成一个函数, 输入这样的一个二维数组和一个整数, 判断数组中是否含有该整数

  • 一看都想二分, 一次排除的倒是很多, 状态转移不好做
  • 从二维数组的右上角开始查找
    • 如果当前元素等于目标值, 则返回 true
    • 如果当前元素大于目标值, 则说明目标值在当前元素的左边, 列索引减一
    • 如果当前元素小于目标值, 则说明目标值在当前元素的下边, 行索引加一
  • 这样稳定将数组分成两部分

面试题 4: 替换空格

将字符串中的空格替换为 %20

  • 非常简单, 先保证空间足够, 从后往前替换, 不会覆盖未处理的字符

面试题 5: 从尾到头打印链表

  • 非常简单, 递归打印即可
  • 也可以用栈来实现, 先入后出

面试题 6: 重建二叉树

根据前序遍历和中序遍历重建二叉树

  • 根据前序遍历确定根节点
  • 根据中序遍历将数组分成左右两部分
  • 递归重建左子树和右子树

面试题 7: 用两个栈实现队列

  • 一个栈用于入队, 一个栈用于出队
  • 入队时直接入栈
  • 出队时, 如果出队栈为空, 则将入队栈中的元素全部弹出并压入出队栈, 然后出队栈弹出栈顶元素

面试题 8: 旋转数组的最小数字

把一个数组最开始的若干个元素搬到数组的末尾, 我们称之为数组的旋转, 输入一个递增排序的数组的一个旋转, 输出旋转数组的最小元素

  • 二分查找
    • 如果中间元素大于等于左边界, 则说明中间元素在左半部分, 最小元素在右半部分, 左边界移动到中间元素
    • 如果中间元素小于等于右边界, 则说明中间元素在右半部分, 最小元素在左半部分, 右边界移动到中间元素
    • 当左边界和右边界相邻时, 右边界就是最小值
  • 完备一下
    • 考虑数组完全有序的情况, 先比较左边界和右边界, 如果左边界小于右边界, 则数组完全有序, 直接返回左边界
    • 考虑左边界和右边界和中间元素都相等的情况, 无法判断, 只能顺序查找 (本质是不能判断旋转左倾还是右倾)

面试题 9: 斐波那契数列

  • 非常简单, 递归即可退出面试
  • 可以用动态规划优化
  • 正解矩阵快速幂

面试题 10: 二进制中 1 的个数

求汉明重量

  • 错误的解法
    • 循环右移 (移 n) 检验最后一位是否为 \(1\), 负数的右移会补 \(1\), 会导致死循环
    • 循环左移 (移 flag) 检验最后一位是否为 \(1\), 可以, 但是效率低
  • 位运算
    • 每次将 \(n\) 与 \(n-1\) 做按位与操作, 会将 \(n\) 的二进制表示中的最低位的 \(1\) 变成 \(0\)
    • 重复操作直到 \(n\) 变成 \(0\)
    • 操作次数就是 \(1\) 的个数

高质量的代码

面试题 11: 数值的整数次方

实现 double pow(x, n) 函数, 计算 \(x\) 的 \(n\) 次方

  • 非常简单, 循环即可退出面试
  • 要考虑 \(n\) 为负数的情况, 可以先将 \(n\) 取相反数, 最后返回 1 / res (校验 res < 0.0000001lf)
  • 再加一个快速幂的优化

面试题 12: 打印 1 到最大的 n 位数

输入数字 \(n\), 按顺序打印出从 \(1\) 到最大的 \(n\) 位十进制数, 比如输入 \(3\), 则打印出 \(1\), \(2\), \(3\) 一直到最大的 \(3\) 位数 \(999\)

  • 非常简单, 开始打印, 退出面试即可
  • 用字符串模拟
    • 模拟加一, \(n+1\) 位不是 \(0\) 时, 说明已经打印完了 \(n\) 位的所有数
    • 打印时忽略前导 \(0\)
  • \(n\) 位全排列

面试题 13: 在 \(O(1)\) 时间删除链表节点

  • 非常简单, 用下一个节点的值覆盖当前节点, 然后删除下一个节点即可
  • 要注意的是, 要删除的节点是否是尾节点或只有一个节点

面试题 14: 调整数组顺序使奇数位于偶数前面

  • 非常简单, 用双指针, 一个指向头, 一个指向尾, 头指针遇到偶数, 尾指针遇到奇数, 就交换
  • 拓展性
    • 可以将判断奇偶的条件抽象出来, 注入可调用对象

面试题 15: 链表中倒数第 k 个节点

  • 非常简单, 用两个指针, 一个先走 \(k-1\) 步, 然后两个指针一起走, 当快指针到达尾节点时, 慢指针就是倒数第 \(k\) 个节点
  • 要注意的是, 判断 \(k\) 的语义是否正确
    • 正数
    • 小于等于链表长度

面试题 16: 反转链表

  • 非常简单, 用三个指针, 一个指向前驱, 一个指向当前节点, 一个指向后继, 然后依次反转即可

面试题 17: 合并两个排序的链表

  • 非常简单, 用两个指针, 一个指向头, 一个指向当前节点, 然后依次比较, 小的就接入当前节点, 然后指针后移

面试题 18: 树的子结构

  • 先找相同的根节点, 然后递归判断左右子树是否相同

解决面试题的思路

面试题 19: 二叉树的镜像

  • 非常简单, 递归交换左右子树即可

面试题 20: 顺时针打印矩阵

  • 非常简单, 模拟

面试题 21: 包含 min 函数的栈

  • 最小栈

面试题 22: 栈的压入, 弹出序列

  • 模拟, 用一个栈模拟压入, 然后判断弹出序列是否正确
    • 弹出序列的每个元素, 都要和栈顶元素比较, 如果相等, 就弹出栈顶元素, 否则, 就继续压入栈

面试题 23: 从上往下打印二叉树

  • 层序遍历

面试题 24: 二叉搜索树的后序遍历序列

给你一个数组, 判断是否是二叉搜索树的后序遍历序列

  • 递归
    • 后序遍历的最后一个元素就是根节点
    • 前面的元素可以分为两部分, 一部分是左子树的后序遍历序列, 一部分是右子树的后序遍历序列
    • 左子树的后序遍历序列的所有元素都应该小于根节点, 右子树的后序遍历序列的所有元素都应该大于根节点
    • 递归判断左子树和右子树是否是后序遍历序列

面试题 25: 二叉树中和为某一值的路径

  • 遍历

面试题 26: 复杂链表的复制

  • 力扣原题
  • 难点在处理随机指针的复制时, 要找到源节点与复制节点的对应关系
  • 哈希表 / 复制不拆分

面试题 27: 二叉搜索树与双向链表

将二叉搜索树转换为双向链表 (原地)

  • 中序遍历即可

面试题 28: 字符串的排列

给一个字符串, 打印出该字符串中字符的所有排列

  • 每次选择一个字符, 放在序列的第一个位置, 然后递归处理剩余的字符

优化时间和空间效率

面试题 29: 数组中出现次数超过一半的数字

  • 摩尔投票法, 力扣原题

面试题 30: 最小的 k 个数

  • 减治法 / 最大堆

面试题 31: 连续子数组的最大和

  • 动态规划 / 贪心, 力扣原题

面试题 32: 从 1 到 n 整数中 1 出现的次数

  • 从最高位开始枚举每位, 计算该位上 \(1\) 出现的次数
    • 这位若大于 \(1\), 则该位上 \(1\) 出现的次数为 \(10^i\) (i 为当前位数)
    • 这位若等于 \(1\), 则该位上 \(1\) 出现的次数为 \(n - 10^i + 1\) (i 为当前位数)

面试题 33: 把数组排成最小的数

数组 [3, 32, 321] 排成的最小的数为 \(321323\)

  • 排序, 自定义比较函数 (字典序)

面试题 34: 丑数

只包含因子 \(2\), \(3\), \(5\) 的数称为丑数, 求第 \(n\) 个丑数

  • 根据已经算出的丑数组中的 \(T_2\), \(T_3\), \(T_5\), 乘以 \(2\), \(3\), \(5\) 获得最小数 (下一个数)
    • \(T_2\), \(T_3\), \(T_5\) 分别指向当前丑数组中, 前面的数都乘以 \(2\), \(3\), \(5\) 小于当前丑数组的最后一个数, 后面的数反之的数
    • 考虑缓存

面试题 35: 第一个只出现一次的字符

  • 哈希表

面试题 36: 数组中的逆序对

  • 归并排序, 合并时左数组小无逆序对
    • 右数组小, 则左数组中的每个元素都与其构成逆序对, 数量为 \(mid - i + 1\)

面试题 37: 两个链表的第一个公共节点

  • 力扣原题

面试中的各项能力

面试题 38: 数字在排序数组中出现的次数

  • 二分查找, 找到第一个小于 \(k\) 的位置, 然后往后找, 直到找到第一个大于 \(k\) 的位置

面试题 39: 二叉树的深度

  • 递归, 取左右子树的深度的较大值 + 1
  • 后序遍历

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

数组中只出现一次的数字有两个, 怎么办

  • 还是先异或, 得到的结果就是这两个数的异或结果
  • 然后找到异或结果中第一个为 \(1\) 的位, 假设为第 \(i\) 位
  • 然后根据第 \(i\) 位是否为 \(1\) 来将数组分为两部分, 分别异或, 就可以得到这两个数

面试题 41: 和为 S 的两个数字 VS 和为 S 的连续正数序列

题目一: 和为 S 的两个数字

  • 双指针, 一个指向头, 一个指向尾, 向中间移动

题目二: 和为 S 的连续正数序列

  • 滑动窗口, 窗口内的数的和小于 \(S\), 右指针右移, 大于 \(S\), 左指针右移
  • 窗口内的数的和等于 \(S\), 记录窗口内的数, 左指针右移

面试题 42: 翻转单词顺序 VS 左旋转字符串

题目一

  • 原题

题目二

  • 原题

面试题 43: n 个骰子的点数

扔 \(n\) 个骰子, 求点数和的概率分布

  • 动态规划
    • \(dp[i][j]\) 表示扔 \(i\) 个骰子, 点数为 \(j\) 的次数
    • \(dp[i][j] = \sum_{k=1}^6 dp[i-1][j-k]\)

面试题 44: 扑克牌的顺子

  • 模拟

面试题 45: 圆圈中最后剩下的数字

  • 约瑟夫环问题
    • \(f(n, m) = (f(n-1, m) + m) \mod n\)

面试题 46: 求 1 + 2 + ... + n

  • 逆天问题

面试题 47: 不用加减乘除做加法

  • 模拟一个加法器

面试题 48: 不能继承的类

  • 逆天问题

面试题 49: 把字符串转换为整数

  • 略

面试题 50: 树中两个节点的最低公共祖先

  • 力扣原题

新增面试题

面试题 51: 数组中的重复的数字

在一个长度为 \(n\) 的数组中, 所有的数字都在 \(0\) 到 \(n-1\) 的范围内, 数组中某些数字是重复的, 请找出数组中任意一个重复的数字

  • 一开始我想的是位图秒杀
  • 正解抽屉原理
    • 假设数组中没有重复的数字, 那么数组中每个数字都对应一个下标
    • 现在有重复的数字, 那么至少有一个下标对应的数字重复了

面试题 52: 构建乘积数组

给一个数组 \(A[0, 1, \dots, n-1]\), 构建一个数组 \(B[0, 1, \dots, n-1]\), 其中 \(B[i] = A[0] \times A[1] \times \dots \times A[i-1] \times A[i+1] \times \dots \times A[n-1]\)

  • 力扣原题

面试题 53: 正则表达式匹配

给一个字符串 \(s\) 和一个正则表达式 \(p\), 实现正则表达式匹配

  • 力扣原题
  • 模拟, 主要是处理 *, 分叉即可

面试题 54: 表示数值的字符串

  • 模拟

面试题 55: 字符流中第一个不重复的字符

  • 哈希表

面试题 56: 链表中环的入口节点

  • 力扣原题
  • 快慢指针

面试题 57: 删除链表中重复的节点

  • easy
  • 哑节点 + 双指针

面试题 58: 二叉树的下一个节点

  • 力扣原题
  • 分类讨论即可

面试题 59: 对称的二叉树

  • 力扣原题

面试题 60: 把二叉树打印成多行

  • 力扣原题
  • 层序遍历

面试题 61: 按之字形顺序打印二叉树

  • 力扣原题
  • 层序遍历, 每一层的节点顺序根据层数的奇偶性来确定

面试题 62: 序列化二叉树

  • 力扣原题
  • 前序遍历, 用占位符补全为完全二叉树

面试题 63: 二叉搜索树的第 k 个节点

  • 力扣原题
  • 中序遍历, 第 \(k\) 个节点就是第 \(k\) 小的节点

面试题 64: 数据流中的中位数

  • 维护一个大根堆和一个小根堆
    • 大根堆存储较小的一半数
    • 小根堆存储较大的一半数
  • 插入时, 先插入大根堆, 然后将大根堆的堆顶元素弹出, 插入小根堆
  • 中位数就是大根堆的堆顶元素, 如果是偶数个元素, 则是大根堆的堆顶元素和小根堆的堆顶元素的平均值

面试题 65: 滑动窗口的最大值

  • 力扣原题
  • 单调队列
    • 队头元素就是当前窗口的最大值
    • 新元素入队时, 队尾元素出队, 直到队尾元素大于等于新元素
    • 队头元素出队时, 如果队头元素不在当前窗口内, 则出队

面试题 66: 矩阵中的路径

一个由 \(m \times n\) 个格子组成的矩阵, 每个格子中都有一个字符, 问是否有一个路径, 使得路径上的字符按顺序组成字符串 \(s\)

  • 回溯

面试题 67: 机器人的运动范围

机器人在一个 \(m \times n\) 的矩阵中, 机器人从 \((0, 0)\) 开始, 只能向右或向下移动, 不能进入行坐标和列坐标的数位之和大于 \(k\) 的格子

  • 回溯