剑指offer系列

题目：输入n个整数，找出其中最小的前K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4.** 分析 这是一道很经典的topK问题。前段时间我在参加360实习生面试的时候就考到了这个问题。主要解决方法如下： 排序 基于partition函数 堆(或红黑树) 这三种方法的推荐指数依次…

题目：输入一个整数数组，判断该数组是不是某二叉搜索时的后序遍历的结果。如果是则返回true，否则返回false。假设输入的数组的任一两个数字都不相同。** 分析 我们先假设该数组是某颗二叉搜索树的后序遍历序列，则它有如下性质： 数组最后一个元素是该二叉树的根节点； 若数组为arr，长度为n，则arr[0..k-1]<a…

题目一：写一个函数，输入n，求斐波那契数列的第n项。斐波那契数列的定义如下： $$f(n)=\begin{cases}0 & &{n=0} \\\ 1 & &{n=1} \\\ f(n-1)+f(n-2) & &{n>1} \end{cases} $$ 分析 根据上述公式，我们可以很容易地写出如下递归代码： 不过递归方…

题目：把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。 分析 很自然地，最直观的解法就是设置一个最小值，并顺次检查数组的每一个元素，如果小于最小值，就更新这个…

题目：用两个栈实现一个队列。队列的声明如下，请实现它的两个函数appendTail和deleteHead，分别完成在队列尾部插入节点和在队列头部删除节点的功能。 分析 首先，我们需要知道队列和栈他们各自的特点。他们都是一个线性数据结构。在STL里面，他们是作为容器适配器出现的。尽管如此，栈和队列在逻辑和对数据的操作方式…

题目：输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建出下图所示的二叉树并输出它的头结点。二叉树的定义如下：

题目：请实现一个函数，把字符串中的每个空格替换成“%20”。例如输入“We are happy.”，则输出“We%20are%20happy.”。 分析 最容易想到的办法就是从前向后扫描字符串，如果遇到空格，就把它后面的子串向后移动2个字节长度。 代码如下 string ReplaceBlank(string str)

题目一：输入一个英文句子，反转句子中单词的顺序，但单词内字符的顺序不变。为简单起见，标点符号和普通字母一样处理。例如输入字符串”I am a student.”，则输出”student. a am I”。** 分析 解法如下： 1. 先将整个字符串翻转； 2. 将每个单词翻转(以空格分隔)。 代码如下： 题目二：字…

题目一：输入一个递增排序的数组和一个数字s,在数组中查找两个数，使得他们的和正好是s。如果有多对数字的和等于s,输出任意一对即可。** 分析 今天上课，老师说了，在面试的时候不要一上来就去找最优的解法，因为你一时半会儿可能会找不到最优的。而且就算立即做出来了，面试官会认为你以前刷过这道题。所以可以先将最简单的思路哪怕是…

题目：一个整型数组中除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个数字。要求时间复杂度是O(n)，空间复杂度是O(1)。** 分析 我们先来看一道问题： 一个整型数组中除了一个数字出现了一次之外，其他的数字都出现了两次。请找出这个数字。 这题怎么做呢？记得我们原来有一个模拟面试，当时面试老师就给我出了这么…

题目：输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字。例如：输入如下矩阵： 1&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;2&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;3&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;4 5&nbsp;&…

题目：定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的min函数。在该栈中，调用min，push及pop函数的时间复杂度都是O(1)。 分析 栈应该是我们很熟悉的一种数据结构了，它是一种“后进先出”的数据结构，并且只能在栈的一端(栈顶)进行操作。所以其push和pop操作的时间复杂度都是O(1)。如果题目没…

题目：输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入序列，序列4,5,3,2,1,是该压栈序列对应的一个弹出序列。但4,3,5,1,2就不可能是该压栈序列的弹出序列。** 分析 栈是一种“后进先出”(LIFO)的数…

题目：在一个二维数组中，每一行都按照从左到右递增的顺序排列，每一列都按照从上到下的顺序排列。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。** 分析 此题最直观的做法就是逐行逐列搜索。但这种做法没有利用数组有序递增这个特性，时间复杂度是 O(m*n)(假设数组为 n 行 m 列)。肯定是不…

题目一：输入一颗二叉树的根节点，求该树的深度。从根节点到叶节点一次经过的节点形成树的一条路径，最长路径的长度为树的深度。** 二叉树节点定义如下： 分析 此题可利用递归很方便的完成，步骤如下： 判断参数root是否为空？为空就返回0； 否则计算root的左右子树的高度； 比较左右子树高度，取较大者，返回较大的值加1（r…

