6．把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。
a)使用ArrayList来存放元素
public class Solution {
public static int minNumberArray(int[] array) {
int min = array[0];
for(int i = 0; i < array.length; i++){
if(min > array[i]){
min = array[i];
}
}
return min;
}
public ArrayList minNumberInRotateArray(int [] array) {
ArrayList list = new ArrayList();
int minNum = minNumberArray(array);
int i;
for(i=0; i < array.length; i++){
if(minNum == array[i]){
break;
}
}
//把最小数和最小数之后的元素放入list
for(int j = i; j < array.length; j++){
list.add(array[j]);
}
//把最小数前面的元素放入list
for(int k = 0;k < i; k++){
list.add(array[k]);
}
return list;
}
}
b) 使用数组来存放旋转后的数组
public class Solution {
public static int minNumberArray(int[] array) {
int min = array[0];
for(int i = 0; i < array.length; i++){
if(min > array[i]){
min = array[i];
}
}
return min;
}
public int[] minNumberInRotateArray(int [] array) {
int[] arr = new int[array.length];
int minNum = minNumberArray(array);
int i;
for(i=0; i < array.length; i++){
if(minNum == array[i]){
break;
}
}
int l = 0;
//把最小数和最小数之后的元素放入list
for(int j = i; j < array.length; j++,l++){
arr[l] = array[j];
}
//把最小数前面的元素放入list
for(int k = 0;k < i; k++,l++){
arr[l] = array[k];
}
return arr;
}
public static void main(String[] args) {
Solution s = new Solution();
int[] arr1 = new int[]{3,4,5,1,2};
int[] arr2 = s.minNumberInRotateArray(arr1);
for(int i = 0; i < arr2.length; i++){
System.out.print(arr2[i]);
}
}
}
7．大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项。n<=39。
a)题目中提示n的值小于等于39，所以我们可以定义一个长度为39的数组，这样就不会超出大小。还有使用数组存放斐波拉契数比使用方法递归的时间效率高很多。程序中没有判断输入的数字是否大于39，这个很简单。
public class Solution {
public int Fibonacci(int n) {
int flag;
int[] arr = new int[39];
arr[0] = 1;
arr[1] = 1;
if(n<=0){
flag = 0;
}else if(n == 1){
flag = 1;
}else{
for(int i = 2; i < n; i++){
arr[i] = arr[i-1] + arr[i-2];
}
flag = arr[n-1];
}
return flag;
}
public static void main(String[] args) {
Solution s = new Solution();
System.out.println(s.Fibonacci(20));
}
}
b)还有一种方法就是使用递归，这一方法的代码十分简单，但是时间有点长，通过不了网上在线编译器的测试。
public class Solution {
public int Fibonacci(int n) {
int flag;
if(n<=0){
flag = 0;
}else if(n == 1){
flag = 1;
}else{
flag = Fibonacci(n-1)+Fibonacci(n-2);
}
return flag;
}
public static void main(String[] args) {
Solution s = new Solution();
System.out.println(s.Fibonacci(20));
}
}
8．一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
a)这是一个斐波拉契数列问题
观察可以得出，当n等于1时为1，n等于2时为2，n等于3时为3，n等于4时为5，可以观察出当n大于2时，结果等于n-1的结果加上n-2的结果，所以直接可以使用递归来实现。
public class Solution {
public int JumpFloor(int target) {
if(target <= 0){
return -1;
} else if(target == 1){
return 1;
} else if(target == 2){
return 2;
} else{
return (JumpFloor(target-1)+JumpFloor(target-2));
}
}
public static void main(String[] args) {
Solution s = new Solution();
System.out.println(s.JumpFloor(3));
}
}
9．一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
a)这一题的解题步骤和上一体类似，也是斐波拉契数列。
public class Solution {
public int JumpFloor(int target) {
if(target <= 0){
return -1;
} else if(target == 1){
return 1;
} else if(target == 2){
return 2;
} else{
return (JumpFloor(target-1)+JumpFloor(target-2));
}
}
public static void main(String[] args) {
Solution s = new Solution();
System.out.println(s.JumpFloor(3));
}
}
10．我们可以用2*1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？
a)这题和前面两题类似，下面直接给出代码
public class Solution {
public int RectCover(int target) {
if(target <= 0){
return 0;
} else if(target == 1){
return 1;
} else if(target == 2){
return 2;
} else{
return RectCover(target-1)+RectCover(target-2);
}
}
public static void main(String[] args) {
Solution s = new Solution();
System.out.println(s.RectCover(4));
}
}