今天分享一个LeetCode题,题号是3,标题是:无重复字符的最长子串,题目标签:散列表、双指针和字符串。解题思路里有算法动画视频,别漏看了哦,这是最直观最可视化的解题思路,是精粹。
给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。
示例 2:
输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b",所以其长度为 1。
示例 3:
输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke",所以其长度为 3。
请注意,你的答案必须是 子串 的长度,"pwke" 是一个子序列,不是子串。
这道题最简单的方式是使用暴力法,逐个检查所有的子字符串,剔除掉包含重复字符的字符串,然后计算出所有符合条件的字符串的长度,最后得到最大长度。
虽然能得出正确答案,但是会消耗执行用时和计算空间。俺就优雅一点,不使用暴力。
如何优化或如何选择合适的数据结构,是个问题,没有思路时可以看一下此题的标签:散列表、双指针和字符串。
如果从散列表入手,毫无疑问在写代码过程中用到HashMap,那HashMap跟这道题有什么关系呢?
如果想不出来有什么关系?那也没关系,俺先从直接寻址表入手。如果还没学习过直接寻址表或者散列表可以点击这篇文章<漫画 | 什么是散列表?>。
假定是输入字符串“pwwkew”,我们可以把字符串里每一个字符都看成一个关键字,一个关键字可以指向直接寻址表的一个槽。直接寻址表需要多少个槽可以计算出来,可以通过ASCII码,每一个字符对应着一个十进制位。
对字符串所使用的字符集进行假设,常用的表有如下所示:
int [26] 用于字母 ‘a’ - ‘z’ 或 ‘A’ - ‘Z’
int [128] 用于ASCII码
int [256] 用于扩展ASCII码
看上面题目描述,输入示例都是字母,没有其它的字符,但不排除其它的字符。所以将直接寻址表设定为一个长度为128的数组,值都默认为0,同时将输入字符串转换为字符数组。创建start和end下标,起始下标都为0,maxLen为无重复的最长字串的长度,起始为0,如下图:
start或end下标所指的字符,映射直接寻址表的一个槽(p的ASCII码为112十进制),置为1,如下图:
end下标++,此时的end下标为1,所指向的字符映射直接寻址表中的一个槽(w的ASCII码为119),判断此槽是否为0,如果是,则置为1,end下标继续向下移动,如下图:
end下标++,此时的end下标为1,所指向的字符映射直接寻址表中的一个槽(w的ASCII码为119),判断此槽是否为0,如果不是,意味着字符冲突了,有重复的字符。那就通过移动start下标消除重复的字符。
移动之前先将start下标所指的字符‘p’,‘p’的ASCII码为112,就将直接寻址表下表为112的槽置为0,然后start++,如下图:
在判断end下标所指的字符‘w’,‘w’的ASCII码为119,如上图,查看直接寻址表下表为119的槽,还是为1,则继续移动start下标,重复刚才的步骤的,将直接寻址表下表为119的槽置为0,然后start++,如下图:
这时候判断end下标所指的字符,映射直接寻址表中的一个槽(下表为119),已经置为0了,说明start下标和end下标之间已经没有重复的字符,则放行end下标,end下标继续++。
http://mpvideo.qpic.cn/0b78ceaacaaanmaj5jjn7rpfaeodaeiqaaia.f10002.mp4?dis_k=81b220c245a1ee4a0698c517896eeaca&dis_t=1581669772
public int lengthOfLongestSubstring(String s) {
if (s == "") return 0;
int start = 0, end = 0, maxLen = 0;
char[] array = s.toCharArray(); // 字符串 转 字符数组
int[] map = new int[128]; // 作为直接寻址表
map[array[start]] = 1;
while (end < s.length()) {
maxLen = maxLen > (end - start + 1) ? maxLen : (end - start + 1);
end++;
if (end == s.length()) break;
while (map[array[end]] != 0) {
map[array[start++]] = 0;
}
map[array[end]] = 1;
}
return maxLen;
}
执行用时 : 4 ms, 在所有 Java 提交中击败了91.40%的用户
内存消耗 : 36.7 MB, 在所有 Java 提交中击败了75.59%的用户
用直接寻址表击败了90%以上的用户,说明还是挺快的嘛,但是内存消耗才刚刚击败75%,这就是直接寻址表的缺点。直接寻址表仅适合少量数据的计算。
和直接寻址表对应的是散列表,散列表也是先创建一定长度的数组,HashMap是创建一个长度默认为16的数组,存储链表或者红黑树。
通过散列表方式的代码我就不写了,留给你们做吧?,俺就给个提示。
同样是"pwwkew"作为输入字符串,创建一个HashMap对象,将输入字符串的每一个字符作为键,而值跟直接寻址表一样作为标记。
方式都一样,不过是将直接寻址表改为散列表的数据结构。散列表的执行用时和直接寻址表差不多,而内存消耗会大大降低,从而大大提升性能。
做完这道题之后,提交代码,看一下执行结果,没有达到100%的,说明还有更好的方式在等着你。我也习惯查看排名第一的代码,看一下哪些方式是遗漏了的,或者用了怎么样的数据结构可以更好实现的。
public int lengthOfLongestSubstring(String s) {
if (s == "") return 0;
char[] cs = s.toCharArray();
int result = 0, i = 0;
for (int j = 0; j < s.length(); j++) {
for (int k = i; k < j; k++) {
if (cs[j] == cs[k]) {
i = k + 1;
break;
}
}
if (j - i + 1 > result)
result = j - i + 1;
}
return result;
}
这段代码没有用直接寻址表,也没有用散列表,而是直接用双指针控制下标。
俺啰嗦一点昂,其实回头看动画视频,把直接寻址表忽略掉,光看右边s和e的下标移动,也是和上面代码一样的,妙啊妙啊。
-END-
长按下图二维码关注公众号,「算法无遗策」持续更新算法