hi,你好!欢迎访问本站!登录
本站由网站地图腾讯云宝塔系统阿里云强势驱动
当前位置:首页 - 教程 - 杂谈 - 正文 君子好学,自强不息!

【Leetcode 做题学算法周刊】第二期

2019-11-18杂谈搜奇网44°c
A+ A-

首发于微信民众号《前端生长记》,写于 2019.11.05

背景

本文纪录刷题历程当中的悉数思索历程,以供参考。重要内容涵盖:

  • 题目剖析设想
  • 编写代码考证
  • 查阅别人解法
  • 思索总结

目次

  • 20.有用的括号
  • 21.兼并两个有序链表
  • 26.删除排序数组中的反复项
  • 27.移除元素
  • 28.完成strStr

Easy

20.有用的括号

题目地点

题目形貌

给定一个只包括 '(',')','{','}','[',']' 的字符串,推断字符串是不是有用。

有用字符串需满足:

  1. 左括号必需用雷同范例的右括号闭合。
  2. 左括号必需以准确的递次闭合。

注重空字符串可被认为是有用字符串。

示例:

输入: "()"
输出: true

输入: "()[]{}"
输出: true

输入: "(]"
输出: false

输入: "([)]"
输出: false

输入: "{[]}"
输出: true

题目剖析设想

这道题从题面来看,依然须要对字符串做遍历处置惩罚,找到互相婚配的括号,剔除后继承做处置惩罚即可。所以这道题我的解题主意是:

  • 运用栈来纪录,婚配的一对就出栈,末了推断栈是不是为空

有几点须要注重下,能够削减一些盘算量:

  1. 题面说清楚明了字符串只含有三种括号,所以长度为奇数,肯定无效
  2. 只需有一对不符合,则可剖断肯定无效
  3. 客栈长度凌驾字符串长度一半,则肯定无效
  4. 先找到右括号则肯定无效

编写代码考证

Ⅰ.纪录栈

代码:

/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function(s) {
    if (s === '') return true;
    if (s.length % 2) return false;
    // hash 表做好索引
    const hash = {
        '(': ')',
        '[': ']',
        '{': '}'
    }
    let arr = []
    for (let i = 0; i < s.length; i++) {
        if (!hash[s.charAt(i)]) { // 推入的是右括号
            if (!arr.length || hash[arr[arr.length - 1]] !== s.charAt(i)) {
                return false
            } else {
                arr.pop()
            }
        } else {
            if (arr.length >= s / 2) {   // 长度凌驾一半
                return false
            }
            arr.push(s.charAt(i))
        }
    }
    return !arr.length
};

效果:

  • 76/76 cases passed (64 ms)
  • Your runtime beats 90.67 % of javascript submissions
  • Your memory usage beats 64.59 % of javascript submissions (33.8 MB)
  • 时刻复杂度: O(n)

查阅别人解法

发明一个很暴力的解法,虽然效力不高,然则思绪清奇。我们来看看完成:

Ⅰ.暴力正则

代码:

/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function(s) {
    if (s === '') return true;
    if (s.length % 2) return false;

    while(s.length) {
        const s_ = s
        s = s.replace('()','').replace('[]','').replace('{}','')
        if (s === s_) return false;
    }
    return true;
};

效果:

  • 76/76 cases passed (104 ms)
  • Your runtime beats 14.95 % of javascript submissions
  • Your memory usage beats 19.75 % of javascript submissions (35.7 MB)
  • 时刻复杂度: O(n)

思索总结

就这题而言,我照样更倾向于增添一个辅佐栈来做纪录。因为一旦去掉只包括括号的限定,那末正则将没法解答。

21.兼并两个有序链表

题目地点

题目形貌

将两个有序链表兼并为一个新的有序链表并返回。新链表是经由过程拼接给定的两个链表的一切节点构成的。

示例:

输入:1->2->4, 1->3->4
输出:1->1->2->3->4->4

题目剖析设想

这道题从题面上就说清楚明了这是一道链表相干题目,要举行链表兼并,无非是修改链表指针指向,或许是链表拼接。所以,这道题我有两种思绪的解法:

  • 修改指针,不停掏出某一条链表中的数,插进去到别的一条链表
  • 链表拼接,递归比较哪条链表的元素更小,就截取拼接到另一条

