LeetCode - Longest Substring Without Repeating Characters
date
Nov 19, 2018
note
slug
leetcode-3
type
Post
status
Published
tags
技术
summary
最近启动了刷 LeetCode 的进程,Accepted 了几道题,但两天不到就忘了,即使是留了注释,想想写写笔记还是蛮有必要的,但我不希望不经思考整理就贴一堆代码,把博客搞的乱糟糟的,像 XSDN、XX园、X书 一样,所以也只是想把一些印象深刻的部分,留个笔记。
最近启动了刷 LeetCode 的进程,Accepted 了几道题,但两天不到就忘了,即使是留了注释,想想写写笔记还是蛮有必要的,但我不希望不经思考整理就贴一堆代码,把博客搞的乱糟糟的,像 XSDN、XX园、X书 一样,所以也只是想把一些印象深刻的部分,留个笔记。
过去的我过于年少轻狂,把某些高级语言当成了全部,并未好好去用 C/C++ 写过点什么。忽视了那些底层的基础的后果便是,现在在写一些很简单的东西,在需要保证代码质量的时候,要纠结许久去思考某一段代码需要消耗比较大的代价才能下决定。用 C 语言写代码有个好,通过它可以让你弄清楚,计算机底层可以给你什么基本能力,什么能力是需要通过这些基本的东西通过封装的方式实现的,也相当于顺便强化计算机基础了,所以我也打算就用 C 来刷这一套算法题。
题目:
3.Longest Substring Without Repeating CharactersExamples:Given"abcabcbb"
, the answer is"abc"
, which the length is 3.Given"bbbbb"
, the answer is"b"
, with the length of 1.Given"pwwkew"
, the answer is"wke"
, with the length of 3. Notethat the answer must be a substring, "pwke" is a subsequence and not asubstring.
程序需要统计输入字符串的最长无重复子串的长度。最初想到的是,从第一个字符开始,遍历这个字符的字符,直到出现重复的字符,统计此时的字符串长度,然后从第二个字符开始,重复这个过程,取最大的一个,直到最后一个字符为止,其中因为边界的问题的处理,折腾了许久,不过还是实现了下面的第一版的代码:
int lengthOfLongestSubstring(char* s) { int p = 0; char c; int maxLen = 0, tempLen = 0; while (s[p] != '\0') { int q = p + 1; while ((c = s[q]) != '\0') { int hasRepeat = false; for (int i = p; i < q; i++) { if (s[i] == c) { hasRepeat = true; break; } } if (hasRepeat) { break; } q++; } if ((tempLen = q - p) > maxLen) { maxLen = tempLen; } p++; } return maxLen; }
这段代码在 leetcode-cn.com OJ 上的运行时间是 180ms,只战胜了 29% 的 C 语言提交,显然这个 O(n^3) 的算法并没有什么竞争力。
这段算法有一个地方比较浪费 CPU 的是,在一个字符失败以后,又重叠判断了一部分相同的元素,看题解提示说用一种 “Sliding Window” 的方法(名字听起来好像 TCP 协议的发送窗口~),通过这种方法,我们只需要把其中不重复的部分保持起来,出现重复的话,就把开头的字符排除掉,这样,这部分字符仍然保持不重复,但是往前移动了一位,就不需要再回头比较元素是否重复了。
题解是用 Java 来写的,用了哈希表去保存字符的状态,C语言上哪找哈希表啊,不过不急,先改改看看什么情况,就有了下面的代码:
int lengthOfLongestSubstring(char* s) { if (s[0] == '\0') return 0; int p = 0, q = 1; char c; int maxLen = 1, tempLen = 0; while ((c = s[q]) != '\0') { bool hasRepeat = false; for (int i = p; i < q; i++) { if (s[i] == c) { hasRepeat = true; break; } } if (hasRepeat) { p++; } else { q++; } if ((tempLen = q - p) > maxLen) { maxLen = tempLen; } } return maxLen; }
其中补充了空白字符的情况,复杂度降到了 O(n^2),OJ 显示花了 32ms,战胜了 49% 的提交,想想,还是有进步空间啊。
剩下的问题就是这个判断重复的循环了,像题解的哈希表一样,把一个个的遍历,换成一键查询得到结果,可以变得更快!但是,C语言并没有原生实现哈希表数据结构,要实现一个,显然,哈希函数跑起来的开销估计可能比这个循环还大吧。
仔细分析需要做一对一映射的数据。每次循环需要查询的只是一个 char ,大小是一个字节,本身只有 256 种情况,而可见字符都遵循 ASCII 编码,也就是说,本题目给的输入中,最多只是前 128 种情况。
面对这样的需求,在C语言里面,开个 128 长度的数组,显然就能覆盖所有的情况了,其中的冗余,在内存不要钱的今天,显然也是可以接受的。
稍微改改,把这一个查找代码
bool hasRepeat = false; for (int i = p; i < q; i++) { if (s[i] == c) { hasRepeat = true; break; } }
换成利用 C 数组实现的 char->boolean 的字典:
int lengthOfLongestSubstring(char* s) { // only zero if (s[0] == '\0') return 0; int p = 0, q = 1; char c; int table[128] = {0}; table[s[p]] = 1; int maxLen = 1, tempLen = 0; while ((c = s[q]) != '\0') { if (table[c]) { table[s[p++]] = 0; } else { table[s[q++]] = 1; } // calc if ((tempLen = q - p) > maxLen) { maxLen = tempLen; } } return maxLen; }
时间复杂度降到 O(2n) = O(n),运行时间降到了 12ms,愉快地击败了 100% 的 C 语言提交