LeetCode #003# Longest Substring Without Repeating Characters（js描述）

索引

思路1：分治策略
思路2：Brute Force - O(n^3)
思路3：动态规划？
- O(n^2)版，错误思路：420 ms
- O(n)版，思路转变: 100 ms
语言层面的些许优化

问题描述：https://leetcode.com/problems/longest-substring-without-repeating-characters/

思路1：分治策略

按照算法导论上的分治算法框架强行写的。

class CommonUtil {

    static lightCopy(obj) {

        let result = {}

        Object.assign(result, obj);

        return result;

    }

}

// O(???), Runtime: 7792 ms, faster than 1.00% ...

var lengthOfLongestSubstring = function(s) {

    if (s == "") return 0;

    let buildMaps = (symbol, p, q, r) => {

        let map = [],

            length = 0;

        let current = () => q - length;

        if (symbol == "right") {

            current = () => q - 1 + length;

        }

        let init = () => { // 创建一个空对象,免去繁琐的初始化过程

            map[length++] = {};

        };

        let isSafe = () => { // 越界or字符重复返回false

            let out = symbol == "right" ? current() >= r : current() < p;

            let repeat = map[length - 1][s[current()]];

            return !out && !repeat;

        };

        let createMap = () => { // 复制map>>添加元素>>为下次调用做准备

            map[length] = CommonUtil.lightCopy(map[length - 1]);

            map[length][s[current()]] = true;

            length++;

        };

        init();

        while (isSafe()) {

            createMap();

        }

        return map;

    };

    let combineMaps = (leftMaps, rightMaps, max) => {

        let compatible = (map1, map2) => {

            if (map1.length < map2.length) {

                let temp = map1;

                map1 = map2;

                map2 = temp;

            }

            let keys = Object.keys(map2);

            return !keys.some(x => map1[x]);

        };

        let getPairs = (totalReduce) => {

            let reducePairs = [];

            for (let k = 0; k <= totalReduce; ++k) {

                reducePairs.push({

                    i: k,

                    j: totalReduce - k,

                });

            }

            return reducePairs;

        };

        const leftLen = leftMaps.length - 1,

            rightLen = rightMaps.length - 1,

            baseLen = leftLen + rightLen;

        let sum = 0;

        let totalReduce = 0;

        while ((sum = baseLen - totalReduce) > max) {

            // 只检测比子问题解的值更大的情形,由大往小找,一旦找到立刻停止搜索

            let reducePairs = getPairs(totalReduce);

            for (let k = 0; k != reducePairs.length; ++k) {

                let i = leftLen - reducePairs[k].i;

                let j = rightLen - reducePairs[k].j;

                if (i > 0 && j > 0 && compatible(leftMaps[i], rightMaps[j])) {

                    return sum;

                }

            }

            totalReduce++;

        }

        return max;

    };

    let findMaxCrossingSubstring = (p, q, r, subMaxLength) => {

        if (s[q - 1] == s[q]) { // 不可连接

            return subMaxLength;

        } else {

            let leftMaps = buildMaps("left", p, q, r);

            let rightMaps = buildMaps("right", p, q, r);

            return combineMaps(leftMaps, rightMaps, subMaxLength);

        }

    };

    let findMax = (start, end) => {

        if (start + 1 < end) {

            let mid = Math.floor((start + end) / 2); // Divide

            let maxLeft = findMax(start, mid); // Conquer

            let maxRight = findMax(mid, end); // Conquer

            const subMaxLength = Math.max(maxLeft, maxRight); // Combine

            return findMaxCrossingSubstring(start, mid, end, subMaxLength); // Combine

        } else {

            return 1; // basecase

        }

    };

    return findMax(0, s.length);

};

思路2：Brute Force - O(n^3)

js代码如下：

let satisfyCondition = (i, j, s) => {

    let map = {};

    for (let k = i; k <= j; ++k) {

        if (map[s[k]]) return false;

        map[s[k]] = true;

    }

    return true;

};

// O(n^3), Runtime: 880 ms, faster than 6.67% ...

