剑指offer面试题牛客_递归和循环_变态跳台阶(java版)

1
2
3
4
5
6
public class Solution {
    public int JumpFloorII(int target) {
        return 1<<target-1;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/*
f(n) = f(n-1) + f(n-2) +...+f(1) + f(0)
f(n+1) = f(n) + f(n-1) + ... + f(1) + f(0)

f(n+1) - f(n) = f(n)

f(n+1) = 2f(n)

f(n+1) = 2f(n) = 4f(n-1) = 8f(n-2) = 2^(n+1)f(0) = 2^(n+1)
这里递推式推错了， 因为f(0)不等于1

f(n+1) = 2^n f(1) = 2^n

f(n) = 2^(n-1); 养成使用移位计算指数的习惯
*/
public class Solution {
    public int JumpFloorII(int target) {
        return 1 << (target - 1);
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class Solution {
    public int JumpFloorII(int target) {
        // f(n) = 2f(n-1)
        if(target == 1)
            return 1;
        int a=1, res=0;
        for(int i=2; i<=target; i++){
            res = 2*a;
            a = res;
        }
        return res;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class Solution {
    public int JumpFloorII(int target) {
        /*
        思路:
            1)f(n) = f(n-1) + f(n-2) +...+ f(2) + f(1) + f(0)    这个递归式太长了, 能用是能用, 但是不妨化简一下
        */
        //execute
        if(target == 0) return 1;
        int res=0;
        for(int i=1; i<=target; i++)
            res = res + JumpFloorII(target - i);
        return res;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class Solution {
    public int JumpFloorII(int target) {
        /*
        思路:
            1)f(n) = f(n-1) + f(n-2) +...+ f(2) + f(1) + f(0)    这个递归式太长了, 能用是能用, 但是不妨化简一下
        */
        //input check
        if(target < 1) return 0;
        //execute
        int[] arr = new int[target+1];
        arr[0] = 1;
        for(int i=1; i<=target; i++)
            for(int j=i-1; j>=0; j--)
                arr[i] += arr[j];
        return arr[target];
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class Solution {
    public int JumpFloorII(int target) {
        /*
        思路:
            1)f(n) = f(n-1) + f(n-2) +...+ f(2) + f(1) + f(0)
            2)f(n-1) = f(n-2)+...+ f(2) + f(1) + f(0)
            综合1)和2),得到f(n) = 2f(n-1), 这样的递归式就简洁了许多!
        */
        //input check
        if(target<1) return 0;
        //execute
        if(target==1) return 1;
        return 2*JumpFloorII(target-1);
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class Solution {
    public int JumpFloorII(int target) {
        //input check
        if(target<1) return 0;
        //execute
        if(target == 1) return 1;
        int[] arr = new int[target+1];
        arr[1] = 1;
        for(int i=2; i<=target; i++)
            arr[i] = 2*arr[i-1];
        return arr[target];
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class Solution {
    public int JumpFloorII(int target) {
        /*
        思路:
            1)f(n) = f(n-1) + f(n-2) +...+ f(2) + f(1) + f(0)
            2)f(n-1) = f(n-2)+...+ f(2) + f(1) + f(0)
            综合1)和2),得到f(n) = 2f(n-1), 这样的递归式就简洁了许多!
            进一步地, f(n) = 2f(n-1)= 2*2f(n-2)=2*2*2f(n-3)= 2^(n-1)*f(1)= 2^(n-1)  学好数学很关键!
        */
        //input check
        if(target<1) return 0;
        //execute
        return 1 << (target-1); //注意是谁移位!!!!! 是1, 不是2!!!!
    }
}