两种体式格局的区分很明显,修改指针的体式格局须要存储和不停修改指针指向,拼接的体式格局直接做链表拼接。

固然这里也有一些特别值须要斟酌进来。

编写代码考证

Ⅰ.修改指针

代码:

/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var mergeTwoLists = function(l1, l2) {
    if (l1 === null) return l2
    if (l2 === null) return l1
    // 效果链表
    let l = new ListNode(0)
    // 不停更新的当前结点指针,对象赋值为传址,所以下面改指针指向即可
    let cursor = l
    // 会有一个先遍历完,变成 null
    while(l1 !== null && l2 !== null) {
        if (l1.val <= l2.val) { // 哪一个小,指针就指向哪
            cursor.next = l1
            l1 = l1.next
        } else {
            cursor.next = l2
            l2 = l2.next
        }
        // 能够明白为 l.next.next.next ...
        cursor = cursor.next
    }
    // 有一个为空则能够直接拼接
    cursor.next = l1 === null ? l2 : l1
    return l.next
};

效果:

  • 208/208 cases passed (60 ms)
  • Your runtime beats 99.51 % of javascript submissions
  • Your memory usage beats 51.04 % of javascript submissions (35.4 MB)
  • 时刻复杂度 O(m + n) ,离别代表两个链表长度

Ⅱ.链表拼接

代码:

/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var mergeTwoLists = function(l1, l2) {
    if (l1 === null) return l2
    if (l2 === null) return l1
    if (l1.val < l2.val) {
        l1.next = mergeTwoLists(l1.next, l2)
        return l1   // 这个是兼并后的了
    } else {
        l2.next = mergeTwoLists(l1, l2.next)
        return l2   // 这个是兼并后的了
    }
};

效果:

  • 208/208 cases passed (68 ms)
  • Your runtime beats 96.41 % of javascript submissions
  • Your memory usage beats 51.04 % of javascript submissions (35.4 MB)
  • 时刻复杂度 O(m + n) ,离别代表两个链表长度

查阅别人解法

思绪基本上都是这两种,未发明方向差别的解法。

无非是有些解法分外拓荒了新的链表来纪录,或许一些细节上的差别。

思索总结

这里的链表拼接解法,有无发明跟 上一期 14题中的分治思绪是一样的?对,实际上这个也是分治思绪的一个运用。

26.删除排序数组中的反复项

题目地点

题目形貌

给定一个排序数组,你须要在原地删除反复涌现的元素,使得每一个元素只涌现一次,返回移除后数组的新长度。

不要运用分外的数组空间,你必需在原地修改输入数组并在运用 O(1) 分外空间的前提下完成。

示例:

给定数组 nums = [1,1,2],

函数应该返回新的长度 2, 而且原数组 nums 的前两个元素被修改为 1, 2。

你不须要斟酌数组中超出新长度背面的元素。

给定 nums = [0,0,1,1,1,2,2,3,3,4],

函数应该返回新的长度 5, 而且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4。

你不须要斟酌数组中超出新长度背面的元素。

申明:

为何返回数值是整数,但输出的答案是数组呢?

请注重,输入数组是以“援用”体式格局通报的,这意味着在函数里修改输入数组关于调用者是可见的。

你能够设想内部操纵以下:

// nums 是以“援用”体式格局通报的。也就是说,不对实参做任何拷贝
int len = removeDuplicates(nums);

// 在函数里修改输入数组关于调用者是可见的。
// 依据你的函数返回的长度, 它会打印出数组中该长度范围内的一切元素。
for (int i = 0; i < len; i++) {
    print(nums[i]);
}

题目剖析设想

假如是纯真的数组去重,那有许多种要领能够做。所以题目也加了限定前提,总结一下比较重要的几点:

  • 不要运用分外的数组空间,空间复杂度为 O(1)
  • 原地删除反复元素
  • 不须要斟酌凌驾新长度背面的元素

这意味着不允许运用新的数组来解题,也就是对原数组举行操纵。末了一点注重点能够看出,数组项的拷贝复制是一个方向,第二点能够看出数组删除是一个方向。删除元素的话就不会凌驾,所以不须要斟酌二者连系。所以这题我分两个方一直解:

  • 拷贝数组元素
  • 删除数组元素

