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

 找回密码
 立即注册
  • 刘烨过39岁生日感慨:不敢再装三十几岁的男孩子
  • 操心太多?被传赴美陪产的陈冠希怎么这么显老
  • 徐静蕾公开与男友相处细节:他做事比我果断
  • 影版《奶酪陷阱》又有新人加入 朴山多拉演女主好友
  • 亮点太多!赵薇怀抱"小沈阳" 身后的苏有朋亮了
  • 杨坤恋情曝光!揭秘他至今不婚不育的隐情
  • 小沈阳搂张柏芝合唱 手放在这个部位有点尴尬
  • 余文乐自认说错话:不是被逼承认恋情 想保护对方
  • 罗晋绯闻女友苗圃复出 嫁大21岁富商变豪门阔太
  • 回归家庭做奶爸 陈思诚逛婴幼儿店认真挑玩具
  • 供应商望而祛步:对西尔斯的未来表示怀疑
  • 英特尔股息提高使收益上升3.00%
  • 随着美国代表推动调查,TransDigm的股价下跌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
搜索
查看: 3034|回复: 8

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

[复制链接]

21

主题

33

帖子

79

积分

新手上路

Rank: 1

积分
79
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所以处理起来很麻烦
--

新浪微博官方账号】美国省钱快报FunInUSA : 每日滚动更新美国市场折扣资讯微商进货首选资讯渠道。
回复 百度谷歌雅虎搜狗搜搜有道360奇虎

举报

6

主题

234

帖子

234

积分

中级会员

Rank: 3Rank: 3

积分
234
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?

23

主题

91

帖子

152

积分

注册会员

Rank: 2

积分
152
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
: .



--

19

主题

73

帖子

116

积分

注册会员

Rank: 2

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

19

主题

94

帖子

131

积分

注册会员

Rank: 2

积分
131
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));
:        }
:     }
: ...................



--

2

主题

240

帖子

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所以处理起来很麻烦
--

15

主题

1176

帖子

2321

积分

金牌会员

Rank: 6Rank: 6

积分
2321
QQ
发表于 2016-10-25 12:20:44 | 显示全部楼层
有空一起交流一下

25

主题

1171

帖子

2295

积分

金牌会员

Rank: 6Rank: 6

积分
2295
QQ
发表于 2016-10-29 17:34:31 | 显示全部楼层
楼下的接上

24

主题

1167

帖子

2297

积分

金牌会员

Rank: 6Rank: 6

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

本版积分规则

美国华人网|唐人社区|什么值得买FunInUSA.net发布的内推面经 -求助一道算法题, 在限定三个operation下使一个数变成1的最小- 唐人社区|北 ...帖子由网友提供或转载于网络,若发布的内推面经 -求助一道算法题, 在限定三个operation下使一个数变成1的最小- 唐人社区|北 ...侵犯了您的权益,请联系我们.
Sasa.com

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

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

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

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