专栏首页前端有的玩「算法与数据结构」我的2020前端算法小结

「算法与数据结构」我的2020前端算法小结

前言

最近好多事情,最近前端分享会也如期而至,有幸这次分享会,正好周末有时间,做个总结吧。

这次想分享的就是「算法与数据结构」,刷了一段时间题目,逛了逛LeetCode,看了很多关于这个方面的文章,有所感悟,准备做个记录吧。

当你想花时间去了解学习一件对你来说,很苦难的事情的时候,我们需要明确目标,学习它的意义,它有什么用,对你有哪方面帮助。

升职加薪必备,对以后成长有所帮助,嗯,加薪,加薪,加薪。

那么问题来了,为什么要进大厂呢⬇️

❝年轻时候去大厂的目标,是为了避免,【你得顿悟,是别人的基本功】 ❞

嗯,闲聊就止步于此,接下来开始吧~

站在巨人肩膀上,学起来就很轻松了, 这里我是参考网上的算法刷题路线,可以参考一下~

公众号「前端UpUp」,回复「算法」,即可获取脑图,以及文末的题目汇总pdf。

接下来,我们就根据这个脑图来梳理一遍吧~


数据结构

数据结构可以说是算法的基石,如果没有扎实的数据结构基础,想要把算法学好甚至融会贯通是非常困难的,而优秀的算法又往往取决于你采用哪种数据结构。学好这个专题也是很有必要的,那么我们可以稍微的做个分类。

  • 常用数据结构
    • 数组,字符串
    • 链表
    • 队列
  • 高级数据结构
    • 前缀树
    • 线段树
    • 树状数组
    • 主席树

那么显然,最常见的数据结构一定是需要掌握的,对于高级的数据结构而言,如果你有时间,对它有所热爱的话,可以深入了解,比如这个「主席树」在解决一些问题 的时候,算法复杂度是log级别的,某些场景下很有帮助。

这里想提及的就是「树」。它的结构很显然是很直观的,树当然有很多的性质,这里也列举不完,比如面试中常考的树:

❝普通二叉树、平衡二叉树、完全二叉树、二叉搜索树、四叉树(Quadtree)、多叉树(N-ary Tree)。 ❞

对于它而言的话,我们需要到哪些程度呢?

对于常见树的遍历,从树的前序遍历,到中序遍历,后续遍历,以至于层次遍历,掌握好这四种遍历的递归写法和非递归写法是非常重要的,接下来需要懂得分析各种写法的时间复杂度和空间复杂度。

面试准备阶段,把树这个结构花时间去准备的话,对于你理解递归还是很有帮助的,同时也能帮助你学习一些图论的知识,更加准确的说,树是面试考察的热门考点,尤其是二叉树!

❝掌握好这些数据结构是基础,绝大部分的算法面试题都得靠它们来帮忙,因此,一定要花功夫勤练题目来深入理解它们。 ❞


排序算法

这应该是面试最常考,最核心的算法。如果你能把排序算法理解的很透彻的话,接下来的其他算法也是一样的旁敲侧击。

当时我梳理得是常见的6个排序算法:

  • 冒泡排序
  • 计数排序
  • 快速排序
  • 归并排序
  • 插入排序
  • 选择排序

在此之前,我也写过一篇排序算法的文章,个人觉得言简意赅,可以看看「算法与数据结构」梳理6大排序算法

有时候,面试官喜欢会问冒泡排序和插入排序,基本上这些都是考察你的基础知识,并且看看你能不能快速地写出没有bug的代码。

又比如,当面试官问你归并排序、快速排序和拓扑排序等的时候,这个时候考察的是你平时对算法得积累,所以有必要做个总结。

我们拿「归并排序」来举例子,我们应该如何表达清楚呢?首先,我们应该把这个它的思路说清楚:

归并排序的核心思想就是分治,它将一个复杂的问题分成两个或者多个相同或相似的子问题,然后把子问题分成更小的子问题,直到子问题可以简单的直接求解,最原问题的解就是子问题解的合并。「归并排序」将分治的思想体现得淋漓尽致。

当你向面试官理清楚这个思路时,面试官心里就有底了,他会想,嘿,这个小伙子不错!那你接下来都有底气了!

有了思想,那么实现起来就不难了:

