剑指Offer系列刷题笔记汇总
倒数

def back(i):
    res = 0
    while(i>0):
        res = res*10 + i%10
        i //= 10
    return res
if __name__ == '__main__':
    i = 750
    print(back(i))
    #  57

斐波那切数列

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

解题思路：
1.如果青蛙第一次跳1级台阶，那么后面应该有f(n-1)种跳法
2.如果青蛙第一次跳2级台阶，那么后面应该有f(n-2)种跳法
3.所有总共的跳法为：f(n) = f(n-1)+f(n-2)转换为斐波那契数列。

class Solution:
    def jumpFloor(self, number):
        # write code here
        if number <= 0:
            return 0
        if number == 1:
            return 1
        if number == 2:
            return 2
        a = 1
        b = 2
        while number>2:
            temp = a
            a = b
            b = b + temp
            number = number - 1
        return  b

if __name__ == '__main__':
    s = Solution()
    print(s.jumpFloor(5))  # 8

青蛙变态跳台阶

# -*- coding:utf-8 -*-
class Solution:
    def jumpFloorII(self, number):
        # write code here
        # 先找规律试下
        # number = 1;    1
        # number = 2;    2
        # number = 3;    4
        # number = 4;    8
        # 1,2,4,8,...,2^(n-1）能推理出公式规律
        # 则number = n; 2^(n-1)
        # return pow(2,number-1)
         
        # 方法2：重新反向思考，如果把n级台阶的跳法看成n的函数f(n)，则青蛙跳
        # f(n) = f(n-1) + f(n-2) + ...+ f(1)
        # 同理：
        # f(n-1) = f(n-2) + f(n-3) + ... + f(1)
        # 即： f(n) = f(n-1) + f(n-1) = 2f(n-1)
        # 这时候看这个其实比fibnacci公式还要简单
        if number == 1:
            return 1
        a = 1
        temp = 1
        for i in range(1,number):
            temp = 2 * a
            a = temp
        return temp