美国华人网FuninUSA_唐人社区_北美华人论坛:找礼品卡,找折扣,找报价,找工作,找内推,找项目,找股票

 找回密码
 立即注册

点击进入授权页面

只需一步,快速开始

  • 杨洋穿高领长袖 竟是为了遮盖身上的伤痕
  • 韦小宝5个老婆20年后重聚 就差方怡荃姐姐
  • 网友炸锅:史上最奇葩剃头菜刀+锤子 画面魔性
  • 日本教授制成“人造精子”:不孕不育有救了
  • 不抽烟不喝酒 24岁工程师疯狂加班后猝死
  • 德国人BT的秘密:30年陈酿油污 瞬间不见
  • 剖腹产新后果被发现:相关基因遗传影响人类进化
  • 被曝已怀孕明年3月意大利完婚?唐嫣方这样回应…
  • 宋小宝累倒暂时告别综艺圈:不断透支有点吃不消了
  • 甜馨收到男神王源的礼物?爱不释手一脸开心
  • 美国股市道琼指数一路狂飙超过19000点,创下百年来记录-美国房产信息
  • 2017年预测比特币增长165%到2000美元
  • 印度央行出人意料地保持利率不变
  • 如果特朗普削减公司税这些股票将飙升
  • 特朗普的税时代,4项投资方法
Logo1-800-PetMeds Free Shipping $49Take $10 Off Your First Order w/code: SAVE10 - 234 x 60
ASICS AmericaPagoda Piercing Banner 234x60Sierra Trading Post
搜索
查看: 3009|回复: 8

内推面经 -求助一道算法题, 在限定三个operation下使一个数变成1的最小- 唐人社区|北 ...

[复制链接]
TA在交友中心
0 0 39
  @ME:   

17

主题

26

帖子

65

积分

新手上路

Rank: 1

积分
65
QQ
发表于 2016-10-2 22:13:27 | 显示全部楼层 |阅读模式
分享到:
{$content}

唐人社区-北美华人论坛-内推面经版-求助一道算法题, 在限定三个operation下使一个数变成1的最小


  JobHunting
标 题: 求助一道算法题, 在限定三个operation下使一个数变成1的最小操作数


The description of the problem is : Write a function which takes a positive
integer as a string and returns the minimum number of operations needed to
transform the number to 1. The number is up to 309 digits long, so there won
't too many character than you can express in that many digits. The
transform process is limited to three operations: 1. Add 1 2. Subtract 1 3.
Divide the number by 2 (only even number allow here)
我的想法是用dfstraverse所有可能, 用memorization来剪枝,但是最后还是超时了,
求教如何进一步优化或者一种方法处理。 因为输入时string所以处理起来很麻烦
--

回复 百度谷歌雅虎搜狗搜搜有道360奇虎

举报

TA在交友中心
0 0 7
  @ME:   

5

主题

225

帖子

232

积分

中级会员

Rank: 3Rank: 3

积分
232
QQ
发表于 2016-10-2 22:45:27 | 显示全部楼层
JobHunting
标  题: Re: 求助一道算法题, 在限定三个operation下使一个数变成1的最小


https://leetcode.com/problems/integer-replacement/

【 在 dashenswen (dashenswen) 的大作中提到: 】
: The description of the problem is : Write a function which takes a
positive
: integer as a string and returns the minimum number of operations needed to
: transform the number to 1. The number is up to 309 digits long, so there
won
: 't too many character than you can express in that many digits. The
: transform process is limited to three operations: 1. Add 1 2. Subtract 1 3
.
: Divide the number by 2 (only even number allow here)
: 我的想法是用dfstraverse所有可能, 用memorization来剪枝,但是最后还是超时了,
: 求教如何进一步优化或者一种方法处理。 因为输入时string所以处理起来很麻烦


--
Look. If you had one shot or one opportunity to seize everything you ever wanted in one moment.
Would you capture it or just let it slip?
TA在交友中心
0 0 54
  @ME:   

21

主题

80

帖子

134

积分

注册会员

Rank: 2

积分
134
QQ
发表于 2016-10-2 23:05:27 | 显示全部楼层
JobHunting
标  题: Re: Re: 求助一道算法题, 在限定三个operation下使一个数变成1


