题目1 二维数组中的查找

题目描述

在一个二维数组中(每个一维数组的长度相同),每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。

题目解析

其实这个题目是非常有规律的,所以才可以用复杂度更小的方法来实现。由于其每行自左向右递增,每列自上而下递增,所我们可以设置一个初始位置,让他不在(0,0)的位置,而是第一列最后一个位置,如果实际数比它大了,那就向右查找,否则向上查找。

代码

题目2 替换空格

题目描述

请实现一个函数,将一个字符串中的每个空格替换成“%20”。例如,当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。

题目解析

代码

题目3 从尾到头打印链表

题目描述

输入一个链表,按链表值从尾到头的顺序返回一个ArrayList。

题目解析

其实很容易想到,可以使用FILO的堆栈来进行处理。

代码

题目4 重建二叉树

题目描述

输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6},则重建二叉树并返回。

题目解析

我们根据前序遍历的特点可以发现,前序遍历的第一个数字一定是这个二叉树的根节点;然后根据中序遍历的特点可发现,根节点左侧的数字一定是左子树,右侧一定是右子树。然后将中序遍历以根节点为中心划分成两个部分,这又是两个子树,然后这个子树又可以根据前序遍历找到各个子树的根节点……以此类推,这非常适合有递推来实现。

就拿这个例子来说。

前序遍历:

序号01234567
内容12473568

中序遍历:

序号01234567
内容47215386

这又就把中序遍历分为了4/7/2和5/3/8/6两个部分。然后考虑4/7/2这个部分,前序遍历的第2个数字是划分4/7/2的数字,这样,2是这个子树的根节点,4/7都位于左子树。

然后再看右子树,也就是3/5/6/8这四个数字。同理可以得出,3是右子树的根节点,然后5在左子树,8/6在右子树。再去8/6这个子树看,根据前序遍历可以看到6为子树的根节点,根据中序遍历可以看到,8为子树的左结点。

接下来考虑代码实现问题。首先肯定要判断所给的两个数组是不是空,若是空肯定是个空树,否则继续进行。我们可以使用类里面的一个私有函数来进行具体的重建功能,而这个函数的参数自然是前序遍历结果、起始位置、结束位置、中序遍历结果、起始位置、结束位置。

当然作为刚开始的时候,起始位置肯定是0,结束位置肯定是length-1

使用这个私有函数进行递归,肯定有停止递归的条件,那就是开始位置大于结束位置的时候,自然就代表迭代结束了。

然后新建一个TreeNode,第一个节点自然是前序遍历的第一个节点,所以可以:

接下来自然要开始进行判断,寻找前序遍历和中序遍历相等值的位置,由于前序遍历里面的点都可以作为中序遍历里面的根节点,所以我们只需要在中序遍历里面找到与前序遍历中值相等的位置,就是该子树的根节点的位置,就可以根据这个点划分左子树和右子树了。而中序遍历中到的根节点的位置i左侧有几个数字就是左子树有几个元素,右边有几个数字就是右子树有几个元素

对于左子树来说,左子树的起始位置自然是startPre的下一个位置,而结束是startPre+i-startIn(startPre是位置,i-startIn是从中序遍历中看左子树有几个元素),而中序遍历的开始位置自然是startIn,结束位置是i-1。

对于右子树来说,中序遍历的起始位置自然是i+1,结束位置是endIn;而对于前序遍历来说,自然是startPre+左子树的元素数+1,而左子树我们知道是i-startIn了,所以起始位置是startPre+i-startIn+1,结束位置自然是endPre。

于是,完成了这个程序的编写。

代码

题目5 用两个栈实现队列

题目描述

用两个栈来实现一个队列,完成队列的Push和Pop操作。 队列中的元素为int类型。

题目解析

思路很简单,就是用两个堆栈,push直接push进去就可以。由于队列是FIFO,而堆栈是FILO,所以只要使用push后的堆栈再push到另一个堆栈里面,这个时候pop出来的顺序总体上来说就是FIFO了。

代码

题目6 旋转数组的最小数字

题目描述

把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。 输入一个非减排序的数组的一个旋转,输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转,该数组的最小值为1。 NOTE:给出的所有元素都大于0,若数组大小为0,请返回0。

题目解析

最傻瓜的方式就是直接进行比较了,但是这样的时间复杂度为O(n),我们可以考虑降低复杂度。考虑到这个旋转数组本质上是一个基本有序的数组,所以我们可以考虑借鉴二分查找的思想。
令low=0,high=len-1,即两个指针分别指向数组的开头和结尾。我们令mid=(low+high)/2。
- 若a[mid]>a[high],则代表最小的元素一定在后面(因为这两块都是递增的),所以low=mid+1
- 若a[mid]==a[high],这种情况比较复杂,需要一个一个的试,所以high=high-1,一点点缩小范围。
- a[mid]<a[high],则代表最小数字一定就是array[mid]或者在mid的左边。因为右边必然都是递增的,所以直接high=mid(一定不能为mid-1)。

代码

题目7 数值的整数次方

题目描述

给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。

题目解析

假如我们要计算313,我们既可以直接乘(复杂度为O(n)),也可以用快速算法降低复杂度。方法是怎样的呢?
我们关注指数部分,13=(1101)2所以313=3(1000)2 * 3(0100)2 * 3(0001)2
这样的话,我们可以将exponent&1操作,如最低位为1,那么就是做ans=ansbase,否则不做。然后对exponent进行右移,每右移1位,base=basebase,这样若为1,则ans=base;若为101,则为ans=base(basebase)。然后就可以得到结果了,代码如下。

代码