拆分单词 dp timu题目：给定一个非空字符串 s 和一个包含非空单词列表的字典 ，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。 说明：拆分时可以重复使用字典中的单词。字典中没有重复的单词。样例：示例 1： 输入: s = “leetcode”, wordDict = [“leet”, “code”] 输出: true 解释: 返回 true 因为 “leetcode” 可以被拆分成 “l 2019-05-04 算法
dfs+树与图的遍历(深度，重心) 邻接表存图 123456789101112131415161718192021222324252627#include <iostream>using namespace std;const int maxn = 1e6;int ver[maxn],next[maxn],head[maxn],edge[maxn];int tot = 0;// 存图void add(int u,i 2019-05-03 算法 dfs
并查集模板 1.合并2个点时，可以判断2个点是否属于一个联通分量，如果不属于，那么加入该连通分量，2. 最后判断该图 有几个单独的联通分量，3. 或者将图压缩成 最小生成树时，判断每个点是否属于最小生成树中，不是就加入树中， 用一个pre[i]表示点i在图中的顶点，初始化时每个点i（都是一个单独的联通分量）所以顶点就是，判断联通分量的数量也是判断pre[i] == i， 合并两个u,v，一开始标记pre 2019-05-03 算法 并查集
欧拉函数例题(poj3090) 欧拉函数例题 除了(1,0)(1,1)(0,1)三个点的，发现其余可视点gcd(x,y)=1 发现关于(1,1)这条线所有点都是对称的，不妨取下半部分，x<y,此时1<=x<y<=n,这就转化到求与y互质数x的个数, y有多个选择,且y>=2,最后答案从2~N累加起来 求欧拉函数值，就是分解质因数的过程，1.试除法分解质因数累加和，但是只能求出 $\ups 2019-05-02 算法 欧拉函数
欧拉函数性质及推导 互质 gcd(a,b) = 1 则a,b互质, gcd(a,b,c) = 1 则两两互质gcd(a,b) = gcd(a,c) = gcd(b,c) = 1 欧拉函数定义:[1,N)中与N互质数的个数被称为欧拉函数,记作 $\upsilon(N)$由算数基本定理知：$N = p_1^{c_1} * p_2^{c_2}*p_3^{c_3}……p_i^{c_i}$ 先推倒i= 2019-05-01 算法 欧拉函数
O(n)时间求 最长回文子串 Manacher算法 回文字符串分为奇回文和偶回文，在字符串中间插入任意字符使得串变成奇回文串 暴力思想：肯定是找一个点往两边任意扩展,遍历一次,Manacher时间为O(n) 开一个数组p[]记录 以点i为中点 的最长回文串的半径, 假设前i-1个点的p[]都已经求出来来，现在考虑p[i]如何推导 重点：3. R是p[1]~p[i-1]中推出来的右端最远最长回文子串的右端点,且用pos记录下来，每一步更新 2019-04-30 算法 回文子串
逛画展(单调队列) 这么简单的我都想不出来思路： 开一个vis[]标记在区间[l,r]中已经出现的画的数量,当每个画vis[i]==1那么看到的画的数量++,左端如果画的数量>1那么向左移动, 右端不断标记然后加入队列中，当 画的数量=画家的数量 记录区间端点值 123456789101112131415161718192021222324252627282930313233#include < 2019-04-30 算法
poj1961(kmp) poj1961思路： 满足 $i % (i-prefix[i]) == 0$ 且i != i-prefix[i] ,说明当前子串S[1~i]的长度是（最长公共前后缀）的前缀长度的倍数，那么 i/(i-prefix[i])就是循环节的个数 12345678910111213141516171819202122232425262728293031323334353637383940414243 2019-04-29 算法 kmp
kmp模式匹配 kmp 匹配的目的是 询问一个字符串s1 len(s1)<=len(s2) 是否是 字符串s2 的子串 s1 叫做 pattern模式串 暴力匹配都知道 abcde 前缀：a ab abc abcd abcde 真前缀不包括abced 后缀同理 所以我们求出s1的prefix[]要后移一位，才是最长公共(真)前后缀 为什么prefix[]要右移？？？ 当不断比较s2[i] 与 p 2019-04-29 算法 kmp模式匹配
荷马史诗(Huffman编码) Huffman编码 huffman树的路径来存字符，节点的权值来存字符串的数量 ，满足 $\Sigma_{i} ^{i=n} w_i * l_i$ ，则新字符串的总长度最小， 求最长字符串的最小值：在合并的过程中，合并一个就加入到队列中，如果val值相同，那么每次合并合并次数最少(即深度最小)的点，这样能使合并次数多的字符串（子树大的）往根节点靠拢（画图理解，子树往中间填，而不是往长的地方填） 2019-04-28 算法 huffman树