首页 > 站内公告 > #牛客堂直播视频#常见面试题精讲(五)(9.9)

#牛客堂直播视频#常见面试题精讲(五)(9.9)

头像
管理员
编辑于 2015-10-15 16:03:54 APP内打开
赞 10 | 收藏 14 | 回复3 | 浏览17856
【本期题目】
题目一
给定一个数组arr,该数组无序,但每个值均为正数,再给定一个正数k。求arr的所有子数组中所有元素相加和为k的最长子数组长度。例如,arr=[1,2,1,1,1],k=3。累加和为3的最长子数组为[1,1,1],所以结果返回3。
要求:时间复杂度O(N),额外空间复杂度O(1)。

题目二
给定一个无序数组arr,其中元素可正、可负、可0,给定一个整数 k。求arr所有的子数组中累加和小于或等于k的最长子数组长度。例如:arr=[3,-2,-4,0,6],k=-2,相加和小于或等于-2的最长子数组为{3,-2,-4,0},所以结果返回4。

题目三
给定一个N*N的矩阵matrix,在这个矩阵中只有0和1两种值,返回边框全是1的最大正方形的边长长度。
例如:
01111
01001
01001
01111
01011
其中,边框全是1的最大正方形的大小为4*4,所以返回4。

题目四
给定一个整型矩阵matrix,其中的值只有0和1两种,求其中全是1的所有矩形区域中,最大的矩形区域为1的数量。
例如:
1110
其中,最大的矩形区域有 3 个 1,所以返回3。
再如:
1011
1111
1110
其中,最大的矩形区域有6个1,所以返回6。

题目五
有一个机器按自然数序列的方式吐出球(1 号球,2 号球,3 号球,......),你有一个袋子,袋子最多只能装下K个球,并且除袋子以外,你没有更多的空间。设计一种选择方式,使得当机器吐出第N号球的时候(N>K),你袋子中的球数是K个,同时可以保证从1号球到N号球中的每一个,被选进袋子的概率都是K/N。举一个更具体的例子。有一个只能装下10个球的袋子,当吐出100个球时,袋子里有10个球,并且1~100号中的每一个球被选中的概率都是10/100。然后继续吐球,当吐出1000个球时,袋子里有10个球,并且1~1000号中的每一个球被选中的概率都是10/1000。继续吐球,当吐出i个球时,袋子里有10个球,并且1~i号中的每一个球被选中的概率都是10/i,即吐球的同时,已经吐出的球被选中的概率也动态地变化。

【分享嘉宾介绍】
左程云
华中科技大学本科--计算机科学与技术专业、 芝加哥大学硕士--计算机科学专业
IBM软件工程师、 百度软件工程师、 刷题5年的算法热爱者
《程序员代码面试指南--IT名企算法与数据结构题目最优解》 作者,电子工业出版社7月底将出版发行,书籍涉及算法与数据结构编程题目240道以上,并且个人实现出最优解,大部分题目为面试高频题

【参与牛客堂直播】
每周三晚8:00~9:30,直播页面 http://www.nowcoder.com/live/courses

【直播题目讨论】
加入牛客3群260877110

【本期答案领取地址】

加入牛客讨论5群(272820159)
群资料中文件:2015-9-9讲座代码

3条回帖

回帖
加载中...
话题 回帖

近期精华帖

热门推荐