运维开发网

前端进阶算法:常见算法题及完美题解

运维开发网 https://www.qedev.com 2021-05-18 09:32 出处:51CTO 作者:mob604756ff98d6
前端进阶算法:常见算法题及完美题解,         引言瓶子君又来啦,她带着前端算法来了大厂面试越来越难,对算法的要求也越来越多,当面试官问到一个算法题,给出一份完美答案能大大提高面试官的好感度,本系列就是致力于打造一套适用于前端的算法。往期精彩系列视频面试超高频在线编程题,搞懂这些足以应对大部分公司前端进阶算法5:全方位解读前端用到的栈结构(+leetcode刷题)10 问 10 答,带你快速入门前端算法前端进阶算法4:链表原来

         

引言

瓶子君又来啦,她带着前端算法来了

大厂面试越来越难,对算法的要求也越来越多,当面试官问到一个算法题,给出一份完美答案能大大提高面试官的好感度,本系列就是致力于打造一套适用于前端的算法。

往期精彩系列

  • 视频面试超高频在线编程题,搞懂这些足以应对大部分公司

  • 前端进阶算法5:全方位解读前端用到的栈结构(+leetcode刷题)

  • 10 问 10 答,带你快速入门前端算法

  • 前端进阶算法4:链表原来如此简单(+leetcode刷题)

  • 前端进阶算法3:从浏览器缓存淘汰策略和Vue的keep-alive学习LRU算法

  • 瓶子君前端算法集训营第一期开营啦,免费哟

  • 前端进阶算法2:从Chrome  V8源码看JavaScript数组(附赠腾讯面试题)

  • 前端进阶算法1:如何分析、统计算法的执行效率和资源消耗?

以及题目:

  • 图解leetcode88:合并两个有序数组[8]
  • 字节&leetcode1:两数之和[9]
  • 腾讯:数组扁平化、去重、排序[10]
  • leetcode349:给定两个数组,编写一个函数来计算它们的交集[11]
  • leetcode146:设计和实现一个LRU(最近最少使用)缓存机制[12]
  • 阿里算法题:编写一个函数计算多个数组的交集[13]
  • leetcode21:合并两个有序链表[14]
  • 有赞&leetcode141:判断一个单链表是否有环[15]
  • 图解leetcode206:反转链表[16]
  • leetcode876:求链表的中间结点[17]
  • leetcode19:删除链表倒数第 n 个结点[18]
  • 图解字节&leetcode160:编写一个程序,找到两个单链表相交的起始节点[19]
  • 图解字节&leetcode151:翻转字符串里的单词[20]
  • 图解leetcode14:最长公共前缀[21]
  • 百度:实现一个函数,判断输入是不是回文字符串[22]
  • 字节&Leetcode3:无重复字符的最长子串[23]
  • 字节&leetcode155:最小栈(包含getMin函数的栈)[24]
  • 图解腾讯&leetcode20:有效的括号[25]
  • leetcode1047:删除字符串中的所有相邻重复项[26]

本节是第四周的总结与回顾,下面开始进入正题吧!

一、百度:实现一个函数,判断输入是不是回文字符串

1. 解法一:使用API

function isPlalindrome(input) {

  if (typeof input !== 'string') return false;

  return input.split('').reverse().join('') === input;

}

2. 解法二:不使用API

function isPlalindrome(input) {

  if (typeof input !== 'string') return false;

  let i = 0, j = input.length - 1

  while(i < j) {

      if(input.charAt(i) !== input.charAt(j)) return false

      i ++

      j --

  }

  return true

}

3. 更多题解

详见 百度:实现一个函数,判断输入是不是回文字符串[27]

二、字节&Leetcode3:无重复字符的最长子串

1. 题目

给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度。

示例 1:

输入: "abcabcbb"

输出: 3 

解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。

示例 2:

输入: "bbbbb"

输出: 1

解释: 因为无重复字符的最长子串是 "b",所以其长度为 1。

示例 3:

输入: "pwwkew"

输出: 3

解释: 因为无重复字符的最长子串是 "wke",所以其长度为 3。

     请注意,你的答案必须是 子串 的长度,"pwke" 是一个子序列,不是子串。

2. 解法

解法一:维护数组

解题思路: 使用一个数组来维护滑动窗口

遍历字符串,判断字符是否在滑动窗口数组里

  • 不在则 push 进数组
  • 在则删除滑动窗口数组里相同字符及相同字符前的字符,然后将当前字符 push 进数组
  • 然后将 max 更新为当前最长子串的长度

