硬核！一周刷爆LeetCode，算法大神（左程云）耗时112天打造出算法与数据结

四边形不等式

求解所有≤n数字中有多少个1？

我们的策略是划分为两部分:以最高位数字为1领头的数字的个数+忽略最高位数字统计的1的个数。

例如123456789

1.最高位为亿，所以以最高位数字为1领头的数字为100000000——123456789，有（123456789－100000000+1）个

2.现在忽略最高位，但是要记住最高位数字为1，然后直接求0——99999999这上面出现了多少个1。

最终答案ans=1x（0——99999999的1的个数）+第一步求出的数据，即为原问题的答案。

那如何求0——99999999上1的个数呢？

不妨先求1000——9999上1的个数。首先以最高位1开头的数字——(1000——1999)有1000个。然后统计忽略最高位的数字开头的统计1的个数——9x(0——999上1的个数），先不要骂我，解释，统计完最高位1开头的数字后，剩下（1000——1999）（2000——2999）（3000——3999）（4000——4999）、（5000——5999）、（6000——6999）(7000——7999）、（8000——8999）、（9000——9999）9项，这9项都是忽略啦最高位为1的统计个数。由此1000——9999上1的个数统计完了。

现在我们从0——9开始，0——9上面有1个1；（10——99）上面有10+9x（0——9上1的个数）即使19个1；（100——999）上有100+9x[（0——9上1的个数）+（10——99上1的个数）]=100+9x（0－99上1的个数）……如果求（0——999）上1个数=（0——9）+（10——99）+（100——999）如此问题解决

后缀树解释:

1.由于1——4、2——5、3——6都一一对应了，所以没办法只能继续让123后面的456……和456后面的789……进行比较

2.而在表中456恰好比789排名靠后，所以这也预示了123企图靠后面的456……排名超过456后面的789……的计划打破了。所以没有办法，123排名靠后，456排名靠前

对于直接连接头节点的节点来说，直接连接头节点没什么好说的！

对于普通节点

1.先看自己父亲的file指针指向的那个节点，看那个节点有没有指向自己这个字符的路，有就将自己的file指针指向它。

2.没有的话，先来到自己父亲节点file指针指向的位置，从这里开始一直顺着file指针审查每一个节点，当第一次遇到指向自己这个字母的节点停止，让自己的file指针指向这个节点对应自己字母的路径上的节点。

3.若一直沿着file指针向上到达了头节点无路可走啦，就再从头节点开始，看头节点直接相连的next节点有没有和自己字母一样的，令自己的file指针指向那个字母所在位置。 若连头节点直接的next指针都没有和自己一样的字母，没办法，只好让自己指向头节点。

意义:哪一个字符串和我当前经历的字符串的后缀相等且最长。比如有字符串abcdefg、cdefg、efg。目前审查abcdefg，审查到了g位置，有两个字符串和它一直匹配到目前的g位置。而我们的要求是:①要匹配到字符串当前的位置②不仅要匹配到当前字符位置，还要求不能和当前审查的这个字符串的开头相同——不能与abcdefg的开头的a也匹配啦，所以截止到g位置，理论上最长可以匹配bcdefg，发现没有，缩小一下cdefg，这个有，成为最佳匹配！

总结匹配要求:

例1.匹配asdfghj……这个字符串。当前要找到j这个位置处的file指针进行asdfghj的匹配。但是要求对它进行匹配的这个字符串开头不能和它一样——也是a，那么理论上最多可以匹配到最长答案为sdfghj，实际上只能尽可能匹配。

例2.对于abcd、cd、d来说，目前匹配到了abcd中的d，我们可以匹配以d为结尾的bcd、cd、d，其中在其余字符串中有的最长的是cd。

为什么第一层file指针都指向头节点？

因为身在第一层说明必然每个字符不相同，每个字符的file指针找不到和自己相同的字母，只好指向头节点？

哪个字符串是完全等于以第一层为结尾的后缀整体的，只能是第一层这个节点本身，但是自己必然等于自己这没有意义！

匹配文章的意义？

每一次尽可能的在一个单词串上匹配，实在匹配不下去了跳转到下一个地方承继上面匹配的结果继续匹配。