一道樂視網的面試題，求解答？

沒做出來,es6的bfs留下當參考吧

function bfs(x){
let m=new Set([0]);
for(let i=0;;i++){
let k=new Set();
for(let j of m){
if ((j+i)==x) return i;
if ((j-i)==x) return i;
k.add(j+i);
k.add(j-i);
}
m=k;
}
}
&>
&> [200,300,40000].map(bfs);
[ 20, 24, 283 ]

function calc(x){
if (x&<0) x=-x; let n1=parseInt((1+Math.sqrt(8*x+1))/2,10); let x1=n1*(n1-1)/2 if (x1==x) return n1-1; let x2=x1+n1-x; if (!(x21)) return n1; if (!(n11)) return n1+1; return n1+2; } for(i=0;i&<1000;i++){ if (bfs(i)!=calc(i)) console.log(i) }

聲明：僅考慮正距離。

首先，反過來考慮一個問題：

1：利用二次方程求解公式求出x0

double x0=Math.ceil((Math.sqrt(1+8*k)-1)/2);


2：奇偶性判斷

如果k和奇偶性不同，則需要修正x0

if(k % 2 == 0){
if(x0 % 4 == 1){
x0 += 2;
} else if (x0 % 4 == 2){
x0 += 1;
}
}else{
if(x0 % 4 == 0){
x0 += 1;
} else if (x0 % 4 =3){
x0 += 2;
}
}


一開始覺得很難，覺得自己很水。。。。後來洗澡的時候想了一下，居然想出來答案了，真是覺得自己萌萌噠。

答案樓上已經說得很清楚了，我簡單地說說：

1.螞蟻最少跳多少步？

2. 有沒有比p少的步數？

3. 為什麼第p步一定能剛剛好跳到「輸入數據」？

可以這樣想，如果沒有後跳的話，跳躍過程是一個1～n的求和過程，即

現在過程中加入了後跳，所以上面的求和式中有某些元素會變成負，由正變負相當於減2k，因此上式可改為， 即1～n的和減去一個偶數後等於x

所以這個問題會有兩種情況：

class Solution:
def JumpSteps(self, x):
s = 0
i = 0
steps = 0

return steps


大號被禁言了換小號來重新答一發

int jumpTo(long x) {

//sum和x奇偶性相同，這裡很多答主都指出了，雖然我大號答的時候並沒有多少人指出來

//奇偶性不同的話，就要看下一個，那麼要找一個奇數n才可以，這裡還是有人以為return n就可以了，拿衣服

第一印象：如果x大於0，可以至多2x步解決問題，先向後跳再向前跳，會前進1個單位，重複x次可以到達x處。

編程實現步驟如下：

根據數學推導不難驗證以下結論：

因此之前的程序可以簡化了，直接計算得出結論。

這個方法很快，但有可能不是最優，有目標可能不需要多兩步。但是可以接受了。

根據數學推導不難驗證以下結論：

因此可以優化上一次的程序第3步如下：

問題可以簡化為，求的值

因為每次只能向前或者向後跳個單位，所以我們只能先找到後面可以取到的最大值，即然後通過改變數字前面的正負號使為要求的數值，可以概述為向後求最大然後向前取整，但向前取的時候只能使值為偶數（因為把一個值由正改為負時相當於減去2倍的這個值），所以減的值只能是偶數

#include &
using namespace std;