首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往

题目描述 把只包含质因子2、3和5的称作(Ugly Number)。 例如6、8都是,但14不是,因为它包含质因子7。 习惯上我们把1当做是第一个。求按从小到大的顺序的第N个。...思路: 首先从的定义我们知道,一个的因子只有2,3,5,那么p = 2 ^ x * 3 ^ y * 5 ^ z 那么我们可以理解为每一个数字都是上一个数字×2或者3,5来的 因此我们只需要定义三个数字...,i2保存由乘2得到的最小的,同理的i3,i5 为什么i2可以保存×2的最小的呢?...因为i2是保存从1开始每一位×2的结果 那么前面的x2的必定比后面的×以2的小 且如果取了当前值为就不能再取了,因此每次需要进行向后+1,x2最小的值只能来自于下一位了 所有的数分为三种类型...return list.get(list.size()-1); } 提一下为什么这里用if并列三个条件而不是else if,因为这里可能同时出现相同的计算结果,因为这里存在一个公倍数的问题

20420
  • 您找到你想要的搜索结果了吗?
    是的
    没有找到

    题目描述 把只包含质因子2、3和5的称作(Ugly Number)。例如6、8都是,但14不是,因为它包含质因子7。 习惯上我们把1当做是第一个。求按从小到大的顺序的第N个。...解题思路 判断一个是不是,最简单的方法就是让这个数不断除以2,3,5。要求第N个,只要从1开始,依次判断每个数是不是,如果是,则相应的序号加1,直到序号为N,就是我们要的数了。...换个思路,我们只求,不要去管非。...每个必然是由小于它的某个乘以2,3或5得到的,这样我们把求得的都保存下来,用之前的数分别乘以2,3,5,找出这三这种最小的并且大于当前最大的值,即为下一个我们要求的

    59210

    II

    注意事项:我们可以认为 1 也是一个 样例 如果n = 9, 返回 10 思路 其实改题的题意就是在所有 列表中,找到第 n 个。...最简单的做法是从 1 开始,判断每一个是否是一个,是的话则加到数列表中,直到数列表的大小等于 n,但是这种方法效率较低,我们可以根据规律而尝试只创造出有效的。...观察规律可得,是取已有的乘以 2 或 3 或 5 得到的,那么我们可以先将特殊的 1 放进数列表中。...因为已存在的肯定在列表中是按照顺序存放的,所以对于乘以 2 而言,肯定存在一个 p2,在它之前的每一个乘以 2 都是当前列表中最后一个的,通用,在它之后的每一个乘以 2 的结果都是大于当前列表中最后一个的...* 5) ); } return uglys.get(n -1); } }; 原题地址 LintCode:

    36520

    II 暴力遍历规律利用set暴力去重排序。

    规律 这种题说起来都是数学题,只要能找出规律来就能减少运算量。...注意到这样一个现象:一个乘以2,3,5的话肯定还是,也就是说可以由生成,我们如果只有一个初始值1,那么还是可以生成。我们把序列记作res....第二个应该是: min(res[1]*2,res[1]*3,res[1]*5); min(2,3,5)=2 第三个应该是: min(res[2]*2,res[1]*3,res[1]*5); min...(4,3,5)=3 第三个应该是: min(res[2]*2,res[2]*3,res[1]*5); min(4,6,5)=4 每次更新只更新一个数十为了保证这样更新的一定是有序的,我们用了三个指针在这里...,2,3,5这三个因子保持不动,哪一个因子作用的被采纳,我们就把对应的指针+1,移到下一个数上,这样虽然会有重复计算(因为一般情况下我们每次都只更新一个指针),但是可以保证每次更新的都是最小的

    66410

    剑指offer

    题目描述 把只包含因子2、3和5的称作(Ugly Number)。例如6、8都是,但14不是,因为它包含因子7。 习惯上我们把1当做是第一个。求按从小到大的顺序的第N个。...解题思路 不难找,关键是如何让他们从小到大找到 下一个总是由以前的某个乘以2或3或5得到,我们只要每次找到以前的中的一些,然后乘以2,3,5,将其中最小的那个加入集合,再重复以上过程...,直到第N次 因为总不能每次都从集合头开始尝试,我用i2,i3,i5记录上次乘以2,3,5的数字的下标,得到新的数字,记为num2,num3,num5,然后最小的那个,并将那个所对应的下标++...#include class Solution { public: int getmin(int a, int b, int c) { int smaller...a: b; return smaller < c ?

    23040

    C语言单身狗问题

    ,证明他不是"单身狗",终止循环,寻找下一个 } } if (j == sz) { return str[i];//当遍历完整个数组时还没有找到和它相等的,则该数字即为"单身狗...进阶思路: 在C语言中有一个异或(^)逻辑运算符,我们可以利用它的自反性质来找出"单身狗". 如果有对异或(^)还不是很了解的朋友可以先移步这篇博客,了解一下关于异或的一些性质,有助于理解后面的操作....【C语言】异或(^)操作符详解 先将文章里面的部分内容截出方便我们后续使用: 异或的运算法则(部分): 接下来我们画图来解释一下异或操作的步骤: 可以发现,凡是出现过两次的数字,两两异或后都变成了0,而唯一的只出现了一次的数字...,与0异或的结果仍然是它本身,这说明整个数组相异或的结果恰好就是我们要的"单身狗"....因此在后续的类似"单身狗"的问题中,希望大家可以多多使用异或的方式来提升查找的效率.

    10610
    领券