阅读 13855

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

引言

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

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

往期精彩系列文章:

三篇交流群刷题总结:

题目(题目仅仅会在「前端进阶算法集训营」里发布,每早 9: 00):

数组篇:

链表篇:

字符串篇:

栈篇:

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

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

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. 更多题解

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

二、字节&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:无重复字符的最长子串

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

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刷题)

四、字节&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函数的栈)

五、图解腾讯&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:有效的括号

六、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)

3. 更多题解

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

七、前端算法集训营第一期免费加入啦

从0到1构建完整的数据结构与算法体系!

在这里,瓶子君不仅介绍算法,还将算法与前端各个领域进行结合,包括浏览器、HTTP、V8、React、Vue源码等。

在这里,你可以每天学习一道大厂算法题(阿里、腾讯、百度、字节等等)或 leetcode,瓶子君都会在第二天解答哟!

扫码加入,若群人数已达上线,关注公众号「前端瓶子君」,回复「算法」即可自动加入

⬆️ 扫码关注公众号「前端瓶子君」,回复「算法」即可自动加入 👍👍👍

关注下面的标签,发现更多相似文章
评论