《剑指offer》笔记 - 第2章 面试需要的基础知识

c++题目应考虑的问题

• 各种输入参数的异常情况。
• 输出输出类型是否要使用引用和加const修饰。
• new之前是否要使用delete，如果这样尽量将delete放在前面，防止如果new失败又把原来的内存给delete掉了。
• 赋值操作符中要记得判断前后是不是一个对象。

赋值操作符测试用例

测试用例和记得异常情况都有哪些一样重要。

• 将一个实例赋值给另一个实例。
• 将一个实例赋值给他自己。
• 连续赋值。

实现singeleton模式的关键点

• 构造函数为私有。
• 定义一个静态实例在内部。
• 定义一个静态方法，能够通过这个方法访问这个静态实例，并且保证他在第一次访问被创建一次。
• 如果是考虑到多线程的情况要保证加锁以只创建一次。

树

• 宽度优先遍历：一层一层访问所有节点。

二叉搜索树

左子节点总是小于或等于根节点，右子节点总是大于或等于根节点。

利用前序遍历和中序遍历重建二叉树问题

$P_{57}$

栈与队列

用两个栈实现队列的问题

先都压入一个栈中，要增删的时候把所有都弹出到另一个栈，然后栈顶就是队列头了。 $P_{61}$

用两个队列实现栈

先往一个队列插，之后要增删的时候将所有都插到另一个队列除了最后一个，对最后一个进行操作，就实现了栈的操作。 $P_{62}$