编写代码考证

Ⅰ.拷贝数组元素

代码:

/**
 * @param {number[]} nums
 * @return {number}
 */
var removeDuplicates = function(nums) {
    if (nums.length === 0) return 0;
    var len = 1
    for(let i = 1; i < nums.length; i++) {
        if(nums[i] !== nums[i - 1]) { // 后一项不即是前一项
            nums[len++] = nums[i] // 拷贝数组元素
        }
    }
    return len
};

效果:

  • 161/161 cases passed (68 ms)
  • Your runtime beats 99.81 % of javascript submissions
  • Your memory usage beats 77.54 % of javascript submissions (36.6 MB)
  • 时刻复杂度 O(n)

Ⅱ.删除数组元素

代码:

/**
 * @param {number[]} nums
 * @return {number}
 */
var removeDuplicates = function(nums) {
    if (nums.length === 0) return 0;
    for(let i = 1; i < nums.length;) {
        if(nums[i] === nums[i - 1]) { // 后一项即是前一项
            nums.splice(i, 1)
        } else {
            i++
        }
    }
    return nums.length
};

效果:

  • 161/161 cases passed (96 ms)
  • Your runtime beats 75.93 % of javascript submissions
  • Your memory usage beats 30.85 % of javascript submissions (37.3 MB)
  • 时刻复杂度 O(n)

查阅别人解法

这里瞥见一种很奇妙的解法,双指针法。相当于一个用于计数,一个用于扫描。

Ⅰ.双指针法

代码:

/**
 * @param {number[]} nums
 * @return {number}
 */
var removeDuplicates = function(nums) {
    if (nums.length === 0) return 0;

    let i = 0;
    for(let j = 1; j < nums.length; j++) {
        if (nums[j] !== nums[i]) {
            nums[++i] = nums[j]
        }
    }
    return i + 1  // 下标 +1 为数组长度
};

效果:

  • 161/161 cases passed (68 ms)
  • Your runtime beats 99.81 % of javascript submissions
  • Your memory usage beats 84.03 % of javascript submissions (36.5 MB)
  • 时刻复杂度 O(n)

思索总结

就三种解法而言,删除数组元素会频仍修改数组,不发起运用。双指针法和拷贝数组元素代码逻辑相似,然则思绪上是判然差别的。

27.移除元素

题目地点

题目形貌

给定一个数组 nums 和一个值 val,你须要原地移除一切数值即是 val 的元素,返回移除后数组的新长度。

不要运用分外的数组空间,你必需在原地修改输入数组并在运用 O(1) 分外空间的前提下完成。

元素的递次能够转变。你不须要斟酌数组中超出新长度背面的元素。

示例:

给定 nums = [3,2,2,3], val = 3,

函数应该返回新的长度 2, 而且 nums 中的前两个元素均为 2。

你不须要斟酌数组中超出新长度背面的元素。

给定 nums = [0,1,2,2,3,0,4,2], val = 2,

函数应该返回新的长度 5, 而且 nums 中的前五个元素为 0, 1, 3, 0, 4。

注重这五个元素可为恣意递次。

你不须要斟酌数组中超出新长度背面的元素。

申明:

为何返回数值是整数,但输出的答案是数组呢?

请注重,输入数组是以“援用”体式格局通报的,这意味着在函数里修改输入数组关于调用者是可见的。

你能够设想内部操纵以下:

// nums 是以“援用”体式格局通报的。也就是说,不对实参作任何拷贝
int len = removeElement(nums, val);

// 在函数里修改输入数组关于调用者是可见的。
// 依据你的函数返回的长度, 它会打印出数组中该长度范围内的一切元素。
for (int i = 0; i < len; i++) {
    print(nums[i]);
}

题目剖析设想

这题跟上一题异常相似,所以我们能够沿用上题的方一直解这道题:

  • 删除数组元素
  • 双指针法

编写代码考证

Ⅰ.删除数组元素

代码:

/**
 * @param {number[]} nums
 * @param {number} val
 * @return {number}
 */
