剑指offer笔记(1)
Table of Contents

《剑指Offer》(应该是第一版) 读书笔记。

第一章 面试流程

面试的形式：

电话面试：

对于远程共享桌面面试，一般是当场编码：

现场面试：

行为面试：

关于简历中的项目经历：

一个介绍项目经历的例子：

微软 Winforms 是微软 .NET 中的一个 UI 平台（Situation），本人的工作是在添加少量新功能之外负责维护已有的功能（Task）。新的功能主要是让 Winforms 控件的风格和 Win7 的风格保持一致。在维护方面，对于较难的问题我能使用 WinDbg 等工具进行调试（Action）。在过去两年中我总共修改了超过 200 个 Bug（Result）。

对于项目还有可能被问到如下问题：

关于简历中的技能：

为什么跳槽：

技术面试：

提问环节：

第二章 面试所需要的基础知识

C++中有哪4个与类型转换相关的关键字，分别应该在什么场合下被使用？

C++ 空类型的 sizeof

  1. 当定义一个空的类型，没有任何成员变量或者成员函数，对该类型求 sizeof ，得到的结果为 1 ，原因是当我们声明该类型实例的时候，它都必须在内存中占有一定的空间，至于占多少空间，由编译器决定，VS 中每个空类型的实例要占用 1 个字节的空间。
  2. 在上述类型中添加一个析构函数和一个构造函数，则再求 sizeof 的结果是 1 ，原因是调用析构函数和构造函数只需要知道函数的地址即可，而这些函数的地址只与其类型相关，而与类型的实例无关。
  3. 如果把析构函数标记为虚函数，则求 sizeof ，在 32 位机器上得到 4 ， 在 64 位机器上得到的是 8 。原因是，编译器一旦发现一个类型中有虚函数，就会为该类型生成一个 虚函数表 ，并在该类型的每一个实例中添加一个指向虚函数表的指针。

C++ 拷贝构造函数定义

class A {
 public:
  A(int n) {
    value = n;
  }

  // 编译出错，实参到形参的传值又会调用拷贝构造函数，形成递归调用
  A(A other) {
    value = other.value;
  }

  // 正确的拷贝构造函数
  A(const A &other) {
    value = other.value;
  }

  void print() {
    cout << value << endl;
  }

 private:
  int value;
};

面试题1：赋值运算符的实现

// 题目：如下为类型 CMyString 的声明，请为该类型添加赋值运算符函数
class CMyString {
 public:
  CMyString(char *pData = NULL);
  CMyString(const CMyString &str);
  ~CMyString();

  CMyString& operator=(const CMyString& str);

  void Print();

 private:
  char *m_pData;
};

实现赋值运算符函数要注意：

// 实现赋值运算符函数
// 利用局部变量自动释放原有内存
CMyString& CMyString::operator=(const CMyString& str) {
  if (&str != this) {
    CMyString strTmp(str);
    // 与临时变量交换成员指针，这样 strTmp 析构时自动释放原有内容的内存
    char *pTmp = strTmp.m_pData;
    strTmp.m_pData = m_pData;
    m_pData = pTmp;
  }
  return *this;
}

面试题2：单例模式的实现

Singleton 模式，实现一个只能生成一个实例的类。

设计模式经典 GoF 定义的单例模式需要满足以下两个条件：

如果系统有类似的实体（有且只有一个，且需要全局访问），那么就可以将其实现为一个单例。实际工作中常见的应用举例：

Lazy Singleton

Lazy initialization，要用到时才分配资源

Eager Singleton
Meyers Singleton
class Singleton {
 public:
  static Singleton& Instance() {
    static Singleton instance_;  // 使用 local static 对象
    return instance_;
  }

 private:
  // 构造函数声明为私有，防止外部显式构造新实例
  Singleton()   {
    cout << "Singleton 类构造函数" << endl;
  }
  ~Singleton() {}  // 防止外部对单例指针进行 delete 操作

