《剑指Offer》记录
第1章 面试的流程
- 编程时应注意的三点：
- 思考清楚再开始编码；
- 良好的代码命名和缩进对齐；
- 能够单元测试；
-
现场面试时，记得准备几个问题。（每轮面试的最后，面试官可能会让面试者问问题）
-
项目经验的描述（STAR）
- Situation：简短的项目背景；
- Task：自己完成的任务；
- Action：为了完成任务自己做了哪些工作，怎么做的；
- Result：自己的贡献；
常被问的问题包括:
- 你在项目中遇到的最大的问题是什么？
- 在项目中你学到了什么？
- 面试中应聘者需要具备的素质：
- 基础知识扎实全面，包括编程语言、数据结构（链表、二叉树...）、算法（查找、排序...）等；
- 写出正确的、完整的、鲁棒的高质量代码（边界条件、特殊输入...）；
- 思路清晰地分析、解决复杂问题；
- 从时间、空间复杂度两方面优化算法；
- 优秀的沟通、学习、发散思维能力；
- 高质量代码的例子——将字符串转换成整数 int StrToInt(char* string)，你是否能考虑到下面几个方面？
- 判断指针string是否为空；
- 正负号；
- 非数字字符；
- 数值溢出（临时变量用long long，若超过int范围报错，否则返回int值）；
第2章 面试的基础知识
- 编程语言（如C++）
面试题1 为CMyString实现赋值运算符。
class CMyString
{
public:
CMyString(char* pData=NULL);
CMyString(const CMyString& str);
~CMyString(void);
private:
char* m_pData;
};
考虑因素：
- 返回值类型声明为该类型的引用（允许连续赋值），并且函数结束前返回*this。
- 传入参数声明为常量引用；
- 释放实例自身已有的内存；
- 判断传入参数和当前实例是否为同一个实例；
高阶：
- 考虑申请内存失败的情况。方法：创建一个临时实例，将其与本身交换。
-
数据结构的例子：向单链表尾部插入一个数据。需要注意的是，由于当输入链表为空时，会修改指向输入链表的指针，因此要将输入指针设为指向指针的指针，否则出了这个函数，它仍是一个空指针。
-
算法和数据操作：
面试题8：旋转数组（例如[3, 4, 5, 1, 2]）中的最小值。需要考虑的内容：
- 使用二分法；
- 本身数组是排序的（即没有断点）；
- 数组中有相同数字的情况（在某一部分出现这种情况则只能顺序查找）；
面试题9的相关题目：斐波那契的变体
用一个2x1的小矩形去覆盖2xn的大矩形，有多少种方法？本质仍是斐波那契数列。
面试题10：二进制中1的个数。
常规解法：
//与 1、10、100、1000依次相与
int NumberOf1(int n)
{
int count = 0;
usigned int flag = 1;
while(flag)
{
if(n & flag)
count++;
flag = flag << 1;
}
return count;
}
高阶解法：
//n-1会将n的右数第一个1变成0，右边的所有0变成1，so (n-1) & n 抹去了n的右数第一个1
int NumberOf1(int n)
{
int count = 0;
while(n)
{
++count;
n = (n-1) & n;
}
return count;
}
第3章 高质量的代码
-
面试题13：在O(1)时间删除链表节点
如果遍历链表找到目标节点的前驱，并进行删除，则需要O(n)的时间，要在O(1)时间内删除节点，采用的方法是将目标节点的后继复制到目标节点，并删除目标节点的后继节点！
需要注意的内容包括：
- 要删除的不是尾节点；
- 链表只有一个节点；
- 链表有多个节点，删除尾节点；
第4章 解决面试题的思路
-
面试题26：复杂链表的复制
复杂链表的节点不仅包含一个指向下一个节点的指针pNext，还有一个指向链表中任意节点或者NULL的指针pSibling。
- 方法1：第一遍按单链表的方式复制链表，同时记录A->A'的映射关系，第二遍复制pSibling；
-
方法2：第一步，在每个A后面插入A'，第二步，插入pSibling，第三布将链表按奇偶拆分长两部分；
第5章 优化时间和空间效率
- 面试题29：数组中出现次数超过一半的数字
- 解法一：基于partition的O(n)算法。如果一个数出现超过一半，那么数组排序后，它一定位于中位数处！因此把问题转换成寻找第k大的数！用快排的思想，每次随机选一个数字作为分隔，把比这个数小的都移到这个数前面，大的都移到这个数后面，然后返回这个数在数组中的位置i，如果正好是k，那么就找到了，否则，如果i>k，就在i前继续寻找，如果i<k则在后部继续寻找。书上说这个方法是O(n)的，《算法导论》上有证明。
- 解法二：根据数组特点找出O(n)算法。如果一个数出现超过一半，那么它出现得比其他所有数加起来都多！方法：遍历数组，保存上一次出现的数，当前数和上个数相同是，记录次数+1，不相等则记录次数-1，如果次数减为0，下次需要记录当前数字。最后保存的数字，可能就是我们要找的。
- 上面两个方法找出来的数，都需要一个O(n)的判定函数来进行判定，它是不是真的出现了超过一半次数。
- 面试题30：最小的k个数
- 解法一：利用partition的O(n)算法。
- 解法二：最小堆。特别适合海量数据的场景。
-
面试题31：连续子数组最大和
解法：从头逐个累加，若当前累加结果小于零，则抛弃当前结果，将和置零，从下一个数字开始重新累加。要持续判断当前和是否大于当前最大和。 -
面试题32：从1到n整数中1出现的次数
实例分析：以21345为例，我们把它分成两段，1-1345和1346-21345，第二段是20000个数。我们来看1346-21345。这一段，1出现在首位有10000次（如果首位为1则不足10000次，而是1345+1次）。再看这一段中，1出现在后4位是什么情况，我们进一步把1346-21345分解成1346-11345和11346-21345，即两个10000，那么这4位中，任意一位为1时，其他3位可以任选0-9，因此出现次数为2*103。代码直接贴图了：
注意，复杂度是O(logn)哦！ -
面试题33：把数组排成最小的数
解法：两个字符串m和n，可以拼成mn也可以拼成nm，于是定义一个比较方法，若mn<nm则m<n，即m应该放在n前面。因此对数组进行排序，然后拼接即可。 -
面试题34：丑数
LeetCode里做过，题解264. Ugly Number II，感觉自己写的代码好优美呢哈哈哈哈哈。 -
面试题36：数组中的逆序对
解法：用归并排序的想法做。假设数组的前面一半和后面一半已经各自排好序，那么合并时候，依次取两个部分尾部较大的数写入新数组，如果取的是前面一半的数，那么当前后面一半还剩的数，都会跟它构成逆序数！
第6章 面试中的各项能力
- 知识迁移能力
面试题39：二叉树的深度
- 如果是求二叉树深度，那么直接递归进行遍历即可，因为对于某个节点只需要求左右子树中深度更深的一个。
- 如果是判断一棵树是否为平衡二叉树（左右节点高度差不超过1），那么需要使用后续遍历，以免重复计算。
面试题40：数组中只出现一次的数字
一个整形数组中，除了两个数字以外，其他数字都出现了两次，请找出这两个数字。
- 如果只有一个数字出现一次，其他数字出现两次，那么将所有数字异或得到的结果就是那个数字（其他数字两次异或抵消了）；
- 问题转换成，怎么把现在的数组分成两部分，让这两部分每部分只包括一个只出现一次的数字。
- 因为两个只出现一次的数字不同，那么对它们求异或，它们至少有一位二进制是不同的，根据这个二进制位，将原数组分为两个数组，那么每个小数组就只包含一个只出现一次的数字了！
面试题41：和为s的两个数字 VS 和为s的连续正数序列（都是排序数组）
- 和为s的两个数字：两个指针，一个代表子序列的头head，一个代表子序列的尾tail，若当前和小于s，则tail+=1，若当前和>s，则head+=1。
- 和为s的连续正数序列：与上面类似，当前和超了，则抛弃较小的数，当前和不足，则加入一个更大的数。
面试题42：翻转单词顺序 VS 左旋转字符串
- 翻转单词顺序：二次反转策略，先把整个字符串翻转，再逐个翻转单词。
- 左旋转字符串：左旋m位，则将原字符串按m分为两部分，分别翻转两部分，再整个翻转。
- 抽象建模能力
面试题43：n个骰子的点数。
n个骰子扔地上，s为朝上一面的点数和，求所有s的可能值及其概率。
- 方法一：递归统计；
-
方法二：循环思路，当前抛了m个筛子，抛第m+1个的时候，和为n的数目为前m次和为您n-1、n-2、n-3、n-4、n-5、n-6的总数！
代码直接贴过来：
面试题45：约瑟夫环
- 用环形链表模拟。
- 数学公式。证明如下：
设f(n, m)表示在0, 1, …, n-1中每次删掉第m个数字后剩下的数字，这个数字k = (m-1)%n；
删除k后剩下的数字为0, 1, …, k-1, k+1,…, n-1，并且下次从m+1开始删，相当于序列为k+1,…, n-1, 0, 1, …, k-1，该序列最后剩下的数字也一定是关于n和m的函数，不过这个序列不是从0开始计数的，因此我们设f’(n-1, m)是在序列k+1,…, n-1, 0, 1, …, k-1中每次删除第m个数字剩下的数字，那么f(n, m) = f’(n-1, m)。
我们将k+1,…, n-1, 0, 1, …, k-1序列映射到0, 1, …, n-2的函数设为p，p(x) = (x-k-1)%n，p-1(x) = (x+k+1)%n, 因此
f(n, m) = f’(n-1, m) = p-1[f(n-1, m)] = [f(n-1, m)+k+1]%n = [f(n-1, m)+(m-1)%n+1]%n = [f(n-1, m)+m]%n
递推公式及代码如下：
- 发散思维能力
这部分题好多是涉及语言特点的，比如C++的类等，我这方面还没有准备，没有学好，先简单记一下，可能语言过关了再回头看会好一些。
面试题46：求1+2+...+n
不准用乘除、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）
-
利用构造函数
-
利用虚函数
-
利用函数指针
-
利用模板类型
面试题47：不用加减乘除做加法
用位运算！不考虑进位=a^b，进位=a&b<<1，需要循环进行，直到不产生进位！
相关问题：不用新变量交换两个变量的值。
- a = a + b
b = a - b
a = a - b - a = a ^ b
b = a ^ b
a = a ^ b
面试题48：不能被继承的类
-
把构造函数设为私有函数
-
使用友元
第7章 两个面试案例
略，主要还是要把细节考虑到，如参数的检查，边缘条件，错误输入等。
第8章 英文版新增面试题
-
面试题51：数组中重复的数字
一个长度为n的数组里所有数字都在0到n-1之间，某些数字是重复的，但不知道有几个是重复的，请找出任意一个重复数字。
解法：从头到尾扫描数组，当扫描到下标为i值为m的数字，若m=i，则继续扫描下一个数字，若m≠i，比较它和第m个数字，若相等，则找到了一个重复数字，否则交换m和i位置的数字，即将当前数字归位。 -
面试题57：删除链表中重复的节点
需要注意的是：如果链表的头可能修改，则传入参数的时候不能是ListNode* pHead，而需要是ListNode** pHead！ -
面试题64：数据流中的中位数
解法：我们维护两个堆，一个大顶堆b，一个小顶堆s。我们保证b的最大值比s的最小值要小，那么b里所有值都比s小了，然后让两个堆中元素个数相等，那么通过两个堆的堆顶就能求中位数啦。
具体可以在数字总数目为偶数时，把数字插入s，数目为奇数时，插入b。但还是要根据数字的大小，维持b的顶比s的顶小。 -
面试题65：滑动窗口的最大值
这题之前根神跟我们说过，确实设计很精巧。
- 可以用带最大值的队列做（用两个带最大值的栈模拟队列）；
- 用deque做，贴代码吧：
vector<int> maxInWindows(const vector<int>& num, unsigned int size)
{
vector<int> maxInWindows;
if(num.size() >= size && size >= 1)
{
deque<int> index;
for(unsigned int i = 0; i < size; i++)
{
while(!index.empty() && num[i] >= num[index.back()])
index.pop_back();
index.push_back(i);
}
for(unsigned int i = size; i < num.size(); i++)
{
maxInWindows.push_back(num[index.front()]);
while(!index.empty() && num[i] >= num[index.back()])
index.pop_back();
if(!index.empty() && index.front() <= (int)(i - size))
index.pop_front(i);
}
maxInWindows.push_back(num[index.front()]);
}
return maxInWindows;
}
