Ink's Blog

Less is more

「剑指 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。 这道题目乍一看好像很简单,就是打印数字嘛,其实里面有一个很重要的坑,那就是大数问题,即这里面的数字可能极其大,超过计算机存储整数的最大范围。 因此我们需要找到一种合适的方式来表达一个大数,最常用也最容易的方法就是用字符串或者数组表示大数,我们这里用数组的方式......

「剑指 Offer」面试题 11:数值的整数次方

给定一个 double 类型的浮点数 base 和 int 类型的整数 exponent,求 base 的 exponent 次方。不得使用库函数,同时不需要考虑大数问题。 求一个浮点数的整数次方,我们很容易想到的方法就是累乘,这样做的时间复杂度是 O(n)。我们也可以通过如下公式求 a 的 n 次方: n 为偶数:a^n = a^(n/2) * a^(n/2)n 为奇数:a^n = ......

「剑指 Offer」面试题 10:二进制中 1 的个数

请实现一个函数,输入一个整数,输出该数二进制表示中 1 的个数。例如把 9 表示成二进制是 1001,有两位是 1。因此如果输入是 9,该函数输出 2。 这道题目考察二进制和位运算,一个数字转换成二进制以后有五种位运算,分别是与、或、异或、左移和右移。 其中与、或和异或运算规律如下表: 运算规则 与(&) 0 & 0 = 0 1 & 0 = ......

「剑指 Offer」面试题 9:斐波那契数列

输入一个整数 n,输出斐波那契数列的第 n 项。斐波那契数列的定义如下:F0 = 0F1 = 1Fn = F[n-1]+ F[n-2] (n > 1) 这个题目看到的第一眼,很容易就想到使用递归的方法来做,只要我们知道了斐波那契数列第 0 项和第 1 项的值,其他项的值都可以通过这两项递归累加得到。 但是这样真的没问题吗?每次使用递归的时候我们都要考虑一下有没有性能问题,比如求解 ......

「剑指 Offer」面试题 8:旋转数组的最小数字

把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。输入一个非减排序的数组的一个旋转,输出旋转数组的最小元素。 例如数组 {3,4,5,1,2} 为 {1,2,3,4,5} 的一个旋转,该数组的最小值为 1。 NOTE:给出的所有元素都大于 0,若数组大小为 0,请返回 0。 首先分析一下题目,给定的是一个旋转数组,旋转数组是什么概念呢?就是原始数组是一个非减排序的数组,看......

「剑指 Offer」面试题 7:用两个栈实现队列

用两个栈来实现一个队列,完成队列的Push和Pop操作。 队列中的元素为int类型。 队列特点是先进先出,栈的特点是先进后出,所以我们需要两个栈来达到负负为正的效果,即元素先进入第一个栈,再进入第二个栈,然后再出来,最终的顺序仍然是先进先出。 import java.util.Stack;public class Solution { Stack<Integer&g......