给Google onsite面经添砖加瓦

yxyxyx 发表于 2016-10-16 23:35
不是啊，我的算法仍然是4啊
111,000,000,011 (+1) -> 111,000,000,100 (往右进两位）-> 001,110,000,001 ...

你的思路跟我挺像的，不過你用+1 -1來說明，我想很難讓大家看懂。這題的關鍵在於可以用+1把多個1，ˊ轉化成兩個1。假設你有一個數是111...1 (n個1)，原本的表示法需要用n個2^x來表示，但是+1之後，數字變成了1000...0 (1個1後面帶n個0)，只需要1個2^x表示，加上你要把多加的1 (2^0) 扣回去，所以原數字可以用兩個2^x表示。-1並不是很必要，反正right shift都會被吃掉。

思路：
一開始count = 0
看least significant bit
->是0忽略
->是1的話，count++，然後往左看有無連續1 (實際上看左邊一位就行)
    ->左邊是1，+1讓他進位
    ->左邊是0忽略
往右shift一個bit，重複上述步驟ˋ直到number變成0

實際上遇到1個1就count++，為什麼呢？假如這個1是單獨的，那麼我們必定要用一個2^x表示它。假如是連續的，那麼如上面所說，我們可以用+1進位後，用兩個2^x來表示，這邊count++是先算你多加的1 (2^0)，另外一個1因為被你進位跑去左邊了，所以之後遇到他會是單獨的1，到時候你還是會算到他，所以總共是兩個1。

楼主加油啊。看描述免得不错

yxyxyx 发表于 2016-10-17 00:01
恩。暴力算是一种算法。其实我感觉也可以数学算出来。下面写一下算法，不知道正确与否。。。

比如一开 ...

你电面过了吗？啥时候直播啊？

ytsr 发表于 2016-10-16 15:26
你电面过了吗？啥时候直播啊？

lol要哭了

楼主有结果了吗？

请问下楼主吃药片这两问的时间复杂度都是怎么回答的？谢谢

第一题，这样对不对
对每一位 如果是0，dp[i] = dp[i-1] ；如果是1， dp[i]  = min(dp[i-1]+1, num of 1, 2+num of 0)

目测遇到了同一个国人姐姐。我当时做2^n的题的时候她给的提示是化成一棵二叉树，左子树是比它小的最大的2的幂，右边是比他大的最小的2次幂

wcyz666 发表于 2016-10-17 12:00
目测遇到了同一个国人姐姐。我当时做2^n的题的时候她给的提示是化成一棵二叉树，左子树是比它小的最大的2的 ...

其实我也是这么做的。。。沾一下大神的仙气！

jy_121 发表于 2016-10-17 11:30
请问下楼主吃药片这两问的时间复杂度都是怎么回答的？谢谢

第一问没问，第二问n^2