Clover装El Capitan已经很好用了 - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>Apple - 家有苹果

Clover装El Capitan已经很好用了

Clover装El Capitan已经很好用了# Apple - 家有苹果

C*42015-09-17 07:09

1 楼

博士acta有好几篇，课题比较新。国内数IF，好像不好找教职。

d*w2015-09-17 07:09

2 楼

You are given an unsorted array A of n elements, now construct an array B
for which
B[i] = A[j] where j is the least number such that A[j] > A[i] and j>i
if such a j does not exist B[i] = -1
Eg:
A={1,3,5,7,6,4,8}
B = {3 5 7 8 8 8 -1}

g*i2015-09-17 07:09

3 楼

一直用Unibeast，现在才发现Clover真是领先一代。Trick就是研究下用哪些EFI
driver.
用了一年Yosemite， Xeon四核依然卡。
10.11流畅的像10.8，10.9的样子。

I*W2015-09-17 07:09

4 楼

学校，导师，获奖？？，这些都很重要。

s*l2015-09-17 07:09

5 楼

void next_record(int* a, int* b, int n)
{
/* assert(n>0); */
int i,j,k=0;
int m = a[0];
for (i=1;iif (a[i]>m){
m = a[i];
for (j=k;jk = j;
}
}
// for (j=k;jb[k] = -1;
if (k==n-1) return;
next_record(a+k+1,b+k+1,n-k-1);
}

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

: You are given an unsorted array A of n elements, now construct an array B
: for which
: B[i] = A[j] where j is the least number such that A[j] > A[i] and j>i
: if such a j does not exist B[i] = -1
: Eg:
: A={1,3,5,7,6,4,8}
: B = {3 5 7 8 8 8 -1}

C*42015-09-17 07:09

6 楼

upenn,导师David J Srolovitz，在国家实验室做有名字的博后。

l*g2015-09-17 07:09

7 楼

你程序里的m不能这么用。问题里的example你的code刚好可以适用，但下面的case就不
行了
{1, 2, 10, 3, 4, 5}
你算出的结果是：{ 2, 10, -1, -1, -1, -1}
但实际应该是：{ 2, 10, -1, 4, 5, -1}
为你修改一下：
void next_record(int *a, int *b, int len)
{
// skip some boundary checks here
int k = 0;
b[len-1] = -1;

for (int i = 0; i < len-1; i++)
{
if (a[i] < a[k])
{
b[i] = a[k];
}
else
{
bool found = false;
for (int j = i+1; j < len; j++)
{
if (a[j] > a[i])
{
b[i] = a[j];
found = true;
k = j;
break;
}
}
if (!found)
{
b[i] = -1;
k = i+1;
}
}
}
return;
}

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

:
: void next_record(int* a, int* b, int n)
: {
: /* assert(n>0); */
: int i,j,k=0;
: int m = a[0];
: for (i=1;i: if (a[i]>m){
: m = a[i];
: for (j=k;j

I*W2015-09-17 07:09

8 楼

upenn和uiuc差不多级别的了，没啥大区别。打听一下哪个老板对学生支持就去哪个。
，

s*h2015-09-17 07:09

9 楼

What if
A = [5,3,4,6]

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

: 你程序里的m不能这么用。问题里的example你的code刚好可以适用，但下面的case就不
: 行了
: {1, 2, 10, 3, 4, 5}
: 你算出的结果是：{ 2, 10, -1, -1, -1, -1}
: 但实际应该是：{ 2, 10, -1, 4, 5, -1}
: 为你修改一下：
: void next_record(int *a, int *b, int len)
: {
: // skip some boundary checks here
: int k = 0;

C*42015-09-17 07:09

10 楼

uiuc的话应该是做理论/计算生物物理，教职是不是多一点？

c*n2015-09-17 07:09

11 楼

什么破公司的题啊, 这题可真难看懂.

B

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

h*02015-09-17 07:09

12 楼

如果你自己没有特殊喜好，理论/计算生物物理未来应该更好。

【在 C****4 的大作中提到】

: uiuc的话应该是做理论/计算生物物理，教职是不是多一点？

s*l2015-09-17 07:09

13 楼

谢谢发现这个问题,我错误地把题目理解成找下一个比所有当前元素都大的record(纪录
), 所以函数也取名为next_record.
现在把最后一句
从
for (j=k;j改成
b[k] = -1;
if (k==n-1) return;
next_record(a+k+1,b+k+1,n-k-1);

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

C*42015-09-17 07:09

14 楼

我本科是纯理论/计算凝聚态物理背景的，没什么偏好。理论/计算生物物理是不是比纳
米材料计算也要好一点？

i*d2015-09-17 07:09

15 楼

有点类似max rectangle in histogram
只不过这个是找后面第一个比自己大的
可以O(n)
假设C[i] = min{ j | A[j]>A[i] && j > i}
C[n-1] = -1
for i <= n-2 ~ 0:
j = i+1;
while (j!=-1 && A[j]<=A[i])
j = C[j]
C[i] = j
就是处理到A[i]的时候，先看A[i+1]，符合最好，不符合的话说明A[i+1] <= A[i]
那下一个满足要求的肯定至少是C[i+1]
最后根据C转存到A就可以了

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

h*02015-09-17 07:09

16 楼

这是我的感觉。生物物理是未来的重要方向，纳米做的比较烂。

【在 C****4 的大作中提到】

: 我本科是纯理论/计算凝聚态物理背景的，没什么偏好。理论/计算生物物理是不是比纳
: 米材料计算也要好一点？

f*g2015-09-17 07:09

17 楼

不是应该是
B = { 6, 4, 6, -1}？

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

: What if
: A = [5,3,4,6]

t*r2015-09-17 07:09

18 楼

好奇问一嘴，Srolovitz的学生，还在国家实验室，难道你在LANL？
Director fellow?

f*g2015-09-17 07:09

19 楼

2 cents：
从最后一个开始scan。
并用一个stack维持一个有序递增数列。
O(n)。
有待验证

D*12015-09-17 07:09

20 楼

都给了这个多信息了随便一Google也能查实了
别为难楼主了

【在 t*********r 的大作中提到】

: 好奇问一嘴，Srolovitz的学生，还在国家实验室，难道你在LANL？
: Director fellow?

g*s2015-09-17 07:09

21 楼

good observation to associate it with max rect in hist.

【在 i****d 的大作中提到】

: 有点类似max rectangle in histogram
: 只不过这个是找后面第一个比自己大的
: 可以O(n)
: 假设C[i] = min{ j | A[j]>A[i] && j > i}
: C[n-1] = -1
: for i <= n-2 ~ 0:
: j = i+1;
: while (j!=-1 && A[j]<=A[i])
: j = C[j]
: C[i] = j

e*52015-09-17 07:09

22 楼

LANL出去不太好找但是如果能申请到0.5M一般就能留下，就是挣了钱没地方花

【在 t*********r 的大作中提到】

: 好奇问一嘴，Srolovitz的学生，还在国家实验室，难道你在LANL？
: Director fellow?

l*a2015-09-17 07:09

23 楼

一开始没往O(n)的算法想。
还欠火候。

C*42015-09-17 07:09

24 楼

地方太差，可能还是想去caltech之类做博后

【在 e*******5 的大作中提到】

: LANL出去不太好找但是如果能申请到0.5M一般就能留下，就是挣了钱没地方花

l*g2015-09-17 07:09

25 楼

是的，我错了，光顾着抓前面spellscroll的bug了
下面的optimization是不对的
if (a[i] < a[k])
{
b[i] = a[k];
}
看来spellscroll修改后的程序也还是不对

【在 f***g 的大作中提到】

: 不是应该是
: B = { 6, 4, 6, -1}？

t*r2015-09-17 07:09

26 楼

还好吧基本上找的都能找到。
LANL就算能留下，长久看想活下来也不易，都是Programmatically funded，说没就没
。。。（可能有点悲观了）

【在 e*******5 的大作中提到】

: LANL出去不太好找但是如果能申请到0.5M一般就能留下，就是挣了钱没地方花

l*g2015-09-17 07:09

27 楼

赞，这个是正解
有个小bug, while loop应该改成这样
while(a[j] <= a[j])
{
j = C[j];
if (j == -1)
break;
}

【在 i****d 的大作中提到】

e*52015-09-17 07:09

28 楼

是啊，见到没钱了的PI去别的组蹭钱打杂好惨啊。还有变态的审查，装个电脑都能把荷
枪实弹的的军警招来

【在 t*********r 的大作中提到】

: 还好吧基本上找的都能找到。
: LANL就算能留下，长久看想活下来也不易，都是Programmatically funded，说没就没
: 。。。（可能有点悲观了）

s*l2015-09-17 07:09

29 楼

嗯,想起来,以前看过这道题的
http://discuss.joelonsoftware.com/default.asp?interview.11.8033

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

: 赞，这个是正解
: 有个小bug, while loop应该改成这样
: while(a[j] <= a[j])
: {
: j = C[j];
: if (j == -1)
: break;
: }

t*d2015-09-17 07:09

30 楼

what is the bug? I can't see the difference.
also, how's the runtime turn out to be n? isn't the worst time still n^2
because of the while loop? average time nLgn ?

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

: 赞，这个是正解
: 有个小bug, while loop应该改成这样
: while(a[j] <= a[j])
: {
: j = C[j];
: if (j == -1)
: break;
: }

t*d2015-09-17 07:09

31 楼

can you prove it's O(n)?

g*s2015-09-17 07:09

32 楼

ohh. b[n] can be used as stack.
So, loop twice, it can be solved in O(n) with O(1) extra space.

l*l2015-09-17 07:09

33 楼

void nextLarger(int a[],int b[],int n)
{
stack st;
st.push(0);
for (int i=1;i{
while (!st.empty() && a[i]> a[st.top()])
{
b[st.top()] = i;
st.pop();
}
st.push(i);
}
while (!st.empty())
{
b[st.top()] = -1;
st.pop();
}
}

g*s2015-09-17 07:09

34 楼

this one need extra O(n) space. But in fact, it can be polished to use b[]
as the stack at the same time.
So, it can be solved in O(n) by extra O(1) space.

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

: void nextLarger(int a[],int b[],int n)
: {
: stack st;
: st.push(0);
: for (int i=1;i: {
: while (!st.empty() && a[i]> a[st.top()])
: {
: b[st.top()] = i;
: st.pop();