LeetCode - Longest Substring Without Repeating Characters

2018-11-19

技术

最近启动了刷 LeetCode 的进程，Accepted 了几道题，但两天不到就忘了，即使是留了注释，想想写写笔记还是蛮有必要的，但我不希望不经思考整理就贴一堆代码，把博客搞的乱糟糟的，像 XSDN、XX园、X书一样，所以也只是想把一些印象深刻的部分，留个笔记。

过去的我过于年少轻狂，把某些高级语言当成了全部，并未好好去用 C/C++ 写过点什么。忽视了那些底层的基础的后果便是，现在在写一些很简单的东西，在需要保证代码质量的时候，要纠结许久去思考某一段代码需要消耗比较大的代价才能下决定。用 C 语言写代码有个好，通过它可以让你弄清楚，计算机底层可以给你什么基本能力，什么能力是需要通过这些基本的东西通过封装的方式实现的，也相当于顺便强化计算机基础了，所以我也打算就用 C 来刷这一套算法题。

题目：

3.Longest Substring Without Repeating Characters

Examples:

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 语言提交~~