[397] Integer Replacement

嗯.......... 嗯?! XD
給一個數字, 如果它可以整除2, 就除, (怎麼好像廢話XD)
不行的話, 可以加一或減一 (隨便你～)(其實不是隨便你, 因為要選最後次數小的)
加一或減一之後就可以整除2了(廢話again)那就除2 (贅詞超多XD)
要問經過幾次之後這個數會等於1  ?
要算最小的次數

看完題目就會想說,又可以加一又可以減一,
那應該是加一跟減一出來的結果一樣吧(才不是)不然幹嘛這麼隨意
結果竟然真的有差呢呵呵 (戳自己太陽穴)

Integer Replacement
int integerReplacement(int n) {
    if (n==1)
        return 0;

    int count = 1;
    if (n==2)
        return 1;
    if (n==3)
        return 2;
    int t1,t2;
//printf("%d count[%d]\n",n, count);
    if (n%2==0)
        count = count + integerReplacement((unsigned int)n /2);
    else
    {
        t1 = integerReplacement((unsigned int)(n+1));
        t2 = integerReplacement((unsigned int)(n-1));
        count = count + ((t1 < t2) ? t1 : t2);    
    }
    return count;
}
是說因為它規定是正整數,
所以不會有世界大的測資進來
再怎麼跑也是最久xx ms 那樣
所以看不出來我的運算時間如何(其實應該是很慢)
看了別人的解法有一些小技巧 (which is 我一向覺得很機歪, 誰曉得啊啊啊啊啊)
比方說整除二要怎麼寫呢?
直覺就是 n%2 == 0 嘛 ,  %是取餘數的意思 (該不會只有我的直覺長這樣)
不過原來可以寫 n&1 , 是1那就是奇數, 是0就是偶數,
會這樣寫的人是不是腦海中都有一個bit mapping的表呀是不是
不然為什麼會想到這樣寫?!
讓我想到之前工作的時後要弄一個加密的東西, 必須算它是不是某個數的倍數,
我寫完直觀寫法之後, code review完就變成一串 << && >> 左移右移and然後or 的東西
今天如果那code不是我寫的,  我又沒有內建bit運算的 mapping表(有這種東西嗎)的話
那我怎麼知道它是在幹嘛啊啊啊啊啊啊啊啊(左手背拍右手心)
(跳一下)
另外一個小技巧是,
可以用 加一之後整除4的話 , 會比選擇減一來的快
為什麼你們會知道呢為什麼～～～～～（搖演算法奇才們的肩膀）
你們生下來就知道嗎
還是你們列了幾千幾萬個資料後確定是這樣呢？
是一個歸納法是不是
歸納出來的結論一定是Qmonster世紀無敵超級笨吧屋屋屋屋屋
打完收工.....(是在順便偷偷抱怨什麼喇XD!)