[Swift]LeetCode754.到达终点数字|ReachaNumber

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› 移动开发›Swift 教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址： https://www.cnblogs.com/strengthen/p/10532569.html
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎，请直接点击！！！

进入博主App Store主页，下载使用各个作品！！！

注：博主将坚持每月上线一个新app！！！

You are standing at position 0 on an infinite number line. There is a goal at position target.

On each move, you can either go left or right. During the n-th move (starting from 1), you take n steps.

Return the minimum number of steps required to reach the destination.

Example 1:

Input: target = 3
Output: 2
Explanation:
On the first move we step from 0 to 1.
On the second step we step from 1 to 3.

Example 2:

Input: target = 2
Output: 3
Explanation:
On the first move we step from 0 to 1.
On the second move we step  from 1 to -1.
On the third move we step from -1 to 2.

Note:

target will be a non-zero integer in the range [-10^9, 10^9].

在一根无限长的数轴上，你站在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]范围中的非零整数。

Runtime: 4 ms

Memory Usage: 18.4 MB

 1 class Solution {
 2     func reachNumber(_ target: Int) -> Int {
 3         let target = abs(target)
 4         let a: Double = 1; let b: Double = 1; let c: Double = -2 * Double(target);
 5         let delt = b * b + 4 * a * c
 6         //一元二次方程求根公式
 7         var count = Int(ceil((-b+sqrt(abs(delt)))/(2*a)))
 8         // 第n步往回走, 累加值相应减少2n
 9         // 当累加值减去target等于2n时, 返回结果
10         var sum = Int((1 + Double(count)) / 2 * Double(count))
11         while (Int(sum) - target) % 2 != 0 {
12             count += 1
13             sum += count
14         }
15         return count
16     }
17 }

Runtime: 8 ms

Memory Usage: 18.6 MB

 1 class Solution {
 2     func reachNumber(_ target: Int) -> Int {
 3         var target = abs(target)
 4         var res:Int = 0
 5         var sum:Int = 0
 6         while (sum < target || (sum - target) % 2 == 1)
 7         {
 8             res += 1
 9             sum += res
10         }
11         return res
12     }
13 }

12ms

 1 class Solution {
 2     func reachNumber(_ target: Int) -> Int {
 3         var target = abs(target)
 4         var k = 0
 5         
 6         while (target > 0) {
 7             k += 1
 8             target -= k
 9         }
10         
11         return target&1 == 0 ? k : (k+1+(k&1))
12     }
13 }

16ms

 1 class Solution {
 2   func reachNumber(_ target: Int) -> Int {
 3     let target = abs(target)
 4     
 5     var sum = 0
 6     var steps = 0
 7     
 8     while sum < target {
 9       steps += 1
10       sum += steps
11     }
12     
13     let dist = sum - target
14     
15     if dist == 0 || dist % 2 == 0 {
16       return steps
17     } else {
18       if (dist + steps + 1) % 2 == 0 {
19         return steps + 1
20       } else {
21         return steps + 2
22       }
23     }
24   }
25 }