作者按：因为是和同学合买的书，所以不方便在书上勾画。特此记录。
1、面试题1：赋值运算符函数
- 内存泄漏、常量引用
2、面试题3：数组中重复的数字
- p38～p39：C/C++，在32位系统上，对任意指针求sizeof，得到的结果都是4。在C/C++中，当数组作为函数的参数进行传递时，数组就自动退化为同类型的指针。
- 一维数组、char* 和char []
3、面试题4：二维数组中的查找
- 二维数组
- 二维数组在内存中占据连续的空间（这一点与一维数组相同）。在内存中从上倒下存储各行元素，在同一行中按照从左到右的顺序存储。因此我们可以根据行号和列行计算出相对于数组首地址的偏移量，从而找到对应的元素。
- C++中表示二维数组的4种方法：
#include<cstdio>
#include<vector>
//静态二维数组，常量数组，不能二次修改
int matrix[][4] = {{1, 2, 8, 9}, {2, 4, 9, 12}, {4, 7, 10, 13}, {6, 8, 11, 15}};
//使用一维数组表示二维数组
int row, column = 2;
// columns的值是matrix的列数
int target = matirx[row*columns+column]; // /matrix[row*columns+column]等价于matrix[row][column]
//动态二维数组
//申请空间
int** matrix = new int*[rows];
for(int i=0;i<rows;i++)
{
matrix[i] = new int[columns];
}
//释放空间
for(int i=0;i<rows;i++)
{
delete[] matrix[i];
}
delete[] matrix;
//利用vector创建二维数组
vector<vector<int> > matrix
int row = matrix.size();
int columns = matrix[0].size();
int target = matrix[row][column];
4、面试题5：替换空格
- C/C++中每个字符串都以字符
'\0'作为结尾。这样需要注意的是：每个字符串都有一个额外的字符开销。 - p49：举例说明char []和char* []的区别。理解如下：
char str1[] = "hello world";
char str2[] = "hello world";
char* str3 = "hello world";
char* str4 = "hello world";
str1 != str2：str1和str2 表示两个不同常量字符串的初始化地址，所以不相同；
str3 = str4：str3和str4 表示两个char类型指针变量，我们无须为它们分配内存以存储字符串的内容，只需要把它们指向"hello world"这个常量字符串在内存中的地址就可以了。常量字符串在内存中只有一个拷贝，所以str3 = str4。
- 解题思路：判断字符串是否有效=>计算字符串的长度和字符串中的空格数=>修改前/后字符串末尾指针p1和p2=>进入while循环，判断条件p1>=0 && p1<p2=> 如果p1走到空格，则p2依次填入
'0''2''%'同时p2向前移动；否则，将p1所指位置的字符符知道p2所在位置=>p1--=>直至推出while 循环。 - 在合并两个数组（包括字符串）时，如果从前往后复制每个数字（或字符）则需要重复移动数字（或字符）多次，那么我们可以从后往前复制，这样就能减少移动的次数，从而提高效率。
5、面试题6：从尾到头打印链表
- 单向链表 vs 数组
- 数组名是指针常量
- 循环、递归和栈3个相互关联的概念的理解
- 解题思路：有两种解法，一是利用C++的stack结构，另外一种就是利用递归。这两种方法都要先判断链表首节点及其下一个节点是否存在。如果存在，就利用while循环，从头到尾将节点依次压入栈中（stack.push()）。再利用stack.top()和stack.pop()函数将数据取出，这样就能做到在不改变原始链表的结构下，从尾到头输出链表数据。
- 本题求解代码中有两点值得注意：
//定义stack：
#include<stack>
std::stack<ListNode*> nodes;
//vector类型作为函数的返回值
vector<int> values;
values.push_back(pNode->val);
return values;
//举例
vector<int> test;//建立一个vector
test.push_back(1);
test.push_back(2);//把1和2压入vector这样test[0]就是1,test[1]就是2
6、面试题7：重建二叉树
- 树的逻辑结构：除根节点之外每个节点只有一个父节点，根节点没有父节点；除叶节点之外所有节点都有一个或多个字节点，叶节点没有子节点。
- 前序/后序/中序遍历、深度优先遍历、宽度优先遍历
- 二叉树、二叉搜索树
- 堆、红黑树
- 常量数组获取首地址，vector容器获取首地址
// 直接将数组名a（数组元素首地址）作为实参传给相应函数
int a[5] = {1, 2, 3, 4, 5};
// a.data()获取数组元素的首地址，vector 的 data 方法是在C++11中才被支持的
vector<int> a;
a.data();
- C++环境下，在class类中定义public函数时，不允许先声明后使用。
7、面试题9：用两个栈实现队列
- C++ template<typename Dtype> 类型模版，较为简单的例子就是：
// 例入：设计两个数的加法
// 原始求解代码
int sum(int a,int b);
double sum(double a,double b);
float sum(float a,float b);
// 使用template <typename T>
template <typename T>
T sum(T a, T b)
{
return a+b;
}
- 用栈表示队列、用队列表示栈
8、面试题10：斐波那契数列
- 通常基于递归的实现方法代码会比较简洁，但性能不如基于循环的实现方法。
- 循环、递归、排序、查找、回溯法、动态规划、贪心算法、位运算
- 递归由于是函数调用自身，而函数调用是有时间和空间的小号的：每一次函数调用，都需要在内存栈中分配空间以保存参数、返回地址及临时变量，而且，往栈里压入数据和弹出数据都需要时间。
- 用递归分析问题，用循环写代码。
- 除了效率之外，递归还有可能引起更严重的问题：调用栈溢出。在前面的分析中提到需要为每一次函数调用在内存栈中分配空间，而每个进程的栈的容量是有限的。
- C语言的教材中会用以下代码求解斐波那契数列并用来讲解递归函数。不可否认的是，这种表示方法确实可以很好的表达递归的思想，但是这种递归的解法有很严重的效率问题。一些数列的中间项被重复计算。
long long Fibonacci(unsigned int n)
{
if(n<=0)
return 0;
if(n==1)
return 1;
return Fibonacci(n-1) + Fibonacci(n-2);
}
- 类似于这种循环/递归题目，其测试样例设计功能测试（取值范围内的数值）、边界值测试（大于、等于和小于边界值的数值）和性能测试（因为在写Fibonacci相关的编程题的时候涉及循环，所以为了测试代码的性能，选择取值范围内较大的数值）。
9、面试题11：旋转数组的最小数字
- 手撕各种排序，并比较不同排序算法的优劣。能从额外空间消耗、平均时间复杂度和最差时间复杂度等方面去比较它们的优缺点。
- 查找：顺序查找、二分查找、哈希表查找和二叉排序树查找
- 如果面试题是要求在排序的数组（或者部分排序的数组）中查找一个数字或者统计某个数字出现的次数，那么我们都可以尝试用二分查找算法。
- 这道面试题中有两个陷阱：第一个是当旋转数组本身就是非递减数组（即数组的第一个数值<最后一个数值），这时直接输出数组的第一个元素即可；另外一个是当index1，index2和indexMid指向的三个数字相等，只能采取顺序查找，因为不能确定numbers[indexMid]属于前递增序列还是后递增序列。
10、面试题12：矩阵中的路径
- 用回溯法解决的问题的所有选项可以形象地用树状结构表示。
- 指针传递 vs 引用传递
- 这道题递归返回条件有两个：一是找到了包含指定string的路径；二是返回hasPath的bool类型值，即沿着可能结果树中的某个节点一直走到叶节点都没有找到指定是string，返回false。
- 通常在二维矩阵上找路径这类问题都可以应用回溯法解决。
- 相同的问题还有面试题13：机器人的运动范围。
11、面试题14：剪绳子
- 如果面试题是求一个问题的最优解（通常是求最大值或者最小值），而且该问题能够分解成若干个子问题，并且子问题之间还有重叠的更小的子问题，就可以考虑用动态规划解决这个问题。除此之外，动态规划问题还有一个特点，从上至下分析问，从下至上求解问题。
- ……。由于子问题在分解大问题的过程中重复出现，为了避免重复求解子问题，我们可以用从下往上的顺序先计算小问题的最优解并存储下来，再以此为基础去求大问题的最优解。
- 剪绳子这道题有一个内在要求：除非绳子长度是1，否则你就一定要剪一刀。
- 如果使用贪心算法，涉及到数学公式：
3(n-3) > 2(n-2) >n，n>=5。
12、面试题15：二进制中1的个数
- 位运算是把数字用二进制表示之后，对每一位上0或者1的运算。
- 除法的效率比移位运算要低得多，在实际编程中应尽可能地用一位运算符代替乘除法。
- 一个整数减去1之后再和它自己做与运算，这个整数中唯一的1就会变成0。这样就可以判断一个整数是不是2的整数次方。
13、面试题16：数值的整数次方
- 从3个方面确保代码的完整性：从功能测试、边界测试和负面测试（错误输入）3个方面设计测试用例，以确保代码的完整性。
- 这道面试题看似简单，却隐含各种陷阱和小技巧：
如果底数是0，指数是负数或0怎么办？00是非法的。
如果底数正常，但指数是负数或0怎么办？如：a-2。
使用何种错误处理方式：返回值？全局变量？抛出异常？
利用a的n次方公式，这样可以利用递归代替循环。
double PowerWithUnsignedExponent(double base, unsigned int exponent)
{
/*
double result = 1.0;
for (int i = 1; i <= exponent; ++i)
{
result *= base;
}
*/
if(exponent == 0)
return 1;
if(exponent == 1)
return base;
// 利用公示
// 利用右移 >> 代替 /
double result = PowerWithUnsignedExponent(base, exponent>>1);
result *= result;
// 用位与运算符代替求余运算符（%）
if ((exponent & 0x1) == 1)
result *= base;
return result;
}
14、面试题17：打印从1到最大的n位数。
- 大数问题。
- 如何在每一次增加1之后快速判断是不是到了最大的n位数是本题的一个陷阱；因为使用字符串表示n位数，那么不足n位时，前面几位补0，在打印的时候就会出现“098”这种情况，不符合阅读习惯。能不能按照我们的阅读习惯打印数字是面试官设置的另外一个小陷阱。
15、面试题18：删除链表的节点
- 删除节点之前，要判断链表中是否存在该节点，只这一步就需要O(n)的时间复杂度。
- 删除节点时，要判断该节点是否时头节点、尾节点、中间节点、链表中是否只有一个节点且即是待删除的节点等等。
- 通常删除节点时，需要从头节点开始遍历，然后找到待删除的节点一通操作:
ListNode* pNode = *pListHead;
while(pNode->m_pNext != pToBeDeleted)
{
pNode = pNode->m_pNext;
}
pNode->m_pNext = pToBeDeleted->m_pNext;
delete pToBeDeleted;
pToBeDeleted = nullptr;
但是，此处提供了一种新思路：因为待删除节点的下一个节点可以在O(1)时间内找出，将下一个节点的值复制到待删除节点的位置，然后删除下一个节点即可。
- 关于执行delete/delete[]操作后，还要给指针赋空值（nullptr）的原因：
delete是释放指针指向的内存，并不是指针本身所占有的内存。杜绝指针变成野指针的错误。详见：delete一个指针之后,要记得设置为NULL
16、面试题19：正则表达式匹配
- 首先要明白什么是正则表达式？正则表达式与字符串之间如何让匹配？
17、面试题20：表示数值的字符串
- 表示数值的字符串遵循模式A[.[B]][e|EC]或.B[e|EC]。
- 这道题需要依次从整数部分、小数部分和指数部分各个数位判断是否满足要求，并且因为涉及函数之间的参数传递，所以各个函数参数传递的是存放字符串数组首地址内存的地址，这样*str一直在从高位向低位遍历，而不是一直指向字符串数组常量的首地址。
- 全面考虑数值整数、小数、指数部分的特点，比如哪些部分可以出现正负号，而那些部分不能出现；哪些部分可以没有，哪些部分不可或缺等。
18、面试题21：调整数组顺序使奇数位于偶数前面
- 这道题本身求解的时候只需要两个指针，一个从前向后遍历该一维数组，负责找到数组中的偶数，一个从后向前遍历，负责找到数组中的奇数；当两个指针恰好相邻，且偶数指针的值大于奇数指针的值的时候，那偶数指针之前的数组元素就全部是奇数了，奇数指针之后的元素就全部是偶数了。
- 但newcoder上对这道题做了改变，要求奇数与奇数，偶数与偶数的相对位置不变。那就是这道题暴力求解即可。时间复杂度是O(n2)。
19、面试题22：链表中倒数第k个节点
- 这道题本身可以用暴力求解，也可以按照剑指offer上的解题思路求解。
- 这道题是典型的需要考虑代码鲁棒性的问题。
- 求链表的中间节点。如果链表中的节点总数为奇数，则返回中间节点；如果节点总数是偶数，则返回中间两个节点的任意一个。为了解决这个问题，我们也可以定义两个指针，同时从链表的头节点出发，一个指针一次走一步，另一个指针一次走两步。当走得快的指针走到链表的末尾时，走得慢的指针正好在链表的中间。
- 当我们用一个指针遍历链表不能解决问题时，可以尝试用两个指针来遍历链表。可以让其中一个指针遍历的速度快一些，或者让它先在链表上走若干步。
20、面试题23：链表中环的入口节点
- 把一个问题分解成几个简单的步骤，是一种常用的解决复杂问题的办法。为了解决这个问题，我们可以把这道题分解成3个步骤：找出环中任意一个点（即判断链表中是否存在环）；得到环中节点的数目；找到环的入口节点。
21、面试题24：反转链表
- 拿到题不要马上开始写代码，要先分析和设计。
- 这道题在分析设计阶段就要考虑需要几个指针变量：只想当前遍历到的节点、它的前一个节点、它的后一个节点。
22、面试题25：合并两个排序链表
- 这道题如果用递归求解的会简单一点。但是由于函数之间频繁的调用需要占用大量的内存空间。使用循环求解，会显得代码较为复杂，且要注意每次使用指针的时候，都要考虑这个指针此时指向哪，有没有可能时nullptr，如果是应该怎么处理。
ListNode* noMerge(ListNode* pHead1, ListNode* pHead2)
{
if(pHead1 == nullptr)
{
return pHead2;
}
if(pHead2 == nullptr)
{
return pHead1;
}
ListNode* mergeHead = nullptr;
ListNode* current = nullptr;
while(pHead1!=nullptr && pHead2!=nullptr)
{
if(pHead1->val <= pHead2->val)
{
if(mergeHead == nullptr)
{
mergeHead = current = pHead1;
}
else
{
current->next = pHead1;
current = current->next;
}
pHead1 = pHead1->next;
}
else
{
if(mergeHead == nullptr)
{
mergeHead = current = pHead2;
}
else
{
current->next = pHead2;
current = current->next;
}
pHead2 = pHead2->next;
}
}
if(list1 == nullptr)
{
current->next = pHead2;
}
else
{
current->next = pHead1;
}
return mergeHead;
}
23、面试题26：树的子结构
- 涉及到二叉树时，用到的指针比链表还要复杂。特别要注意空指针。
- 可以在这道题中学习如何构建二叉树，链表类似：
// 二叉树节点的内容
struct BinaryTreeNode
{
double m_dbValue;
BinaryTreeNode* m_pLeft;
BinaryTreeNode* m_pRight;
};
// 创建每个节点
BinaryTreeNode* CreateBinaryTreeNode(double dbValue)
{
BinaryTreeNode* pNode = new BinaryTreeNode();
pNode->m_dbValue = dbValue;
pNode->m_pLeft = nullptr;
pNode->m_pRight = nullptr;
return pNode;
}
//链接每个节点
void ConnectTreeNodes(BinaryTreeNode* pParent, BinaryTreeNode* pLeft, BinaryTreeNode* pRight)
{
if(pParent != nullptr)
{
pParent->m_pLeft = pLeft;
pParent->m_pRight = pRight;
}
}
// 用完即焚
void DestroyTree(BinaryTreeNode* pRoot)
{
if(pRoot != nullptr)
{
BinaryTreeNode* pLeft = pRoot->m_pLeft;
BinaryTreeNode* pRight = pRoot->m_pRight;
delete pRoot;
pRoot = nullptr;
DestroyTree(pLeft);
DestroyTree(pRight);
}
}
// 举例
// 树中结点含有分叉，树B是树A的子结构
// 8 8
// / \ / \
// 8 7 9 2
// / \
// 9 2
// / \
// 4 7
void Test1()
{
BinaryTreeNode* pNodeA1 = CreateBinaryTreeNode(8);
BinaryTreeNode* pNodeA2 = CreateBinaryTreeNode(8);
BinaryTreeNode* pNodeA3 = CreateBinaryTreeNode(7);
BinaryTreeNode* pNodeA4 = CreateBinaryTreeNode(9);
BinaryTreeNode* pNodeA5 = CreateBinaryTreeNode(2);
BinaryTreeNode* pNodeA6 = CreateBinaryTreeNode(4);
BinaryTreeNode* pNodeA7 = CreateBinaryTreeNode(7);
ConnectTreeNodes(pNodeA1, pNodeA2, pNodeA3);
ConnectTreeNodes(pNodeA2, pNodeA4, pNodeA5);
ConnectTreeNodes(pNodeA5, pNodeA6, pNodeA7);
BinaryTreeNode* pNodeB1 = CreateBinaryTreeNode(8);
BinaryTreeNode* pNodeB2 = CreateBinaryTreeNode(9);
BinaryTreeNode* pNodeB3 = CreateBinaryTreeNode(2);
ConnectTreeNodes(pNodeB1, pNodeB2, pNodeB3);
Test("Test1", pNodeA1, pNodeB1, true);
DestroyTree(pNodeA1);
DestroyTree(pNodeB1);
}
23、面试题29：二叉树的镜像
- 因为对递归的整体掌握不好，所以暂时还只会用循环代替递归。但是循环的过程有需要不断的创建新的变量，如果是涉及到链表或者二叉树的算法题，则可能会出现各种错误。
- 这道题在求解的时候，使用栈。
// 创建一个栈结构，里面每一个元素的类型是BinaryTreeNode*
std::stack<BinaryTreeNode*> stackTreeNode;
24、面试题29：顺时针打印矩阵
- 要求解这道题关键有两点：
1）将复杂的问题分解为简单的问题：矩阵可以继续顺时针打印的条件和顺时针打印时分为几步，执行每一步需要什么条件；
2）解决这个问题时会在代码中包含多个循环，并且需要判断多个边界条件。
25、面试题30：包含min函数的栈
- 这道题我的第一反应是在栈里添加一个成员变量存放最小的元素。但如果这个最小元素是栈顶元素的话，在pop()之后，如何在剩下的栈中元素中选出最小的元素？
- 这道题的求解方法是开辟内存建立一个辅助栈，用于存储每一个元素压入栈时最小元素。如果最小等于栈顶，那么就把其压入栈；如果最小不变，则吧辅助栈top()压入栈。
26、面试题31：栈的压入、弹出序列
- 《剑指offer》上一般使用指针表示一维数组的首元素，但是牛客网上一般时vector表示一维数组。所以在使用时就有些区别。
class Solution {
public:
bool IsPopOrder(vector<int> pushV,vector<int> popV) {
int length = pushV.size();
std::stack<int> stackData;
bool isPopOrder = false;
if(length > 0)
{
int popCount = 0;
int pushCount = 0;
while(popCount < length)
{
while(stackData.empty() || stackData.top() != popV[popCount])
{
if(pushCount == length)
break;
stackData.push(pushV[pushCount]);
pushCount++;
}
// 此时break，是因为上面的while循环都到压入序列的最后一个元素了，
// 都没有找到对应的出栈元素。
// 所以这也不用继续了。
if(stackData.top() != popV[popCount])
break;
stackData.pop();
popCount++;
}
if(stackData.empty() && popCount == length)
isPopOrder = true;
}
return isPopOrder;
}
};
27、面试题33：二叉搜索树的后序遍历序列
- 如果面试题要求处理一颗二叉树的遍历序列，则可以先找到二叉树的根节点，再基于根节点把整颗树的遍历序列拆分成左子树对应的字序列和右子树对应的子序列，接下来再递归地处理这两个子序列。
28、面试题34：二叉树中和某一值的路径
- 通过这道题，我发现我还是不具有把递归转换成循环的能力。
- 这道题牛客网上OJ的话，需要返回vector<vector<int>>，但是作者给的解题思路中只是将找到的路径简单的打印出来。所以，按照作者的解题思路，我在牛客网上找了一种解题代码如下：
/*
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};*/
class Solution {
void DFSFindPath(TreeNode* root, int resNumber,
vector<vector<int>> &pathList, vector<int> &tempPath)
{
resNumber -= root->val;
tempPath.push_back(root->val);
// 如果是叶节点， 并且路径上节点值的和等于输入的值，
// 则保存这条路径
bool isLeaf = root->left == nullptr && root->right == nullptr;
if(resNumber == 0 && isLeaf)
pathList.push_back(tempPath);
// 如果不是叶节点，则遍历它的子节点
if(root->left != nullptr)
DFSFindPath(root->left, resNumber, pathList, tempPath);
if(root->right != nullptr)
DFSFindPath(root->right, resNumber, pathList, tempPath);
tempPath.pop_back();
}
public:
vector<vector<int>> FindPath(TreeNode* root,int expectNumber) {
vector<vector<int>> pathList;
vector<int> tempPath;
if(root == nullptr)
return pathList;
DFSFindPath(root, expectNumber, pathList, tempPath);
return pathList;
}
};