遍历完,返回 max 即可

画图帮助理解一下:

前端进阶算法:常见算法题及完美题解

代码实现:

var lengthOfLongestSubstring = function(s) {

    let arr = [], max = 0

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

        let index = arr.indexOf(s[i])

        if(index !== -1) {

            arr.splice(0, index+1);

        }

        arr.push(s.charAt(i))

        max = Math.max(arr.length, max) 

    }

    return max

};

时间复杂度:O(n2), 其中 arr.indexOf() 时间复杂度为 O(n) ,arr.splice(0, index+1) 的时间复杂度也为 O(n)

空间复杂度:O(n)

解法二:维护下标

解题思路: 使用下标来维护滑动窗口

代码实现:

var lengthOfLongestSubstring = function(s) {

    let index = 0, max = 0

    for(let i = 0, j = 0; j < s.length; j++) {

        index = s.substring(i, j).indexOf(s[j]) 

        if(index !== -1) { 

            i = i + index + 1 

        } 

        max = Math.max(max, j - i + 1) 

    }

    return max

};

时间复杂度:O(n2)

空间复杂度:O(n)

解法三:优化的Map

解题思路:

使用 map 来存储当前已经遍历过的字符,key 为字符,value 为下标

使用 i 来标记无重复子串开始下标,j 为当前遍历字符下标

遍历字符串,判断当前字符是否已经在 map 中存在,存在则更新无重复子串开始下标 i 为相同字符的下一位置,此时从 ij 为最新的无重复子串,更新 max ,将当前字符与下标放入 map

最后,返回 max 即可

代码实现:

var lengthOfLongestSubstring = function(s) {

    let map = new Map(), max = 0

    for(let i = 0, j = 0; j < s.length; j++) {

        if(map.has(s[j])) {

            i = Math.max(map.get(s[j]) + 1, i)

        }

        max = Math.max(max, j - i + 1)

        map.set(s[j], j)

    }

    return max

};

时间复杂度:O(n)

空间复杂度:O(n)

3. 更多题解

详见 字节&Leetcode3:无重复字符的最长子串[28]

三、文章:全方位解读栈结构

1. 数据结构栈

栈是一种遵从后进先出 (LIFO / Last In First Out) 原则的有序集合,它的结构类似如下:

前端进阶算法:常见算法题及完美题解

代码实现

function Stack() {

  let items = []

  this.push = function(e) { 

    items.push(e) 

  }

  this.pop = function() { 

    return items.pop() 

  }

  this.isEmpty = function() { 

    return items.length === 0 

  }

  this.size = function() { 

    return items.length 

  }

  this.clear = function() { 

    items = [] 

  }

}

查找:从栈头开始查找,时间复杂度为 O(n)

插入或删除:进栈与出栈的时间复杂度为 O(1)

2. 面试:调用栈

调用栈是 JavaScript 用来管理函数执行上下文的一种数据结构,它记录了当前函数执行的位置,哪个函数正在被执行。如果我们执行一个函数,就会为函数创建执行上下文并放入栈顶。如果我们从函数返回,就将它的执行上下文从栈顶弹出。也可以说调用栈是用来管理这种执行上下文的栈,或称执行上下文栈(执行栈)。

3. 面试:栈空间与堆空间

JavaScript 中的内存空间主要分为三种类型:

  • 代码空间:主要用来存放可执行代码
  • 栈空间:调用栈的存储空间就是栈空间。
  • 堆空间

代码空间主要用来存放可执行代码的。栈空间及堆空间主要用来存放数据的。接下来我们主要介绍栈空间及堆空间。

当调用栈中执行完成一个执行上下文时,需要进行垃圾回收该上下文以及相关数据空间,存放在栈空间上的数据通过 ESP 指针来回收,存放在堆空间的数据通过副垃圾回收器(新生代)与主垃圾回收器(老生代)来回收。

4. 详情

详细请看 前端进阶算法5:全方位解读前端用到的栈结构(+leetcode刷题)[29]

四、字节&leetcode155:最小栈(包含getMin函数的栈)

1. 题目

设计一个支持 pushpoptop 操作,并能在常数时间内检索到最小元素的栈。

  • push(x) —— 将元素 x 推入栈中。
  • pop() —— 删除栈顶的元素。
  • top() —— 获取栈顶元素。
  • getMin() —— 检索栈中的最小元素。

示例:

MinStack minStack = new MinStack();

minStack.push(-2);

minStack.push(0);

minStack.push(-3);

minStack.getMin();   --> 返回 -3.

