第一题：
在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
这是非常简单的一道题，最常规的一种方式就是两个方向上扫描，但是要保证其中一个扫描方向数字是递增的，而另外一个方向上数字是递减的。
下面给出我的解法，从矩阵中的右上角开始，从右往左扫，当横向当前数的下一个数小于目标数的时候往下少，找到返回true，越界返回false。
public class Solution {
public boolean Find(int target, int [][] array) {
for(int i = array[0].length-1; i >= 0; i--) {
if(array[0][i] <= target) {
for(int j = 0; j < array.length; j++) {
if(array[j][i] == target) return true;
}
}
}
return false;
}
}
第二题
请实现一个函数，将一个字符串中的空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。
这题不解释了，太简单，很多编程语言直接用字符串处理函数就能做了，用正则也能做，当然，题目本身可能并不希望你这么干。
public class Solution {
public String replaceSpace(StringBuffer str) {
char[] arr = str.toString().toCharArray();
int len = arr.length;
int blankCount = 0;
for(int i = 0; i < len; i++) {
if(arr[i] == ' ')
blankCount++;
}
int[] res = new int[len+blankCount];
int j = 0;
for(int i = 0; i < len; i++) {
if(arr[i] == ' ') {
res[j++] = '%';
res[j++] = '2';
res[j++] = '0';
} else {
arr[j++] = arr[i];
}
}
StringBuffer sb = new StringBuffer();
for(int i = 0; i < res.length; i++) {
sb.append(res[i]);
}
return sb.toString();
}
}
第三题
输入一个链表，从尾到头打印链表每个节点的值。
最简单的思路就是用栈倒序输出。
public class Solution {
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
ArrayList<Integer> list = new ArrayList<>();
Stack<Integer> stack = new Stack<>();
while(listNode != null) {
stack.push(listNode.val);
listNode = listNode.next;
}
while(!stack.isEmpty()) {
list.add(stack.pop());
}
return list;
}
}
第四题
输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。
总算来了个比较有意思的题目。给你前序和中序，让你重构二叉树返回。我们直接按题目中给的例子来讲。
前序遍历是{1,2,4,7,3,5,6,8}，也就是说 {1}这个数字就是根。而中序遍历是{4,7,2,1,5,3,8,6}，从而可以划出两个子集{4,7,2,1} {5,3,8,6}分别为组成以{1}为根的左右子树。
依照这个逻辑下去，就可以得出整棵树的结构了。这显然就是一些重复步骤，用递归去做是最好的方式。再进一步思考，我们只需要知道前序和中序遍历的边界下标，就能在递归过程中计算出我们要得到的数据。接下来，让我们直接看代码。
public class Solution {
public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
return rebuilder(pre, in, 0, pre.length-1, 0, in.length-1);
}
public TreeNode rebuilder(int[] pre, int[] in, int prel, int prer, int inl, int inr) {
if(prel > prer) return null;
TreeNode node = new TreeNode(pre[prel]);
for(int i = inl; i <= inr; i++) {
if(in[i] == pre[prel]) {
node.left = rebuilder(pre, in, prel+1, prel+i-inl, inl, i-1);
node.right = rebuilder(pre, in, prel+i-inl+1, prer, i+1, inr);
break;
}
}
return node;
}
}
第五题
用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。
也是非常简单的一题。要用两个栈模拟队列，我们只需要保持两个原则。第一，当你要push一个元素到其中一个栈时候，另外一个栈必须为空。第二，当你要pop一个元素的时候，必须把栈中的所有元素倾倒到另外一个空栈，然后再pop数据出去。
public class Solution {
Stack<Integer> stack1 = new Stack<Integer>();
Stack<Integer> stack2 = new Stack<Integer>();
public void push(int node) {
while(!stack2.isEmpty()) {
stack1.push(stack2.pop());
}
stack1.push(node);
}
public int pop() {
while(!stack1.isEmpty()) {
stack2.push(stack1.pop());
}
return stack2.pop();
}
}
第六题
把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。 输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。 NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。
咋看之下，这题似乎扫描一遍数组就行了。没错，确实如此，但是题目本身是希望你用二分去做的，不然给你非递减这个特性就没有意义了。题目说，非递减数列做旋转，旋转之后其实主要有两种情况，一种就是旋转后和旋转前一样，一种是旋转后和选择前发生了变化（这里暂时忽略数列中过的数全部相等的情况），第一种情况，数列的最后一个数一定是大于第一个数的。第二种情况，最小的数一定在数列中。而这个数列也会分成两个递增的子数列，且两个子序列相连的边界数字一定是递减的，比如：{3,4,5} {1, 2}两个递增数列，5和1这两个边界是下降的，从而我们可以得到二分的条件，假设：当前位置为i，那么当a[i-1] > a[i]时， i就是最小的数。
public class Solution {
public int minNumberInRotateArray(int [] array) {
return binarySearch(array, 0, array.length-1);
}
/**
大体上就是一个二分搜索，注意搜索条件即可
*/
public int binarySearch(int[] arr, int l, int r) {
if (arr[0] < arr[arr.length - 1])
return arr[0];
int mid = (l + r) / 2;
// 这一句就是为了覆盖数列数字全部相等的情况
if(mid == r) return arr[r];
if (arr[mid] < arr[mid - 1])
return arr[mid];
int res = 0;
if(l <= r) {
if (arr[mid] < arr[l])
res = binarySearch(arr, l, mid);
else
res = binarySearch(arr, mid, r);
}
return res;
}
}
第七题
大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项。
n<=39
这题没啥好讲的，为了避免爆栈，应该采用迭代的方式。
public class Solution {
public int Fibonacci(int n) {
if(n == 0)
return 0;
if(n == 1)
return 1;
int count = 1;
Queue<Integer> queue = new LinkedList<Integer>();
queue.add(0);
queue.add(1);
int res = -1;
while(count != n) {
res = queue.poll() + queue.peek();
queue.add(res);
count++;
}
return res;
}
}
第八题
一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
这题考察的就是一个递推的是个思想。假设i表示青蛙要跳上的台阶，当i==1时，只有一种方法；当i==2时，可以从上一个台阶，或上上一个台阶跳上去，所有有两种方式，从而可以知道，当i > 1时，res = step1 + step2(这里的step1和step2分别表示跳到上一个台阶和跳到上上一个台阶的跳法)。
public class Solution {
public int JumpFloor(int target) {
if(target == 1)
return 1;
if(target == 2)
return 2;
int result = 0;
int step1 = 1, step2 = 1;
target -= 1;
while(target-- != 0) {
result = step1 + step2;
step1 = step2;
step2 = result;
}
return result;
}
}
第九题
一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
这道题，最简单最快速的方法，就是直接用排列组合去做。把n个台阶分成1部分、2部分、3...n部分，c(N,0)+c(N,1)+...+C(N,N) = 2^N。
public class Solution {
public int JumpFloorII(int target) {
return (int)Math.pow(2, target-1);
}
}
第十题
我们可以用21的小矩形横着或者竖着去覆盖更大的矩形。请问用n个21的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？
这道题的思路其实和第八题非常类似，假设n=5，我们可以看成n=3和n=4两种情况，但是注意：n=3时，剩下2个小矩阵，所以还可以排成2种，但是有其中一种（竖着排列的）会与n=3时候的重复，所以其实也只能排一种。所以我们可以知道：当 n==1时 res = 1；当n==2时，res=2，当n>2时，res = cnt[n-1] + cnt[n-2]。
public class Solution {
public int RectCover(int target) {
if(target == 0)
return 0;
if(target == 1)
return 1;
if(target == 2)
return 2;
return RectCover(target-1) + RectCover(target-2);
}
}
