小米算法岗笔试(求问第二题)
1.4/2
第一题设计题无妨
第二题是输入数字,求编码组合的数量
数字 1~26 -分别以英文 a~z 代表
样例:
输入:13
输出 : 2 (编码为 a c 或 m )
我的思路是当前数字和前一位数组合结果X<=26,则dp[i] = dp[i-1]+dp[i-2]
否则dp[i] = dp[i-1],但只对了40%。 请问大佬是怎么解的。
第一题设计题无妨
第二题是输入数字,求编码组合的数量
数字 1~26 -分别以英文 a~z 代表
样例:
输入:13
输出 : 2 (编码为 a c 或 m )
我的思路是当前数字和前一位数组合结果X<=26,则dp[i] = dp[i-1]+dp[i-2]
否则dp[i] = dp[i-1],但只对了40%。 请问大佬是怎么解的。
全部评论
考虑了0也是80%
我最开始的思路也是dp,也只过了40%。最后时刻,换成记忆化搜索,居然AC了
。思路感觉dp一样,具体啥原因也没弄明白
感觉要考虑0,比如102,只有一种

我的对了70%,你少考虑了一种情况就是20,10这种情况,当前必须和前一位结合,所以dp[i]=dp[i-2],但是我也没有全对,有没有大佬解答一下
我用回溯,过了80,但是不知道哪里有问题,自己写的用例都通过了
除了10+20其他的都编码不了
对于x=10和20的时候dp[i]=dp[i-2],但我只有80%不知道为啥
我到最后想到要考虑"0"在序列中的问题
相关推荐
点赞 评论 收藏
分享
小舰大杀四方:现在的就业环境真是艰难,你好歹磕磕绊绊也走过三面了,回答的肯定也不错,尤其是hr面问了你这么多问题,,,结果一周都没消息。想知道现在的公司到底在高贵什么啊
点赞 评论 收藏
分享
牛客49896997...:电话都漏出来,要保护个人隐私,我先来,你说我见过最美的牛客女孩 点赞 评论 收藏
分享
点赞 评论 收藏
分享