var lengthOfLongestSubstring2 = function(s) {

    if (s == "") return 0;

    let max = 1,

        length, i, j;

    for (i = 0; i != s.length; ++i) {

        for (j = i + 1; j != s.length; ++j) {

            length = j - i + 1;

            if (length > max) {

                if (satisfyCondition(i, j, s)) {

                    max = length;

                } else {

                    break;

                }

            }

        }

    }

    return max;

};

思路3：动态规划？

最开始思路有点离谱，于是记录下写了n个版本的心路历程。

O(n^2)，错误思路：420 ms

原始思路：完全依靠一个动态的hashMap的map[key]操作判断当前字符与上一个最长子串的兼容性。（每一个这样的“上一个子串”都对应一个全新、特定的hashMap）

js代码如下：

var lengthOfLongestSubstring3 = function(s) {

    let m = [], // 保存最优解的值,以长度作为下标

        b = [], // 保存长度为i时,new的值

        p, r, map = {};

    let init = () => {

        b[0] = 0;

        m[0] = 0;

    };

    let work = () => {

        for (let len = 1; len <= s.length; ++len) {

            r = len - 1; // 引入r:将子问题规模len转化为当前字符的下标

            if ((p = map[s[r]]) == undefined) { // 兼容直接+1

                map[s[r]] = r;

                b[len] = b[len - 1] + 1;

            } else { // 不兼容重新计算

                map = {};

                for (let i = p + 1; i <= r; ++i) {

                    map[s[i]] = i;

                }

                b[len] = r - p;

            }

            m[len] = Math.max(m[len - 1], b[len]);

        }

    };

    init();

    work();

    return m[s.length];

};

因为规模为n的问题实际仅依赖于规模为n-1的子问题，所以只需保存上一轮迭代的相关值就行了。

O(n)版，思路转变: 100 ms

before：

判定兼容性：仅用map[key]判断
维护hashMap：兼容添加键值对，不兼容重新创建hashMap并添加相应的键值对
在如何高效地动态修改hashMap上钻牛角尖

after：

判定兼容性：map[key]判断+利用map[key]里存储的下标,同时维护“上一个最长子串的起始下标”构造一个简单的判定条件
维护hashMap：兼容添加键值对，不兼容更新相应键的值就可以了（对于JS而言，两个代码都一样）
通过添加条件而不是修改hashMap，筛掉对hashMap的无效命中

代码如下：

var lengthOfLongestSubstring6 = function(s) {

    let m = 0, lastIndex = {}, lastBegin = 0, currentIndex;

    for (let len = 1; len <= s.length; ++len) {

        currentIndex = len - 1;

        let ch = s[currentIndex];

        if (lastIndex[ch] !== undefined && lastIndex[ch] >= lastBegin) { // 不兼容

            lastBegin = lastIndex[ch] + 1;

        }

        lastIndex[ch] = currentIndex;

        m = Math.max(m, currentIndex - lastBegin + 1);

    }

    return m;

};

语言层面的些许优化

实际运行效果最好。

var lengthOfLongestSubstring7 = function(s) {

    if (s.length < 2) return s.length;

    let max = 0, lastBegin = 0, code, characterIndex = new Array(255), fresh;

    for (let i = 0; i !== s.length; ++i) {

        code = s.charCodeAt(i);

        if (characterIndex[code] >= lastBegin) {

            lastBegin = characterIndex[code] + 1;

        }

        fresh = i - lastBegin + 1;

        if (fresh > max) {

            max = fresh;

        }

        characterIndex[code] = i;

    }

    return max;

};

js代码性能优化的小结：

缩短变量名绝对是最得不偿失的做法！大大降低可读性的同时，对性能的提升几乎为0（在网络上传输有专门的精简代码工具）
将函数手动内联同样不能提升性能（约等于0）
用if语句取代m = Math.max(m, xxxx);当m>xxxx成立时，采用if语句可以省去一次不必要的赋值。
当数组长度能确定在某个范围时用new Array(size)取代[]
当打算用HashMap的时候，以数字作为键的数组>obj>new Map()
尽量不要用类似if(变量)作为条件判断，因为有时0可能是变量的可行值之一，但是会被转化成false
尽量用===取代==，避免转型出错，似乎对性能还有微乎其微的帮助？？？。。。。
显式地对null、undefined、NaN等值进行判断，可以减少一些莫名其妙的bug
undefined与任何数比较都返回false

巴特西