剑指offer的Python实现(二)
6旋转数组的最小数字
链接:https://www.nowcoder.com/questionTerminal/9f3231a991af4f55b95579b44b7a01ba
来源:牛客网
Python方法大总结
方法一:直接min函数,有点像开挂
class Solution:
def minNumberInRotateArray(self, rotateArray):
# write code here
if not rotateArray:
return 0
else:
return min(rotateArray)
方法二:先sort排序
class Solution:
def minNumberInRotateArray(self, rotateArray):
# write code here
if not rotateArray:
return 0
else:
rotateArray.sort()
return rotateArray[0]
方法三:二分查找
class Solution:
def minNumberInRotateArray(self, rotateArray):
# write code here
length = len(rotateArray)
if length == 0:
return 0
elif length == 1:
return rotateArray[0]
else:
left = 0
right = length - 1
while left < right:
mid = (left + right)/2 找中间值应该放在循环的里边
if rotateArray[mid] < rotateArray[j]:
right = mid
else:
left = mid+1
return rotateArray[i]
方法四:比较
class Solution:
def minNumberInRotateArray(self, rotateArray):
# write code here
length = len(rotateArray)
if length == 0:
return 0
elif length == 1:
return rotateArray[0]
else:
for i in range(length-1):
if rotateArray[i] > rotateArray[i+1]:
return rotateArray[i+1]
return rotateArray[length-1]
自己写的错误代码:
# p = 0
# q = l - 1
# x = rotateArray[l/2]
# while p+1 == q:
# if rotateArray[p] < x:
# p = l/2
# elif rotateArray[q] > x:
# q = l/2
# else:
# return True
# return max(rotateArray[p],rotateArray[q])
二分法怎么学的,都不会写
7斐波那契数列
大家都知道斐波那契数列,现在要求输入一个整数n,请你输出斐波那契数列的第n项(从0开始,第0项为0)。n<=39
递归可以解决,但是会有很严重的效率问题。
这棵树的很多结点是重复的,而且重复的结点数会随着n的增大而急剧增加,计算量也会急剧增大。用递归方法计算的时间复杂度是以n的指数的方式递增的。要想办法避免重复计算。
更简单的办法是从下往上计算,首先根据f(0)和f(1)算出f(2),再根据f(1)和f(2)算出f(3),..,以此类推,可以算出第n项了。时间复杂度为O(n)。
用循环:
# -*- coding:utf-8 -*-
class Solution:
def Fibonacci(self, n):
# write code here
if n == 0:
return 0
elif n == 1:
return 1
else:
fib0 = 0
fib1 = 1
fibn = 0
for i in range(2,n+2):
fibn = fib0 + fib1
fib1 = fib0
fib0 = fibn
return fibn
第二种:
# -*- coding:utf-8 -*-
class Solution:
def Fibonacci(self,n):
if n == 0:
return 0
elif n ==1:
return 1
else:
a = 0
b = 1
for i in range(2,n+1):
a,b = b,a+b
return b
8.跳台阶
一只青蛙一次可以跳上1级台阶,也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法(先后次序不同算不同的结果)。
同上题,也是斐波那契数列
# -*- coding:utf-8 -*-
class Solution:
def jumpFloor(self, number):
# write code here
if number == 1:
return 1
elif number ==2:
return 2
else:
a = 1
b = 2
for i in range(3,number+1):
a,b = b,a+b
return b
9.变态跳台阶
一只青蛙一次可以跳上1级台阶,也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
推算得知2(n-1)种跳法
# -*- coding:utf-8 -*-
class Solution:
def jumpFloorII(self, number):
# write code here
return 2**(number-1)
10.矩形覆盖
我们可以用2*1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形,总共有多少种方法?
先把2*8的覆盖方法记为f(8),用第一个1*2小矩形去覆盖大矩形最左边时有两个选择,当竖着放的时候,右边还剩2*7的区域,这种情形下的覆盖方法记为f(7)。接下来考虑横着放的情况,当1*2的小矩形横着放左上角的时候,左下角必须再横着放一个1*2的小矩形,而在右边还剩下2*6的区域,这种情形下的覆盖方法记为f(6), 因此f(8) = f(7) + f(6), 因此还是斐波那契数列。
# -*- coding:utf-8 -*-
class Solution:
def rectCover(self, number):
# write code here
if number == 0:
return 0
elif number ==1:
return 1
elif number ==2:
return 2
else:
a ,b = 1,2
for i in range(3, number+1):
a, b = b, a+b
return b