题解 | 丑数

丑数

https://www.nowcoder.com/practice/6aa9e04fc3794f68acf8778237ba065b

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 
     * @param index int整型 
     * @return int整型
     */
    int GetUglyNumber_Solution(int index) {
        // write code here
        if(index<=0)return 0;//简单错误处理
        vector<long long> uglyNums;
        uglyNums.push_back(1);
        int t2 = 0, t3 = 0, t5 = 0;
        int cnt = 1;
        while(cnt<index){
            ++cnt;
            long long curMax = uglyNums.back();
            long long nextMax = min(min(uglyNums[t2]*2, uglyNums[t3]*3), uglyNums[t5]*5);
            uglyNums.push_back(nextMax);
            while(uglyNums[t2]*2<=nextMax) ++t2;
            while(uglyNums[t3]*3<=nextMax) ++t3;
            while(uglyNums[t5]*5<=nextMax) ++t5;
        }
        return uglyNums.back();
    }
};

只要确保不是大数问题,数字又很大就开long long吧。

确定我们下一次选择的值会比当前最大丑数大,所以所有的选择都要往后走到合适位置(显然在最后一个之前,所以无需验证越界)

然后从比当前最大丑数大的三个可能性中选,选好后更新3个选择点。

主要是解决了重复问题。

全部评论

相关推荐

不愿透露姓名的神秘牛友
06-29 17:30
找实习找着找着就要进入7月了,马上秋招也要开始了,找实习还有意义吗?
绝迹的星:有面就面, 没面上就当日薪4位数大佬免费培训, 面上了再考虑要不要实习
点赞 评论 收藏
分享
06-19 19:06
门头沟学院 Java
码农索隆:别去东软,真学不到东西,真事
点赞 评论 收藏
分享
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务