题目:
- 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].
解题思路:
看完题目后,我脑子里首先出现的是动态规划算法解决这一类问题。但是仔细想想,又觉得不太对,首先 target 的范围很大,没有这个大的数组可以保存中间结果。之后脑子里闪过了无数的方法,但都被一一否决了。万般无奈之下,想起了 "找规律" 的老办法。题目要求是从 0 开始,第 n 次操作可以到达 target,那么可以先试试找出每次操作可以到达的的 number,是否能够发现其中的规律。
- function unique(a) {
- var res = [];
- for (var i = 0,
- len = a.length; i < len; i++) {
- var item = a[i];
- for (var j = 0,
- jLen = res.length; j < jLen; j++) {
- if (res[j] === item) break;
- }
- if (j === jLen) res.push(item);
- }
- return res;
- }
- var reachNumber = function(target) {
- var l = [0]
- for (var i = 1; i < 6; i++) {
- var tl = []
- while (l.length > 0) {
- var t = l.pop() tl.push(t - i) tl.push(t + i)
- }
- var tl = unique(tl).sort(function(a, b) {
- return a - b
- })
- //console.log(i,':',tl[0],tl[1],tl[2],tl[3])
- console.log(i, ': ', tl) for (var j = 0; j < tl.length; j++) {
- l.push(tl[j])
- }
- }
- };
- reachNumber()
输出的结果如下:
1 ':' [-1, 1]
2 ':' [-3, -1, 1, 3]
3 ':' [-6, -4, -2, 0, 2, 4, 6]
4 ':' [-10, -8, -6, -4, -2, 0, 2, 4, 6, 8, 10]
5 ':' [-15, -13, -11, -9, -7, -5, -3, -1, 1, 3, 5, 7, 9, 11, 13, 15]
为了控制输出的长度,这里设置了 i<6 的条件,其实适当把 i 放大,会发现更明显的规律。
这里就直接把规律列出来了:
a. 第 n 次操作能到达的最大范围是 -(1+2+...+n) 和 (1+2+...+n);
b. 负数的 number 和正数的 number 是对称的,可以令 target = abs(target);
c. n%4 == 0 或者 n%4 == 3 的时候,只能移动到小于偶数的 number;
d. n%4 == 1 或者 n%4 == 2 的时候,只能移动到奇数的 number;
所以,要找出最小的 n,可以到达 abs(target) 分两种情况:
1. abs(target) 是偶数,需要满足上面的 a 和 c 两个条件;
2.abs(target) 是奇数,需要满足上面的 a 和 d 两个条件;
代码如下:
- var reachNumber = function(target) {
- if (target < 0) {
- target = -target
- }
- if (target == 1 || target == -1) {
- return 1
- }
- var isOdd = target % 2
- var count = 1;
- var t = 1;
- while (count++) {
- t += count
- if (t >= target && isOdd == 0 && (count % 4 == 3 || count % 4 == 0)) {
- return count;
- } else if (t >= target && isOdd != 0 && (count % 4 == 1 || count % 4 == 2)) {
- return count
- }
- }
- };
- console.log(reachNumber(1))
来源: http://www.bubuko.com/infodetail-2450277.html