❝一开始先把数组从中间划分成两个子数组,一直递归地把子数组划分成更小的子数组,直到子数组里面只有一个元素,才开始排序。 排序的方法就是按照大小顺序合并两个元素,接着依次按照递归的返回顺序,不断地合并排好序的子数组,直到最后把整个数组的顺序排好。 ❞

贴一份之前的代码:

const merge = (left, right) => { // 合并数组

    let result = []
    // 使用shift()方法偷个懒,删除第一个元素,并且返回该值
    while (left.length && right.length) {
        if (left[0] <= right[0]) {
            result.push(left.shift())
        } else {
            result.push(right.shift())
        }
    }
    while (left.length) {
        result.push(left.shift())
    }

    while (right.length) {
        result.push(right.shift())
    }
    return result
}

let mergeSort = function (arr) {
    if (arr.length <= 1)
        return arr
    let mid = Math.floor(arr.length / 2)
    // 拆分数组
    let left = arr.slice(0, mid),
        right = arr.slice(mid);
    let mergeLeftArray = mergeSort(left),
        mergeRightArray = mergeSort(right)
    return merge(mergeLeftArray, mergeRightArray)
}

// let arr = [2, 9, 6, 7, 4, 3, 1, 7, 0, -1, -2]
// console.log(mergeSort(arr))

对于这部分的算法而言,可以围绕从「解题思路」-->>「实现过程」-->>「代码实现」。基本上以这三步来实现的话,掌握常见的排序算法完成是没有问题的。

那么这部分就暂时梳理到这里吧。


动态规划

动态规划难,可以说是很多面试者也是我最怕的部分,尤其是面试的时候,怕面试官考这个算法了。遇到没有做过的题目,这个时候,能否写出状态转移方程是十分重要的。接下来我们聊一聊这个专题吧。

首先,强烈推荐我之前分析这个专题如何准备的:「算法与数据结构」一张脑图带你看动态规划算法之美

如果从点赞角度来看,可以说,是我写算法以来,得到大家肯定最多的一次了,可以看看,不过这里也会涵盖部分。

如何学动态规划,从哪里入手,应该这么去做,这么去刷题,肯定是很多初学者一开始就会遇到的问题。

  • 概念
  • 动态规划解决了什么问题
  • 动态规划解题的步骤
  • 如何高效率刷dp专题

首先,你得了解动态规划是什么,它的思想是什么,定义又是啥。这里引入维基百科对它的定义:

❝Wikipedia 定义:它既是一种数学优化的方法,同时也是编程的方法。 ❞

当然了,看完这段话,我们肯定对它不了解的,我们可以翻译一下,首先它可以算是一种优化的手段,优化一些重复子问题的操作,将很多重叠子问题通过编程的方式来解决,比如「记忆划搜索」。又比如,如果一个原问题,可以拆分成很多子问题,它们之间没有任何后续性,当前的决策对后续没有影响的话,每个子问题的最优解,就可以组合成原问题的最优解了。

当然了,对于动态规划每个人理解是不同的,对于应用到具体的场景中,需要我们都去用多维度的状态去表述它的含义,这里也就是状态转移方程的含义所在。

嗯,那么动态规划解决了什么问题呢,很显然,对于重复性问题来说,它可以很好的解决,那么从某个维度上来看,它可以优化一个算法的时间复杂度,也就是通常意义上的,拿空间来换取时间的操作。

「动态规划解题步骤」:这个应该就是实际落地的操作,需要我们去通过大量的题目来完成,具体我们需要怎么做呢?

解题思路,三大步骤?

  1. 「状态定义」
  2. 「列出状态转移方程」
  3. 「初始化状态」

「算法与数据结构」一张脑图带你看动态规划算法之美强烈推荐这篇问题,里面讲的很清楚了。

「如何高效率刷dp专题」:首先,你得找到对应的dp专题,这里的话,我帮你准备好了,接下来我说一下我是怎么刷leetcode上面的题目的。

一般而言,刷完中等的leetcode上的dp专题,基本上可以满足要求了。那么对于中等的dp题目,很多时候,我是写不吃来的,那我应该如何去做呢?

  • 首先,我先看题解,把它的状态转移方程写下来,仔细的品味一下,它这么定义,解决了我之前的什么难点,为啥我是没有想到的。
  • 然后,看完之后,尝试按照这个题解思路,我自己能不能单独实现呢?
  • 如果不能的话,就照着它的代码,写一遍,多看看状态转移方程是如何写的,把这个题目收藏起来。
  • 等到下次,或者是隔天,再来看一遍题目,然后看看能不能单独完成,如果不能,第三天再这么操作。

