一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 1368|回复: 25
收起左侧

求教一道狗家的面试题

[复制链接] |试试Instant~ |关注本帖
hidden_track 发表于 2016-5-19 06:24:19 | 显示全部楼层 |阅读模式

2016(4-6月) 码农类 本科 全职@Google - 内推 - Onsite |Otherfresh grad应届毕业生

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
input: int n. 1point 3acres 璁哄潧
function: 将n用2的指数表示,使得指数表达式的个数最少
output : int num(指数的最少个数). from: 1point3acres.com/bbs
e.g: input = 28
28 = 2^4 + 2^3 + 2^2  => num = 3
28 = 2^5 - 2^2             => num = 2
所以 output = 2

这题感觉可以用贪心,想了好久还是没想出来,求各位大神指点
goha111 发表于 2016-5-19 15:55:26 | 显示全部楼层
之前刚睡醒 题看的一知半解的就开始写答案真是太抱歉了- -   

我说下我的想法(以下所有数字都以二进制表示):. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
.1point3acres缃
首先有两点值得注意:

  1. trailing zeros不影响最终的结果。
        比如:1100, 11000, 11000000的最优解都是num = 2。因为对于多项式来说,trailing zeros只是在原基础上 * 2,也就是各个指数+1,但并不影响项的数目。
  
  2. 对于长串1,比如111, 11111,  11111111, 可以+1 -1,变为相应的2^n - 2^0,填了一项,但多了很多个0,转变为利用性质1,这样可以极大化简。


所以我的思路是,对于一个数字n,首先转化为2进制数字,然后从二进制数最低位向最高位开始循环:

  如果这个bit = 0,那么根据上述性质1,去掉不影响结果,那么直接pass,看下一个bit;
  如果这个bit = 1,那么根据性质2,继续查找接下来的连续的1,直到下一个bit为0或者已经到了最高位,然后将下一个bit置为1,从最低位到这位的bit都变为0,然后num = num + 1; 这时候由于后面的bit都是0,根据性质1, 又可以进行化简;   
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
如此循环  直到结束。

可能说的不是很明白,举个例子n = 236 = (11101100) 2:
首先初始化num = 0; 从最低bit开始向高位循环,遇到0 pass, 变为 111011;(即236 = 2^2 * 59 )
最低bit为1,向前找连续的1,找到2个,那么将倒数第3bit置为1,其余变为0,即为111100,num +1 变为1;(即 236 = 2^2 *(60 - 1) )
最低bit为0,一直pass,变为1111,即 236 = 2^2 *(2^2 * 15 - 1)
最低bit为1,向前找连续1,直到最高位,那么变为10000,num + 1变为2,即 236 = 2^2 *(2^2 * (16 - 1) - 1)
最低bit为0,一直pass,变为1,即236 = 2^2 *(2^2 * (2^4 - 1) - 1)

只剩一个1,那么num+1, 最终num=3。  从多项式里 可以看出最终的化简结果是:2^8 - 2^4 - 2^2

. 鍥磋鎴戜滑@1point 3 acres
已经验证过几个corner case,比如 如果是11101,那么无论是加1进位 还是减1再去掉结尾0,结果是一样的,对num没有影响。

这个程序应该还蛮好写的, 回去写一下再贴一下。  希望大家看看这个算法如何,是不是可以~~  一起讨论下~~

补充内容 (2016-5-19 15:58):
忘记说复杂度。由于转化为2进制,并在bit循环。int的话,int最大长度为32bit,也就是说,时间复杂度为O(1)
回复 支持 2 反对 1

使用道具 举报

cyqiii 发表于 2016-5-19 08:00:50 | 显示全部楼层
ericLaw 发表于 2016-5-19 07:55
你这个例子就是1100000 - 1

我的意思是每一位都需要考虑两种情况,所以复杂度是2^(log2(N)) =O(N)
而这实际就是用dp的思路

补充内容 (2016-5-19 08:03):
这个数字可以很复杂,0和1的pattern反复出现好几次,比如11100111001110011100111
回复 支持 3 反对 0

使用道具 举报

