zcd's blog

https://leetcode.cn/problems/construct-binary-tree-from-inorder-and-postorder-traversal/ 根据一棵树的中序遍历与后序遍历构造二叉树。 注意: 你可以假设树中没有重复的元素。 First Solution: 初解，盯着示例1想出来的构造，我也不知道为啥想到用指针(于是后面优化成了下标) 123456789101112131415161718192021222324252627282930313233class Solution {public: TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) { if (inorder.size() == 0) return nullptr; auto p_in = inorder.begin(), p_post = postorder.begin(); TreeNod...

https://leetcode.cn/problems/path-sum-ii/ 给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。 叶子节点 是指没有子节点的节点。 示例 1： 输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22 输出：[[5,4,11,2],[5,8,4,5]] 示例 2： 输入：root = [1,2], targetSum = 0 输出：[] 一开始写了一坨返回值为vector<vector<int>>的递归函数，写了半天最后因为vector合并情况太多直接索性放弃了，后来才认识到这样的拷贝开销(( 1234567891011121314151617181920212223242526class Solution {private: vector<vector<int>> res; vector<int> path;...

Wilson定理 对于自然数n>1n>1n>1,当且仅当nnn是素数时,(n−1)!≡−1(modn)(n-1)! \equiv -1\pmod{n}(n−1)!≡−1(modn). 证明：先证对素数ppp有(p−1)!≡−1(modp)(p-1)!\equiv -1 \pmod{p}(p−1)!≡−1(modp). p=2,3p=2,3p=2,3时显然，当p>3p>3p>3时，Fp:=Z/pZ\mathbb{F}_{p}:=\mathbb{Z}/p\mathbb{Z}Fp​:=Z/pZ为域，非零元皆有乘法逆元. 考虑a2≡1(modp)⇒0≡a2−1≡(a+1)(a−1)(modp)⇒a=1,p−1a^{2}\equiv 1\pmod{p} \Rightarrow 0 \equiv a^{2}-1\equiv(a+1)(a-1) \pmod{p}\Rightarrow a=1,p-1a2≡1(modp)⇒0≡a2−1≡(a+1)(a−1)(modp)⇒a=1,p−1 故Fp∖{0,1,p−1}\mathbb{F}_{p} \smallsetm...

设ppp为素数，我们以符号pa∣∣np^{a}||npa∣∣n表达pa∣∣np^{a}||npa∣∣n而pa+1∤np^{a+1}\nmid npa+1∤n. 代数学讲义中的一道习题就是证明勒让德公式： 设ppp为素数.对所有非零整数mmm取唯一的vp(m)∈Z≥0v_{p}(m)\in \mathbb{Z}_{\geq 0}vp​(m)∈Z≥0​使得pvp(m)∣∣mp^{v_{p}(m)}||mpvp​(m)∣∣m. (1)设n∈Z≥0n\in \mathbb{Z}_{\geq 0}n∈Z≥0​.证明vp(n!)=∑k=1∞⌊npk⌋v_{p}(n!)=\sum\limits_{ k = 1 }^\infty \left\lfloor \frac{n}{p^{k}} \right\rfloorvp​(n!)=k=1∑∞​⌊pkn​⌋. (2)作ppp进制展开n=a0+a1p+⋯+arprn=a_{0}+a_{1}p+\dots+a_{r}p^{r}n=a0​+a1​p+⋯+ar​pr.基于(1),证明：vp(n!)=n−∑i=0raip−1v_{p}(n!)=\frac{...

一、计算下列各题. (1)用极限定义计算lim⁡x→1x2\lim\limits_{ x \to 1 }x^{2}x→1lim​x2. 解：∀ε>0\forall\varepsilon>0∀ε>0,取δ=min⁡{1,13ε}\delta=\min\{1,\frac{1}{3}\varepsilon\}δ=min{1,31​ε}，则当0<∣x−1∣<δ0<|x-1|<\delta0<∣x−1∣<δ时,∣x2−1∣=∣x−1∣⋅∣x+1∣<3δ≤ε|x^{2}-1|=|x-1|\cdot|x+1|<3\delta\leq\varepsilon∣x2−1∣=∣x−1∣⋅∣x+1∣<3δ≤ε.故lim⁡x→1x2=1\lim\limits_{ x \to 1 }x^{2}=1x→1lim​x2=1. (2)求lim⁡n→∞(1+2n+3n2)n\lim\limits_{ n \to \infty }\left(1 +\frac{ 2}{n}+\frac{3}{n^{2}} \right)^nn→∞lim​(1+n2...

如果有单射f:X→Yf:X\to Yf:X→Y和单射g:Y→Xg:Y\to Xg:Y→X，那么存在着两个集合之间的双射φ:X→Y\varphi:X\to Yφ:X→Y. 证明思路: 令h=g∘fh=g \circ fh=g∘f 记X′=X−g(Y)X'=X-g(Y)X′=X−g(Y),A0=X′A_{0}=X'A0​=X′,A1=h(A0)A_{1}=h(A_{0})A1​=h(A0​),A2=h(A1)A_{2}=h(A_{1})A2​=h(A1​),…\dots…,An+1=h(An)A_{n+1}=h(A_{n})An+1​=h(An​) A=⋃n≥0AnA=\bigcup\limits_{n\geq 0 }A_{n}A=n≥0⋃​An​ 考虑XXX的子集的集合F={U⊂X∣X′∪h(U)⊂U}\mathcal{F}=\{U\subset X\mid X' \cup h(U) \subset U\}F={U⊂X∣X′∪h(U)⊂U},AAA是F\mathcal{F}F所有元素的交集，且有X′∪h(A)=AX' \cup h(A)...

相关题目 28. 找出字符串中第一个匹配项的下标 - 力扣（LeetCode） 实现 strStr() 函数。 给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回  -1。 示例 1: 输入: haystack = “hello”, needle = “ll” 输出: 2 示例 2: 输入: haystack = “aaaaa”, needle = “bba” 输出: -1 说明: 当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。 对于本题而言，当 needle 是空字符串时我们应当返回 0 。这与C语言的 strstr() 以及 Java的 indexOf() 定义相符。 我们称haystack为文本串，needle为模式串，长度分别为m,nm,nm,n 暴力算法很显然，但实在是太慢了，时间复杂度O(mn)O(mn)O(mn) 引入概念 “最长相等前后缀”.当长度为nnn字符串的前i个字符与后iii个字符一样时，取最大的ii...

151. 反转字符串中的单词 - 力扣（LeetCode） 给定一个字符串，逐个翻转字符串中的每个单词。 示例 1： 输入: “the sky is blue” 输出: “blue is sky the” 示例 2： 输入: "  hello world!  " 输出: “world! hello” 解释: 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。 示例 3： 输入: “a good   example” 输出: “example good a” 解释: 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。 要求使用空间复杂度O(1)的解法 很综合的题 基本思路： 移除多余空格 将整个字符串反转 再将单词回正 移除多余空格 由于字符串成员的地址连续，这里用快慢指针移除空格，但要注意需保留分隔单词的空格 最后重置字符串的大小 12345678910111213void deleteExtraSpaces(string& s) {    int slow = 0, fast = 0, len = s...