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

给定一个数组arr，该数组无序，但每个值均为正数，再给定一个正数k。求arr的所有子数组中所有元素相加和为k的最长子数组长度。例如，arr=[1,2,1,1,1]，k=3。累加和为3的最长子数组为[1,1,1]，所以结果返回3。

要求：时间复杂度O(N)，额外空间复杂度O(1)。

给定一个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