  // 下面两个函数不提供实现，防止显式调用
  Singleton(const Singleton&);
  Singleton& operator=(const Singleton&);
};

Scott Meyers在《Effective C++》（Item 04）中的提出另一种更优雅的单例模式实现，使用local static对象（函数内的static对象）。当第一次访问Instance()方法时才创建实例。

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

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

就是 leetcode 的一道题： https://leetcode.com/problems/search-a-2d-matrix-ii/

第一种解法，分治+二分查找。时间复杂度 O(m * log(n))，m 为矩阵行数，n 为矩阵列数。

第二种解法，时间复杂度 O(m + n)，从矩阵右上角开始向左或下进行搜索。以矩阵右上角元素为根节点，想象为一棵 BST（Binary Search Tree）。

第二种解法如何想到？从一个“角”上开始查找，利用矩阵本身的性质。本题除了从右上角出发，也可以从左下角出发，但左上角和右下角不行。

单测构造：

C 语言风格字符串

char str[10];
strcpy(str, "0123456789");  // 错误，"0123456789" 实际长度为 11，末尾有 '\0'

面试题4：替换空格

设计一种方法，将一个字符串中的所有空格替换成 %20 。你可以假设该字符串有足够的空间来加入新的字符，且你得到的是“真实的”字符长度。
对于字符串"Mr John Smith", 长度为 13，替换空格之后的结果为"Mr%20John%20Smith"

分析：字符串就是数组，如果允许另开一个数组，从前向后替换很容易写出 O(n) 的算法。如果不允许开新数组，那么从前向后替换的时间复杂度为 O(n^2)，因为每替换一次后面的字符都要移动。如果从后向前进行替换（设置两个指针，一个指向原字符串末尾，一个指向替换后的新字符串末尾），则可以实现每个字符只移动一次，这样时间复杂度仍为 O(n)，不过需要先扫描一遍原字符串并计算新字符串的长度。

链表

动态数据结构，插入、删除节点效率高；不支持随机存取，查找效率低。

struct ListNode {
  ListNode(int v_) : val(v_) {
    next = NULL;
  }
  int val;
  ListNode *next;
};

// 向链表中添加节点
void add_node_list(ListNode *&head, int val) {
  //...
}

注意向链表中插入节点的函数，函数参数中头指针要用 ListNode& 或者 ListNode* 类型。向一个空链表中插入一个节点时，新插入的节点就是链表的头指针，由于此时会改动头指针，必须用指针引用或二级指针，否则除了这个函数后 head 仍将为 NULL。

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

如果允许修改链表 ==> 链表逆序。

不允许修改链表，使用栈或者递归。

struct ListNode {
  ListNode(int v_) : val(v_), next(NULL) {}

  int val;
  ListNode *next;
};

// 递归实现逆序打印链表
void print_list_reverse_r(ListNode *head) {
  if (head == NULL) {
    return;
  }
  print_list_reverse_r(head->next);
  cout << head->val << endl;
}

面试题6：重建二叉树

给出一棵二叉树的“先序+中序”遍历或者“中序+后序”遍历，重建这棵树。

这题不知道做过几遍了，以先序为例，先序中第一个节点一定是整棵树的根节点，找到根节点在中序遍历中的位置，这样就得到了根节点的左右子树，然后递归去处理即可。

测试用例的设计：

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

push 操作永远向 stack1 中添加元素；pop 操作永远从 stack2 中取出元素，当 stack2 为空时，将 stack1 中所有元素 pop 进 stack2 后再从 stack2 取出元素。

面试题7-2：用两个队列实现一个栈

方法：用一个队列为主队列，一个队列为辅助队列存放临时元素。

查找与排序

排序，各种排序的特点，快速排序的实现等。平均时间复杂度、最坏时间复杂度等都要掌握。

例子，数组本身已经排好序了，而每一轮排序时都以最后一个元素为 pivot ，此时快速排序时间复杂度为 O(n^2)

例子2：

Q: 请实现一个排序算法，时间复杂度要求 O(n)

