• home > theory > algorithm > leetcode >

    算法与数据结构面试通关经验总结:leetCode刷题经验

    Author:zhoulujun Date:

    算法导论是不是好书?是。它讲的内容硬不硬?硬。但对大多数人求职找工作有没有用?没啥用,性价比太低了。什么性价比高?直接刷LeetCode。

    大部分开发岗位工作中都是基于现成的开发框架做事,不怎么会碰到底层数据结构和算法相关的问题,但另一个事实是,只要你想找技术相关的岗位,数据结构和算法的考察是绕不开的,因为这块知识点是公认的程序员基本功。

    学算法,算法导论是不是好书?是。但对大多数人求职找工作有没有用?没啥用,性价比太低了。

    什么性价比高?直接刷LeetCode。但是,到了面试时刻,题海战术对于零时抱佛脚的我,肯定挂!所以用 框架性思维去应战

    如果你掌握了框架思维,现在随便给你一道题目,那你就可以按照固定的思维步骤进行思考:

    这题让我们干什么?奥,让我们操作字符串。字符串本质就是个数组,所以这题考察的大概是数组相关的算法技巧。

    数组有什么算法技巧?你心里有数,无非就是 二分查找快慢指针左右指针滑动窗口前缀和数组差分数组,主要就这些。

    二分查找的适用场景是什么?差分数组的适用场景是什么?你挨个想一遍,这个不行换那个,总能试出来个相对靠谱的吧?

    如果你知道滑动窗口的代码框架,所以你是先把框架写出来,然后往框架里面填充代码。

    扣评论区里面某些大佬的精彩解法吸引,但是我想说,在培养出自己的框架思维之前,这些方法你可以看看,但不要执迷。

    算法刷题指南

    以我的刷题经验,初学者最好从「树」相关的问题开始练习递归思维,然后开始系统系了解各类算法的基本原理

    先学习像数组、链表这种基本数据结构的常用算法比如单链表翻转,前缀和数组,二分搜索等

    学会常用算法之后,不要急着上来就刷回溯算法、动态规划这类笔试常考题,而应该先刷二叉树,因为二叉树是最容易培养框架思维的,而且大部分算法技巧,本质上都是树的遍历问题

    至于理论方面的学习,可以看我的 “讲透学烂二叉树”

    刷玩二叉树,再去做什么回溯动规分治专题,你就会发现只要涉及递归的问题,都是树的问题

    比如动态规划详解说过凑零钱问题,暴力解法就是遍历一棵 N 叉树,回溯算法就是个 N 叉树的前后序遍历问题,排列组合问题抽象成一棵多叉树结构,然后用回溯算法去暴力穷举……

    数据结构是工具,算法是通过合适的工具解决特定问题的方法。

    也就是说,学习算法之前,最起码得了解那些常用的数据结构,了解它们的特性和缺陷。


    数据结构的存储方式

    数据结构的存储方式只有两种:数组(顺序存储)和链表(链式存储)

    • 数组由于是紧凑连续存储,可以随机访问,通过索引快速找到对应元素,而且相对节约存储空间。但正因为连续存储,内存空间必须一次性分配够,所以说数组如果要扩容,需要重新分配一块更大的空间,再把数据全部复制过去,时间复杂度 O(N);而且你如果想在数组中间进行插入和删除,每次必须搬移后面的所有数据以保持连续,时间复杂度 O(N)

    • 链表因为元素不连续,而是靠指针指向下一个元素的位置,所以不存在数组的扩容问题;如果知道某一元素的前驱和后驱,操作指针即可删除该元素或者插入新元素,时间复杂度 O(1)。但是正因为存储空间不连续,你无法根据一个索引算出对应元素的地址,所以不能随机访问;而且由于每个元素必须存储指向前后元素位置的指针,会消耗相对更多的储存空间

    散列表、栈、队列、堆、树、图等等各种数据结构都属于「上层建筑」,而数组和链表才是「结构基础」

    比如说「队列」、「栈」这两种数据结构既可以使用链表也可以使用数组实现。

    • 用数组实现,就要处理扩容缩容的问题;

    • 用链表实现,没有这个问题,但需要更多的内存空间存储节点指针。

    看下《再谈js数据类型与对象数据结构底层实现原理-object array map set 》与《再谈Java数据结构—分析底层实现与应用注意事项》的图:

    计算机数据结构图解2291135-f88efeec448e959e.jpg

    有这些多样化的数据结构,究其源头,都是在链表或者数组上的特殊操作,API 不同而已。

    • 「图」的两种表示方法,

      • 邻接表就是链表:邻接表比较节省空间,但是很多操作的效率上肯定比不过邻接矩阵。

      • 邻接矩阵就是二维数组邻接矩阵判断连通性迅速,并可以进行矩阵运算解决一些问题,但是如果图比较稀疏的话很耗费空间。

    • 「散列表」就是通过散列函数把键映射到一个大数组里。而且对于解决散列冲突的方法,拉链法需要链表特性,操作简单,但需要额外的空间存储指针;线性探查法就需要数组特性,以便连续寻址,不需要指针的存储空间,但操作稍微复杂些。

    • 「树」

      • 用数组实现就是「堆」,因为「堆」是一个完全二叉树,用数组存储不需要节点指针,操作也比较简单;

      • 用链表实现就是很常见的那种「树」,因为不一定是完全二叉树,所以不适合用数组存储。为此,在这种链表「树」结构之上,又衍生出各种巧妙的设计,比如二叉搜索树、AVL 树、红黑树、区间树、B 树等等,以应对不同的问题。

    了解 Redis 数据库的朋友可能也知道,Redis 提供列表、字符串、集合等等几种常用数据结构,但是对于每种数据结构,底层的存储方式都至少有两种,以便于根据存储数据的实际情况使用合适的存储方式

    数据结构的基本操作

    对于任何数据结构,其基本操作无非遍历 + 访问,再具体一点就是:增删查改。

    数据结构种类很多,但它们存在的目的都是在不同的应用场景,尽可能高效地增删查改。话说这不就是数据结构的使命么?

    如何遍历 + 访问?我们仍然从最高层来看,各种数据结构的遍历 + 访问无非两种形式:

    • 线性的:线性就是 for/while 迭代为代表

    • 非线性的:非线性就是递归为代表

    数组遍历框架

    典型的线性迭代结构:

    for (int i = 0; i < arr.length; i++) {
            // 迭代访问 arr[i]
    }

    链表遍历框架

    兼具迭代和递归结构:二叉树遍历框架,典型的非线性递归遍历结构

    /* 基本的二叉树节点 */
    class TreeNode {
      constructor(val) {
        this.val = val;
        this.left = null;
        this.right = null;
      }
    }
    
    var traverse = function(root) {
      if (root === null) return;
      traverse(root.left);
      traverse(root.right);
    };

    你看二叉树的递归遍历方式和链表的递归遍历方式,相似不?再看看二叉树结构和单链表结构,相似不?如果再多几条叉,N 叉树你会不会遍历?


    二叉树框架可以扩展为 N 叉树的遍历框架:

    /* 基本的 N 叉树节点 */
    var TreeNode = function(val, children) {
      this.val = val;
      this.children = children;
    };
    
    // 遍历 N 叉树
    var traverse = function(root) {
      for (var i = 0; i < root.children.length; i++) {
        traverse(root.children[i]);
      }
    };

    N 叉树的遍历又可以扩展为图的遍历,因为图就是好几 N 叉棵树的结合体

    你说图是可能出现环的?这个很好办,用个布尔数组 visited 做标记就行了,经典题:岛屿算法(求岛屿数量与岛屿面积)


    算法的本质

    如果要让我一句话总结,我想说算法的本质就是「穷举」

    比如,密码学算法、机器学习算法,它们的本质确实不是穷举,而是数学原理的编程实现,所以这类算法的本质是数学,不在我们所探讨的「数据结构和算法」的范畴之内。

    「算法工程师」做的这个「算法」,和「数据结构与算法」中的这个「算法」完全是两码事

    • 对前者来说,重点在数学建模和调参经验,计算机真就只是拿来做计算的工具而已;

    • 后者的重点是计算机思维,需要你能够站在计算机的视角,抽象、化简实际问题,然后用合理的数据结构去解决问题

    不妨称算法工程师研究的算法为「数学算法」,称刷题面试的算法为「计算机算法」,我写的内容主要聚焦的是「计算机算法」。

    大部分人的目标是通过算法笔试,找一份开发岗位的工作,所以你真的不需要有多少数学基础,只要学会用计算机思维解决问题就够了。

    其实计算机思维也没什么高端的,你想想计算机的特点是啥?不就是快嘛,你的脑回路一秒只能转一圈,人家 CPU 转几万圈无压力。所以计算机解决问题的方式大道至简,就是穷

    穷举有两个关键难点:无遗漏、无冗余

    • 遗漏,会直接导致答案出错

    • 冗余,会拖慢算法的运行速度。

    当你看到一道算法题,可以从这两个维度去思考:

    1. 如何穷举?即无遗漏地穷举所有可能解。

    2. 如何聪明地穷举?即避免所有冗余的计算,消耗尽可能少的资源求出答案。

    不同类型的题目,难点是不同的,有的题目难在「如何穷举」,有的题目难在「如何聪明地穷举」。

    • 什么算法的难点在「如何穷举」呢?一般是递归类问题,最典型的就是动态规划系列问题。

    • 什么算法的难点在「如何聪明地穷举」呢?一些耳熟能详的非递归算法技巧,都可以归在这一类。

      • 比如后文 Union Find 并查集算法详解 告诉你一种高效计算连通分量的技巧,理论上说,想判断两个节点是否连通,我用 DFS/BFS 暴力搜索(穷举)肯定可以做到,但人家 Union Find 算法硬是用数组模拟树结构,给你把连通性相关的操作复杂度给干到 O(1) 了。

      • 比如贪心算法技巧,后文 当老司机学会贪心算法 就告诉你,所谓贪心算法就是在题目中发现一些规律(专业点叫贪心选择性质),使得你不用完整穷举所有解就可以得出答案。

      • 比如大名鼎鼎的 KMP 算法,你写个字符串暴力匹配算法很容易,但你发明个 KMP 算法试试?KMP 算法的本质是聪明地缓存并复用一些信息,减少了冗余计算,前文 KMP 字符匹配算法 就是使用状态机的思路实现的 KMP 算法。

    数组/单链表系列算法

    单链表常考的技巧就是双指针,后文 单链表六大技巧 全给你总结好了

    比如判断单链表是否成环,拍脑袋的暴力解是什么?就是用一个 HashSet 之类的数据结构来缓存走过的节点,遇到重复的就说明有环对吧。但我们用快慢指针可以避免使用额外的空间,这就是聪明地穷举嘛。



    算法题分类

    LeetCode算法按照类型分类,常见的算法类型包括:

    1. 递归和回溯

    2. 深度优先搜索(DFS)和广度优先搜索(BFS)

    3. 双指针

    4. 动态规划

    5. 贪心算法

    6. 二分搜索

    7. 排序算法

    8. 并查集

    9. 分治算法

    10. 位运算

    以下是针对每种算法或概念进行的简易介绍,以及面试中可能用到的思路提示。

    递归和回溯

    递归是函数调用自身的过程,它可以用来解决可以分解为相似子问题的问题,比如树的遍历、汉诺塔等。递归解决问题时要注意定义清楚终止条件和递归表达式

    回溯算法是一种通过递归来遍历搜索解的算法,它试图分步去解决一个问题。在分步解决问题的过程中,当它通过尝试发现现有的分步答案不能得到有效的正确的解答时,它将取消上一步甚至是上几步的计算,再通过其他可能的分步解答再次尝试寻找问题的答案

    面试思路:

    • 明确每次递归的参数和返回值是什么,递归的终止条件是什么,以及在每一层递归中应该做什么。

    • 对于回溯,注意如何撤销上一步的操作。

    深度优先搜索(DFS)和广度优先搜索(BFS)

    DFS使用栈(实际递归就是隐式栈)来实现,主要用于寻找可能的解的空间,适用于目标明确,解的结构树不宽

    BFS使用队列来实现,层层推进,逐个访问所有可能的状态,适用于最短路径问题

    面试思路:识别问题是不是搜索问题,考虑使用DFS或BFS。

    • DFS适用于需要访问每个节点,找所有可能解的问题。

    • BFS适用于找最短路径或是与距离相关的问题

    双指针

    双指针主要用于对有序数组进行扫描,通过一个头指针和一个尾指针在一个循环中完成两个变量的移动,达到降低时间复杂度的目的

    面试思路:识别是否为有序数组或链表问题,考虑是否可以通过前后指针减少不必要的遍历

    动态规划

    动态规划主要思想是将复杂问题分解成小问题来逐个击破核心是找到状态转移方程。很多问题如最短路径、最长公共子序列等都可以用动态规划解决。

    面试思路:寻找问题中的最优子结构,明确状态、选择以及状态转移方程。

    贪心算法

    贪心算法在每一步选择中都采取当前状态下最好或最优(即最有利)的选择,从而希望导致结果是全局最好或最优的算法。

    面试思路:评估问题是否每一步最优选择可以得到全局最优解,注意不能回退。

    二分搜索

    二分搜索针对已排序的数据集合,每次通过将搜索范围缩小一半的方式来查找目标值,大大减少查找时间

    面试思路:确认数据是否有序,明确二分搜索的左右界及更新规则。

    排序算法

    排序算法有多种,包括快速排序、归并排序、冒泡排序等。重点理解每种排序算法的原理、时间复杂度和空间复杂度。

    面试思路:根据问题的数据规模选择合适的排序算法。

    并查集

    并查集是一种树型的数据结构,用于处理一些不交集的合并及查询问题

    面试思路:识别问题是否涉及组团、配对或网络连通性等。

    分治算法

    分治算法是一种处理问题的策略,通过将大问题分解为小问题逐个击破

    面试思路:识别问题是否可以分解为独立子问题,考虑如何分、如何治。

    位运算

    位运算包含与、或、非、异或等操作,能高效处理整数的二进制表示。

    面试思路:识别问题是否涉及到整数的二进制形式,考虑是否可以通过位运算简化计算。




    转载本站文章《算法与数据结构面试通关经验总结:leetCode刷题经验》,
    请注明出处:https://www.zhoulujun.cn/html/theory/algorithm/leetcode/8501.html