Codility FrogJmp in Python

发表于 更新于 分类于 ， Disqus：

算法复杂度分析

情况 时间复杂度 空间复杂度
最优 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)