题目大意：第i时刻可以移动+i,-i单位距离。初始在原点，问最少对少时间可以移动到target坐标。
Problem:
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:
|
1 2 3 4 5 |
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:
|
1 2 3 4 5 6 |
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:
targetwill be a non-zero integer in the range[-10^9, 10^9].
Idea:
Math
Time complexity: O(sqrt(target))
Space complexity: O(1)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
// Author: Huahua // Running time: 3 ms class Solution { public: int reachNumber(int target) { target = std::abs(target); int k = 0; int sum = 0; while (sum < target) sum += (++k); const int d = sum - target; if (d % 2 == 0) return k; return k + 1 + (k % 2); } }; |
O(1)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
// Author: Huahua // Running time: 3 ms class Solution { public: int reachNumber(int target) { target = std::abs(target); int k = sqrt(target * 2); while (sum(k) < target) ++k; int d = sum(k) - target; if (d % 2 == 0) return k; return k + 1 + (k % 2); } private: int sum(int k) { return k * (k + 1) / 2; } }; |
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Paypal
Venmo
huahualeetcode
huahualeetcode
微信打赏
Be First to Comment