剑指算法
斐波那契数列
- 0 1 1 2 3 5 8 f(i)=f(i-1)+f(i-2)
- 题目:输入整数n,输出斐波那契数列第n项(从0开始,第0项是0)
# 斐波那契数列
解法一:
class Solution:
def Fibonacci(self, n):
if n == 0 or n == 1:
return n
fi_list = []
fi_list.extend([0, 1])
if n>1:
for i in range(2, n + 1):
fi_list.append(fi_list[i - 1] + fi_list[i - 2])
return fi_list[-1]
return None
解法一优化:
class Solution:
def Fibonacci(self, n):
if n == 0 or n == 1:
return n
a=1
b=0
if n>1:
for i in range(2, n + 1):
ret=a+b
b=a
a=ret
return fi_list[-1]
return None
解法二 # 递归解法,会超出时间限制
class Solution:
def Fibonacci(self, n):
if n == 0 or n == 1:
return n
if n>1:
return self.Fibonacci(n-1)+self.Fibonacci(n-2)
return None
青蛙跳台阶
- 一只青蛙一次可以跳上一级台阶,也可以跳上两级,求该青蛙跳上一个n级台阶总共有多少种跳法(先后次序不同算不同的结果)
# 1,2,3,5
解法一:在等于78之后发生错误,原因可能是溢出
class Solution:
def jumpFloor(self, number):
num_jump = 1
for x in range(number + 1):
for y in range(int(number / 2) + 1):
if (x + 2 * y) == number:
if x == 0 or y == 0:
num_jump += 1
else:
num_jump+=self.je_cheng(x+y)/self.je_cheng(x)/self.je_cheng(y)
return int(num_jump)
def je_cheng(self, num):
a = 1
for i in range(1, num + 1):#184550589
a *= i
return a
解法二:斐波那契数列
class Solution:
def jumpFloor(self,number):
if number<1:
return 0
if number==1 or number==2:
return number
a=1
b=2
ret=0
for i in range(3,number+1):
ret=a+b
a=b
b=ret
return ret
变态青蛙跳台阶:
- 一只青蛙一次可以跳n级台阶,求该青蛙跳上一个n级台阶总共有多少种跳法
1 1 2 2 3 4 4 8 n 2^(n-1)
解法一:
class Solution:
def jumpFloorII(self,number):
return pow(2,number-1)
解法二:
class Solution:
def jumpFloorII(self,number):
#f(n)=f(n-1)+f(n-2)+...+f(1)
#f(n-1)=f(n-2)+...+f(1)
#f(n)=2f(n-1) n>1
#f(1)=1 n=1
if number ==1:
return 1
ret=1
a=1
for i in range(2,number+1):
ret=2*a
a=ret
return ret