国内用645D的人海去了 - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>PhotoGear - 摄影器材

国内用645D的人海去了

国内用645D的人海去了# PhotoGear - 摄影器材

C*U2010-07-20 07:07

1 楼

给定两个strings x和y,以及一个值t，需要判断这两个strings的edit distance是否大
于t
O(t*n)时间 O(t)空间算法

w*u2010-07-20 07:07

2 楼

The following inquiries have been added and removed since your last score
update on May 19, 2014:
Lender: Industry: Inquiry Date: Status:
1. SYNCB/BANREP National Credit Cards/Airlines Nov 23, 2012
Added
2. GECRB/BANREP National Credit Cards/Airlines Nov 23, 2012
Removed
请问为啥一个12年添加的Hard Pull在最近冒出来了。。。而且还在当天取消了，有人
遇到过这种情况么

f*x2010-07-20 07:07

3 楼

长草这个，有没有用过的MM？可惜没有一直到大腿。
不会贴图 :(
http://www.jpmon.com/jp5/prod_detail.asp?pid=WLM01-567254&src=e_jpmon_np_100423

g*g2010-07-20 07:07

4 楼

sigh

C*U2010-07-20 07:07

5 楼

int checkEditDistanceFast(const char *pattern, int pLen, const char* text,
int tLen, int editD) {
//if the edit distance is larger than the length difference, then return
false
if(editD < abs(pLen - tLen)) {
return MAX;
}
else {
//compute the number of diagonals requiring consideration
int p = (editD - abs(pLen - tLen)) / 2;
int t = tLen >= pLen ? -p : tLen - pLen - p;
int s = t + 1;
int len = abs(pLen - tLen) + 2 * p + 1;
//initialize the row
int *row = new int[len];
for(int k = 0; k < len; k++) {
row[k] = ((k + t < 0 || k + t > tLen) ? MAX : k + t);
}
//compute row by row
for(int i = 1; i <= pLen; i++) {
bool flag = true;
for(int j = 0; j < len; j++) {
if(j + s < 0 || j + s > tLen) {
row[j] = MAX;
}
else if(j + s == 0) {
int l, u;
l = j - 1 < 0 ? MAX : (row[j - 1] + 1);
u = j + 1 >= len ? MAX : (row[j + 1] + 1);
row[j] = u < l ? u : l;
}
else {
int d, l, u;
d = row[j] + (pattern[i - 1] == text[j + s - 1] ? 0 : 1);
l = j - 1 < 0 ? MAX : (row[j - 1] + 1);
u = j + 1 >= len ? MAX : (row[j + 1] + 1);
row[j] = d < l ? d : l;
row[j] = row[j] < u ? row[j] : u;
}

flag = flag && (row[j] > editD);
}
if(flag)
return MAX;
s++;
}
//get the edit distance
int result = row[abs(pLen - tLen) + 2 * p + t];
delete[] row;
//check edit distance
return result <= editD ? result : MAX;
}
}

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

: 给定两个strings x和y,以及一个值t，需要判断这两个strings的edit distance是否大
: 于t
: O(t*n)时间 O(t)空间算法

t*r2010-07-20 07:07

6 楼

感觉是pull的公司改名了？

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

: The following inquiries have been added and removed since your last score
: update on May 19, 2014:
: Lender: Industry: Inquiry Date: Status:
: 1. SYNCB/BANREP National Credit Cards/Airlines Nov 23, 2012
: Added
: 2. GECRB/BANREP National Credit Cards/Airlines Nov 23, 2012
: Removed
: 请问为啥一个12年添加的Hard Pull在最近冒出来了。。。而且还在当天取消了，有人
: 遇到过这种情况么

r*a2010-07-20 07:07

7 楼

就看见两台

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

: sigh

B*12010-07-20 07:07

8 楼

原题在哪里啊？
看你的这个描述看得不是很清晰。

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

: 给定两个strings x和y,以及一个值t，需要判断这两个strings的edit distance是否大
: 于t
: O(t*n)时间 O(t)空间算法

y*i2010-07-20 07:07

9 楼

you have a Banana Republic (BANREP) visa credit card
GECRB = GE Capital Retail Bank
SYNCB = Synchrony Financial
http://www.bloomberg.com/news/2014-03-13/ge-registers-to-file-i
I don't think this impacts your score

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

x52010-07-20 07:07

10 楼

哪有7台？怎么还有个ipad?

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

: sigh

C*U2010-07-20 07:07

11 楼

给你两个string x和y，我们可以算他们的edit distance。这个leetcode上面好像有吧
？用DP就算出来他们的edit distance是多少。但是这个算法是O(n^2)的。现在我不用
你算具体的edit distance。我告诉你一个正整数t。让你判断这两个edit distance是
不是小于等于t。我们当然可以用DP算法来做算出edit distance是多少。但是现在有更
好的算法，当t小的时候。

【在 B*******1 的大作中提到】

: 原题在哪里啊？
: 看你的这个描述看得不是很清晰。

w*u2010-07-20 07:07

12 楼

原来是这样！学习了。。。。

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

: 感觉是pull的公司改名了？

S*M2010-07-20 07:07

13 楼

什么镜头啊，畸变好厉害

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

: sigh

f*e2010-07-20 07:07

14 楼

仍然用DP做：
好像是一个n by n的表，不用每个entry都算出来，只算t对角阵（t-diagnal），因为每
个元素只能用到另一个数组元素里面的2t个元素，比如A数组的长度为L1，B数组的长度
为L2，则A数组的ith元素x，只能用到B数组的[L2-(L1-i+1)-t,L2-(L1-i+1)+t]th元素。
如果超过这个范围，他右边的edit distance铁定超过t了。
所以...

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

: 给你两个string x和y，我们可以算他们的edit distance。这个leetcode上面好像有吧
: ？用DP就算出来他们的edit distance是多少。但是这个算法是O(n^2)的。现在我不用
: 你算具体的edit distance。我告诉你一个正整数t。让你判断这两个edit distance是
: 不是小于等于t。我们当然可以用DP算法来做算出edit distance是多少。但是现在有更
: 好的算法，当t小的时候。

w*u2010-07-20 07:07

15 楼

Yes, first application of cc. The staff told me it is a kind of club card...
but it is a credit card. I hate her.
Thank you!

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

: you have a Banana Republic (BANREP) visa credit card
: GECRB = GE Capital Retail Bank
: SYNCB = Synchrony Financial
: http://www.bloomberg.com/news/2014-03-13/ge-registers-to-file-i
: I don't think this impacts your score

p*n2010-07-20 07:07

16 楼

边上那俩是自然歪嘴吧

【在 S*M 的大作中提到】

: 什么镜头啊，畸变好厉害

C*U2010-07-20 07:07

17 楼

对
我的code基本上就是这个意思
你帮我看看有什么地方可以优化的
：）

为每
素。

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

: 仍然用DP做：
: 好像是一个n by n的表，不用每个entry都算出来，只算t对角阵（t-diagnal），因为每
: 个元素只能用到另一个数组元素里面的2t个元素，比如A数组的长度为L1，B数组的长度
: 为L2，则A数组的ith元素x，只能用到B数组的[L2-(L1-i+1)-t,L2-(L1-i+1)+t]th元素。
: 如果超过这个范围，他右边的edit distance铁定超过t了。
: 所以...

c*t2010-07-20 07:07

18 楼

你还在做题啊？你是已经接受G offer了吗？还是要面F?

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

: 给定两个strings x和y,以及一个值t，需要判断这两个strings的edit distance是否大
: 于t
: O(t*n)时间 O(t)空间算法

C*U2010-07-20 07:07

19 楼

接了offer了。不过f会给我面试就是了

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

: 你还在做题啊？你是已经接受G offer了吗？还是要面F?

c*t2010-07-20 07:07

20 楼

加油，等待你的面经！

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

: 接了offer了。不过f会给我面试就是了