手机怎么做网站免费的/市场调研方法有哪几种

754. 到达终点数字

难度中等101

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

思维1：首先x与-x的答案是一样的，只是在对1 2 3 ....n中的n-1个位置加正负号是完全相反的而已，因此可以统一为正数；然后就可以采用BFS的方式搜索整个解答树，借用BFS能够搜索最短路径的特点得到答案。问题：层次过深的时候会导致队列过大，所以无论是时间还是空间复杂度都挺令人堪忧的。

class Solution {
public:struct bfs_node{int val;int floor;bfs_node(int v, int f){val = v;floor = f;}};int BFS(int target){queue<bfs_node> bfs_queue;bfs_node node(target, 0);bfs_queue.push(node);while(!bfs_queue.empty()){node = bfs_queue.front();bfs_queue.pop();if(node.val == node.floor + 1 || node.val == -node.floor - 1){return node.floor + 1;}bfs_queue.push(bfs_node(node.val - (node.floor + 1), node.floor + 1));bfs_queue.push(bfs_node(node.val + (node.floor + 1), node.floor + 1));}return -1;}int reachNumber(int target) {return BFS(target);}
};

思维2：与思维1类似，搜索整个解答数，用DFS配合剪枝的方式。

        需要关注的有两点：[负数直接看成正数即可]

                1.要凑成target，最多需要target*2步，因为只需要两步就必定可以凑出1，如(-1+2)。

                2.我们可以倒过来考虑问题，从target开始，逐步考虑1、2.。。。直到target为0为止，在这个过程中可以用哈希表进行记忆化。

        但是由于解答树的深度可能很大，因此方法的缺陷也比较大。

思维3：纯数学解法。首先我们设k是满足下式的最小正整数：

                                                [1]

分情况讨论：

1.取等于的情况，毫无疑问，答案就是k

2.取大于的情况：我们知道当我们将一个整数x变-x并加上它的时候，我们的数会相较原来少掉2*x，所以这里需要讨论多出来的部分是奇数还是偶数的情况

        A.若为偶数，首先我们根据对k的假设可以知道:

                            [2]

                           [3]

              所以必有结果：

                           [4]

               由[2][3]推导，因而可得[4]。

然而在考虑k之前，我们已经考虑过所有小于k的数。设S-target=x，因为x<k且x%2==0，所以x/2必定是整数且属于[1,k]，直接取反即可，此时只用到了k个数。

         B.若为奇数，那么我们设多余的部分为x(x<k)，而我们考虑的数里包括了x-1，我们直接将(x-1)/2取反，这样多余的部分就只剩下1了，再来看k

                   1）k为奇数，那么通过1+k+1-(k+2)使得多余部分为0。

                        [注]：这里要使用k+1和k+2的原因在于[1,k]的数如果使用了就会导致问题，例如我们使用-1+2，假如原来在得到和的时候使用的是1和2，那么我们会把前面[1,k]和减去了2。

                   2）k为偶数(k>=2 &&  k%2==0)，那么通过1+k+1得到新的多余部分为偶数，有下式：

                        当且仅当k>=2时成立，此时让1+k/2对应的数值取反即可。

代码1：

class Solution {
public:int reachNumber(int target) {if(target < 0) target = -target;int k = 0, upper = 0, diff;while(upper < target){++ k;upper += k;}diff = upper - target;return diff == 0 ? k : (diff & 1 ? k + 1 + (k & 1) : k);}
};

代码2：(使用sqrt需要处理一些边界问题，因为浮点强转为int小数会直接截断)

class Solution {
public:int reachNumber(int target) {if(target < 0) target = -target;int k = sqrt(target << 1), upper = (k * (1 + k)) >> 1, diff;while(upper < target){++ k;upper = (k * (1 + k)) >> 1;}diff = upper - target;return diff == 0 ? k : (diff & 1 ? k + 1 + (k & 1) : k);}
};