day10(3.15)

1. 青蛙台阶问题

一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。

答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。

示例 1：

输入：n = 2
输出：2
示例 2：

输入：n = 7
输出：21
示例 3：

输入：n = 0
输出：1
提示：

0 <= n <= 100

思路:

/*
    n = 0 ; 跳0级台阶, 有 1 种方法;
    n = 1 ; 跳1级台阶, 有 2 种方法;    -----跳1级后, 还剩0个台阶,有f(0)种方法
                                            f(1) = f(0)
    n = 2 ; 跳2级台阶, 有 2 种方法;    -----跳1级后, 还剩1个台阶,有f(1)种方法;再跳1级,还有0级,有f(0)种方法
                                            f(2) = f(1) + f(0)
    n = 3 ; 跳3级台阶, 有 ? 种方法;    -----跳1级后, 还剩2个台阶,有f(2)种方法;再跳1级,还有1级,有f(1)种方法
                                            f(3) = f(2) + f(1)
    ......
    由此可见, 就是简单的递归运算
    f(n) = f(n-1) + f(n-2)
*/

class Solution {
    public int numWays(int n) {
        int a=1,b=1,sum=0;
        for(int i=1;i<n;i++){
            sum = (a+b)%1000000007;
            a = b;
            b = sum;
        }
        return b;
    }
}

复杂度分析:

• 时间复杂度 O(N) ： 计算 f(n) 需循环 n 次，每轮循环内计算操作使用 O(1) 。
• 空间复杂度 O(1)O(1) ： 几个标志变量使用常数大小的额外空间。

2. 旋转数组的最小数字

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如，数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一个旋转，该数组的最小值为1

示例 1：
输入：[3,4,5,1,2]
输出：1

示例 2：
输入：[2,2,2,0,1]
输出：0

class Solution {
    public int minArray(int[] numbers) {
        int n = numbers.length;
        int index = 0;
        if(n==1){
            return numbers[0];
        }
        for(int i=0;i<n-1;i++){
            if(numbers[i]<=numbers[i+1]){
                continue;
            }else{
                return numbers[i+1];
            }
        }
        return numbers[0];
    }
}

我改写题目为, 输出旋转前的数组,即: 将数组恢复成原来的递增状态:

class Solution {
    public int minArray(int[] numbers) {
        int n = numbers.length;
        int index = 0;
        if(n==1){
            return numbers[0];
        }
        Queue<Integer> queue1 = new LinkedList<>();
        Queue<Integer> queue2 = new LinkedList<>();    
        for(int i=0;i<n-1;i++){
            if(numbers[i]<=numbers[i+1]){
                queue1.offer(numbers[i]);
                if(i==n-1){
                    queue1.offer(numbers[i+1]);
                }
            }else{
                queue1.offer(numbers[i]);
                for(int j=i+1;j<n;j++){
                    queue2.offer(numbers[j]);
                }
                break;
            }
        }
        if(queue2.isEmpty()){
            while(!queue1.isEmpty()){
                numbers[index] = queue1.poll();
                index++;
            }
        }else{
            while(!queue2.isEmpty()){
                numbers[index] = queue2.poll();
                index++;
            }
            while(!queue1.isEmpty()){
                numbers[index] = queue1.poll();
                index++;
            }
        }
        return numbers[0]; 
    }
}


/*
    使用 "队列" 来解决:  ----先进先出 
    1. 遍历数组, 如果后一个数大于或者等于当前数,那么直接入对;如果小于那么就将后面所有数入队另一个队列
    2. 出队完第二个队列, 装载入数组中,然后出队第一个队列,数组接着进行装载

*/