lc marathon 6.30

263. 丑数

不断除以2，3，5，当没法除且该数不为1时，则说明还有其他质数因子

def isUgly( n: int) -> bool:
    while(n!=1):
        if n%2==0:
            n=n//2
            continue
        if n%3==0:
            n=n//3
            continue
        if n%5==0:
            n=n//5
            continue
        return False
    return True
1
2
3
4
5
6
7
8
9
10
11
12
13

264. 丑数 II

要得到从小到大的第 nn 个丑数，可以使用最小堆实现。

初始时堆为空。首先将最小的丑数 11 加入堆。

每次取出堆顶元素 xx，则 xx 是堆中最小的丑数，由于 2x, 3x, 5x2x,3x,5x 也是丑数，因此将 2x, 3x, 5x2x,3x,5x 加入堆。

上述做法会导致堆中出现重复元素的情况。为了避免重复元素，可以使用哈希集合去重，避免相同元素多次加入堆。

在排除重复元素的情况下，第 nn 次从最小堆中取出的元素即为第 nn 个丑数

class Solution:
    def nthUglyNumber(self, n: int) -> int:
        ls=[1]
        heapq.heapify(ls)
        s=set()
        for i in range(n):
            q=heapq.heappop(ls)
            if q*2 not in s:
                heapq.heappush(ls,q*2)
                s.add(q*2)
            if q*3 not in s:
                heapq.heappush(ls,q*3)
                s.add(q*3)
            if q*5 not in s:
                heapq.heappush(ls,q*5)
                s.add(q*5)
        return q
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

535. TinyURL 的加密与解密

每次来一个url，就自增一个数，作为tinyurl

class Codec:

    def __init__(self):
        self.dic={}
        self.n=0
    def encode(self, longUrl: str) -> str:
        """Encodes a URL to a shortened URL.
        """
        self.n+=1
        self.dic[self.n]=longUrl
        return f"https://tinyurl//{self.n}"


    def decode(self, shortUrl: str) -> str:
        """Decodes a shortened URL to its original URL.
        """
        s=int(shortUrl.strip("https://tinyurl//"))
        return self.dic[s]
        
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

258. 各位相加

直接模拟

class Solution:
    def addDigits(self, num: int) -> int:
        while len(str(num))!=1:
            num = sum([int(i) for i in str(num)])
        return num
1
2
3
4
5