var removeElement = function(nums, val) {
    if (nums.length === 0) return 0;

    for(let i = 0; i < nums.length;) {
        if (nums[i] === val) {
            nums.splice(i, 1)
        } else {
            i++
        }
    }
};

效果:

  • 113/113 cases passed (64 ms)
  • Your runtime beats 89.43 % of javascript submissions
  • Your memory usage beats 47.42 % of javascript submissions (33.7 MB)
  • 时刻复杂度 O(n)

Ⅱ.双指针法

代码:

/**
 * @param {number[]} nums
 * @param {number} val
 * @return {number}
 */
var removeElement = function(nums, val) {
    if (nums.length === 0) return 0;

    let i = 0
    for(let j = 0; j < nums.length; j++) {
        if (nums[j] !== val) {
            nums[i++] = nums[j]
        }
    }
    return i
};

效果:

  • 113/113 cases passed (60 ms)
  • Your runtime beats 95.11 % of javascript submissions
  • Your memory usage beats 98.18 % of javascript submissions (33.3 MB)
  • 时刻复杂度 O(n)

查阅别人解法

看到两个略有差别的要领:

  • 单指针法,运用 const of 替代一次遍历,只是写法区分,没有实质提拔
  • 交流移除,雷同时刻与末了一项交流,同时数组长度减1

Ⅰ.单指针法

代码:

/**
 * @param {number[]} nums
 * @param {number} val
 * @return {number}
 */
var removeElement = function(nums, val) {
    if (nums.length === 0) return 0;

    let i = 0;
    for(const num of nums) {
        if(num !== val) {
            nums[i++] = num;
        }
    }
    return i;
};

效果:

  • 113/113 cases passed (68 ms)
  • Your runtime beats 80.29 % of javascript submissions
  • Your memory usage beats 43.35 % of javascript submissions (33.7 MB)
  • 时刻复杂度 O(n)

Ⅱ.交流移除

代码:

/**
 * @param {number[]} nums
 * @param {number} val
 * @return {number}
 */
var removeElement = function(nums, val) {
    if (nums.length === 0) return 0;

    let i = nums.length;
    for(let j = 0; j < i;) {
        if (nums[j] === val) {
            nums[j] = nums[--i]
        } else {
            j++
        }
    }

    return i;
};

效果:

  • 113/113 cases passed (68 ms)
  • Your runtime beats 80.29 % of javascript submissions
  • Your memory usage beats 44.53 % of javascript submissions (33.7 MB)
  • 时刻复杂度 O(n)

思索总结

这里开辟下思绪:假如要移除的是多项,那末照样运用指针法做处置惩罚适宜;假如是移除单项,那末运用交互移除法实在遍历次数起码。

28.完成strStr

题目地点

题目形貌

完成 strStr() 函数。

给定一个 haystack 字符串和一个 needle 字符串,在 haystack 字符串中找出 needle 字符串涌现的第一个位置 (从0最先)。假如不存在,则返回 -1

示例:

输入: haystack = "hello", needle = "ll"
输出: 2

输入: haystack = "aaaaa", needle = "bba"
输出: -1

申明:

needle 是空字符串时,我们应该返回什么值呢?这是一个在口试中很好的题目。

关于本题而言,当 needle 是空字符串时我们应该返回 0 。这与 C 言语的 strstr() 以及 JavaindexOf() 定义符合。

题目剖析设想

这道题很明显是一道字符串搜刮的题目,预计是在考核算法,然则受限学问面,所以我就先以现有体式格局完成作答,再来进修算法了。

  • IndexOf 这个是原生要领,考核这个就没有意义了,所以不做细致叙述
  • 遍历婚配,相当于本身完成一个 IndexOf

编写代码考证

Ⅰ.遍历婚配

代码:

/**
 * @param {string} haystack
 * @param {string} needle
 * @return {number}
 */
var strStr = function(haystack, needle) {
    if (needle === '') return 0
    if (needle.length > haystack.length) return -1
    if (needle.length === haystack.length && needle !== haystack) return -1
    for(let i = 0; i < haystack.length; i++) {
        if (i + needle.length > haystack.length) {
            return -1
        } else {
            const str = haystack.substr(i, needle.length)
            if (str === needle) {
                return i
            }
        }
    }
    return -1
};

