第五章 - 高频考题(中等)
1906. 查询差绝对值的最小值
0754. 到达终点数字

题目地址(754. 到达终点数字)

题目描述

1
在一根无限长的数轴上,你站在0的位置。终点在target的位置。
2
3
每次你可以选择向左或向右移动。第 n 次移动(从 1 开始),可以走 n 步。
4
5
返回到达终点需要的最小移动次数。
6
7
示例 1:
8
9
输入: target = 3
10
输出: 2
11
解释:
12
第一次移动,从 0 到 1 。
13
第二次移动,从 1 到 3 。
14
示例 2:
15
16
输入: target = 2
17
输出: 3
18
解释:
19
第一次移动,从 0 到 1 。
20
第二次移动,从 1 到 -1 。
21
第三次移动,从 -1 到 2 。
22
注意:
23
24
target是在[-10^9, 10^9]范围中的非零整数。
Copied!

前置知识

  • 数学

公司

思路

不难看出, 问题的本质就是一个有限序列, 1,2,3,4... 。我们的目标是给这个序列的元素添加正负号,是的其和为 target。这和 494.target-sum 的思路是一样的。
拿题目的 target = 3 来说, 就是 1 + 2 = 3。
拿题目的 target = 2 来说, 就是 1 - 2 + 3 = 2。
为什么是有限序列?
因为我们始终可以在 target 次以内走到 target。严格来说, 最少在根号 target 左右就可以走到 target。
和 494.target-sum 不同的是, 这道题数组是无限的,看起来似乎更难,实际上更简单, 因为数组是有规律的,每次都递增 1。
由于 target 正负是对称的, 因此 target 最少走多少布,-target 也是多少步。因此我们只考虑一种情况即可, 不妨只考虑正数的情况。
其实,只要找出第一个满足 1 + 2 + 3 + .... + steps > target 的 steps 即可。
令 1 + 2 + 3 + .... + steps 为 T。接下来,我们来对不同情况进行分析。
  • 如果 T 等于 target,那么 steps 就是我们想求的值,直接返回即可。
  • 否则,我们尝试从 [1, steps] 这 steps 个数中找出几个数改成其符号,不难知道找的这几个数的和是 (T - target) / 2。
    1. 1.
      如果 T 是偶数, 那么我们总可以找出若干数字使其变为符号,满足 1 + 2 + 3 + .... + steps == target,因此直接返回 steps 即可。
    2. 2.
      如果 T 是奇数,(T - target) / 2 是个小数,肯定无法选取的,因此我们还需要在多选数,比如 steps + 1,steps + 2。 由于 T + steps + 1 和 T + steps + 1 + steps + 2 中有且仅有一个是偶数。我们仍然可以套用上面的方法,找出若干数字使其变为负号,满足 1 + 2 + 3 + .... + steps + steps + 1 == target 或者 1 + 2 + 3 + .... + steps + steps + 1 + steps + 2 == target。也就是说在这种情况下答案就是 steps + 1 或者 steps + 2,具体是哪个取决于 T + steps + 1 是偶数还是 T + steps + 1 + steps + 2 是偶数

关键点解析

  • 对元素进行分组,分组的依据是符号, 是+ 或者 -
  • 通过数学公式推导可以简化我们的求解过程,这需要一点数学知识和数学意识

代码(Python)

Python Code:
1
class Solution(object):
2
def reachNumber(self, target):
3
target = abs(target)
4
steps = 0
5
while target > 0:
6
steps += 1
7
target -= steps
8
if target & 1 == 0: return steps
9
steps += 1
10
if (target - steps) & 1 == 0: return steps
11
return steps + 1
Copied!
复杂度分析
  • 时间复杂度:$O(\sqrt target)$
  • 空间复杂度:$O(1)$

相关题目