还有,我个人建议,刷dp的话,最好从易到难,这样子自己也会有信心,也不会再去畏惧它。

进阶题目汇总

以下是我收集的部分题目,希望对你们有帮助。

简单

  • 爬楼梯
  • 打家劫舍
  • 使用最小花费爬楼梯
  • 连续数列
  • 三步问题

中等

  • 打家劫舍 II
  • 最佳买卖股票时机含冷冻期
  • 打家劫舍 III
  • 不同路径
  • 不同路径 II
  • 最长上升子序列

困难

  • 买卖股票的最佳时机 III
  • 买卖股票的最佳时机 IV
  • 青蛙过河
  • 单词拆分 II
  • 最大子矩阵

搜索算法

这部分也是尤其重要的,那么重点学习深度优先搜索算法(简称为 DFS)和广度优先搜索算法(简称为 BFS)。

在这里推荐一个有趣的题目:

穿过迷宫的最少移动次数

如果你也遇到过迷宫类似的问题,就可以考虑搜索算法了,从我个人的角度来说,它的思路其实就是模拟人的思路,每次走到一个路口的时候,我可以走哪里,我之前走过的路,怎么确保,接下来是不能走的,这里需要在编程的角度,如何去实现呢?

这里说一说我的经验,对于刚刚提到的题目而言,我盲猜使用BFS,题目做多了,自然就会有心得,对于BFS和DFS而言,做了两个类似的题目,会发现,原来搜索算法也是有迹可循,也是存在某些套路的。

给些建议:

一开始可能做的时候,抓不到头脑,有思路,但是代码很难写清楚,那么如何去做呢?「看题解」,了解别人的写法是很不错的,可以多个对比,看看哪一份题解代码是你目前可以理解的,然后抄下来,看一遍。

最普通的办法就是:先画图,看看思维上跟实际代码需要做哪些改变,如何去优化这个过程。最后结合别人代码,一定不要直接copy,不去思考为什么这么写,不然后期发现,是没有多大效果的,一定要多结合自己的理解。

嗯,不会就看题解,多思考为什么这么写!!!


写到这里的时候,已经凌晨1点了,算法与数据结构这个方向太大了,一篇文章不可能写得完,我更希望这篇文章对你,有那么一点点的帮助,对我,或你都些许有所帮助,那么它得存在就有那么一点点意义。

进阶题目汇总

这个专题想进阶,就刷我下面提供的题目吧?

DFS

  • 二叉树的最大深度
  • 二叉树的最小深度
  • 朋友圈
  • 找到最终的安全状态
  • 矩阵中的最长递增路径
  • 扫雷游戏
  • 单词接龙

BFS

  • N叉树的层序遍历
  • 二叉树的层序遍历
  • 最小高度树
  • 扫雷游戏

题目汇总

我之前刷题历程是根据这套题来的,我觉得里面题目梯度还是质量都是很不错的。

拿到这个pdf有段时间了,所以不清楚具体作者是谁,有侵权的话,可删。

数组&链表

简单

  • https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array/
  • https://leetcode-cn.com/problems/rotate-array/
  • https://leetcode-cn.com/problems/merge-two-sorted-lists/
  • https://leetcode-cn.com/problems/merge-sorted-array/

中等

  • https://leetcode-cn.com/problems/swap-nodes-in-pairs/
  • https://leetcode-cn.com/problems/3sum/

Map & Set

简单

  • https://leetcode-cn.com/problems/valid-anagram/

中等

  • https://leetcode-cn.com/problems/group-anagrams/

堆栈&队列

简单

  • https://leetcode-cn.com/problems/remove-all-adjacent-duplicates-in-string/
  • https://leetcode-cn.com/problems/remove-outermost-parentheses/

中等

  • https://leetcode.com/problems/largest-rectangle-in-histogram/
  • https://leetcode.com/problems/trapping-rain-water/

二分查找

简单

  • https://leetcode-cn.com/problems/arranging-coins/

中等

  • https://leetcode-cn.com/problems/powx-n/