效果:

  • 74/74 cases passed (64 ms)
  • Your runtime beats 90.58 % of javascript submissions
  • Your memory usage beats 44.22 % of javascript submissions (33.9 MB)
  • 时刻复杂度 O(n)

查阅别人解法

起首查阅《算法导论》,看到字符串婚配有以下四种:

  • 质朴字符串婚配算法
  • Rabin-Karp 算法
  • 应用有限自动机举行字符串婚配
  • KMP 算法

然后再看题解,也许还找到以下三种算法:

  • BM 算法
  • Horspool 算法
  • Sunday 算法

Ⅰ.质朴字符串婚配算法

算法申明:

经由过程一个轮回找到一切有用廉价,该轮回对 n-m+1 个能够的 s 值举行检测,看可否满足前提 P[1..m] = T[s+1...s+m]。个中 n 是字符串长度, 'm' 是婚配字符串长度。

代码:

/**
 * @param {string} haystack
 * @param {string} needle
 * @return {number}
 */
var strStr = function(haystack, needle) {
    if (needle === '') return 0
    if (needle.length > haystack.length) return -1
    if (needle.length === haystack.length && needle !== haystack) return -1

    let i = 0;
    let j = 0;
    while(j < needle.length && i < haystack.length) {
        if(haystack[i] === needle[j]) { // 同位相称,继承推断下一名
            i++;
            j++;
        } else {
            i = i - j + 1; // i 偏移
            j = 0; // j 重置

            if (i + needle.length > haystack.length) { // 我增添的优化点,削减一些运算
                return -1
            }
        }
    }
    if (j >= needle.length) { // 子串比完了,此时 j 应该即是 needle.length
        return i - needle.length;
    } else {
        return -1
    }
};

效果:

  • 74/74 cases passed (56 ms)
  • Your runtime beats 98.45 % of javascript submissions
  • Your memory usage beats 30.12 % of javascript submissions (34.8 MB)
  • 时刻复杂度 O(m*n)

Ⅱ.Rabin-Karp 算法

算法申明:

举行哈希运算,将字符串转成对应的哈希值举行比对,相似16进制。这里题目是字符串,我就用 ASCII 值来示意每一个字符的哈希值,那末就能够盘算出形式串的哈希值,再举行转动比较。

每次转动只须要做牢固的 -*+ 三个操纵,即可得出转动串的哈希值了。

比方盘算 bbc ,哈希值为 hash = (b.charCodeAt() * 128 ^ 2 + b.charCodeAt() * 128 + c.charCodeAt()),假如要盘算后新值 bca 则为 (hash - b.charCodeAt() * 128 ^ 2) * 128 + c.charCodeAt()

代码:

/**
 * @param {string} haystack
 * @param {string} needle
 * @return {number}
 */
var strStr = function(haystack, needle) {
    if (needle === '') return 0
    if (needle.length > haystack.length) return -1
    if (needle.length === haystack.length && needle !== haystack) return -1

    let searchHash = 0 // 搜刮字符串的hash值
    let startHash = 0 // 字符串肇端的hash值

    for(let i = 0; i < needle.length; i++) {
        searchHash += needle.charCodeAt(i) * Math.pow(2, needle.length - i - 1)
        startHash += haystack.charCodeAt(i) * Math.pow(2, needle.length - i - 1)
    }

    if (startHash === searchHash)  return 0

    for(let j = 1; j < haystack.length - needle.length + 1; j++) {
        startHash = (startHash - haystack.charCodeAt(j - 1) * Math.pow(2, needle.length - 1)) * 2 + haystack.charCodeAt(j + needle.length - 1)
        if (startHash === searchHash) {
            return j
        }
    }
    return -1
};

效果:

  • 74/74 cases passed (68 ms)
  • Your runtime beats 81.31 % of javascript submissions
  • Your memory usage beats 16.86 % of javascript submissions (35.4 MB)
  • 时刻复杂度 O(m*n)

注重:这里能够会存在溢出的状况,所以不是一切状况都实用。

Ⅲ.应用有限自动机举行字符串婚配

算法申明:

经由过程对文本字符串 T 举行扫描,找出形式 P 的一切涌现位置。它们只对每一个文本字符搜检一次,而且搜检每一个文本字符时所用的时刻为常数。一句话归纳综合:字符输入引发状况机状况变动,经由过程状况转换图获得预期效果。