题目：输入一颗二叉树和一个整数，打印出二叉树中节点值的和为输入整数的所有路径。从属的根节点开始往下一直到叶节点所经过的节点形成一条路径。二叉树节点的定义如下：** 分析 既然题目要求要打印二叉树上的所有节点，就需要遍历该二叉树。而在最常见的前、中、后序三种遍历方式中，只有前序遍历能第一个访问二叉树的根节点，也就是先累加…

题目：请实现函数ComplexListNode* Clone(ComplexListNode* pHead),复制一个复杂链表。在复杂链表中，每个结点除了有一个next指针指向下一个结点外，还有一个Sibling指向链表中的任意结点或者NULL。结点的C++定义如下：** 分析 很容易想到的办法是先像普通链表一样将该链…

题目：输入一个字符串，打印出该字符串中字符的所有排列。例如输入“abc”，则打印出”abc”,”acb”,”bac”,”bca”,”cab”,”cba”。** 分析 此题即求某个序列的全排列。此序列可以是数组或字符串等。求全排列的方法我介绍两种： 直接用STL算法 自己实现 套用STL的话非常简单，只需要包含头文件`#…

题目：统计一个数字在排序数组中出现的次数。例如输入数组{1,2,3,3,3,3,4,5}和数字3，由于3在数组中出现了4次，因此输出4.** 分析 看到排序数组，我们自然而然会想到二分法。但平常的二分法只能找到这个数字，并不能找出出现的次数，或者该数字的最左和最右边界。那么我们就需要改进一下： 假设数组是升序排列的，当…

题目：数组中有一个数字出现的次数超过了数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2出现了5此，超过了数组的一半，因此输出2.** 分析 最直观的解决办法就是将数组排序，然后取其中位数即可。但排序最快也需要O(nlgn)的时间复杂度，效率不是特别高。代码略。

话说写博客真是个累人的干活，即使是我写如此简单，篇幅如此短小的博客，有时候也真想一弃了之，放任不管。恰逢这几天忙着考试，今天一门，明天一门，后天还有一门。一学期了没好好学，现在可真是后悔呀。。。忙得头晕转向，甚至复习时间都感觉很不够用。但我电脑上设置了闹钟，每天道时间就会提醒我该写博客了。今天打开一看，咦？很久没遇到如…

题目：输入一个整型数组，数组中有正数也有负数。数组中一个或连续多个整数组成一个子数组。求所有子数组的和的最大值，要为时间复杂度为O(n)。** 分析 可以这么想，假设这个数组的具有最大和的连续子数组区间为[x,y)，该数组的中间元素的下标是mid。mid和[x,y)的关系又一下三种： mid<x mid>=y x<=m…

题目：输入一个整数n，求从1到n这n个整数的十进制表示中1出现的次数。例如输入12，从1到12这些整数中包含1的数字有1,10,11和12，所以1一共出现了5次。** 分析 最简单也最容易想到的就是从1到n进行遍历，每到一个数字，就逐个取出它十进制中的每一位数，并判断是否为1。当然，这肯定不是最好的方案。代码从略。 上…

题目：输入一个正整数数组，把数组中所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。例如输入数组{3,32,321}，则打印出这3个数字能排列成的最小数字321323。** 分析 很容易想到的是求出所有整数的全排列，然后将它们拼接为一个数字，找出最小的一组。但这种方法存在两个问题： 假设数组有n个整数，全…

题目：我们把只包含因子2,3和5的数称作丑数。求按从小到大的顺序的第1500个丑数。例如6,8都是丑数，但14不是，因为它包含因子7.习惯上我们把1当做第一个丑数。** 分析 最直观的方法是从1往后逐个判断每个数字，并设一个计数器。如果一个数是丑数，计数器加一。当计数器到1500时，输出这个数即可。但求一个数的所有因子…

题目：请实现一个函数，输入一个整数，输出该数二进制便是中1的个数。例如把9表示成二进制是1001，有2位是1.因此如果输入9，该函数输出2.** 分析 此题考查的是对位运算的掌握，题目不是很难，但一些细节问题还是需要注意的。 方法1：移位 我们把这个数和 0x1 相与，如果结果为 0，则表明该数的最后移位为 0，否则为…

题目：在数组中的两个数字如果前面一个大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中所有逆序对的总数。** 分析 如果采用简单粗暴的方法，即遍历数组，对每个数，检查后面的每一个数是否小于它。时间复杂度为O(n²)。 实际上我们可以采用归并排序来解决这个问题，只需要在归并每一…

题目：输入两个链表，找出它们的第一个公共节点。链表节点定义如下：** 分析 解法有两种,分别介绍如下: 第一种，先分别在两个链表上遍历一次，统计出两个链表的长度，假设为length1和length2，且length1>length2。然后在较长的链表上先走(length1-length2)步，然后两个同时走，如果遇到相…

题目：从上往下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印。例如输入下图所示的二叉树，则依次打印出8,6,10,5,7,9,11.**  二叉树的节点定义如下： 分析 对二叉树而言，第n层最少有1个节点，最多有2^n-1个节点。…

题目：请完成一个函数，输入一个二叉树，输出它的镜像。** 二叉树的节点定义如下： 分析 首先要弄明白什么是二叉树的镜像？镜像就是将二叉树的所有节点的左右指针交换后得到的二叉树。 所以很容易分析出，要得到二叉树的镜像，需要交换它每个节点的左右指针。我们依次遍历该二叉树的每一个节点，交换它的左右指针，然后再交换它的左右子树…

题目：输入两颗二叉树A和B，判断B是不是A的子结构。二叉树的节点定义如下：** 分析 要判断 B 是不是 A 的子结构，也就是要判断 B 是不是 A 的子树。我们可以先遍历 A，如果某一个 S 节点的 value 和 B 树的根节点相同，就判断 S 和 B 的左右子树是否相等，如果相等，B 就是 A 的子结构；否则跳过…

题目：输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是按照递增排序的。** 链表的定义如下： 分析 这是典型的链表归并问题。因为两个链表都是排好序的，所以我们只需要初始化两个指针，分别指向两个链表的第一个节点。并在一个循环中比较两个节点的 value 值，将较小的摘下来放到新链表中去。在循环结束时，肯定会…

题目：定义一个函数，输入一个链表的头结点，反转该链表并输出反转后链表的头结点。链表定义如下：** 此题可以用递归和头插法来做。 递归 用递归做起来稍微复杂一点，而且会有个问题，就是当链表太长时，可能会导致系统栈溢出。 大体思路就是，当我们每递归的链表的一个节点时，如果该节点不是最后一个，就先递归反转它后面的链表，然后将…

题目：输入一个链表，输出该链表中倒数第K个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第一个节点。** 链表的定义如下： 分析 有三种方法：递归法，自定义栈法和前后指针法。 递归法 代码如下： 自定义栈法 前后指针法 这三种方法的优缺点如下： <table> <thead> <tr> <th a…

题目：输入一个整数数组，实现一个函数来调整数组中数字的顺序，是得所有的奇数位于数组的前半部分，所有偶数位于数组的后半部分。** 分析 最简单的办法就是开辟和原数组同样大小的空间，顺次扫描原数组 2 次，第一次将所有奇数放进新数组中，第二次将偶数放入就可以。这种方法的时间复杂度为 O(n)，空间复杂度为 O(n)。 代码…

题目：输入数字 n，按顺序打印出从 1 到最大的 n 位十进制数。比如输入 3，则打印 1,2,3 一直到最大的 3 位数即 999。** 分析 要打印 1 到最大的 n 位数，我们首先想到的方法是先计算出 n,再逐次打印。但有一个很重要的问题，n 大于 9 怎么办？（MAX_INT=2147483647，10 位），…

题目：请实现函数double Power(double base, int exponent)，求base的exponent次方。不得使用库函数，同时不需要考虑大数问题。** 分析 恩，很简单。我们写出的代码如下： 说实话，我第一次做这道题的时候就是这么写的。但现在看来，还是 too young too naive 了…

题目：输入一个链表的头结点，从尾到头反过来打印出每个节点的值。** 分析 这道题有如下几种解决方案： 1. 将链表逆置，然后顺次打印 2. 递归方案 3. 迭代方案 如果逆置链表的话，会改变链表原先的结构。我们可以在面试时询问面试过是否可以改变链表，如果是肯定的回答，就可以采用这种办法。否则只能采用后面的方法。 逆置链…

题目：设计一个类，我们只能生成该类的一个实例 分析 Singleton 即单例模式。既然题目要求只能生成类的一个实例，那我们必须把类的构造函数和拷贝构造函数设置为 private 以阻止类的调用者随意创建对象。 我们来看代码 //单例模式类包含的数据 typedef struct data{ int a; //othe…

题目：如下为类型CMyString的声明，请为该类添加赋值运算符函数。 分析 我们知道，C++ 中类的 6 个默认的函数分别是构造，拷贝构造，析构，赋值运算符的重载，取址运算符的重载和它的常量版本。其中前 4 个在面试中最常问到。比如在继承/组合类中构造和析构函数的调用顺序，派生类中析构函数是否应该设置为 virtua…