goha111 发表于 2016-5-19 16:22:23 | 显示全部楼层
goha111 发表于 2016-5-19 15:55. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
之前刚睡醒 题看的一知半解的就开始写答案真是太抱歉了- -   
. from: 1point3acres.com/bbs
我说下我的想法(以下所有数字都以二进制 ...

  1. def least(n):
  2.     if n == 0:
  3.         return 0
  4.     elif n == 1:
  5.         return 1
  6.     elif n % 2 == 0:
  7.         return least(n // 2)
  8.     else:
  9.         return 1 + least(n + 1)
复制代码
好像这样就可以了的感觉- -
回复 支持 0 反对 2

使用道具 举报

ryanlr 发表于 2016-5-19 10:17:38 | 显示全部楼层
按18垅的思路写了一下。.1point3acres缃
. 1point 3acres 璁哄潧
  1. public int getMin(int n) {
  2.         if (n <= 0)
  3.                 return 0;
  4.         if (n == 1)
  5.                 return 1;. 鍥磋鎴戜滑@1point 3 acres
  6. 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  7.         if ((n & 1) == 1) {
  8.                 return 1 + Math.min(getMin(n + 1), getMin(n - 1));
  9.         } else {
  10.                 return getMin(n >> 1);
  11.         }.鏈枃鍘熷垱鑷1point3acres璁哄潧

  12. }
复制代码
回复 支持 2 反对 0

使用道具 举报

handsomecool 发表于 2016-5-19 09:37:33 | 显示全部楼层
cyqiii 发表于 2016-5-19 08:00. From 1point 3acres bbs
我的意思是每一位都需要考虑两种情况,所以复杂度是2^(log2(N)) =O(N)
而这实际就是用dp的思路
. Waral 鍗氬鏈夋洿澶氭枃绔,
完全同意你说的,我确实漏考虑了, 不能直接countOne。
拿楼主的28为例:. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
28 = 11100  
11100可以等于100+1000+10000
也可以等于1000000 - 100

算法大概是从右往左处理每个bit,在每一个是1的那一位上分别尝试+1或者-1
比如11100在最右是1的那一位加1会进1变成1000000,再在最右是1的那一位-1变成了 0, 两次操作所以结果是2

这样就不会漏掉任何case了,复杂度是2^k   (k是2进制中1的个数) , worst case就是你说的k = log(n) base2  所以O(n)




回复 支持 1 反对 0

使用道具 举报

wzy0791 发表于 2016-5-19 06:52:10 | 显示全部楼层
DP-google 1point3acres
和coin change很像
回复 支持 反对

使用道具 举报

ericLaw 发表于 2016-5-19 06:57:15 | 显示全部楼层
贪心想不出来,我想了一个递归的解法。先求出input的平方根上限和下限,比如28,那就是4和5,因为2的5次方是32比28大,而4次方比28小。然后求出他们和28的距离dl和dh。然后用1+min(findMin(dl),findMin(dh))递归。base case就是如果n等于0,返回0。应该可以解出来。
回复 支持 反对

使用道具 举报

handsomecool 发表于 2016-5-19 07:06:01 | 显示全部楼层
大家是不是想复杂了,也可能我想当然了,每个数字都是两种情况:
1.由比他小的数字相加得到
2.由比他大的数字相减得到
-google 1point3acres
如果是相加得到,直接就是数字的二进制表达式比如:

9 = 1001  (2^3+2^0)
10 = 1010   (2^3 + 2^1). Waral 鍗氬鏈夋洿澶氭枃绔,

如果相减得到,就用比这个数大的最小2的几次方去减,比如

15 = 10000 - 1 (2^4-2^0)


所以每个数字我们只要试试这两种情况即可。


补充内容 (2016-5-19 07:08):
这个复杂度只要O(log(n)) (base2)   算贪心法吧

补充内容 (2016-5-20 01:26):
我最后的回复在18楼,这个回复漏考虑了情况。
回复 支持 反对

使用道具 举报

ericLaw 发表于 2016-5-19 07:07:35 | 显示全部楼层
handsomecool 发表于 2016-5-19 07:06
大家是不是想复杂了,也可能我想当然了,每个数字都是两种情况:. 鍥磋鎴戜滑@1point 3 acres
1.由比他小的数字相加得到
2.由比他大的 ...

你的想法和我的是一样的。
回复 支持 反对

使用道具 举报

ericLaw 发表于 2016-5-19 07:22:05 | 显示全部楼层
handsomecool 发表于 2016-5-19 07:06
大家是不是想复杂了,也可能我想当然了,每个数字都是两种情况:
1.由比他小的数字相加得到
2.由比他大的 ...

我觉得你的想法是对的,漂亮
回复 支持 反对

使用道具 举报

cyqiii 发表于 2016-5-19 07:42:20 | 显示全部楼层
handsomecool 发表于 2016-5-19 07:06
大家是不是想复杂了,也可能我想当然了,每个数字都是两种情况:
1.由比他小的数字相加得到.鐣欏璁哄潧-涓浜-涓夊垎鍦
2.由比他大的 ...

感觉不是两种情况就可以的。我先举一个例子,二进制数1011111可以表示成2^6+2^5-2^0
回复 支持 反对

使用道具 举报

ericLaw 发表于 2016-5-19 07:55:34 | 显示全部楼层
cyqiii 发表于 2016-5-19 07:42
感觉不是两种情况就可以的。我先举一个例子,二进制数1011111可以表示成2^6+2^5-2^0

你这个例子就是1100000 - 1
回复 支持 反对

使用道具 举报

yfang0663 发表于 2016-5-19 07:59:02 | 显示全部楼层
ericLaw 发表于 2016-5-19 06:57
贪心想不出来,我想了一个递归的解法。先求出input的平方根上限和下限,比如28,那就是4和5,因为2的5次方 ...
.1point3acres缃
这个是对的 但是不要递归要dp
回复 支持 反对

使用道具 举报

handsomecool 发表于 2016-5-19 08:09:22 | 显示全部楼层
恩,我之前在描述减法情况时想简单了,每次减法也要分情况,写了下:

int countOne (int n) {
    int counter = 0;
    while(n!=0){
        counter+=n&1?1:0;
        n = n>>1;.1point3acres缃
    }. from: 1point3acres.com/bbs
    return counter;
}

int findMinExpression(int n) {
   
    if(n==1)
        return 1;
    int bigger = 1;
    while (bigger<n) bigger<<=1;
    . from: 1point3acres.com/bbs
    return min(countOne(n), 1+findMinExpression(bigger-n));
    . From 1point 3acres bbs
}

补充内容 (2016-5-19 09:25):
这个恐怕有情况没考虑,估计不对。.鏈枃鍘熷垱鑷1point3acres璁哄潧

补充内容 (2016-5-20 01:27):
我最后的回复在18楼,这个回复也漏了情况
回复 支持 反对

使用道具 举报

cyqiii 发表于 2016-5-19 08:18:45 | 显示全部楼层
handsomecool 发表于 2016-5-19 08:09. visit 1point3acres.com for more.
恩,我之前在描述减法情况时想简单了,每次减法也要分情况,写了下:

int countOne (int n) {

我感觉可能还是有bug,应该不能直接用countOne(n).

因为most significant bit一定是1,所以测试取加或者减两种情况。
int findMinExpression(int n) {
    if(n == 0)
       return 0;
    if(n==1)
        return 1;
    int bigger = 1;
    while (bigger<n) bigger<<=1; 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
   
    return min(1+findMinExpression(n-bigger/2), 1+findMinExpression(bigger-n));. visit 1point3acres.com for more.
}
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
补充内容 (2016-5-19 08:20):
基于上面的解法,可以做memorization优化,加和减中判断了重复的sub integer. 实际上成了dp
回复 支持 反对

使用道具 举报

 楼主| hidden_track 发表于 2016-5-19 08:21:51 | 显示全部楼层
handsomecool 发表于 2016-5-19 08:09
恩,我之前在描述减法情况时想简单了,每次减法也要分情况,写了下:

int countOne (int n) {
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
有个小bug  bigger<=n。
回复 支持 反对

使用道具 举报

yueliu2366 发表于 2016-5-19 08:59:48 | 显示全部楼层
ericLaw 发表于 2016-5-19 06:57
贪心想不出来,我想了一个递归的解法。先求出input的平方根上限和下限,比如28,那就是4和5,因为2的5次方 ...
. 鍥磋鎴戜滑@1point 3 acres
这个思路非常直接,感觉很棒很靠谱。优化一下成dp应该就行了
回复 支持 反对

使用道具 举报

waikai 发表于 2016-5-19 09:21:02 | 显示全部楼层

改了这解法还是不正确吧。return min(countOne(n), 1+findMinExpression(bigger-n)); 这里还是应该改return min(1+findMinExpression(n>>1), 1+findMinExpression(bigger-n))
回复 支持 反对

使用道具 举报

ryanlr 发表于 2016-5-19 09:30:45 | 显示全部楼层
这样行吗?. From 1point 3acres bbs
  1. public int getMinExpressions(int n){
  2.         if(n<=0)
  3.                 return 0;
  4.         if(n==1)
  5.                 return 1;
  6.        
  7.         int p = 1;
  8.         while(p<n){
  9.                 p<<=1;. From 1point 3acres bbs
  10.         }
  11.        
  12.         return Math.min(1+getMinExpressions(n>>1), 1+getMinExpressions(p-n));
  13. }
复制代码

补充内容 (2016-5-19 09:31):
感觉countOne()和递归是一样的效果

补充内容 (2016-5-19 09:53):
public int getMinExpressions(int n){
        if(n<=0)
                return 0;. 1point 3acres 璁哄潧
        if(n==1)
                return 1;
        . 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
        int p = 1;
        while(p<n){
                p<<=1;
        }
        if((n&1)==1){
                return Math.min(1+getMinExpressions(n>>1), 1+getMinExpressio...
回复 支持 反对

使用道具 举报

goha111 发表于 2016-5-19 09:34:37 | 显示全部楼层
我倒是觉得应该这样啊:将N转化成2进制(一直除以2),logN时间。然后比较0的个数和1的个数   1多0少用减法(也就是0的个数),0多1少用加法(也就是1的个数)   不知这样是不是有什么不妥…
回复 支持 反对

使用道具 举报

goha111 发表于 2016-5-19 09:43:50 | 显示全部楼层
goha111 发表于 2016-5-19 09:34
我倒是觉得应该这样啊:将N转化成2进制(一直除以2),logN时间。然后比较0的个数和1的个数   1多0少用减法 ...
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
好像这个思路是不对的… 我再仔细想想……
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-4 22:42

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表