Ink's Blog

Less is more

「剑指 Offer」面试题 21:包含 min 函数的栈

定义栈的数据结构,请在该类型中实现一个能够得到栈的最小元素的 min 函数。在该栈中,调用 min、push 及 pop 的时间复杂度都是 O(1)。 引入一个辅助栈用来存放当前位置的最小元素,入栈时如果该数小于这个最小值,那么辅助栈就入这个数,如果大于该最小值,就还是入之前的元素,出栈的时候同时出即可。 代码如下: import java.util.Stack;public class......

「剑指 Offer」面试题 20:顺时针打印矩阵

输入一个矩阵,按照从外向里以顺时针的顺序依次打印出每一个数字。 例如:如果输入如下矩阵 1 2 3 45 6 7 89 10 11 1213 14 15 16 则依次打印出 1、2、3、4、8、12、16、15、14、13、9、5、6、7、11、10。 代码如下: import java.util.ArrayList;publ......

「剑指 Offer」面试题 19:二叉树的镜像

请完成一个函数,输入一个二叉树,该函数输出它的镜像。 一颗树的镜像的过程是:前序遍历这棵树的每个结点,如果遍历到的结点有子结点,就交换这两个结点,然后再递归得出这两个子结点的镜像,递归的终止条件是已经到达了叶子结点,就得到了整个树的镜像,代码如下: /**public class TreeNode { int val = 0; TreeNode left = nul......

「剑指 Offer」面试题 18:树的子结构

输入两颗二叉树 A 和 B,判断 B 是不是 A 的字结构。(ps:我们约定空树不是任意一个树的子结构) 要查找树 A 中是否存在和树 B 结构一样的子树,这就涉及到一个树的遍历问题,每遍历到一个结点我们就需要判断 B 是否是这个结点所在的子树,如果是的话直接返回,如果不是的话就要继续遍历这个结点的左右子结点。 所以我们需要两个函数,第一个函数控制总的遍历逻辑,第二个函数要判断一个子树是......

「剑指 Offer」面试题 17:合并两个排序的链表

输入两个递增排序的链表,合并这两个链表并使新链表中的结点仍然是按照递增排序的。 首先分析一下合并的过程,比较两个链表的头结点的值,最后的结果要递增排序,因此比较小的值应当是合并以后新链表的头结点,单独拎出来,剩下的两个链表继续进行合并。从这个过程可以看出来,这是一个典型可以用递归解决的问题,总结起来就是首先确定头结点,然后递归合并剩下的两个链表即可。 接下来我们考虑异常情况。每当代码试图......

「剑指 Offer」面试题 16:反转链表

定义一个函数,输入一个链表的头结点,反转该链表并输出反转后链表的头结点。 又是一个链表问题,解决与链表相关的问题总是又大量的指针操作,本题目就是这样。需要反转链表,也就是本来指向下一个结点的指针要指到前一个,需要注意的是在这个过程中要特别注意保存好其中的某些结点,比如前一个结点或者下一个结点,这些是容易出错的点,代码如下: /*public class ListNode { ......

「剑指 Offer」面试题 15:链表中倒数第 k 个结点

输入一个链表,输出该链表中倒数第 k 个结点。 本题目要求倒数第 k 个结点,也就是正数第 n-k+1 个结点,如果我们能够得到链表中结点的个数 n,那我们只要从头结点开始往后走 n-k+1 步就可以了。如何得到结点数 n?这个不难,只需要从头开始遍历链表,每经过一个结点,计数器加 1 就行了。 这种方法需要遍历链表两次,第一次统计出链表中结点的个数,第二次就能找到倒数第 k 个结点,那......

「剑指 Offer」面试题 14:调整数组顺序使奇数位于偶数前面

输入一个整数数组,实现一个函数来调整该数组中数字的顺序,使得所有奇数位于数组的前半部分,所有偶数位于数组的后半部分,并保证奇数和奇数,偶数和偶数之间的相对位置不变。 分析题目要求奇数在前偶数在后,并且重排序之后奇偶原来的顺序不能改变,这就说明我们只能顺序遍历所有的数字,遇到奇偶相邻就左右交换。具体做法就是在向后遍历的过程中用一个变量做为遍历过的奇数的数目,当遍历到的数字是奇数时,首先看一......

「剑指 Offer」面试题 13:在 O(1) 时间删除链表结点

给定单向链表的头指针和一个结点指针,定义一个函数在 O(1) 时间删除该结点。 在单向链表中删除一个结点,最常规的做法无疑是从链表的头结点开始,顺序遍历查找要删除的结点,并在链表中删除该结点,时间复杂度是 O(n),显然不满足本题的要求。 之所以需要从头开始查找,是因为我们需要得到将被删除的结点前面一个结点。在单向链表中,结点中没有指向前一个结点的指针,所以只好从链表的头结点开始顺序查找......

「剑指 Offer」面试题 12:打印 1 到最大的 n 位数

输入数字 n,按顺序打印出从 1 到最大的 n 位十进制数。比如输入 3,则打印出 1、2、3 一直到最大的 3 位数即 999。 这道题目乍一看好像很简单,就是打印数字嘛,其实里面有一个很重要的坑,那就是大数问题,即这里面的数字可能极其大,超过计算机存储整数的最大范围。 因此我们需要找到一种合适的方式来表达一个大数,最常用也最容易的方法就是用字符串或者数组表示大数,我们这里用数组的方式......