1用两个栈实现队列
【题目】用两个栈来实现一个队列,完成队列的Push和Pop操作。 队列中的元素为int类型。
【考察点】栈和队列
【思路】入队:将元素进栈A
出队:判断栈B是否为空,如果为空,则将栈A中所有元素pop,并push进栈B,栈B出栈;
如果不为空,栈B直接出栈。
【错误1】当栈为空时我return了null,但是pop方法的返回值类型是int,所以报错了。因此我改成了-1。
【错误2】最后return stack2.pop()应该写在pop方法内的最外层,不要写在else里面,因为不管有没有经过从stack1出栈到stack2入栈,最后都是要pop出stack2的栈顶元素。
【错误3】是while(!stack1.empty())而不是if(!stack1.empty()),手误写错了,while一直pop出stack1中的所有元素,而if值pop出stack1当前栈顶的一个元素。
【代码】
2旋转数组的最小数字
【题目】把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。 输入一个非减排序的数组的一个旋转,输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转,该数组的最小值为1。 NOTE:给出的所有元素都大于0,若数组大小为0,请返回0。
【考察点】查找和排序
【思路】好气气,看了半天还是不懂二分法的思路!呜呜呜。这个就是比较普通的解法,当某一个位置的元素比下一个位置的元素大时,由旋转的规律,说明下一个元素就是最小值。
【错误】记得有返回值的方法一定要return,且return不能放在while、if这种语句中,要在所有情况下都能return到。
【代码】
3斐波那契数列
【题目】大家都知道斐波那契数列,现在要求输入一个整数n,请你输出斐波那契数列的第n项(从0开始,第0项为0)。n<=39
【考察点】递归和循环
【思路】用循环,没有用递归。分别用f1、f2、f3存储前两个位置的元素值和当前要计算的位置的元素值。当n为1和2时,return 1。从3到以后就通过循环来计算f3=f1+f2,f1和f2的值随着计算的推进也一直往后推进,循环结束return f3。
【错误】刚开始int f3的时候忘记给它初始化了,后面return的时候就报错了。
【代码】
4跳台阶
【题目】一只青蛙一次可以跳上1级台阶,也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法(先后次序不同算不同的结果)。
【考察点】递归和循环
【思路】我用的是递归,当前可以选择跳1步或者2步,跳一步之后的跳法就变成了f(n-1),跳两步的跳法就变成了f(n-2),当n为1的时候只有1种跳法,当n为2的时候有2中跳法,这两个值是我们的递归终止条件。不过这种做法耗时比较长~
【代码】
5变态跳台阶
【题目】一只青蛙一次可以跳上1级台阶,也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
【考察点】递归和循环
【思路】每个台阶都有跳与不跳两种情况(除了最后一个台阶),最后一个台阶必须跳。所以共有2^(n-1)种情况。1左移target-1位,也就是2的(target-1)次方。
【代码】
6矩形覆盖
【题目】我们可以用2*1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形,总共有多少种方法?
【考察点】递归和循环
【思路】有以下几种情形:
1.target <= 0 大矩形为<= 2*0,直接return 0;
2.target = 1大矩形为2*1,只有一种摆放方法,return1;
3.target = 2 大矩形为2*2,有两种摆放方法,return2;
4.target = n 分为两步考虑:
第一次摆放一块 2*1 的小矩阵,则摆放方法总共为f(target - 1)。
第一次摆放一块1*2的小矩阵,则摆放方法总共为f(target-2)。
所以还是一个斐波那契数列。
【代码】