困难

  • https://leetcode-cn.com/problems/dungeon-game/

递归

简单

  • https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/
  • https://leetcode-cn.com/problems/symmetric-tree/
  • https://leetcode-cn.com/problems/minimum-depth-of-binary-tree/
  • https://leetcode-cn.com/problems/minimum-distance-between-bst-nodes/
  • https://leetcode-cn.com/problems/binary-tree-paths/
  • https://leetcode-cn.com/problems/range-sum-of-bst/

中等

  • https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/

哈希表

简单

  • https://leetcode-cn.com/problems/two-sum/
  • https://leetcode-cn.com/problems/valid-anagram/

中等

  • https://leetcode-cn.com/problems/longest-substring-without-repeating-characters
  • https://leetcode-cn.com/problems/top-k-frequent-words

困难

  • https://leetcode-cn.com/problems/number-of-atoms/

二叉树

简单

  • https://leetcode-cn.com/problems/minimum-depth-of-binary-tree/
  • https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/

中等

  • https://leetcode-cn.com/problems/symmetric-tree/
  • https://leetcode-cn.com/problems/binary-tree-zigzag-level-order-traversal/
  • https://leetcode-cn.com/problems/binary-tree-level-order-traversal/

困难

  • https://leetcode-cn.com/problems/serialize-and-deserialize-binary-tree/

二叉搜索树

简单

  • https://leetcode-cn.com/problems/minimum-distance-between-bst-nodes/
  • https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-search

中等

  • https://leetcode-cn.com/problems/validate-binary-search-tree/
  • https://leetcode-cn.com/problems/range-sum-of-bst/
  • https://leetcode-cn.com/problems/contains-duplicate-iii/

困难

  • https://leetcode-cn.com/problems/count-of-smaller-numbers-after-self/

中等

  • https://leetcode.com/problems/number-of-islands/
  • https://leetcode-cn.com/problems/course-schedule-ii

堆和排序

简单

  • https://leetcode-cn.com/problems/kth-largest-element-in-a-stream/

困难

  • https://leetcode-cn.com/problems/find-median-from-data-stream/

DFS

简单

  • https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/
  • https://leetcode-cn.com/problems/minimum-depth-of-binary-tree/

中等

  • https://leetcode-cn.com/problems/friend-circles/
  • https://leetcode-cn.com/problems/find-eventual-safe-states/

困难

  • https://leetcode-cn.com/problems/longest-increasing-path-in-a-matrix/
  • https://leetcode-cn.com/problems/minesweeper/
  • https://leetcode-cn.com/problems/word-ladder/

BFS

简单

  • https://leetcode-cn.com/problems/n-ary-tree-level-order-traversal/
  • https://leetcode-cn.com/problems/binary-tree-level-order-traversal/
  • https://leetcode.com/problems/binary-tree-level-order-traversal-ii/

中等

  • https://leetcode.com/problems/binary-tree-zigzag-level-order-traversal/
  • https://leetcode-cn.com/problems/minesweeper/
  • https://leetcode-cn.com/problems/minimum-height-trees/

Trie树

简单

  • https://leetcode-cn.com/problems/longest-word-in-dictionary/

中等

  • https://leetcode-cn.com/problems/implement-trie-prefix-tree/
  • https://leetcode-cn.com/problems/add-and-search-word-data-structure-design/

困难

  • https://leetcode-cn.com/problems/word-search-ii/

分治算法

简单

  • https://leetcode-cn.com/problems/majority-element/

中等

  • https://leetcode-cn.com/problems/maximum-subarray/
  • https://leetcode-cn.com/problems/search-a-2d-matrix-ii/

回溯算法

简单

  • https://leetcode-cn.com/problems/letter-case-permutation/

中等

  • https://leetcode-cn.com/problems/subsets/
  • https://leetcode-cn.com/problems/permutations/
  • https://leetcode-cn.com/problems/combinations/

困难

  • https://leetcode-cn.com/problems/n-queens/

贪心算法

简单

  • https://leetcode-cn.com/problems/assign-cookies/

中等

  • https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/

动态规划

简单

  • https://leetcode-cn.com/problems/climbing-stairs/
  • https://leetcode.com/problems/house-robber/

