haruhiui

# Biweekly Contest 68 # 5946. 句子中的最多单词数 lc5946-1.pyclass Solution: def mostWordsFound(self, sentences: List[str]) -> int: ans = 0 for st in sentences: ans = max(ans, len(st.split())) return ans# 5947. 从给定原材料中找到所有可以做出的菜 lc5947-1.pyclass Solution: def findAllRecipes(self, recipes: List[str],...

# LCA 一个树的 Lowest Common Ancestor 最近公共祖先。 这篇文章主要目的是在于寻找解决类似 LCA 问题的统一方法。就图一乐 # 两个结点都存在 LeetCode 模板题：236. 二叉树的最近公共祖先 lc236.py# Definition for a binary tree node.# class TreeNode:# def __init__(self, x):# self.val = x# self.left = None# self.right = Noneclass Solution: def lowestCommonAncestor(self,...

# Length of LIS LIS: Longest Increasing Subsequence 最长递增子序列。Length of LIS 就是求一个数组中最长子序列的长度。 300. Longest Increasing Subsequence 总的来说，有两种方法，一种是 DP，另一种还是 DP。 第一种 DP： len-LIS-1.pyclass Solution: def lengthOfLIS(self, nums: List[int]) -> int: n = len(nums) dp = [1] * n for i in range(n): for j in...

# Weekly Contest 272 # 1 - 2108. Find First Palindromic String in the Array lc2108-1.pyclass Solution: def firstPalindrome(self, words: List[str]) -> str: for word in words: if word == word[::-1]: return word return ""# 2 - 2109. Adding Spaces to a String lc2109-1.pyclass Solution: def...

Binary Tree Traversal 二叉树遍历。 前序、中序、后序遍历用到的数据结构都是栈，使用 Python 的 list 来表示栈，有 append() 和 pop() 方法，都是 O(1) 时间。需要注意的是 list 的带参数的 pop(i) 复杂度是 O(n) 。（所以一般如果要用队列的话最好不要用 list 而是用 collections.deque() 的 append() 和 popleft() 来达到 O(1) 。） # 前序遍历 LeetCode 模板题：144. 二叉树的前序遍历 顺序是根左右。 递归版： preorder-recur.py# Definition...

# Weekly Contest 271 (2021/12/12) # 1 - 2103. Rings and Rods lc2103-1.pyclass Solution: def countPoints(self, rings: str) -> int: n = len(rings) // 2 d = defaultdict(set) for i in range(n): d[rings[2*i+1]].add(rings[2*i]) ans = 0 for k, v in d.items(): if len(v) == 3: ans += 1 return ans# 2 -...

# Biweekly Contest 67 (2021/12/11) # 1 - 5934. 找到和最大的长度为 K 的子序列 class Solution: def maxSubsequence(self, nums: List[int], k: int) -> List[int]: c = Counter(sorted(nums, key=lambda x: -x)[:k]) ans = [] for x in nums: if c[x]: ans.append(x) c[x] -= 1 return ans# 2 - 5935. 适合打劫银行的日子 class Solution:...

# Weekly Contest (2021/12/5) # 1 - 2094. Finding 3-Digit Even Numbers 返回由 digits 中的数字组成的满足条件的三位数。 lc2094-1.py class Solution: def findEvenNumbers(self, digits: List[int]) -> List[int]: digits.sort() n = len(digits) ans = set() for i, di in enumerate(digits): if di == 0: continue for j, dj in...

本文不保证完全正确。 # Vector # norm 范数 学习资料：线性代数 - 范数 (2) 向量范数 p-norm 定义： ∥x∥=(∑i=1n∣xi∣p)1/p,p>1\begin{Vmatrix} x \end{Vmatrix} = ( \sum_{i=1}^n |x_i|^p ) ^{1/p}, p > 1 ∥∥∥​x​∥∥∥​=(i=1∑n​∣xi​∣p)1/p,p>1 常见的 1-norm 就是 ∥x∥1=∑i=1n∣xi∣\begin{Vmatrix} x \end{Vmatrix}_1 = \sum_{i=1}^n...

# Trie 前缀树。 借鉴自 宫水三叶 大佬的 【设计数据结构】实现 Trie (前缀树)。 Trie 树（又叫「前缀树」或「字典树」）是一种用于快速查询「某个字符串 / 字符前缀」是否存在的数据结构。 其核心是使用「边」来代表有无字符，使用「点」来记录是否为「单词结尾」以及「其后续字符串的字符是什么」。 # 208. 实现 Trie (前缀树) 实现 Trie 类： Trie () 初始化前缀树对象。 void insert (String word) 向前缀树中插入字符串 word 。 boolean search (String word) 如果字符串 word 在前缀树中，返回...