class Solution {
public:
    int integerReplacement(int n) {
       if (n==0 || n==1) return 0;
       if (n==INT_MAX) return 32;
       if ((n&1)==0) return 1+integerReplacement(n>>1); //even
       else {
           return 1+min(integerReplacement(n-1), integerReplacement(n+1));
       }
    }
};

【 在 coldknight (冷骑士) 的大作中提到: 】
: https://leetcode.com/problems/integer-replacement/
: positive
: won
: .



--

TA在交友中心
0 0 36
  @ME:   

15

主题

67

帖子

99

积分

注册会员

Rank: 2

积分
99
QQ
发表于 2016-10-2 23:07:36 | 显示全部楼层
JobHunting
标  题: Re: Re: Re: 求助一道算法题, 在限定三个operation下使一个数
TA在交友中心
0 0 39
  @ME:   

18

主题

88

帖子

120

积分

注册会员

Rank: 2

积分
120
QQ
发表于 2016-10-3 01:03:13 | 显示全部楼层
JobHunting
标  题: Re: Re: 求助一道算法题, 在限定三个operation下使一个数变成


你这个同时尝试两个possibility
可能会TLE
leetcode讨论里面给了个解法,只把n==3当做例外
但我不知道面试时候遇到怎么能短时间内观察出这个。。。

【 在 magician (爱情魔法师) 的大作中提到: 】
: class Solution {
: public:
:     int integerReplacement(int n) {
:        if (n==0 || n==1) return 0;
:        if (n==INT_MAX) return 32;
:        if ((n&1)==0) return 1+integerReplacement(n>>1); //even
:        else {
:            return 1+min(integerReplacement(n-1), integerReplacement(n+1));
:        }
:     }
: ...................



--
TA在交友中心
0 0 6
  @ME:   

2

主题

229

帖子

212

积分

中级会员

Rank: 3Rank: 3

积分
212
QQ
发表于 2016-10-3 02:43:19 | 显示全部楼层
JobHunting
标  题: 求助一道算法题, 在限定三个operation下使一个数变成1的最小操作数


The description of the problem is : Write a function which takes a positive
integer as a string and returns the minimum number of operations needed to
transform the number to 1. The number is up to 309 digits long, so there won
't too many character than you can express in that many digits. The
transform process is limited to three operations: 1. Add 1 2. Subtract 1 3.
Divide the number by 2 (only even number allow here)
我的想法是用dfstraverse所有可能, 用memorization来剪枝,但是最后还是超时了,
求教如何进一步优化或者一种方法处理。 因为输入时string所以处理起来很麻烦
--
TA在交友中心
0 0 1056
  @ME:   

14

主题

1091

帖子

2152

积分

金牌会员

Rank: 6Rank: 6

积分
2152
QQ
发表于 2016-10-25 12:20:44 | 显示全部楼层
有空一起交流一下
TA在交友中心
0 0 1041
  @ME:   

23

主题

1084

帖子

2125

积分

金牌会员

Rank: 6Rank: 6

积分
2125
QQ
发表于 2016-10-29 17:34:31 | 显示全部楼层
楼下的接上
TA在交友中心
0 0 1049
  @ME:   

23

主题

1083

帖子

2132

积分

金牌会员

Rank: 6Rank: 6

积分
2132
QQ
发表于 2016-10-29 17:34:31 | 显示全部楼层
有空一起交流一下
您需要登录后才可以回帖 登录 | 立即注册  

本版积分规则

玩美生活FunInUSA.net 华人娱乐论坛发布的内推面经 -求助一道算法题, 在限定三个operation下使一个数变成1的最小- 唐人社区|北 ...帖子由网友提供或转载于网络,若发布的内推面经 -求助一道算法题, 在限定三个operation下使一个数变成1的最小- 唐人社区|北 ...侵犯了您的权益,请联系我们.
1&1 Hosting

Copyright ©2011 FunInUSA.com All Right Reserved.  Powered by Discuz! X3.0 小黑屋

本站信息均由会员发表,不代表美国华人网FunInUSA立场,如侵犯了您的权利请发帖投诉  技术支持: 美国华人网FunInUSA

安全联盟认证 安全联盟认证

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