【每日一题20220527】寻找丑数

:mage:‍ 丑数(Ugly Number)是指只包含质因子2、3和5的数。 例如6、8都是丑数,但14不是,因为它包含质因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第 n个丑数。

【示例】
输入:7
输出:8
解释:10以内的丑数依次为:1,2,3,4,5,6,8,所以索引7的数字是8。

题目难度:中等
题目来源:牛客网-寻找丑数

def solution(n:int)-> int:
    # your code here

assert solution(7) == 8
assert solution(50) == 243
def solution(n: int) -> int:
    # your code here
    result = [1]
    u2, u3, u5 = 0, 0, 0
    while n > 1:
        while (m2 := result[u2] * 2) <= result[-1]:
            u2 += 1
        while (m3 := result[u3] * 3) <= result[-1]:
            u3 += 1
        while (m5 := result[u5] * 5) <= result[-1]:
            u5 += 1
        result.append(min(m2, m3, m5))
        n -= 1
    return result[-1]


assert solution(7) == 8
assert solution(50) == 243
class Solution:
    def GetUglyNumber_Solution(self,index: int) -> int:
        if index < 7:
            return index
        i2,i3,i5 = 0,0,0
        res = [1]
        for i in range(1,index):
            tmp = min([res[i2]*2,res[i3]*3,res[i5]*5])
            res.append(tmp)
            if tmp == res[i2]*2:
                i2 = i2+1
            if tmp == res[i3]*3:
                i3 = i3+1
            if tmp == res[i5]*5:
                i5 = i5+1
        return res[index-1]
def solution(n:int)-> int:
    # your code here
    res = []
    i = 1
    while len(res) < n:
        if isUglyNum(i) == True:
            res.append(i)
        if len(res) == n:
            return res[-1]
        i += 1

def isUglyNum(n):
    while n % 2 == 0:
        n = n // 2
    while n % 3 == 0:
        n = n // 3
    while n % 5 == 0:
        n = n // 5
    if n == 1:
        return True
    else:
        return False

assert solution(7) == 8
assert solution(50) == 243
1 Like
def solution(n: int) -> int:
    num = 1
    count = 1
    while count <= n:
        c = num
        while True:
            for i in [2, 3, 5]:
                if c % i == 0:
                    c = c // i
                    break
            else:
                if c == 1:
                    count += 1
                break
        num += 1
    return num - 1


assert solution(7) == 8
assert solution(50) == 243
def solution(n)-> int:
    #数据范围 0≤x≤2000
    num_list=[1]
    for i in range(2,2001):
        c=i
        while i%2==0:
            i/=2
        while i%3==0:
            i/=3
        while i%5==0:
            i/=5
        if i==1:
            num_list.append(c)
    return num_list[n-1]
#一看回复就发现自己啥都不会,果然大神遍地走
    def solution(n: int) -> int:
        # 因数2去除器
        def del_2(n) -> int:
            if n % 2 == 0:
                return del_2(n // 2)
            else:
                return n

        # 因数3去除器
        def del_3(n) -> int:
            if n % 3 == 0:
                return del_3(n // 3)
            else:
                return n

        # 因数5去除器
        def del_5(n) -> int:
            if n % 5 == 0:
                return del_5(n // 5)
            else:
                return n

        lis = [1]
        len = 1
        i = 2

        while len != n:
            if del_2(del_3(del_5(i))) == 1:
                lis.append(i)
                len += 1
                i += 1
            else:
                i += 1
        else:
            print(lis)
            return i-1

    assert solution(7) == 8
    assert solution(50) == 243

函数后面—>int是什么意思?

函数后面—>int是什么意思呢?

关闭