这里重要的中心点是推断每次输入,找到最长的后缀婚配,假如最长时的长度即是查找字符串长度,那就肯定包括该查找字符串。

代码:

/**
 * @param {string} haystack
 * @param {string} needle
 * @return {number}
 */
var strStr = function(haystack, needle) {
    if (needle === '') return 0
    if (needle.length > haystack.length) return -1
    if (needle.length === haystack.length && needle !== haystack) return -1

    // 查找最大婚配后缀长度
    function findSuffix (Pq) {
        let suffixLen = 0
        let k = 0
        while(k < Pq.length && k < needle.length) {
            let i = 0;
            for(i = 0; i <= k; i++) {
                // 找needle中的若干项为当前状况对应字符串的婚配项
                if (Pq.charAt(Pq.length - 1 - k + i) !== needle.charAt(i)) {
                    break;
                }
            }

            // 一切项都婚配,即找到了后缀
            if (i - 1 == k) {
                suffixLen = k+1;
             }
            k++
        }
        return suffixLen
    }

    // 猎取一切输入的字符集,比方 'abbc' 和 'cd' 合集为 ['a','b','c','d']
    const setArr = Array.from(new Set(haystack + needle)) // 用户输入的可选项

    // 竖立状况机
    const hash = {}
    for(let q = 0; q < haystack.length; q++) {
        for(let k = 0; k < setArr.length; k++) {
            const char = haystack.substring(0, q) + setArr[k] // 下个状况的字符
            const nextState = findSuffix(char)
            // 求比方 0.a 0.b 0.c 的值
            if (!hash[q]) {
                hash[q] = {}
            }
            hash[q][char] = nextState
        }
    }

    // 依据状况机求解
    let matchStr = ''
    for(let n = 0; n < haystack.length; n++) {
        const map = hash[n]
        matchStr += haystack[n]
        const nextState = map[matchStr]

        if (nextState === needle.length) {
            return n - nextState + 1
        }
    }
    return -1
};

效果:

  • 74/74 cases passed (84 ms)
  • Your runtime beats 35.05 % of javascript submissions
  • Your memory usage beats 5.05 % of javascript submissions (39.8 MB)
  • 时刻复杂度 O(n)

Ⅳ.KMP 算法

算法申明:

能够明白为在状况机的基础上,运用了一个前缀函数来举行状况推断。实质上也是前缀后缀的头脑。

代码:

// @lc code=start
/**
 * @param {string} haystack
 * @param {string} needle
 * @return {number}
 */
var strStr = function(haystack, needle) {
    if (needle === '') return 0
    if (needle.length > haystack.length) return -1
    if (needle.length === haystack.length && needle !== haystack) return -1

    // 生成婚配串各个位置下下的最长大众前后缀长度哈希表
    function getHash () {
        let i = 0 // arr[i] 示意 i 前面的字符串的最长大众前后缀长度
        let j = 1
        let hash = {
            0: 0
        }
        while (j < needle.length) {
            if (needle.charAt(i) === needle.charAt(j)) { // 相称直接 i j 都后移
                hash[j++] = ++i
            } else if (i === 0) {   // i 为出发点且二者不相称,那末肯定为0
                hash[j] = 0
                j++
            } else {
                // 这里解释一下: 因为i前面的字符串与j前面的字符串具有雷同的最长大众前后缀,也就是说i前面字符串的最长大众后缀与j前面字符串的最长大众前缀雷同,所以i只需回到i前面字符串最长大众前缀的后一名最先比较
                i = hash[i - 1]
            }
        }
        return hash
    }

    const hash = getHash()
    let i = 0 // 母串中的位置
    let j = 0 // 子串中的位置
    while(i < haystack.length && j < needle.length) {
        if (haystack.charAt(i) === needle.charAt(j)) {  // 两个婚配,同时后移
            i++
            j++
        } else if (j === 0) { // 两个不婚配,而且j在出发点,则母串后移
            i++
        } else {
            j = hash[j - 1]
        }
    }
    if (j === needle.length) {  // 轮回完了,申明婚配到了
        return i - j
    } else {
        return -1
    }
};