中等

  • https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/
  • https://leetcode.com/problems/house-robber-ii/
  • https://leetcode.com/problems/house-robber-iii/
  • https://leetcode.com/problems/unique-paths/
  • https://leetcode.com/problems/unique-paths-ii/

困难

  • https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iv/
  • https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iii/

本文分享自微信公众号 - 前端有的玩(gh_918bae0a9616),作者:TianTianUp

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-12-15

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 前端学习数据结构与算法系列(一):初识数据结构与算法

    作为一个对算法没有任何认知,非科班出身的前端程序员,如果想提高自己的能力,不再只写业务代码当一个应用工程师,算法是必须掌握的一门本领。算法也是一种思想,当你去读...

    一只图雀
  • 重学前端(四)-数据结构与算法

    最近在撸vue 和react的源码,虽然晦涩难懂,但是却发现新大陆,发现了数据结构和算法在前端的重要性,比如在react中,发现react的fiber树,对应的...

    用户7413032
  • 算法与数据结构

    七月半夏
  • 数据结构与算法

    树的遍历分为深度优先搜索和广度优先搜索。深度优先搜索有先序遍历、中序遍历、和后序遍历三种方式。广度优先搜索是层次遍历。

    不作声
  • 数据结构与算法

    一个会写诗的程序员
  • 数据结构与算法-

    因为很大的数已经超过了计算机可以存储,虽然 Python3 中的整型是没有限制内存大小的,但是不代表其他语言没有内存限制,所以一般将两个整数直接相加并不现实

    机器视觉CV
  • 算法与数据结构

    longzeqiu
  • 数据结构与算法在前端领域的应用

    这是一个我即将做的一个《数据结构与算法在前端领域的应用》主题演讲的一个前菜。希望通过这个分享让大家认识到其实前端领域也有很多算法的,从而加深前端同学对算法的认识...

    lucifer210
  • 前端领域的数据结构与算法解读 - fiber

    这一次我们顺着前面的内容,讲一些经典的数据结构与算法,本期我们来讲一下时下比较火热的 Reactfiber。

    lucifer210
  • JavaScript 数据结构与算法(一)前言

    例如:一个庞大的图书馆中存放了大量的书籍,我们不仅仅要把书放进入,还应该在合适的时候能够取出来。

    XPoet
  • python算法与数据结构-算法和数据结构介绍(31)

    什么是算法和数据结构?如果将最终写好运行的程序比作战场,我们程序员便是指挥作战的将军,而我们所写的代码便是士兵和武器。

    Se7eN_HOU
  • 数据结构与算法 - 线性结构

    首先,这篇文章不是讲解数据结构的文章,而是结合现实的场景帮助大家 理解和复习数据结构与算法 。

    皮小蛋
  • 算法与数据结构(一)

      用计算机实现问题求解,实质上就是在计算机中建立一个解决问题的模型。用来表示问题或处理问题的模型可以有不同的抽象形式:

    Hongten
  • 算法与数据结构algorithm

    算法与数据结构 《Data structures》 介绍:高级数据结构大全,基本算法:二叉树等 《基于用户投票的排名算法(一):Delicious和Hacker...

    Albert陈凯
  • 数据结构与算法(一)

    算法的概念 算法是计算机处理信息的本质,因为计算机程序本质上是一个算法来告诉计算机确切的步骤来执行一个指定的任务。一般地,当算法在处理信息时,会从输入设备或数据...

    酱紫安
  • 数据结构与算法(二)

    排序与搜索 排序算法(英语:Sorting algorithm)是一种能将一串数据依照特定顺序进行排列的一种算法。 排序算法的稳定性 稳定性:稳定排序算法会让原...

    酱紫安
  • 数据结构与算法-树

    用户3470542
  • 数据结构与算法(三)

    当我们在记录这个算法的步骤的时候,不能写出“一个长度为N的有序数组中用二分查找需要的步骤为XX步”.这样写不仅浪费时间又啰嗦,这是我们不想要的,那么有什么办法简...

    LittleU
  • 数据结构与算法(六)

    之前的文章告诉你,在使用大O记法的时候,考虑的是最坏的情况,因为在一般逻辑中,最坏的情况下都考虑到了,那么还有什么情况比最坏的情况还坏呢?但是本文告诉你,只考虑...

    LittleU

扫码关注云+社区

领取腾讯云代金券