【编程】：《剑指offer》题目思路整理

本文主要内容，来自于本人在阅读何海淘《剑指offer》这本书过程中，对题目解题思路的整理。牢记这些题目和思路可以帮助我们应对常见的编程面试题，我认为是很有帮助的。

题号	题目标题	题目介绍	解题思路	详解
1	赋值运算符函数		一个简单的办法是我们先用new分配新内容再用delete释放已有的内容。这样只在分配内容成功之后再释放原来的内容，也就是当分配内存失败时我们能确保 CMyString 的实例不会被修改。我们还有一个更好的办法是先创建一个临时实例，再交换临时实例和原来的实例。
3	二维数组中的查找	题目：在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。	首先选取数组中右上角的数字。如果该数字等于要查找的数字，查找过程结束；如果该数字大于要查找的数字，剔除这个数字所在的列；如果该数字小于要查找的数字，剔除这个数字所在的行。也就是说如果要查找的数字不在数组的右上角，则每一次都在数组的查找范围中剔除一行或者一列，这样每一步都可以缩小查找的范围，直到找到要查找的数字，或者查找范围为空。
4	替换空格	题目：请实现一个函数，把字符串中的每个空格替换成“%20”。例如输入“We are happy.”，则输出“We%20are%20happy.”	从后往前替换空格。
5	从尾到头打印链表	题目：输入一个链表的头结点，从尾到头反过来打印出每个结点的值。	运用栈或者递归实现。
6	重建二叉树	题目：输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建出图2.6所示的二叉树并输出它的头结点。	前序遍历第一个是根结点，对应在中序遍历中则把左右子树分开。利用这一点，不断找根节点和左右子树。
7	用两个栈实现队列	题目：用两个栈实现一个队列。队列的声明如下，请实现它的两个函数appendTail和deleteHead，分别完成在队列尾部插入结点和在队列头部删除结点的功能。	两个栈分别用于入队和出队。Stack1用于入队，每次在队列尾部插入元素，就插入Stack1栈顶；Stack2用于出队，出队时若Stack1为空，则直接弹出Stack2栈顶元素，否则则把Stack1中元素逐个按顺序压入Stack2中，再弹出Stack2栈顶元素。
8	旋转数组的最小数字	题目：把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。	二分法查找，对比中间元素和首尾元素的大小来缩小搜索范围，直至找到最小值。对于特殊情况：首尾元素和中间元素大小相等，则只好用顺序查找的方式了。
9	斐波那契数列	题目：写一个函数，输入n，求斐波那契（Fibonacci）数列的第n项。	避免递归解法。一步步地计算得到第n项。
10	二进制中1的个数	题目：请实现一个函数，输入一个整数，输出该数二进制表示中 1 的个数。例如把9表示成二进制是1001，有2位是1。因此如果输入9，该函数输出2。	输入数字不变，用一个unsigned int整数flag与输入数字做与运算，flag初始值为1，不断左移一位，便可从右至左统计输入数字中1的个数。
11	数值的整数次方	题目：实现函数 double Power（double base, int exponent），求 base 的exponent次方。不得使用库函数，同时不需要考虑大数问题。	通过不断累乘实现。注意处理底数为0以及指数为0和负数的情况。
12	打印1到最大的n位数	题目：输入数字n，按顺序打印出从1最大的n位十进制数。比如输入3，则打印出1、2、3一直到最大的3位数即999。	为了应对大数情况，应该用数组或者字符串来储存数字。运用递归可以更好地解决这个问题。
13	在O(1)时间删除链表节点	题目：给定单向链表的头指针和一个结点指针，定义一个函数在 O（1）时间删除该结点。	把带删除节点的下一个节点的值复制到待删除节点，然后删除下一个节点（间接删除了目标节点）。注意考虑特殊情况：删除尾节点，以及链表中只有一个节点。
14	调整数组顺序使奇数位于偶数前面	题目：输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数位于数组的前半部分，所有偶数位于数组的后半部分。	双指针，一个指针从左往右移动，一个指针从右往左移动，当左指针指向偶数而右指针指向奇数时，交换这两个数。
15	链表中倒数第k个结点	题目：输入一个链表，输出该链表中倒数第 k 个结点。为了符合大多数人的习惯，本题从1 开始计数，即链表的尾结点是倒数第1 个结点。例如一个链表有6个结点，从头结点开始它们的值依次是1、2、3、4、5、6。这个链表的倒数第3个结点是值为4的结点。	双指针。一个指针先从头指针走k步，另一个指针也从头指针开始便利链表，二者之间始终保持k步的距离，当第一个指针指向空指针的是时候，第二个指针正好指向倒数第k个指针。注意考虑链表为空，k = 0，以及k大于链表节点数的情况。
16	反转链表	题目：定义一个函数，输入一个链表的头结点，反转该链表并输出反转后链表的头结点。	遍历链表的时候，用三个指针分别储存：当前节点，它的前一个节点，它的后一个节点。
17	合并两个排序的链表	题目：输入两个递增排序的链表，合并这两个链表并使新链表中的结点仍然是按照递增排序的。	遍历链表的时候，可以设置一个冗余头节点，依次选择值小的那个节点来进行链接。也可以用递归的解法，确定当前节点后，其下一个节点可视为两个链表融合后的返回值。
18	树的子结构	题目：输入两棵二叉树A和B，判断B是不是A的子结构。	运用递归的方式来比较两个树。首先找到和树B根节点相同的节点，然后再比较二者的子树是否重叠。
19	二叉树的镜像	题目：请完成一个函数，输入一个二叉树，该函数输出它的镜像。	递归。先交换左右子节点，然后再分别对子节点做镜像操作。（先对子节点做镜像操作，再交换左右子节点也可以）
20	顺时针打印矩阵	题目：输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字。	一圈圈地从外向内打印元素，注意处理单行、单列、一个元素这些特殊情况。
21	包含min函数的栈	题目：定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的min函数。在该栈中，调用min、push及pop的时间复杂度都是O（1）。	两个栈，一个用于压入元素，另一个储存当前的最小值。每次入栈新元素时，将其和最小栈的栈顶元素比较，若小于它，则将其压入最小栈，否则，复制栈顶元素至最小栈。
22	栈的压入、弹出序列	题目：输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1、2、3、4、5 是某栈的压栈序列，序列4、5、3、2、1 是该压栈序列对应的一个弹出序列，但 4、3、5、1、2 就不可能是该压栈序列的弹出序列。	用一个栈来辅助判断，依次定位弹出序列中的每个元素在压栈序列中的位置，做入栈和出栈操作，如果有冲突，则说明弹出序列不对。
23	从上往下打印二叉树	题目：从上往下打印出二叉树的每个结点，同一层的结点按照从左到右的顺序打印。例如输入图4.5中的二叉树，则依次打印出8、6、10、5、7、9、11。	用一个队列来实现。先把根节点入队，然后每次节点出队时打印节点值，同时把节点的子节点依次插入队尾，直至无节点可以入队为止。
24	二叉搜索树的后序遍历序列	题目：输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。	数组的最后一个元素是根节点，利用它可以把数组分为两个子数组：左子树元素组成的数组，右子树元素组成的数组。保证左子数组的元素都小于根节点值，右子数组的元素都大雨根节点值。然后便可递归式地判断左子数组和右子数组是否可以右搜索二叉树后序遍历得到。
25	二叉树中和为某一值的路径	题目：输入一棵二叉树和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。	树的深度优先搜索，利用栈来实现。从根节点搜索所有到叶子节点的路径，判断路径节点的和是否满足要求。是则打印栈中所有元素，否则退回树的上一层。用递归实现。
26	复杂链表的复制	题目：请实现函数ComplexListNodeClone（ComplexListNodepHead），复制一个复杂链表。在复杂链表中，每个结点除了有一个m_pNext指针指向下一个结点外，还有一个m_pSibling 指向链表中的任意结点或者NULL。	复制链表中的每个节点，将其插入原节点之后。复制完所有节点之后，该链表中奇数位置的节点为原节点，偶数位置节点为复制节点。这样可以很方便地找到随随机指针的位置。然后把该链表按奇偶节点拆开即可。
27	二叉搜索树与双向链表	题目：输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。	中序遍历整个树，将树节点存在栈中，最后依次出栈连接相邻节点。也可以只用递归的方式中序遍历树，在遍历的同时连接相邻节点。
28	字符串的排列	题目：输入一个字符串，打印出该字符串中字符的所有排列。例如输入字符串abc，则打印出由字符a、b、c所能排列出来的所有字符串abc、acb、bac、bca、cab和cba。	把字符串分为第一个字符和余下字符组成的字符串。依次将原字符串中的每个字符置于首位，在接上剩余字符组合结果，就是所有可能的排列结果。用递归实现。
29	数组中出现次数超过一半的数字	题目：数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。	用快速排序法排序数组，则位于数组中间的值就是所求值。因此不需要把整个数组排序，只需要找到排序后数组中间值即可（求数组中第k大的数）
30	最小的k个数	题目：输入n个整数，找出其中最小的k个数。例如输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。	用快速排序法排序数组，则该题等价于找到第k小的数。找到该数以后，该数以及其左边的数字即为最小的k个数。也可以用大小为k的容器容纳数组中的数，遍历数组时，如果发现了比容器中最大值更小的值，则取代最大值。遍历数组之后，就可以得到最小的k个数。
31	连续子数组的最大和	题目：输入一个整型数组，数组里有正数也有负数。数组中一个或连续的多个整数组成一个子数组。求所有子数组的和的最大值。要求时间复杂度为O（n）。	两个变量，一个记录当前得到的最大子序列值，一个记录包含当前元素的最大子序列值。若后一个变量小于0，则将该变量置为0，从新开始查询。动态规划法：f(i)表示以第i个数字结尾的子数组的最大和，所有的值即为max(f(i))。
32	从1到n整数中1出现的次数	题目：输入一个整数n，求从1到n这n个整数的十进制表示中1出现的次数。例如输入12，从1到12这些整数中包含1 的数字有1，10，11和12，1一共出现了5次。	待更新。
33	把数组排成最小的数	题目：输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。例如输入数组{3, 32, 321}，则打印出这3个数字能排成的最小数字321323。	按照数字组合后的大小对数字进行排序（自定义排序）。排序后的数组按顺序组成的数字即为最小数。注意大数问题：用字符串表示数字。
34	丑数	题目：我们把只包含因子2、3和5的数称作丑数（Ugly Number）。求按从小到大的顺序的第1500个丑数。例如6、8都是丑数，但14不是，因为它包含因子7。习惯上我们把1当做第一个丑数。	已知当前最大的丑数为M，则下一个丑数一定是前面丑数乘以2，3，5后比M大的数字中的最小值。记录每次乘以数字的位置，则不需要遍历前面的每个丑数。
35	第一个只出现一次的字符	题目：在字符串中找出第一个只出现一次的字符。如输入”abaccdeff”，则输出’b’。	用哈希表统计每个字符在字符串中出现的次数。
36	数组中的逆序对	题目：在数组中的两个数字如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。	待更新。
37	两个链表的第一个公共节点	题目：输入两个链表，找出它们的第一个公共结点。	两个指针分别从两个链表头开始遍历链表，到达链表尾部的时候，将其置于另一个链表头部，开始遍历。则二者会相交于第一个重合节点。
37	两个链表的第一个公共节点	题目：输入两个链表，找出它们的第一个公共结点。	两个指针分别从两个链表头开始遍历链表，到达链表尾部的时候，将其置于另一个链表头部，开始遍历。则二者会相交于第一个重合节点。
38	数字在排序数组中出现的次数	题目：统计一个数字在排序数组中出现的次数。例如输入排序数组{1,2, 3,3,3,3,4,5}和数字3，由于3在这个数组中出现了4次，因此输出4。	二分法分别查找该数字在数组中第一次出现的位置和最后一次出现的位置。二分查找可以用递归实现。
39	二叉树的深度	题目一：输入一棵二叉树的根结点，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。	递归法求左右子树深度，根节点深度等于较大深度加1。
40	数组中只出现一次的数字	题目：一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是 O（n），空间复杂度是O（1）。	把数组分为两个子数组，每个子数组只包含一个只出现一次的数。每个子数组元素依次做异或运算，最终的结果就是那个只出现一次的数。

