Algorithm
leetcode 第3题：无重复字符的最长子串
给定一个字符串，请你找出其中不含有重复字符的最长子串 的长度。
示例 1:
输入: "abcabcbb"输出: 3
解释:因为无重复字符的最长子串是"abc"，所以其长度为 3。
示例 2:
输入: "bbbbb"输出: 1
解释: 因为无重复字符的最长子串是"b"，所以其长度为 1。
示例 3:
输入: "pwwkew"输出: 3
解释: 因为无重复字符的最长子串是"wke"，所以其长度为 3。
请注意，你的答案必须是子串 的长度，"pwke"是一个子序列，不是子串。
解题思路一：遍历字符串，把字符存入集合中，如果集合中存在遍历的字符，这个集合中的长度就是不重复子串长度，记录最大的长度，然后把集合中存在的这个字符和之前的字符删除掉，继续存放这个遍历的字符。最后集合中的长度和最大的长度比较，最大者就是最长子串的长度。
分析：linkedList集合插入时的时间复杂度是1，但是每次遍历都需要查询这个集合，查询复杂度就显得略高。
public int lengthOfLongestSubstring(String s) {
List<Character> list = new LinkedList<Character>();
int substringLen = 0; //最小子串的长度
int length = s.length();
for (int i = 0; i < length; i++) {
char c = s.charAt(i);
if (list.contains(c)) {
int size = list.size();
if (size > substringLen) substringLen = size;
Iterator<Character> iterator = list.iterator();
while (iterator.hasNext()) {
Character next = iterator.next();
iterator.remove();
if (next.equals(c)) break;
}
}
list.add(c);
}
//集合中的长度和子串的长度比较，最大者就是最大子串的长度
int size = list.size();
if (size > substringLen) return size;
return substringLen;
}
解题思路二：遍历这个字符串字符，定义一个左指针，记录子串的左边界，定义一个哈希集合，存放遍历的字符和下标，如果哈希集合存在遍历的字符，并且他的下标在左指针的右侧，说明有这个子串结束，比较并记录最大子串的长度，然后以这个重复字符的的位置为左指针的开始位置，继续下一次循环。最后字符串的最后一个子串的长度和最大的长度比较，最大者就是最长子串的长度。
分析：哈希集合插入时的复杂度是1，查询的复杂度也是1，推荐这个解题思路。
public int lengthOfLongestSubstring(String s) {
int left = -1;//记录子串的边界
int substringLen = 0;//子串的长度
Map<Character, Integer> map = new HashMap<Character, Integer>();
int length = s.length();
for (int i = 0; i < length; i++) {
char c = s.charAt(i);
if (map.containsKey(c) && map.get(c) > left) {
if (substringLen < (i - 1) - left) substringLen = (i - 1) - left;
left = map.get(c);
}
map.put(c, i);
}
//比较最后子串的长度和之前最大子串的长度返回最大
if (substringLen < (length - 1) - left) substringLen = (length - 1) - left;
return substringLen;
}
Review
Tip
http://www.cnblogs.com/skywang12345/p/3624343.html
这篇讲解红黑树原理与实现
Share
一次window中数据库mysql的搬移
这周有个实习生的电脑在C盘安装着mysql5.7服务，由于C盘文件多，他直接把C盘的mysql剪切到了D盘，服务打不开了，纳尼，还有这种神操作，那就顺着这种方式解决吧
1.启动Mysql服务时，报错：系统找不到指定文件
因为路径不对，需要去注册表中更改一下服务路径。
win+r打开输入regedit打开注册表，选择HKEY_LOCAL_MACHINE ->SYSTEM -> CurrentControlSet -> services ->MySQL
点击ImagePath修改现在所在的目录，那一行配置中包含两个路径，一个是mysql的路径，一个是my.ini配置文件路径
2.修改my.ini配置文件，把里面的路径换成现在mysql位置的路径
3.把mysql目录下中data目录里面的东西剪切了出来，里面包含着数据库和日志，试着启动mysql，启动失败，在data中有个 主机服务名.err的文件，这个显示错误日志，查看日志，报错：Table ‘mysql.plugin’ doesn't exist,没有对mysql进行初始化。初始化：mysql目录下\bin>mysqld --initialize(黑窗口中执行)，在data中生成了一些基础数据库和关联文件，再次启动成功。
4.给他操作时，结果忘了密码。停掉服务，打开my.ini配置文件。在 [mysqld]节点中下面加入skip-grant-tables
启动服务，回车进入mysql服务，修改密码：
mysql> update mysql.user set authentication_string=password('密码') where user=‘root’; (mysql数据库)
mysql> alter user 'root'@'localhost' identified by '密码'；
mysql> flush privileges;
然后把my.ini加入的skip-grant-tables注释掉，重新启动服务。
5.把之前的data中的数据库搬到了现在安装目录的data中，查询表中的数据报错：Mysql table ‘XX’ dosen't not exist.
经查询没有把ibdata1搬过去，然后复制过去后，启动，OK
ibdata1文件存储了InnoDB表的元数据，变更缓冲区，双写缓冲区，撤销日志。如果引擎是MyISAM则不需要搬。
