专栏首页代码随想录这五道数组相关的面试题,你一定要会!

这五道数组相关的面试题,你一定要会!

在算法面试中,数组是必考的基础数据结构 其实数据的题目在思想上一般比较简单的,一想就是这么一回事

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

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

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

第一道:搜索插入位置

leetcode 编号35

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

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

暴力解法时间复杂度:O(n) 二分法时间复杂度:O(logn)

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

第二道:移除元素

leetcode 编号27

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

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

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

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

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

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

第三道:赎金信

leetcode 编号383

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

  • 第一点“为了不暴露赎金信字迹,要从杂志上搜索各个需要的字母,组成单词来表达意思” 这里说明杂志里面的字母不可重复使用。
  • 第二点 “你可以假设两个字符串均只含有小写字母。” 说明只有小写字母,这一点很重要

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

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

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

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

leetcode 编号209

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

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

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

第五道:螺旋矩阵

leetcode 编号59

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

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

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

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

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

总结

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

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

本文分享自微信公众号 - 代码随想录(code_thinking),作者:代码随想录

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

原始发表时间:2020-06-01

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 数组:总结篇

    数组是非常基础的数据结构,在面试中,考察数组的题目一般在思维上都不难,主要是考察对代码的掌控能力

    代码随想录
  • 程序员算法面试中,必须掌握的数组理论知识

    数组是非常基础的数据结构,在面试中,考察数组的题目一般在思维上都不难,主要是考察对代码的掌控能力

    代码随想录
  • 本周小结!(算法性能分析系列一)

    本周有点特殊,有点家事非常忙,没有时间更新算法题目,所以把很久之前写过的文章翻了出来,更新了部分内容,重新排个版(因为之前的排版真的有点难看)。

    代码随想录
  • 2020年第十届C/C++ B组第二场蓝桥杯省赛真题

    题目描述 小蓝要为一条街的住户制作门牌号。这条街一共有2020位住户,门牌号从1到2020编号。小蓝制作门牌的方法是先制作0到9这几个数字字符,最后根据需要将...

    小二哥
  • 一道关于组合的js算法题目

    有一个数组,如果有3个值:[3,2,6]。交叉组合后返回:3-2,3-6,2-6,3-2-6

    挥刀北上
  • 1000道Python题库系列分享十(37道)

    上一期题目链接:1000道Python题库系列分享九(31道) 上一期题目答案: ? 本期题目: ?

    Python小屋屋主
  • CVE-2020-35616 POC Joomla ACL安全漏洞

    Joomla是继WordPress和Shopify之后的第三大免费开源内容管理系统(CMS)。它是用来建立网站和发布网络内容的。其用户友好的格式...

    Aran
  • 500强榜单发布,通信行业全面衰退,5G能力挽狂澜吗?

    7月10日晚,《财富》正式发布中国500强企业排行榜,对过去一年中国上市企业取得的业绩和成就进行了总结——上榜的500家上市公司的总营业收入达到45.5万亿元人...

    悲了伤的白犀牛
  • 你还没学会CAN通信波特率的设置?

    记得最早是在15年就给大家推送过关于CAN通信波特率的设置,当时是以NXP的kinetis系列之KV46为例子来给大家介绍的,最近推送了几篇有关CAN通信的文章...

    用户1605515
  • 1000道Python题库系列分享十一(9道)

    Python小屋屋主

扫码关注云+社区

领取腾讯云代金券