Skip to main content
 首页 » 编程设计

Java面试剑指offer系列二

2022年07月19日21wayfarer

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)); 
 
              } 
 
}

本文参考链接:https://www.cnblogs.com/wgl1995/p/5768887.html