LeetCode 双周赛 152

661
Algorithm
LeetCodeContest
本文最后更新于 1 分钟前，文中所描述的信息可能已发生改变。

Q1. 不同三位偶数的数目 ​

解题思路 ​

暴力

示例代码 ​

python
class Solution:
    def totalNumbers(self, digits: List[int]) -> int:
        cnt = Counter(digits)
        ans = 0
        for i in range(100, 1000, 2):
            tmp = Counter()
            while i:
                tmp[i % 10] += 1
                i //= 10
            if all(cnt[k] >= v for k, v in tmp.items() if v):
                ans += 1
        return ans

Q2. 最多可以参加的会议数目 ​

解题思路 ​

哈希表

示例代码 ​

python
class Spreadsheet:

    def __init__(self, rows: int):
        self.table = {}

    def cal(self, cell):
        if cell[0].isupper():
            return self.table.get(cell, 0)
        return int(cell)

    def setCell(self, cell: str, value: int) -> None:
        self.table[cell] = value

    def resetCell(self, cell: str) -> None:
        self.setCell(cell, 0)

    def getValue(self, formula: str) -> int:
        formula = formula[1:]
        a, b = formula.split('+')
        return self.cal(a) + self.cal(b)

# Your Spreadsheet object will be instantiated and called as such:
# obj = Spreadsheet(rows)
# obj.setCell(cell,value)
# obj.resetCell(cell)
# param_3 = obj.getValue(formula)

Q3. 删除元素后K个字符串的最长公共前缀 ​

解题思路 ​

Trie，用字典树，当个数大于k时，记录LCP(最长公共前缀)的最大值和次大值

优化，利用LCP性质，排序后，比较步长为k的字符串，找到LCP的最大值和次大值

参考：排序 + LCP 性质 + 简洁写法（Python/Java/C++/Go）

示例代码 ​

python
class Node:
    __slots__ = ['son', 'cnt', 'is_end']

    def __init__(self):
        self.son = dict()
        self.cnt = 0
        self.is_end = False


class Trie:
    def __init__(self):
        self.root = Node()

    def insert(self, word: str, k: int) -> int:
        mx = 0
        cur = self.root
        for i, char in enumerate(word):
            if char not in cur.son:
                cur.son[char] = Node()
            cur = cur.son[char]
            cur.cnt += 1
            if cur.cnt >= k:
                mx = i + 1
        cur.is_end = True
        return mx

class Solution:
    def longestCommonPrefix(self, words: List[str], k: int) -> List[int]:
        n = len(words)
        trie = Trie()
        mx = mx2 = 0
        t = ''
        for i, word in enumerate(words):
            tmp = trie.insert(word, k)
            if tmp > mx:
                mx, mx2 = tmp, mx
                t = word[: mx]
            elif tmp > mx2:
                mx2 = tmp
        ans = [mx] * n
        for i, word in enumerate(words):
            if word.startswith(t):
                ans[i] = mx2
        return ans
python
class Solution:
    def cal_lcp(self, s, t):
        for i, (x, y) in enumerate(zip(s, t)):
            if x != y:
                return i
        return min(len(s), len(t))

    def longestCommonPrefix(self, words: List[str], k: int) -> List[int]:
        n = len(words)
        idx = sorted(range(n), key=lambda i: words[i])
        mx = mx2 = mx_i = 0
        for i in range(n - k + 1):
            lcp = self.cal_lcp(words[idx[i]], words[idx[i + k - 1]])
            if lcp > mx:
                mx, mx2, mx_i = lcp, mx, i
            elif lcp > mx2:
                mx2 = lcp
        ans = [mx] * n
        for i in idx[mx_i: mx_i + k]:
            ans[i] = mx2
        return ans

Q4. 最长特殊路径II ​

这道题很神秘，以后再来解决吧！

Push Module
LeetCode Weekly Contest 441