效果:

  • 74/74 cases passed (60 ms)
  • Your runtime beats 94.74 % of javascript submissions
  • Your memory usage beats 23.73 % of javascript submissions (35.1 MB)
  • 时刻复杂度 O(n)

Ⅴ.BM 算法

算法申明:

基于后缀婚配,婚配从后最先,但挪动照样夙昔最先,只是定义了两个划定规矩:坏字符划定规矩亲睦后缀划定规矩。

浅显来说就是先考证是不是为坏字符,然后推断是不是在搜刮词中举行对应的偏移举行下一步考证。假如婚配的话就从后往前校验,假如依然婚配,就为好后缀。中心头脑是每次位移都在坏字符亲睦后缀划定规矩中取较大值,因为两个划定规矩都只与婚配项相干,所以能够提早生成划定规矩表。

代码:

/**
 * @param {string} haystack
 * @param {string} needle
 * @return {number}
 */
var strStr = function(haystack, needle) {
    if (needle === '') return 0
    if (needle.length > haystack.length) return -1
    if (needle.length === haystack.length && needle !== haystack) return -1

    function makeBadChar (needle) {
        let hash = {}
        for(let i = 0; i < 256; i++) { // ascii 字符长度
            hash[String.fromCharCode(i)] = -1 // 初始化为-1
        }
        for(let i = 0; i < needle.length; i++) {
            hash[needle.charAt(i)] = i  // 末了涌现该字符的位置
        }
        return hash
    }

    function makeGoodSuffix (needle) {
        let hashSuffix = {}
        let hashPrefix = {}
        for(let i = 0; i < needle.length; i++) {
            hashSuffix[i] = -1
            hashPrefix[i] = false
        }
        for(let i = 0; i < needle.length - 1; i++) { // needle[0, i]
            let j = i
            k = 0 // 大众后缀子串长度,尾部取k个出来举行比较
            while(j >= 0 && needle.charAt(j) === needle.charAt(needle.length - 1 - k)) { // needle[0,needle.length - 1]
                --j
                ++k
                hashSuffix[k] = j + 1 // 肇端下标
            }

            if (j === -1) { // 申明悉数婚配,意味着此时大众后缀子串也是形式的前缀子串
                hashPrefix[k] = true
            }
        }
        return { hashSuffix, hashPrefix }
    }

    function moveGoodSuffix (j, needle) {
        let k = needle.length - 1 - j
        let suffixes = makeGoodSuffix(needle).hashSuffix
        let prefixes = makeGoodSuffix(needle).hashPrefix
        if (suffixes[k] !== -1) { // 找到了跟好后缀一样的子串,猎取下标
            return j - suffixes[k] + 1
        }
        for(let r = j + 2; r < needle.length; ++r) {
            if (prefixes[needle.length - r]) { // needle.length 是好后缀子串长度
                return r // 对齐前缀到好后缀
            }
        }
        return needle.length // 悉数婚配,直接挪动字符串长度
    }

    let badchar = makeBadChar(needle)
    let i = 0;
    while(i < haystack.length - needle.length + 1) {
        let j
        for(j = needle.length - 1; j >= 0; --j) {
            if (haystack.charAt(i + j) != needle[j]) {
                break; // 坏字符,下标为j
            }
        }
        if (j < 0) { // 婚配胜利
            return i // 第一个婚配字符的位置
        }
        let moveLen1 = j - badchar[haystack.charAt(i + j)]
        let moveLen2 = 0
        if (j < needle.length -1) { // 假如有好后缀
            moveLen2 = moveGoodSuffix(j, needle)
        }
        i = i + Math.max(moveLen1, moveLen2)
    }

    return -1
};

效果:

  • 74/74 cases passed (72 ms)
  • Your runtime beats 69.29 % of javascript submissions
  • Your memory usage beats 5.05 % of javascript submissions (37 MB)
  • 时刻复杂度 O(n)

Ⅵ.Horspool 算法

算法申明:

将主串中婚配窗口的末了一个字符跟形式串中的末了一个字符比较。假如相称,继承从后向前对主串和形式串举行比较,直到完整相称或许在某个字符处不婚配为止。假如不婚配,则依据主串婚配窗口中的末了一个字符在形式串中的下一个涌现位置将窗口向右挪动。

