動機

值得回味的題目

Problem

A super ugly number is a positive integer whose prime factors are in the array primes.

Given an integer n and an array of integers primes, return the nth super ugly number.

The nth super ugly number is guaranteed to fit in a 32-bit signed integer.

 

Example 1:

Input: n = 12, primes = [2,7,13,19]Output: 32Explanation: [1,2,4,7,8,13,14,16,19,26,28,32] is the sequence of the first 12 super ugly numbers given primes = [2,7,13,19].

Example 2:

Input: n = 1, primes = [2,3,5]Output: 1Explanation: 1 has no prime factors, therefore all of its prime factors are in the array primes = [2,3,5].

 

Constraints:

  • 1 <= n <= 106
  • 1 <= primes.length <= 100
  • 2 <= primes[i] <= 1000
  • primes[i] is guaranteed to be a prime number.
  • All the values of primes are unique and sorted in ascending order.

Sol1: BFS

算完就往queue裡面塞

class Solution:
    def nthSuperUglyNumber(self, n: int, ps: List[int]) -> int:
        q = [1]
        nn = set([1])
        while n != 1:
            x = heappop(q)
            for z in [x*y for y in ps]:
                if z not in nn:
                    heappush(q, z)
                    nn.add(z)
            #print(q)
            n -= 1
        return heappop(q)

Sol2: dp

從最後一個值去算乘每個質數，找出最小與沒有重複的

class Solution:
    def nthSuperUglyNumber(self, n: int, ps: List[int]) -> int:
        q = [1]
        idx = [0]*len(ps)
        for i in range(1,n):
            nowI = -1
            tmp = q[idx[0]]*ps[0]+1
            for j in range(0,len(ps)):
                tmp2 = q[idx[j]]*ps[j]
                oldtmp = tmp
                if tmp2 !=tmp:
                    tmp = min(tmp, tmp2)
                    if tmp != oldtmp:
                        nowI = j
                else:
                    idx[j] += 1
            idx[nowI] += 1
            q.append(tmp)
                    
        #print(q)
        return q[-1]

Sol3: dp+bfs (case study)

在queue中放

(算出來的值, 質數, 被算到的次數)

把算出來的值放入queue中，但是要看放入queue的是不是有重複的值

class Solution:
    def nthSuperUglyNumber(self, n: int, primes: List[int]) -> int:
        q = [(p, p, 1) for p in primes]
        heapq.heapify(q)
        dp = [1]
        while len(dp) < n:
            dp.append(q[0][0])
            while q and q[0][0] == dp[-1]:
                _, p, i = heapq.heappop(q)
                heapq.heappush(q, (dp[i] * p, p, i + 1))
        return dp[-1]