Leetcode 754. Reach a Number [Python]

本文主要是介绍Leetcode 754. Reach a Number [Python]，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

先来一个BFS吧，可以想做一个binary tree，root是0.左侧子树是0-1，右侧是0+1.然后每一层的边的权重比上一层+1.也就是第二层节点是-1，1，其左子是 - 1 -2，-1+2以及1-2和1+2. 找到target时，返回层数-1.这样做会TLE。

class Solution:def reachNumber(self, target: int) -> int:level = 1que = collections.deque()que.append(0)while que:size = len(que)for _ in range(size):curpos = que.popleft()if curpos == target:return level - 1newpos1 = curpos + levelnewpos2 = curpos - levelque.append(newpos1)que.append(newpos2)level += 1return -1

接下来是binary search版本

class Solution:def reachNumber(self, target: int) -> int:target = abs(target)r = targetl = 1while r > l:mid = l + (r- l)//2#sumif (1 + mid)*mid//2 < target:l = mid + 1else:r = mid#cursum:overpart = (l + 1)*l//2 - targetwhile overpart%2:overpart += l + 1l += 1return l

从每次增加的量入手，第一次增加1，第二次2，一直增加的总和到某一个数，也就是走的步数n，那最后停留（只看+的）的位置为1+2+3+4.。。。+n，计算为（1+n）*n//2. 假设n为binary search的目标值，l =0，r = target。当我们计算的到的mid ->n,使得（1+n）*n//2 大于target值后，我们尝试增加下一步（步数+1），直到使得超过target的部分为偶数，超过部分为overpart，则我们其实上再需要多走一步，-overpart/2，这样，总量增加量实际上要减去+的overpart/2，并且还要增加一个-的overpart/2。

这篇关于Leetcode 754. Reach a Number [Python]的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---