Leetcode Weekly Contest 65 题解及训练
754. Reach a Number
大意
给出一个 target
这个数称之为目标数字。我们的其实数字是 0
,每次可以进行 +n
和 -n
的操作,这个 n
是次数,当我们重复进行这个操作并第一次到达 target
的时候,输出 n
。
思路
比赛的时候,首先想到的是 BFS 搜,感觉就是一道搜索题。但是 target
的数据量是 [-10^9, 10^9]
,高达 2e9
的数量级,搜索肯定是行不通的。再考虑剪枝手段,发现这样的数字正负是对称的,可以减一半的基数,再建立一个 visited
的表来标记已经访问的数字,但是复杂度也是相当的大。
第二考虑动态规划,但是在推倒转移方程的时候,发现 dp[n]
与 dp[n - 1]
没有直接的数量关系,而且整体的关系网图是一个树形结构,所以在 dp[n]
的时候,要考虑 2^n
种情况,显然状态压缩行不通。(比赛GG)
赛后在 Discuss 中看到一个数学思路。
- 由于问题具有对称性,所以可以先将
target
绝对值,得到T
; - 计算前 n 项和
sum
并让其满足下式:
$$sum=1+2+3+…+n\geq T$$
- 如果 $1+2+3+…+n=T$ 直接返回
n
- 否则令 $res=sum-T$,如果
res
是偶数,那么肯定存在一个整数x
保证 $2x=res$在 $[1,n]$ 中。我们让这个x
取反即可,仍旧返回n
$$res\ is\ odd\Longrightarrow T=1+2+3+…-x+…+n\ \ (x\subseteq [1,n])$$
- 如果
res
是奇数且n + 1
是奇数,继续向sum
中添加n + 1
。然后得到x
同上一操作进行翻转。如果n + 1
是偶数,那么继续添加n + 2
在做x
翻转操作。由于 $sum\geq T$ 且是sum
的最小值,所以n
能保证最小值。
import math
class Solution:
def reachNumber(self, target):
target_abs = abs(target)
n = math.ceil((-1 + math.sqrt(1 + 8 * target_abs)) / 2)
sum = n * (n + 1) / 2
if sum == target:
return n
res = int(sum - target)
if res & 1 == 0:
return n
else :
return n + (1 if n & 1 == 0 else 2)