python-剑指offer6-10
6、查找和排序
把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。 输入一个非减排序的数组的一个旋转，输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。 NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。
class Solution:
def minNumberInRotateArray(self, rotateArray):
# write code here
if len(rotateArray) == 0:
return 0
for i in range(len(rotateArray)-1):
if rotateArray[i+1] < rotateArray[i]:
return rotateArray[i+1]
# 都没找到
return rotateArray[0]解题思路：首先得弄清题意，旋转数组是[3,4,5,1,2]，两部分都是递增的，前部分总大于或等于第二部分
7、递归和循环
大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0）。
class Solution:
def Fibonacci(self, n):
# write code here
if n == 0:
return 0
if n == 1:
return 1
if n >= 2:
res = [0 for _ in range(n+1)]
res[1] = 1
for i in range(2,n+1):
res[i] = res[i-1] + res[i-2]
return res[-1]8、动态规划
一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。
class Solution:
def jumpFloor(self, number):
# write code here
if number == 1:
return 1
if number == 2:
return 2
res=[0 for _ in range(number)]
res[0]=1
res[1]=2
for i in range(2,number):
res[i]=res[i-1]+res[i-2]
return res[-1]解题思路：动态规划。第i个台阶的跳法与第i-1个和i-2个台阶有关。因为青蛙可以跳1级或者2级。
9、动态规划
我们可以用2*1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？
class Solution:
def rectCover(self, number):
# write code here
if number == 0:
return 0
elif number == 1:
return 1
elif number == 2:
return 2
res=[0 for _ in range(number+1)]
res[1]=1
res[2]=2
for i in range(3,number+1):
res[i]=res[i-1]+res[i-2]
return res[-1]解题思路：本质上还是斐波那契数列
10、
输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。
class Solution:
def NumberOf1(self, n):
# write code here
count = 0
if n < 0:
n = n & 0xffffffff
while n:
n = (n-1) & n
count +=1
return count解题思路：Pyhton负数的补码表示。以1100为例，1100 减去 1 得到 1011，发现其实减去1就是将最右的1变为0，将右边的0变为1， 所以 1100 和 1011 做按位与运算，得到 1000 就相当于抹掉了最右边的1。按照这种思路，只要一直减去1，就逐个从右边抹掉了1，当整个数 = 0 时说明抹完了，循环次数就是1的个数。
11、优化递归、界限判断
给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。
class Solution:
def Power(self, base, exponent):
# write code here
if base == 0:
return 0
if exponent == 0:
return 1
e = abs(exponent)
tmp = base
res = 1.0
while(e > 0):
#如果是奇数，乘以一次，是偶数，乘以平方
if (e & 1 == 1):
res =res * tmp
e = e >> 1
tmp = tmp * tmp
return res if exponent > 0 else 1/res解题思路：注意界限的判断，以及位运算的使用>>。
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2020-05-25 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读