牛客网《BAT面试算法精品课》视频链接：《BAT面试算法精品课》 笔记链接： 牛客网《BAT面试算法精品课》笔记一：排序 牛客网《BAT面试算法精品课》笔记二：字符串 牛客网《BAT面试算法精品课》笔记三：队列和栈 牛客网《BAT面试算法精品课》笔记四：链表 牛客网《BAT面试算法精品课》笔记五：二分搜索 牛客网《BAT面试算法精品课》笔记六：二叉树 牛客网《BAT面试算法精品课》笔记七：位运算 牛客网《BAT面试算法精品课》笔记八：排列组合 牛客网《BAT面试算法精品课》笔记九：概率 牛客网《BAT面试算法精品课》笔记十：大数据 牛客网《BAT面试算法精品课》笔记十一：动态规划 字符串面试题的特点： 1.广泛性 01.字符串可以看做字符类型的数组与数组排序，查找，调整有关 02.很多其他类型的面试题可以看做字符串类型的面试题 2.需掌握的概念 回文，子串(连续)，子序列(不连续)，前缀树(Trie树)，后缀树和后缀数组，匹配，字典序 3.需掌握的操作 01.与数组有关的操作：增删改查 02.字符的替换 03字符串的旋转 字符串题目的常见类型： 1.规则判断 01.判断字符串是否符合整数规则 02.判断字符串是否符合浮点数规则 03判断字符串是否符合回文字符串规则……等等许多规则 2.数字运算 Int和long类型表达整数范围有限，所以经常用字符串实现大整数，与大整数相关的加减乘除操作，需要模拟笔算的过程 3.与数组操作有关的类型 01.数组有关的调整，排序等操作需要掌握 02.快速排序的划分过程需要掌握和改写 4.字符计数 01.哈希表 02.固定长度的数组V/C++(256长度)，JAVA(65536长度) 03.滑动窗口问题，寻找无重复字符子串问题，计算变位词问题 5.动态规划类型 01.最长公共字串 02.最长公共子序列 03.最长回文子串 04.最长回文子序列……等 6.搜索类型 01宽度优先搜索 02深度优先搜索 7高级算法和数据结构解决的问题 01.Manacher算法解决最长回文子串问题 02.KMP算法解决字符串匹配问题 03.前缀树结构 04.后缀树和后缀数组 字符串相关题型： 案例1. 这道题表面上看起来是二叉树的题目，实际上是字符串的题目 [](http://www.wjgbaby.com/wp-content/uploads/2018/04/18042102.png) "普通解法为二叉树遍历+匹配问题，考察t1中每个节点为头的子树是否与t2一致，时间复杂度为O(N*M)，N代表t1节点数，M代表t2节点数。")
class Solution {
public:
int lengthOfLongestSubstring(string s) {
map<char, int> mp;
for (int i=0; i<s.length(); i++)
mp[s[i]] = -1;//初始化哈希表
int pre = -1, Max = 0;
for (int i=0; i<s.length(); i++){
pre = max(pre, mp[s[i]]);
Max = max(Max, i-pre);
mp[s[i]] = i;
}
return Max;
}
};