拼多多-到达终点数字
2019-07-27 本文已影响0人
葡萄肉多
在一根无限长的数轴上，你站在0的位置。终点在target的位置。
每次你可以选择向左或向右移动。第 n 次移动（从 1 开始），可以走 n 步。
返回到达终点需要的最小移动次数。
示例 1:
输入: target = 3
输出: 2
解释:
第一次移动，从 0 到 1 。
第二次移动，从 1 到 3 。
示例 2:
输入: target = 2
输出: 3
解释:
第一次移动，从 0 到 1 。
第二次移动，从 1 到 -1 。
第三次移动，从 -1 到 2 。
注意:
target是在[-10^9, 10^9]范围中的非零整数。
思路
-
target的正负无影响，比如：
2 = 1-2+3
-2 = -1+2-3
所以将输入取绝对值，全部设为正 -
每次右移，1+2+3+···+i 直到 sum>=target；
-
如果target = sum i 即为结果
如果target-sum 差值为偶数，可以翻转一个数字的符号来完成等式。比如sum-target=4，那么我们把2变成-2，那么sum减小了4。
也就是可以归结为：
- 当sum-target为偶数，1+...-（sum-target）/2+...+k=target，那么答案依然是k。#2
- 当sum-target为奇数，那么sum-target+1是一个偶数，类似#2的证明，1+...-(sum-target+1)/2+...k=target-1
- 向左时无论当前步数是奇是偶，相当于乘2，都会变成偶数。所以只有当(sum - target)为偶数时，才能通过向左移动使得最终到达target。
代码
target = abs(int(input()))
sum = 0
i = 1
re = i
while True:
sum += i
if sum >= target and (sum - target) % 2 == 0:
re = i
break
i += 1
print(re)