minStack.pop();

minStack.top();      --> 返回 0.

minStack.getMin();   --> 返回 -2.

2. 解法

在常数时间内检索到最小元素的栈,即仅需保证 getMin 的时间复杂度为 O(1) 即可

var MinStack = function() {

    this.items = []

    this.min = null

};

// 进栈

MinStack.prototype.push = function(x) {

    if(!this.items.length) this.min = x 

    this.min = Math.min(x, this.min)

    this.items.push(x) 

};

// 出栈

MinStack.prototype.pop = function() {

    let num = this.items.pop() 

    this.min = Math.min(...this.items)

    return num

};

// 获取栈顶元素

MinStack.prototype.top = function() {

    if(!this.items.length) return null

    return this.items[this.items.length -1] 

};

// 检索栈中的最小元素

MinStack.prototype.getMin = function() {

    return this.min

};

时间复杂度:进栈O(1),出栈O(n),获取栈顶元素O(1),获取最小元素O(1)

空间复杂度:O(n)

3. 更多题解

详见 字节&leetcode155:最小栈(包含getMin函数的栈)[30]

五、图解腾讯&leetcode20:有效的括号

1. 题目

给定一个只包括 '('')''{''}''['']' 的字符串,判断字符串是否有效。

有效字符串需满足:

  • 左括号必须用相同类型的右括号闭合。
  • 左括号必须以正确的顺序闭合。

注意空字符串可被认为是有效字符串。

示例 1:

输入: "()"

输出: true

示例 2:

输入: "()[]{}"

输出: true

示例 3:

输入: "(]"

输出: false

示例 4:

输入: "([)]"

输出: false

示例 5:

输入: "{[]}"

输出: true

2. 解法:利用栈结构

解题思路: 将字符串中的字符依次入栈,遍历字符依次判断:

  • 首先判断该元素是否是 {([ ,直接入栈
  • 否则该字符为 })] 中的一种,如果该字符串有效,则该元素应该与栈顶匹配,例如栈中元素有 ({, 如果继续遍历到的元素为 ), 那么当前元素序列为 ({) 是不可能有效的,所以此时与栈顶元素匹配失败,则直接返回 false ,字符串无效

当遍历完成时,所有已匹配的字符都已匹配出栈,如果此时栈为空,则字符串有效,如果栈不为空,说明字符串中还有未匹配的字符,字符串无效

画图帮助理解一下:

前端进阶算法:常见算法题及完美题解

代码实现:

var isValid = function(s) {

    let map = {

        '{': '}',

        '(': ')',

        '[': ']'

    }

    let stack = []

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

        if(map[s[i]]) {

            stack.push(s[i])

        } else if(s[i] !== map[stack.pop()]){

            return false

        }

    }

    return stack.length === 0

};

时间复杂度:O(n)

空间复杂度:O(n)

3. 更多题解

详见 图解腾讯&leetcode20:有效的括号[31]

六、leetcode1047:删除字符串中的所有相邻重复项

1. 题目

给出由小写字母组成的字符串 S重复项删除操作 会选择两个相邻且相同的字母,并删除它们。

在 S 上反复执行重复项删除操作,直到无法继续删除。

在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。

示例:

输入:"abbaca"

输出:"ca"

解释:

例如,在 "abbaca" 中,我们可以删除 "bb" 由于两字母相邻且相同,这是此时唯一可以执行删除操作的重复项。之后我们得到字符串 "aaca",其中又只有 "aa" 可以执行重复项删除操作,所以最后的字符串为 "ca"。

提示:

  1. <= S.length <= 20000
  2. S 仅由小写英文字母组成。

2. 解法:利用栈

解题思路: 遍历字符串,依次入栈,入栈时判断与栈头元素是否一致,如果一致,即这两个元素相同相邻,则需要将栈头元素出栈,并且当前元素也无需入栈

解题步骤: 遍历字符串,取出栈头字符,判断当前字符与栈头字符是否一致

  • 不一致,栈头字符进栈,当前字符进栈
  • 一致,即栈头字符与当前字符相同相邻,都不需要进栈,直接进入下次遍历即可

遍历完成后,返回栈中字符串

代码实现:

var removeDuplicates = function(S) {

    let stack = []

    for(c of S) {

        let prev = stack.pop()

        if(prev !== c) {

            stack.push(prev)

            stack.push(c)

        }

    }

    return stack.join('')

};

时间复杂度:O(n)

空间复杂度:O(n)

0

精彩评论

暂无评论...
验证码 换一张
取 消