注解

• 左移运算符m«n表示把m左移n位。左移n位的时候，最左边的n位将被丢弃，同时在最右边补上n个0。右移运算符m»n表示把m右移n位。右移n位的时候，最右边的n位将被丢弃。但右移时处理最左边位的情形要稍微复杂一点。如果数字是一个无符号数值，则用0填补最左边的n位。如果数字是一个有符号数值，则用数字的符号位填补最左边的n位。也就是说如果数字原先是一个正数，则右移之后在最左边补n个0；如果数字原先是负数，则右移之后在最左边补n个1。
• 除法的效率比移位运算要低得多，在实际编程中应尽可能地用移位运算符代替乘除法。
• 一个整数减去 1 之后再和原来的整数做位与运算，得到的结果相当于是把整数的二进制表示中的最右边一个1变成0。很多二进制的问题都可以用这个思路解决。
• 我们用右移运算符代替了除以2，用位与运算符代替了求余运算符（%）来判断一个数是奇数还是偶数。位运算的效率比乘除法及求余运算的效率要高很多。既然要优化代码，我们就把优化做到极致。
• 题目29的另一种更高效解法：数组中有一个数字出现的次数超过数组长度的一半，也就是说它出现的次数比其他所有数字出现次数的和还要多。因此我们可以考虑在遍历数组的时候保存两个值：一个是数组中的一个数字，一个是次数。当我们遍历到下一个数字的时候，如果下一个数字和我们之前保存的数字相同，则次数加1；如果下一个数字和我们之前保存的数字不同，则次数减1。如果次数为零，我们需要保存下一个数字，并把次数设为1。由于我们要找的数字出现的次数比其他所有数字出现的次数之和还要多，那么要找的数字肯定是最后一次把次数设为 1 时对应的数字。
• 题目34:假设数组中已经有若干个丑数排好序后存放在数组中，并且把已有最大的丑数记做M，我们接下来分析如何生成下一个丑数。该丑数肯定是前面某一个丑数乘以2、3或者5的结果，所以我们首先考虑把已有的每个丑数乘以2。在乘以2的时候，能得到若干个小于或等于M的结果。由于是按照顺序生成的，小于或者等于M肯定已经在数组中了，我们不需再次考虑；还会得到若干个大于M的结果，但我们只需要第一个大于M的结果，因为我们希望丑数是按从小到大的顺序生成的，其他更大的结果以后再说。我们把得到的第一个乘以2后大于M的结果记为M2。同样，我们把已有的每一个丑数乘以3和5，能得到第一个大于M的结果M3和M5。那么下一个丑数应该是M2、M3和M5这3个数的最小者。
• 题目37:首先遍历两个链表得到它们的长度，就能知道哪个链表比较长，以及长的链表比短的链表多几个结点。在第二次遍历的时候，在较长的链表上先走若干步，接着再同时在两个链表上遍历，找到的第一个相同的结点就是它们的第一个公共结点。
• 题目39变体:题目二：输入一棵二叉树的根结点，判断该树是不是平衡二叉树。如果某二叉树中任意结点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。
• 题目40:任何一个数字异或它自己都等于0。也就是说，如果我们从头到尾依次异或数组中的每一个数字，那么最终的结果刚好是那个只出现一次的数字，因为那些成对出现两次的数字全部在异或中抵消了。想明白怎么解决这个简单问题之后，我们再回到原始的问题，看看能不能运用相同的思路。我们试着把原数组分成两个子数组，使得每个子数组包含一个只出现一次的数字，而其他数字都成对出现两次。如果能够这样拆分成两个数组，我们就可以按照前面的办法分别找出两个只出现一次的数字了。我们在结果数字中找到第一个为 1 的位的位置，记为第 n 位。现在我们以第 n位是不是 1 为标准把原数组中的数字分成两个子数组，第一个子数组中每个数字的第n位都是1，而第二个子数组中每个数字的第n位都是0。由于我们分组的标准是数字中的某一位是1还是0，那么出现了两次的数字肯定被分配到同一个子数组。因为两个相同的数字的任意一位都是相同的，我们不可能把两个相同的数字分配到两个子数组中去，于是我们已经把原数组分成了两个子数组，每个子数组都包含一个只出现一次的数字，而其他数字都出现了两次。我们已经知道如何在数组中找出唯一一个只出现一次数字，因此到此为止所有的问题都已经解决了。