五道数组相关的面试题 6月30日【今日算法】

在算法面试中，数组是必考的基础数据结构

其实数据的题目在思想上一般比较简单的，一想就是这么一回事

但是如果不熟练的话，用代码实现就不是那么回事了，难就难在代码实操上

这里呢 我从leetcode中给大家总结了五道数组相关的经典面试题目

每一道题目都代表一个类型，一个思想，如果没有做过的同学强烈建议抽空做一下

第一道：搜索插入位置

这道题目呢，考察的数据的基本操作，思路很简单，但是在通过率在简单题里并不高，不要轻敌

可以使用暴力解法，通过这道题目，如果要求更优的算法，建议试一试用二分法，来解决这道题目

暴力解法时间复杂度：O(n)

二分法时间复杂度：O(logn)

二分法是算法面试中的常考题，建议通过这道题目，锻炼自己手撕二分的能力。

第二道：移除元素

在这道题目中，我们只要理解数组在内存中的结构，就知道数据中的元素只能被覆盖掉，而能直接删掉

所以这里题目中说的移除元素，其实是覆盖掉某一个元素

那么暴力的解法，很简单，两层for循环，一个for循环遍历数组元素 ，第二个for循环更新数组

很明显暴力解法时间复杂度是O(n), 然后尝试一个更优解，快慢指针法，时间复杂度可以做到O(n)

快慢指针法是解决数据问题中常见操作，头一个接触这个算法 还是有点懵的，

建议通过这道题目了解一下快慢指针法

第三道：赎金信

这道题题意很清晰，就是用判断第一个字符串ransom能不能由第二个字符串magazines里面的字符构成，但是这里需要注意两点1.

第一点“为了不暴露赎金信字迹，要从杂志上搜索各个需要的字母，组成单词来表达意思” 这里说明杂志里面的字母不可重复使用。

第二点 “你可以假设两个字符串均只含有小写字母。” 说明只有小写字母，这一点很重要

因为题目只有小写字母，那我们可以采用空间换取时间的哈希策略(字典计数法)，

用一个长度为26的数组还记录magazine里字母出现的次数，然后再用ransomNote去验证这个数组是否包含了ransomNote所需要的所有字母。

建议通过这道题目，深入理解一下字典计数法的思想

第四道：长度最小的子数组

这道题目暴力是也可以的，时间复杂度为O(n^2)

其实也是通过一个快指针和慢指针来实现一个滑动窗口，最终得到长度最小的子数组，时间复杂度为O(n)

建议通过这道题目了解一下滑动窗口的思想

第五道：螺旋矩阵

这是一道模拟题，就是模拟螺旋矩阵

这道题绝对是面试中的常客，特别是笔试的时候

而且这道题很多同学就算做过，过一段时间，还是做这道题目 ，还是做不好。

解题的关键在于在循环遍历的时候需要定义好自己的循环不变量

这道题目是数组面试题中最常见的一个类型之一

总结

这五道题是数组中非常典型的题目

如果这几道题目还没有做过，还等啥，赶紧搞起啊！

来源 | 代码随想录

作者 | 代码随想录