Codility FrogJmp in Python

  • Shuwei Zhang & Jinhai ZHOU
  • 1 Minutes
  • 2017年5月31日

算法复杂度分析

情况 时间复杂度 空间复杂度
最优 O(1) O(1)
平均 O(1) O(1)
最差 O(1) O(1)

算法复杂度不依赖于输入数据的多少,该算法总是在固定时间内完成。

算法分析

已知长度Y-X,步长D,求步数。难点在于长度能否整除步长,若能整除,返回步长,若不能整除,对步长向上取整。向上取整可以同python math库里的ceil函数。如果不想加载math库,只用python内建函数可以吗?其实也是可以的。难度在对于求得的步长是否+1上。由于python除法/会截断小数部分,我们可以用取余%操作判断长度能否整除步长,若能整除,返回步长,若不能整除,对步长+1即可。

Python 数值转换

python 数值转换函数int()把bool型转换为int型整数值,int(True) => 1 int(False) => 0

源代码

1
2
3
def solution(X, Y, D):
# write your code in Python 2.7
return (Y-X)/D + int((Y-X)%D > 0)