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

【本期题目】
1、生成窗口最大值数组
有一个整型数组arr和一个大小为w的窗口从数组的最左边滑到最右边,窗口每次向右边滑一个位置。
例如,数组为[4,3,5,4,3,3,6,7],窗口大小为3时:

[4 3 5] 4 3 3 6 7 窗口中最大值为5
4 [3 5 4] 3 3 6 7 窗口中最大值为5
4 3 [5 4 3] 3 6 7 窗口中最大值为5
4 3 5 [4 3 3] 6 7 窗口中最大值为4
4 3 5 4 [3 3 6] 7 窗口中最大值为6
4 3 5 4 3 [3 6 7] 窗口中最大值为7

如果数组长度为n,窗口大小为w,则一***生n-w+1个窗口的最大值。请实现一个函数,给定一个数组arr,窗口大小w。返回一个长度为n-w+1的数组res,res[i]表示每一种窗口状态下的最大值。以本题为例,结果应该返回[5,5,5,4,6,7]。


2、最大值减去最小值小于或等于num的子数组数量
给定数组arr和整数num,返回有多少个子数组满足如下情况:
max(arr[i..j]) - min(arr[i..j]) <= num
max(arr[i..j])表示子数组arr[i..j]中的最大值,min(arr[i..j])表示子数组arr[i..j]中的最小值。如果数组长度为 N,请实现时间复杂度为 O(N)的解法。


3、复制含有随机指针节点的链表
一种特殊的链表节点类描述如下:
class Node {
public int value;
public Node next;
public Node rand;
public Node(int data) {
this.value = data;
}
Node类中的value是节点值,next指针和正常单链表中next指针的意义一样,都指向下一个节点,rand指针是Node类中新增的指针,这个指针可能指向链表中的任意一个节点,也可能指向null。给定一个由Node节点类型组成的无环单链表的头节点 head,请实现一个函数完成这个链表中所有结构的复制,并返回复制的新链表的头节点。要求除了需要返回的东西外,不再使用额外的数据结构并且在时间复杂度为 O(N)内完成原问题要实现的函数。



4、一种怪异的节点删除方式
链表节点值类型为int型,给定一个链表中的节点node,但不给定整个链表的头节点,如何在链表中删除node?请实现这个函数,并分析这么会出现哪些问题。要求时间复杂度为O(1)。



5、设计可以变更的缓存结构
【题目】
设计一种缓存结构,该结构在构造时确定大小,假设大小为 K,并有两个功能:
1,set(key,value):将记录(key,value)插入该结构。
2,get(key):返回key对应的value值。
【要求】
1,set和get方法的时间复杂度为O(1)。
2,某个key的set或get操作一旦发生,认为这个 key 的记录成了最经常使用的。 
3,当缓存的大小超过K时,移除最不经常使用的记录,即set或get最久远的。
【举例】
假设缓存结构的实例是***,大小为3,并依次发生如下行为:
1,***.set("A",1)。最经常使用的记录为("A",1)。 
2,***.set("B",2)。最经常使用的记录为(“B”,2),(“A”,1)变为最不经常的。
3,***.set("C",3)。最经常使用的记录为(“C”,2),(“A”,1)还是最不经常的。 
4,***.get("A")。最经常使用的记录为(“A”,1),(“B”,2)变为最不经常的。 
5,***.set("D",4)。大小超过了 3,所以移除此时最不经常使用的记录(“B”,2),加入记录(“D”,4),并且为最经常使用的记录,然后("C",2)变为最不经常使用的记录。

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

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

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

【本期答案领取地址】

加入牛客讨论5群(272820159)
群资料中文件:2015-08-26讲座题目

全部评论
最后一题,不明白为什么要双向链表啊
点赞 回复
分享
发布于 2015-08-28 22:49
怎么看代码啊
点赞 回复
分享
发布于 2015-09-02 22:03
小红书
校招火热招聘中
官网直投
我怎么加不进去260877110群??验证信息要输入什么呢?
点赞 回复
分享
发布于 2015-09-03 21:22
public static int getNum(int[] arr, int num) {   if (arr == null || arr.length == 0) {    return 0;   }   LinkedList<Integer> qmin = new LinkedList<Integer>();   LinkedList<Integer> qmax = new LinkedList<Integer>();   int i = 0;   int j = 0;   int res = 0;   while (i < arr.length) {    while (j < arr.length) {     while (!qmin.isEmpty() && arr[qmin.peekLast()] >= arr[j]) {      qmin.pollLast();     }     qmin.addLast(j);     while (!qmax.isEmpty() && arr[qmax.peekLast()] <= arr[j]) {      qmax.pollLast();     }     qmax.addLast(j);     if (arr[qmax.getFirst()] - arr[qmin.getFirst()] > num) {      break;     }     j++;    }    if (qmin.peekFirst() == i) {     qmin.pollFirst();    }    if (qmax.peekFirst() == i) {     qmax.pollFirst();    }    res += j - i;    i++;   }   return res;  } 这种代码怎么想得到= =
点赞 回复
分享
发布于 2015-09-09 16:29
11111111111111111111111166666666666
点赞 回复
分享
发布于 2015-09-19 08:43
视频现在下载不了?
点赞 回复
分享
发布于 2015-10-04 11:40

相关推荐

点赞 评论 收藏
转发
点赞 收藏 评论
分享
牛客网
牛客企业服务