请教，这是什么树，开得花很多，还很香 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>gardening - 拈花惹草

请教，这是什么树，开得花很多，还很香

请教，这是什么树，开得花很多，还很香# gardening - 拈花惹草

w*h2014-04-17 07:04

1 楼

老印
自我介绍；
Coding: Integer数组，先升序后降序，例如：1,3,5,9,15,10,9,7,5，找出最大元素；
设计Least Recently Used Cache；
什么是abstract class;
什么是singleton pattern, 如何实现；
什么是Model-View-Controller pattern.

e*t2014-04-17 07:04

2 楼

http://www.dealsofamerica.com/Bali-Aluminum-Blinds-on-Sale-from

r*e2014-04-17 07:04

3 楼

请教，这是什么树，开得花很多，还很香

s*n2014-04-17 07:04

4 楼

第一题，2分法查找
第二题，DoubleLinkedList + Hashtable

T*m2014-04-17 07:04

5 楼

很像一种pearlbush

p*22014-04-17 07:04

6 楼

第二题什么意思呀？

l*a2014-04-17 07:04

7 楼

假定你访问过一些item,设计数据结构使得每次新读入一个item，
你可以判断是否已经访问过，已经访问过的话，更新他的访问顺序
新则插入
只能保存一定数目的item,如果到上限了
删掉访问时间距离现在最久的

【在 p*****2 的大作中提到】

: 第二题什么意思呀？

m*q2014-04-17 07:04

8 楼

第一题大概是:
int find_max(int a[], int n)
{
ASSERT(n>0);
int i = 0, j = n-1;

while (i < j) {
int mid = i + (j - i + 1)/2;
if (mid == 0 || a[mid] >= a[mid-1])
i = mid;
else
j = mid-1;
}
return j;
}

【在 s******n 的大作中提到】

: 第一题，2分法查找
: 第二题，DoubleLinkedList + Hashtable

p*22014-04-17 07:04

9 楼

多谢。这样的话，用个数组代替双向链表应该也够用了。

【在 l*****a 的大作中提到】

: 假定你访问过一些item,设计数据结构使得每次新读入一个item，
: 你可以判断是否已经访问过，已经访问过的话，更新他的访问顺序
: 新则插入
: 只能保存一定数目的item,如果到上限了
: 删掉访问时间距离现在最久的

l*a2014-04-17 07:04

10 楼

数组的插入删除比较麻烦吧

【在 p*****2 的大作中提到】

:
: 多谢。这样的话，用个数组代替双向链表应该也够用了。

s*n2014-04-17 07:04

11 楼

看不懂if (mid==0 || ...)什么意思，这样是不是更清楚？
int find_max(int a[], int n)
{
ASSERT(n>0);
int i = 0, j = n-1;

while (i < j-1) {
int mid = (i + j)/2;
ASSERT(mid>i && midif (a[mid-1] < a[mid] && a[mid]i = mid;
} else if (a[mid-1] > a[mid] && a[mid]>a[mid+1]) {
j = mid;
} else if (a[mid-1] < a[mid] && a[mid]>a[mid+1]) {
return mid;
} else {
//如果a[mid]==a[mid-1], etc.则输入数据不对
return -1;
}
}
return -1;
}

【在 m**q 的大作中提到】

: 第一题大概是:
: int find_max(int a[], int n)
: {
: ASSERT(n>0);
: int i = 0, j = n-1;
:
: while (i < j) {
: int mid = i + (j - i + 1)/2;
: if (mid == 0 || a[mid] >= a[mid-1])
: i = mid;

p*22014-04-17 07:04

12 楼

可以simulate 双向链表。满了之后把新的element copy 到 last element, 然后改改
指针。

【在 l*****a 的大作中提到】

: 数组的插入删除比较麻烦吧

s*n2014-04-17 07:04

13 楼

有个小问题mid == 0 是多余的检查，因为0<=i这个效率比我前面写的那个高，跳过了不少validation

【在 m**q 的大作中提到】

: 第一题大概是:
: int find_max(int a[], int n)
: {
: ASSERT(n>0);
: int i = 0, j = n-1;
:
: while (i < j) {
: int mid = i + (j - i + 1)/2;
: if (mid == 0 || a[mid] >= a[mid-1])
: i = mid;

n*w2014-04-17 07:04

14 楼

还是选双向链表好。
有几个好处：
动态大小。空间紧张的时候特别需要这一点，用多少申请多少空间；
插入删除快；
配合hashtable，查找也快。

【在 p*****2 的大作中提到】

:
: 可以simulate 双向链表。满了之后把新的element copy 到 last element, 然后改改
: 指针。

p*22014-04-17 07:04

15 楼

看这个问题保存最近的element, 那应该空间不会太大吧？而且一般都处于满的状态吧
？（当然如果不是这样那用链表没话说）
插入删除的话，数组也可以一样是O(1）呀
用数组也要配合hashtable
数组有一个好处就是不用反复new和delete。heap 操作也是很耗时的。

【在 n*******w 的大作中提到】

: 还是选双向链表好。
: 有几个好处：
: 动态大小。空间紧张的时候特别需要这一点，用多少申请多少空间；
: 插入删除快；
: 配合hashtable，查找也快。

m*q2014-04-17 07:04

16 楼

我写完了看了看也觉得是多余的，但总觉得还是写上放心点;)

【在 s******n 的大作中提到】

: 有个小问题mid == 0 是多余的检查，因为0<=i: 这个效率比我前面写的那个高，跳过了不少validation

s*n2014-04-17 07:04

17 楼

双向表不需要反复new/delete，在置换的时候把新value复制到老value所在的
LinkListNode上。

【在 p*****2 的大作中提到】

:
: 看这个问题保存最近的element, 那应该空间不会太大吧？而且一般都处于满的状态吧
: ？（当然如果不是这样那用链表没话说）
: 插入删除的话，数组也可以一样是O(1）呀
: 用数组也要配合hashtable
: 数组有一个好处就是不用反复new和delete。heap 操作也是很耗时的。