Exit

Leetcode Top 150

posted on September 04, 2024, last updated on Saturday, November 23, 2024 at 10:51 AM

238. Product of Array Except Self

1
2
3
4
5

nums = [a, b, c, d]
prefix_prod = [a, 			a*b, 		a*b*c, 	a*b*c*d]
suffix_prod = [a*b*c*d, b*c*d, 	c*d, 		d				]

prod = [b*c*d, a*c*d, a*b*d, a*b*c]

49. Group Anagrams

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        # use bit to encode letters
        # 2^0 - a 2^1 -b ... 2^25 - z

        def encode(word):
            value = 0

            for i in range(len(word)):
                value += (1 << (ord(word[i]) - ord('a')))
            
            return (value, len(word), word)

        encodings = [encode(word) for word in strs]
        encodings.sort()

        results = [[encodings[0][2]]]

        for i in range(1, len(encodings)):
            
            value, length, word = encodings[i]
            prev_value, prev_length, prev_word = encodings[i-1]

            
            if value == prev_value and length==prev_length:
                results[-1].append(word)
            else:
                results.append([word])

        return results

        
class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        
        sorted_strs = [(sorted(s), s) for s in strs]

        sorted_strs.sort()

        result = [[sorted_strs[0][1]]]

        for i in range(1, len(sorted_strs)):
            sorted_key, word = sorted_strs[i]
            prev_sorted_key, prev_word = sorted_strs[i-1]

            if sorted_key == prev_sorted_key:
                result[-1].append(word)
            else:
                result.append([word])
        
        return result

202. Happy number

  • key solution is to detect if there is a cycle in the number after the transformation
    • the cycle is deterministic. either stay in 1 or create a cycle
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

class Solution:
    def isHappy(self, n: int) -> bool:
        
        seen = set()

        def test(num):
            value = 0

            while num != 0:
                value += (num % 10)**2
                num = num // 10

            return value
        
        
        while n not in seen:
            seen.add(n)
            n = test(n)

        return n == 1

Table of Content

Recent posts