@ the Author: Runsen

@Date:2020/9/28

The essence of programming comes from algorithm, and the essence of algorithm comes from mathematics, programming is just to code mathematical problems. —- Runsen

Take a bouncing text, inset into the poem of September, whether it is the corner of waterside pavilion, or the garden under the moon, as long as there is the space of years, you can join together a beautiful pattern.

Pure mathematician Hardy said, beauty is the first criterion to examine mathematics, ugly mathematics tail will not be long. (Beauty is the first test: There is no permanent place in the world for ugly mathematics.)

I said ugly is ugly number, do not think I am very ugly, and I also think I am very ugly. Ugly number algorithm. I saw it in Ali’s problem. Ali has tested this ugly number in the interview, you must pay attention to this ugly number.

Number of ugly

We call the numbers that contain only the factors 2,3, and 5 ugly numbers, and find the 1,500th ugly number in descending order. It is customary to take 1 as the first ugly number.

Talk is cheap ,show me my code !

Leetcode 263: Determines whether a given number is ugly

Write a program to determine whether a given number is ugly.

Ugly numbers are positive integers that contain only prime factors 2, 3, and 5. Anything less than 1 is not ugly. 1 is ugly. 2, 3, 4 and 5 are all ugly.

The problem is simple: one idea is recursion, the other idea is direct violence.

Step 1: continue the loop as long as num is greater than 5 (2,3,5 is the largest). Step 2: Return False as long as num is not divisible by any of the three numbers. Step 3: Continue the divisible cycle. Note: It is important to note here that "1" in the question returns True.Copy the code

The difficulty of this question is to judge whether 2, 3, and 5 are factors. Corresponding judgments should be made, and special ugly numbers from 1 to 6 cannot be ignored. If a given integer is too large to be easily calculated, it can be divided many times. For example, after dividing 2, 3, and 5 as divisor once or many times, the resulting quotient will be repeated until the simplest operation.

# recursive approach
class Solution:
    def isUgly(self, num: int) - >bool:
        if num <= 0: 
            return False
        elif num <=6 : 
            return True
        if num % 2= =0:
            return self.isUgly(num / 2)
        if num % 3= =0:
            return self.isUgly(num / 3)
        if num % 5= =0:
            return self.isUgly(num / 5)
        return False


# While loop brute force
class Solution:
    def isUgly(self, num: int) - >bool:
        if num <= 0:
            return False
        while num >= 5:
            if num % 2! =0 and num % 3! =0 and num % 5! =0:
                return False
            else:
                if num % 2= =0:
                    num = num // 2
                elif num % 3= =0:
                    num = num // 3
                else:
                    num = num //5
        return True
Copy the code

Leetcode 264: Find the NTH ugly number

Write a program to find the NTH ugly number. Ugly numbers are positive integers whose prime factors are only 2, 3, and 5. Example: Input: n = 10 Output: 12 Description: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 are the first 10 ugly numbers.Copy the code

This problem is a I can not think of DP (dynamic programming) + three Pointers later details.

Considering that ugly number must be a multiple of 2, 3 and 5, three indexes are established at the first ugly number, representing quality factor 2, quality factor 3 and quality factor 5 respectively.

Find the minimum value in the 2 * ugly number set [quality factor 2 index], 3 * ugly number set [quality factor 3 index], 5 * ugly number set [quality factor 5 index], and move the factor pointer corresponding to the ugly number one step forward. Repeat this step until the calculation is complete. The corresponding dp state transition equation: ugly = min(res[i2] * 2, RES [i3] * 3, RES [i5] * 5)

Since the ugly number is only a factor of 2, 3, and 5, the ugly number must be obtained by multiplying the previous ugly number by 2, 3, and 5. Therefore, if we can save the previous ugly number and multiply it by 2, 3, and 5, we can get three ugly numbers. We take the smallest one, which is the latest ugly number.

class Solution:
    def nthUglyNumber(self, n: int) - >int:
        # import heapq for minimum heap solution
        # res = [1]*(n)
        # minheap = [2,3,5]
        # for i in range(1,n):
        # minheap = sorted(set(minheap))
        # res[i] = minheap.pop(0)
        # minheap.append(res[i]*2)
        # minheap.append(res[i]*3)
        # minheap.append(res[i]*5)
        # return res[-1]
        
        res = [1]
        # 3 pointer
        i2 = i3 = i5 = 0
        for _ in range(1,n):
            ugly = min(res[i2] * 2, res[i3] * 3, res[i5] * 5)
            res.append(ugly)
            if ugly == res[i2] * 2: 
                i2 +=1
            if ugly == res[i3] * 3: 
                i3 +=1
            if ugly == res[i5] * 5: 
                i5 +=1
        return res[-1]
Copy the code

Leetcode 313: Super ugly number

Write a program to find the NTH super ugly number.

Super ugly numbers are defined as positive integers and all prime factors are within a given set of prime numbers.

The difference between a super ugly number and finding the NTH ugly number is that primes differ in their prime factors.

The method is exactly the same as the above three-pointer dp. When we are looking for a new super ugly number, we just need to go through the search for prime factors and select the smallest number in the array as the new super ugly number.

Example: input: n = 12, primes = [2,7,13,19] output: 32 For example, given a set of four prime numbers [2, 7, 13, 19], then [1, 2, 4, 7, 8, 13, 14, 16, 19, 26, 28, 32] would be the first 12 super ugly numbers.Copy the code

In fact, it is not difficult, the small logic of the algorithm has made some adjustments, the above three pointer code into the N pointer code, but the idea of the algorithm has not changed.

class Solution:
    def nthSuperUglyNumber(self, n: int, primes: List[int]) -> int:
        nums = [0 for _ in range(len(primes))]
        result = [1]
        for i in range(1,n):
            ugly = min(result[nums[j]] * primes[j] for j in range(len(nums)))
            result.append(ugly)
            for k in range(len(nums)):
                if ugly == result[nums[k]] * primes[k]:
                    nums[k] +=1
        return result[-1]

Copy the code

The road of life, one step can not be less, how hard you work, the heart is the most clear. If you can’t see it yet, that’s ok. Life will teach you in countless falls that all the roads you scribbled or strove for actually have a trace.

Fortunately, it’s still early. Work hard, there is always a way out. I’m still the same teenager!

GitHub, portal ~, GitHub, portal ~, GitHub, Portal ~