面试考的是数组以及链表，要是弄不明白这些基础内容，那么在笔试环节就会直接被筛选淘汰掉。我见识过好多人在反转数组、去重这类题目上受阻，根本并非是因为题目难度大，而是对于内存存储方式缺乏概念。
数组：连续内存的优与劣
在内存里，数组会将所有的元素放置于连续一排的内存格子当中，这会带来一个极为巨大的优势，那就是你能够知晓第100个元素所在的位置，然后直接走过去把它拿取，所花费的时间永远都是O(1)，在Java里面的ArrayList，以及Python的list，它们的底层都是依靠数组来实现的，其访问速度快得令人惊叹。
可付出的代价也是显著明晰的。在2019年的时间段之内，我为一家从事电商业务的公司开展排查订单系统运行缓慢问题的工作，经仔细查看后发觉，他们在数组中间进行数据插入操作的频率相当之高。每一次进行插入动作的时候，后续的上千单订单均需向后挪动位置，致使服务器的CPU标识直接呈现飙红的状态。数组一旦被创建完成，其长度便固定下来，要是想要实现扩容，那就只能重新开辟新的路径，将老的数据全部复制过去。
面试必考的四类数组题
第一类是查找缺失值以及重复值，举例来说，倘若给你一个从1至100的数组，其中少了一个数字，那么怎样能够快速地将其找出来呢？最笨拙的方法是运用两层循环，然而更优的解决办法是采用求和公式，又或者构建一个布尔数组来进行标记，微软在2022年校招时就出过这样的原题，要求时间复杂度为O(n)、空间为O(1)。
第二类是排序以及搜索，快速排序、归并排序、二分查找，这些算法全都依赖数组的随机访问特性，亚马逊面试官曾经问我，无序数组找最大最小值，不使用循环该如何去做，实际上考的是分治思想，把数组拆分成对，两两进行比较。
数组增删操作的硬伤
有一位从事账务系统领域的友人曾遭遇过困境：用户的账单是以按照时间先后顺序存储于数组之中的，在某一日，用户删除了位于中间位置的一笔记录，他们采取的做法是直接将后边的数据进行整体向前移动的操作。随着时间的不断推移与积累，这样的操作占据了系统百分之三十的开销。之后经过更改，采用标记删除的方式，并且定时进行批量清理，才最终得以解决。
数组之中将重复项给删除同样是一道出现频率较高的题目。力扣的第26道题目所给出的即为标准的解决办法：采用双指针，其中有一个指针指向的是当前不存在重复情况的位置，另一个指针则朝着后面进行扫描。有不少新手会直接使用集合Set来处理，而面试官往往会进一步追问：若不借助额外的空间该要如何去实现呢？实际上它本质上就是借助数组自身所具备的覆盖写入特性来达成的。
链表：散落各处的节点
链表犹如一列火车，每节车厢（节点）仅晓得自身以及下一节的位置。在2015年时，我着手开发一个内存数据库，该数据库记录需要频繁地进行增添与删除操作，数组难以承受这样的操作负荷，故而换成双键链表，插入效率提高了几十倍。然而其代价则是，要查找某个节点必须从车头开始逐一计数，平均时间复杂度为O(n)。
在实际的业务情形当中，Java的LinkedList以及Redis的列表均采用链表来实现。然而，它存在着一些问题：每一个节点都需要额外存储指针，这使得内存占用相较于数组而言更大。要是你的数据量为几千个，并且很少进行增加或者删除操作，那么数组是完全能够满足需求的。
链表题的递归思维
用于反转的链表属于经典里的经典，迭代的写法需要维护三个指针，递归的写法更为简洁，其做法是把head.next之后的链表先行反转，然后把head挂在末尾，谷歌的面试官称，这道题目80%的人能够写出迭代的形式，但仅有30%的人能够清晰地写出递归的形式。
探寻中间节点借助快慢指针，一个每次行进两步，另一个每次只走一步。检测环同样依据这样的思路，如同中学物理里的追及问题那般。有一位前往字节跳动的读者进行分享，面试官要求他证实快慢指针必定能够在环内相遇，这便考到了数学推导方面的内容了。
字符串：特殊的字符数组
字符所构成的数组便是字符串，因而数组的全部套路皆能够运用上。然而字符串通常更为长，并且在Java、Python之中字符串是不可变的，每一次进行修改均会生成新对象。在2021年的时候我对一个日志解析程序有所优化，采用StringBuilder来替代String进行拼接，处理的时间从5秒减少到了0.3秒。
采用递归方式对字符串进行反转显得极为优雅迷人：首先依靠substring(1)来实施反转操作，随后再添加上第一个字符。若要统计字符出现的次数，可借助哈希表来达成，或者在字符范围受限的情形下，直接运用数组进行计数。而判断循环移位，其本质实际上就是在字符串拼接之后，查看是否包含相应子串。
树：非线性的数据世界
以树状形态所呈现的结构，乃是更加贴近真实世界的一种存在：公司的组织架构以及商品的分类形式，它们皆属于树的范畴。二叉树在各类考查当中出现的频率是最为高的，这是由于其既能够借助数组来进行存储（堆排序所运用的便是此种方式），同时也能够利用链表进行存储。在2018年的时候，我参与了eBay公司的面试，其中有手写二叉树层序遍历的要求，并且要输出每一层的平均值，而这一过程实际上就是广度优先搜索。
二叉树题目无法避免面临三种遍历情况，若是采用递归的方式来实现，仅仅需要三行代码，然而倘若使用非递归的方式，那就必须得手动去维护栈。众多候选人在编写非递归中序遍历时难以通过指针回溯这一关，实际上这就是在模拟递归函数栈帧的压栈以及出栈的整个过程。
算法基础题别丢分
在排序算法这个范畴之中，快速排序是考查频率最为高的，其关键要点并非体现在代码方面，而是在于分区函数的书写方式。桶排序以及计数排序适用于数据范围存在限定的情景，就像是高考成绩进行排序这种情况。另外还有一道堪称经典的题目：不借助临时变量来实现两个整数的交换操作，采用加减法或者异或的方式。异或这种方式效率较高并且不会出现溢出状况，在Linux内核源码里面就存在这样的运用方式。
你来写代码之际，是优先去考虑访问快速径直采用数组，还是为了能增添删去更为方便从而选择链表呢？于留言区域去聊聊你所踏过的坑，点赞数量高的友人我会通过私信发送一份自身整理的《LeetCode热题100最优解笔记》。
Comments NOTHING