P
Local bulletin
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