剑指offer-5~10
2016-07-05 本文已影响10人
IAmWhoAmI
5.用两个栈实现队列
用两个栈来实现一个队列,完成队列的Push和Pop操作。 队列中的元素为int类型。
import java.util.Stack;
public class Solution {
Stack<Integer> stack1 = new Stack<Integer>();
Stack<Integer> stack2 = new Stack<Integer>();
public void push(int node) {
stack1.push(node);
}
public int pop() {
while(!stack1.isEmpty()){
stack2.push(stack1.pop());
}
int res =stack2.pop();
while(!stack2.isEmpty()){
stack1.push(stack2.pop());
}
return res;
}
}
6.旋转数组的最小数字
把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。输入一个递增排序的数组的一个旋转,输出旋转数组的最小元素。例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转,该数组的最小值为1。NOTE:给出的所有元素都大于0,若数组大小为0,请返回0。
#这题目解法还有问题
import java.util.ArrayList;
public class Solution {
public int minNumberInRotateArray(int [] array) {
if(array.length==0){
return 0;
}
int len = array.length;
int limit = array[0];
int start =0;
int end = len-1;
if(array[end] > limit ){
return limit;
}
/*
* 因为有可能3,3,2,3的时候,最后只剩3,2的时候
* 最后可能一直在start= middle中出不来。所以限定条件是end-start>1
*/
while(end - start > 1){
int middle = (start+end)/2;
if(array[middle] > limit){
start= middle+1;
}else if(array[middle] < limit){
end = middle;
}else{
start= middle;
}
}
return array[start]<array[end] ? array[start]:array[end] ;
}
}
7.斐波那契数列
大家都知道斐波那契数列,现在要求输入一个整数n,请你输出斐波那契数列的第n项。
public class Solution {
public int Fibonacci(int n) {
if(n==0){
return 0;
}
if(n==2){
return 1;
}
if(n==1){
return 1;
}else{
return Fibonacci(n-1)+ Fibonacci(n-2);
}
}
}
8.跳台阶
一只青蛙一次可以跳上1级台阶,也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
public class Solution {
public int JumpFloor(int target) {
if(target==0){
return 0;
}
if(target==1){
return 1;
}
if(target==2){
return 2;
}else{
return JumpFloor(target-2)+JumpFloor(target-1);
}
}
}
public class Solution {
public int JumpFloor(int target) {
if(target==0){
return 0;
}
if(target==1){
return 1;
}
if(target==2){
return 2;
}else{
int a=1;int b= 2;
int i=3;
int sum = 0;
while(i<=target){
sum = a+b;
a=b;
b=sum;
i++;
}
return sum;
}
}
}
9.变态跳台阶
一只青蛙一次可以跳上1级台阶,也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
public class Solution {
public int JumpFloorII(int target) {
if(target==1){
return 1;
}else if(target==2){
return 2;
}
int sum=1;
for(int i=1;i<target;i++){
sum +=JumpFloorII(target-i);
}
return sum;
}
}
10.矩形覆盖
我们可以用21的小矩形横着或者竖着去覆盖更大的矩形。请问用n个21的小矩形无重叠地覆盖一个2*n的大矩形,总共有多少种方法?
public class Solution {
public int RectCover(int target) {
if(target==0){
return 0;
}
if(target==1){
return 1;
}else if(target==2){
return 2;
}else{
return RectCover(target-1)+RectCover(target-2);
}
}
}