剣指offer python
2125 ワード
1、みんなはすべてフィボナッチ数列を知っていて、今1つの整数nを入力することを要求して、フィボナッチ数列の第n項(0から、第0項は0)を出力してください.n<=39
2、カエルが一度に1段の階段を飛び上がることも、2段を飛び上がることもできます.このカエルが1つのn級の階段に飛び上がるのが全部で何種類の跳び方があることを求めます(前後の順序が異なって異なる結果を計算します)
3、一匹のカエルが一度に1段の階段を飛び上がることもできるし、2段を飛び上がることもできるし...n段を飛び上がることもできる.このカエルが1つのn級の階段を跳ぶことを求めて全部で何種類の跳び方があります.法則を探る.
逆方向で
4、毎年6月1日の子供の日に、牛客は孤児院の子供を見舞いに行く小さな贈り物を用意しています.今年もそうです.HFは牛客のベテラン元老として、もちろん小さなゲームも用意されています.その中で、まず、子供たちを大きな輪に囲ませるゲームがあります.そして、彼はランダムに数mを指定し、0番の子供にカウントを開始させた.毎回m-1のあの小さい子供を叫んで歌を歌って、それから赠り物の箱の中で任意の选択の赠り物を选んで、しかももう圏の中に戻らないで、彼の次の小さい子供から、引き続き0...m-1の报数...このように下りて...最后の1人の小さい子供まで、演技をしないで、しかも牛客の名高い"名探侦コナン"の典蔵版を手に入れることができます(定員は限られています!!).どの子がこの贈り物をもらうか考えてみてください.(注:子供の番号は0からn-1)注:式
class Solution:
def Fibonacci(self, n):
if n == 0:
return 0
if n == 1:
return 1
a = 0
b = 1
res = []
# 2 1 , n, n-1
for i in range(n-1):
res = a + b
a = b
b = res
return res
2、カエルが一度に1段の階段を飛び上がることも、2段を飛び上がることもできます.このカエルが1つのn級の階段に飛び上がるのが全部で何種類の跳び方があることを求めます(前後の順序が異なって異なる結果を計算します)
class Solution:
def jumpFloor(self, number):
if number == 1:
return 1
if number == 2:
return 2
ret = 0
a = 1
b = 2
for i in range(number-2):
ret = a + b
a = b
b = ret
return ret
3、一匹のカエルが一度に1段の階段を飛び上がることもできるし、2段を飛び上がることもできるし...n段を飛び上がることもできる.このカエルが1つのn級の階段を跳ぶことを求めて全部で何種類の跳び方があります.法則を探る.
class Solution:
def jumpFloorII(self, number):
num = 2**(number-1)
return num
逆方向で
f(n)=f(n-1)+f(n-2)+...+f(1) f(n-1)=f(n-2)+...f(1) f(n)=2f(n-1)
を探しますclass Solution:
def jumpFloorII(self, number):
if number == 1:
return 1
ret=1
for i in range(number-1):
ret=2*ret
return ret
4、毎年6月1日の子供の日に、牛客は孤児院の子供を見舞いに行く小さな贈り物を用意しています.今年もそうです.HFは牛客のベテラン元老として、もちろん小さなゲームも用意されています.その中で、まず、子供たちを大きな輪に囲ませるゲームがあります.そして、彼はランダムに数mを指定し、0番の子供にカウントを開始させた.毎回m-1のあの小さい子供を叫んで歌を歌って、それから赠り物の箱の中で任意の选択の赠り物を选んで、しかももう圏の中に戻らないで、彼の次の小さい子供から、引き続き0...m-1の报数...このように下りて...最后の1人の小さい子供まで、演技をしないで、しかも牛客の名高い"名探侦コナン"の典蔵版を手に入れることができます(定員は限られています!!).どの子がこの贈り物をもらうか考えてみてください.(注:子供の番号は0からn-1)注:式
f(n)=(f(n-1)+m)%n
でclass Solution:
def LastRemaining_Solution(self, n, m):
# write code here
if n < 1 or m < 1:
return -1
if n == 1:
return 0
value = 0
for i in range(2,n+1):
value = (value + m) % i
return value