头条机试题第2题求除DFS外更简单的做法

2018/3/24镜像同步25 回复

头条笔试题目：初始定义s=1, m=1 定义两个操作A和B： A. m = s, s = s + s B. s = s + m 输入 n, 输出所需要的最小的操作次数，使得 s = n. 例：输入 n = 6 输出 3 解释得到s=6的最短操作序列为 AAB，故输出3

订阅后，新回复会通过你的通知中心匿名送达。

9 条回复

Nroskill机器人#1 · 2018/3/24

我能想到的 result[s][m] = 1 + min(result[s / 2][s / 2], result[s - m][m]) 结果为 min(result[n][1...n])

lzj0218机器人#2 · 2018/3/25

n的数据范围？发自「贵邮」

qweyezhy640机器人#3 · 2018/3/25

public int times(int n){ if(n==1) return 0; int one=0,two=0; while(n%3==0 && n>0){ one++; two++; n = n / 3; } while(n%2==0 && n>0){ one++; n = n / 2; } int prime = 0; if(n>1) prime = n-1; return one+two+prime; } 不知道通过率几许

cc19931002机器人#4 · 2018/3/25

这个矩阵感觉没办法初始化，s/2 可能能比m大，所以不能从左往右，从右往左也不好初始化【在 Nroskill 的大作中提到: 】 : 我能想到的 : result[s][m] = 1 + min(result[s / 2][s / 2], result[s - m][m]) : 结果为 : ...................

cnx1948机器人#5 · 2018/3/25

动态规划

dss886机器人#6 · 2018/3/25

半年没做算法题，连题目都读不懂了。。

l11x0m7机器人#7 · 2018/3/25

第一个操作是在往后面加0，第二个操作是能够直接改变数的。比如44对应二进制为101100，可以先用操作一得到1000，此时m为100，之后只能用操作二来得到101100。时间复杂度为O(logn)

lance6716机器人#8 · 2018/3/25

也可能存在m=1100的情况，在操作2的时候可以加速【在 l11x0m7 的大作中提到: 】 : 第一个操作是在往后面加0，第二个操作是能够直接改变数的。比如44对应二进制为101100，可以先用操作一得到1000，此时m为100，之后只能用操作二来得到101100。时间复杂度为O(logn)

a940100079机器人#9 · 2018/3/25

其实就是求最短序列（质数序列乘法问题）序列A出现，数字*2倍序列AB出现，数字*3倍序列ABB出现,数字*4倍序列ABBB出现，数字*5倍序列A(B*N)出现，数字*(N-2)倍还有，4，6，8这些非质是没有价值的，比如8可以通过2?2?2 细节就不显示了，抛砖引玉，你应该可以理解 A出现是最优的价值，所以如果n是质数，那么就返回n-1 如果n不是质数，那么通过上述方式，直到质数k，然后算上上述每个序列用次数，k-1+total即可

头条机试题第2题 求除DFS外更简单的做法

头条机试题第2题求除DFS外更简单的做法