笔试题：跳跃游戏每一次比上一次多跳1（数学，二进制搜索）_起点出发,从1步开始,每次走的步数都比上一次增加一步

在数轴上有一个起点和一个终点，第一步跳1，第二步跳2，第三步跳3，… 但是可以左右跳，最后问最少跳几步
例子： 0 ——> 2: 0 -> 1 -> -1 -> 2

import math

#二进制进行暴力破解
def brute(n):
    k = 1
    # 遍历跳 1,2,3,4,5...次
    while True:
        # 生成每一次的每一条的步数列表
        base = list(range(1, k + 1))
        # 生成每一跳的左右遍历的二进制数字
        for i in range(2 ** k):
            dist = 0
            # 获取每一位的数值计算最后跳跃坐标
            for j in range(k):
                # i & (1 << j) 将i第j号位上的数值进行保留其余归0，可以用来判断该位是否为0
                coef = 1 if i & (1 << j) else -1
                dist += base[j] * coef
            if dist == n:
                return k
        k += 1


def math_method(n):
    # 求根
    k = math.ceil((math.sqrt(8 * n + 1) - 1) / 2)
    # 求差值
    r = k * (k + 1) // 2 - n
    # 差值要是2的倍数
    if r % 2:
        if k % 2:
            return k + 2
        else:
            return k + 1
    else:
        return k


if __name__ == '__main__':
    for i in range(1, 20):
        print(i, math_method(i), brute(i))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40