# A. Smallest Even Multiple (opens new window)
If n is odd, return n * 2, otherwise just return n.
DETAILS
def smallestEvenMultiple(self, n: int) -> int:
return lcm(n, 2)
def smallestEvenMultiple(self, n: int) -> int:
return n * 2 if n % 2 else n
def smallestEvenMultiple(self, n: int) -> int:
return n << n % 2
# B. Length of the Longest Alphabetical Continuous Substring (opens new window)
Similar to Longest Contiguous Array
DETAILS
def longestContinuousSubstring(self, s: str) -> int:
prev, ans, curr = 'B', 1, 0
for ch in s:
if ord(ch) - ord(prev) == 1:
curr += 1
else:
curr = 1
ans = max(ans, curr)
prev = ch
return ans
# C. Reverse Odd Levels of Binary Tree (opens new window)
Record the values by each layer. Reverse the orders of odd layers.
DETAILS
def reverseOddLevels(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
C = collections.defaultdict(list)
def dfs1(root, level):
if not root:
return
C[level].append(root.val)
dfs1(root.left, level + 1)
dfs1(root.right, level + 1)
dfs1(root, 0)
def dfs2(root, level, pos):
if not root:
return
if level % 2:
root.val = C[level][-(pos + 1)]
dfs2(root.left, level + 1, 2 * pos)
dfs2(root.right, level + 1, 2 * pos + 1)
dfs2(root, 0, 0)
return root
# D. Sum of Prefix Scores of Strings (opens new window)
Please refer to This LC Discussion (opens new window) for my solution in English.
# 解法 1. Counter of Prefixs
把所有单词的每一个前缀都加入到计数器C中。
单词word的分数，等于所有C[pre]之和，其中pre为单词word的所有前缀。
DETAILS
def sumPrefixScores(self, W: List[str]) -> List[int]:
C = collections.defaultdict(int)
for w in W:
for i in range(len(w)):
C[w[:i + 1]] += 1
ans = []
for w in W:
curr = 0
for i in range(len(w)):
curr += C[w[:i + 1]]
ans.append(curr)
return ans
# 解法 2. 前缀树
DETAILS
class Node:
def __init__(self):
self.children = {}
self.cnt = 0
class Trie:
def __init__(self):
self.trie = Node()
def insert(self, word):
node = self.trie
for ch in word:
if ch not in node.children:
node.children[ch] = Node()
node = node.children[ch]
node.cnt += 1
def count(self, word):
node = self.trie
ans = 0
for ch in word:
ans += node.children[ch].cnt
node = node.children[ch]
return ans
class Solution:
def sumPrefixScores(self, A: List[str]) -> List[int]:
trie = Trie()
for a in A:
trie.insert(a)
return [trie.count(a) for a in A]