代码:

/**
 * @param {string} haystack
 * @param {string} needle
 * @return {number}
 */
var strStr = function(haystack, needle) {
    if (needle === '') return 0
    if (needle.length > haystack.length) return -1
    if (needle.length === haystack.length && needle !== haystack) return -1

    let hash = {}
    for(let i = 0; i < 256; i++) {
        hash[i] = needle.length // 默许初始化为最大偏移量,也就是婚配串长度
    }
    for(let i = 0; i < needle.length - 1; i++) {
        hash[needle.charCodeAt(i)] = needle.length - 1 - i // 每一个字符间隔右边的间隔
    }

    let pos = 0

    while(pos < (haystack.length - needle.length + 1)) {
        let j = needle.length - 1 // 从右往左
        while(j >= 0 && haystack.charAt(pos + j) === needle.charAt(j)) {
            j--
        }
        if (j < 0) { // 悉数婚配
            return pos
        } else { // 不婚配
            pos += hash[haystack.charCodeAt(pos + needle.length - 1)]
        }
    }

    return -1
};

效果:

  • 74/74 cases passed (68 ms)
  • Your runtime beats 79.76 % of javascript submissions
  • Your memory usage beats 16.14 % of javascript submissions (35.4 MB)
  • 时刻复杂度 O(n)

Ⅶ.Sunday 算法

算法申明:

它的头脑跟 BM 算法 相似,然则它是夙昔今后婚配,婚配失利时关注主串内介入婚配的后一名字符。假如该字符不存在婚配字符中,则多偏移一名;假如存在,则偏移婚配串长度减该字符最右涌现的位置。

代码:

/**
 * @param {string} haystack
 * @param {string} needle
 * @return {number}
 */
var strStr = function(haystack, needle) {
    if (needle === '') return 0
    if (needle.length > haystack.length) return -1
    if (needle.length === haystack.length && needle !== haystack) return -1

    let hash = {}
    for(let i = 0; i < needle.length; i++) {
        hash[needle.charAt(i)] = needle.length - i // 偏移表
    }

    for(let i = 0; i < haystack.length;) {
        let j
        for(j = 0; j < needle.length; j++) {
            if (haystack.charAt(i + j) !== needle.charAt(j)) {
                break
            }
        }
        if(j === needle.length) { // 完整婚配
            return i
        }
        if (i + needle.length >= haystack.length) { // 未找到
            return -1
        } else {
            i += hash[haystack.charAt(i + needle.length)] || needle.length + 1
        }
    }

    return -1
};

效果:

  • 74/74 cases passed (56 ms)
  • Your runtime beats 98.3 % of javascript submissions
  • Your memory usage beats 74.1 % of javascript submissions (33.6 MB)
  • 时刻复杂度 O(n)

思索总结

就明白的难易度来说,我发起先看 Sunday 算法Horspool 算法,不过 RMP 算法 的婚配思绪打开了眼界,应用后缀前缀来处置惩罚题目。这里把罕见的字符串算法都做了一次尝试,团体下来收成颇丰。

(完)

本文为原创文章,能够会更新学问点及修改毛病,因而转载请保存原出处,轻易溯源,防止陈腐毛病学问的误导,同时有更好的浏览体验
假如能给您带去些许协助,迎接 ⭐️star 或 ✏️ fork
(转载请说明出处:https://chenjiahao.xyz)

  选择打赏方式
微信赞助

打赏

QQ钱包

打赏

支付宝赞助

打赏

  移步手机端
【Leetcode 做题学算法周刊】第二期

1、打开你手机的二维码扫描APP
2、扫描左则的二维码
3、点击扫描获得的网址
4、可以在手机端阅读此文章
未定义标签

本文来源:搜奇网

本文地址:https://www.sou7.cn/282350.html

关注我们:微信搜索“搜奇网”添加我为好友

版权声明: 本文仅代表作者个人观点,与本站无关。其原创性以及文中陈述文字和内容未经本站证实,对本文以及其中全部或者部分内容、文字的真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考,并请自行核实相关内容。请记住本站网址https://www.sou7.cn/搜奇网。

发表评论

选填

必填

必填

选填

请拖动滑块解锁
>>