本篇笔记主要是一些《剑指Offer》这本书上所列举出的一些面试题目。
1. 递增序二维数组中数的查找
题目：在一个二维数组中，每行元素都从左到右递增，每列元素都从上到下递增。请完成一个函数，输入一个这样的二维数组和一个整数，判断该整数是否在数组中。
思路：从左上或者右下角开始查找都需要两个方向查找，因此我们应该选择右上或者左下开始。
2.旋转数组中的最小值
题目：把一个数组的最开始若干个元素（包括0）搬到尾部称为数组的旋转，输入递增数组的旋转数组，输出该旋转数组中最小的值。
思路：我们先考虑旋转0位的特殊情况，这样该数组仍然是递增的，可以二分查找。 如果旋转位数不是0，那么旋转后的第一位元素大于等于最后一位元素。若旋转位数不是0，那么旋转之后是两段递增的数组，对这样的数组我们依然可以考虑使用二分查找。我们每次选定中间的元素，对于这个元素，我们能够根据它和第一位和最后一位数的关系来确定该元素属于前一个递增序列还是后一个递增序列，然后确定该从前半段还是后半段查找。
3.斐波那契数列跳台阶
题目：有一只青蛙每次可以向上跳一级台阶或者二级台阶，那么它要跳上n级台阶共有几种跳法。
解：：f(n) = f(n-1) + f(n-2)
4. 在 O（1）时间里删除链表节点。
题目：给定一个单向链表和链表中的一个节点p，删除该节点。
思路：将p的后继节点的值和指针复制到p上，删除p的后继节点。
5. 调整数组顺序使奇数位于偶数之前。
题目： 输入一个整数数组，实现一个函数调整该数组，使所有的奇数位于前半部分，偶数位于后半部分。
思路：诸如此类将数组的复合某个条件的所有数移到前面的问题，可以参考快速排序算法中的中间函数，采用两个指针分别在头部和尾部向中间移动，遇到两个可交换的就进行一次交换操作。
6.按层遍历二叉树
题目：从上到下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印。
思路：维护一个队列，从根节点开始，若打印一个节点的时候，这个节点有子节点，则将该节点的子节点加入队列末尾中，打印完该节点同样处理队列的头部节点。
网友评论