A: 排序的对象是什么？

Q: 数字，要求对所有员工的年龄排序。

A: 能否使用辅助空间？

Q: 可以，不能超过 O(n)

学会提问，了解问题的背景、细节。 O(n) 说明只能扫描一遍数组，利用计数排序，开一个数组记录每个年龄出现的次数（假设年龄范围 0 到 99）。

面试题8：旋转数组中的最小元素

旋转数组：数组 {1, 2, 3, 4, 5, 6, 7, 8} right rotate 3 位后得到 {6, 7, 8, 1, 2, 3, 4, 5}

输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。

O(n) 复杂度的解法肯定是不行的，要求 O(lg n)

如果没有重复元素，直接利用二分思想。如果 nums[left] < nums[mid] ，说明 rotate 前的首元素在右半段，否则在左半段；终止条件是左右两个指针相邻，返回小的那个。

有重复元素的时候，二分会有问题：

{2, 2, 2, 2, 2, 2, 2, 2, 0, 1, 1, 2} 和 {2, 2, 2, 0, 2, 2, 2, 2, 2, 2, 2, 2}， 我们发现，当第一个数字和最后一个数字，还有中间那个数字全部相等的时候，二分查找法就崩溃了，因为它无法判断到底该去左半边还是右半边。这种情况下，我们将左指针右移一位，略过一个相同数字，这对结果不会产生影响，因为我们只是去掉了一个相同的，然后对剩余的部分继续用二分查找法，在最坏的情况下，比如数组所有元素都相同，时间复杂度会升到O(n)。

面试题9：斐波那契数列

直接用递归效率太低；利用循环+缓存，时间复杂度 O(n)。

实际上利用数学公式，还有 O(log(n)) 的方法：

\begin{equation}
\begin{bmatrix}
f(n) & f(n-1) \\
f(n-1) & f(n-2)
\end{bmatrix}
=
\begin{bmatrix}
1 & 1 \\
1 & 0
\end{bmatrix} ^{n-1}
\end{equation}

这样转化为求一个矩阵的 n 次方问题：要求 n 次方，可以先求 n/2 次方，于是可以利用递归。

变态跳台阶

一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。

就是求斐波那契数列。

一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

要么直接跳到 n 级，要么从其他级跳过来，因此：

f(n) = f(n-1) + f(n-2) + ... + f(1) + 1

f(n-1) = f(n-2) + f(n-3) + ... + f(1) + 1

注意，将第二个式子代回第一个，有 f(n) = 2*f(n-1)

于是 f(n) = 2^(n-1)

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

输入一个 10 进制整数，输出其二进制表示中 1 的个数。

先判断整数的二进制表示中最右边一位是不是 1 。接着把输入的整数右移一位，再判断最右边一位是不是 1。这样每次移动一位，直到整个整数变成 0 为止。如何判断最右边一位是不是 1？与整数 1 进行与运算：

int count_binary_ones(int num) {
  int cnt = 0;
  while (num) {
    if (num & 1) {
      ++cnt;
    }
    num >>= 1;
  }
  return cnt;
}

这个时间复杂度是 O(lg n)，n 是整数大小，因为把整数右移 1 位和把整数除以 2 是等价的。

上面代码还有问题。如果输入的整数为负数怎么办？负数的最高位为1，右移后最高位仍为 1，但如果一直做右移运算，最终数字会变成 0xFFFFFFFF 而陷入死循环。

这里介绍一个性质，任意整数 n，n 与 (n - 1) 进行与操作可以将 n 的二进制的最右边一个 1（不一定是最右边一位）变为 0。
（把一个整数减去 1，再和原整数做与运算，会把该整数最右边一个 1 变成 0。）

利用这个性质可以解决这一题：

int count_binary_ones(int num) {
  int cnt = 0;
  while (num) {
    ++cnt;
    num = num & (num - 1);
  }
  return cnt;
}

这个解法效率更高，因为循环次数只与 n 中 1 的实际个数有关。

二进制其他题目：

Related