iT邦幫忙

1

【小馬的LeetCode練功坊】醜數(Ugly Number)系列- 263,264,313,1201題

哈囉~ 大家好,
今天做leetcode時,看到這一題經典的醜數問題,
分享一下這個系列的思路
(本文以python解題)

263. Ugly Number

題目: 263. Ugly Number
題意: 定義只有質因數2, 3, 5的數字叫Ugly Number(1也定義為Ugly Number),
判斷一個數字是不是Ugly Number

解析: 我覺得此題大概是本系列最簡單的一題,
只有質因數2, 3, 5,若有其它質因數就不是Ugly Number,
那就寫個while迴圈將2,3,5這三個質因數通通去除,
如果結果為1就是Ugly Number了

class Solution:
    def isUgly(self, num: int) -> bool:
        if num<1:
            return False
        for factor in {2,3,5}:
            while num%factor == 0:
                num = num//factor
        return num==1

264. Ugly Number II

題目: 264. Ugly Number II
題意: 定義只有質因數2, 3, 5的數字叫Ugly Number(1也定義為Ugly Number),
要找第n個Ugly Number

解析: 這一題的精髓是由於大部分的正整數都不是Ugly number,
如果用上面那題的函數一一判斷每個正整數是不是Ugly number會超時,
因此要用小的Ugly Number去生出大的Ugly Number,
詳情見geeksforgeeks- Ugly Numbers

class Solution:
    def nthUglyNumber(self, n: int) -> int:
        ugly = [0] * n # To store ugly numbers  
        ugly[0] = 1
        i2 = i3 = i5 = 0

        # set initial multiple value 
        next_multiple_of_2 = 2
        next_multiple_of_3 = 3
        next_multiple_of_5 = 5

        for l in range(1, n): 
            ugly[l] = min(next_multiple_of_2, next_multiple_of_3, next_multiple_of_5) 
            if ugly[l] == next_multiple_of_2: 
                i2 += 1
                next_multiple_of_2 = ugly[i2] * 2
            if ugly[l] == next_multiple_of_3: 
                i3 += 1
                next_multiple_of_3 = ugly[i3] * 3
            if ugly[l] == next_multiple_of_5:  
                i5 += 1
                next_multiple_of_5 = ugly[i5] * 5
        return ugly[-1]

313. Super Ugly Number

題目: 313. Super Ugly Number
題意: 給你一堆質數primes
定義只有primes裡面的質因數的數字叫Super Ugly Number (1總是定義為Super ugly numbers),
要找第n個Super ugly numbers

解析: 此題就是上一題的一般化版本

class Solution:
    def nthSuperUglyNumber(self, n: int, primes: List[int]) -> int:
        ugly = [0] * n # To store ugly numbers  
        ugly[0] = 1
        p_idx = [0] * len(primes)

        # set initial multiple value 
        next_multiple_of_p = primes[:]

        for l in range(1, n): 
            ugly[l] = min(next_multiple_of_p[i] for i in range(len(primes)))
            for i in range(len(primes)):
                if ugly[l] == next_multiple_of_p[i]:
                    p_idx[i] += 1
                    next_multiple_of_p[i] = ugly[p_idx[i]] * primes[i]
        return ugly[-1] 

1201. Ugly Number III

題目: 1201. Ugly Number III
題意: 給你三個數字a, b, c
定義可以被abc整除的數字叫ugly numbers (注意1不是ugly numbers),
要找第n個ugly numbers

解析: 雖然這一題跟上面題目取名相同,
都叫作ugly numbers,
但是定義完全不同,需仔細閱讀,
做法也差蠻多的,
本題可以用數學的排容原理[1,k]區間有幾個數是abc的倍數算出來,
再用二分搜索做

class Solution:
    def gcd(self, m, n):
        return m if n == 0 else gcd(n, m % n)

    def lcm(self, m, n):
        return m * n // self.gcd(m, n)
    
    def count(self, k, a, b, c):
        #數學的排容原理,計算有[1,k]中有幾個數可被a or b or c整除
        na = k // a
        nb = k // b
        nc = k // c
        nab = k // self.lcm(a, b)
        nac = k // self.lcm(a, c)
        nbc = k // self.lcm(b, c)
        nabc = k // self.lcm(self.lcm(a, b), c)
        return na + nb + nc - nab - nac - nbc + nabc
    
    def nthUglyNumber(self, n: int, a: int, b: int, c: int) -> int:
        l, r = 0, 2*10**9  #答案在[l, r]中間
        while l < r:
            mid = l + (r - l)//2
            cnt = self.count(mid, a, b, c)
            print(l, r, mid,cnt)
            if cnt >= n:
                if cnt == n and (mid % a == 0 or mid % b == 0 or mid % c == 0):
                    return mid
                r = mid - 1
            else:
                l = mid + 1
        return l

尚未有邦友留言

立即登入留言