s******n
发帖数: 3946 | 1 abcdefexdcbajklkj
最长的palindromesubstring是jklkj，但是LCS最长的abcdefexdcba显然是更好的候选
者。 |
|
w***y
发帖数: 6251 | 2 在复习dynamic programming. 看到别人的一个list, 都是简写, 很多我都不知道是什
么问题. 麻烦大家帮我看一下吧. 我能猜到的我标了一下, 2-4, 6, 8-11 我都不知道
是什么问题?
1. BST optional BST??
2. COV
3. ILP
4. KS
5. LCS Longest Common Subsequences
6. LSP
7. MCM Matrix chain multiplication
8. ODP
9. SCP
10. SPA
11. SPC
12. TSP Travelling salesman problem |
|
l*********8
发帖数: 4642 | 3 1. BST Optimal Binary Search Tree Problem
2. COV Optimal Covering problem
3. ILP integer linear programming
4. KS Knapsack Problem
5. LCS Longest Common Subsequences
6. LSP Longest Simple path Problem
7. MCM Matrix chain multiplication
8. ODP Optimal Distribution Problem
9. SCP Stagecoach Problem
10. SPA Shortest Path in a Acyclic graph
11. SPC Shortest Path in a Cyclic graph
12. TSP Travelling salesman problem |
|
w****x
发帖数: 2483 | 4
说的不错.我想补充一下:
Iteration能完全代替recursion的只有tail recursion或用栈.
题目做多了很容易感觉出哪题需要用到DP,很多地方不一定要从公式推出.
DP不明显的问题上来说, 需要仔细观察你的解法中是不是有 "重复计算", 把"重复计算
"用数据结构存储最优子结构就可以了.
有的DP可以继续化简空间复杂度, 比如LCS可以把空间复杂度O(n^2)减少到O(n),因为第
n步的DP只 和前一步(第n-1步)的最优子结果有关, 从公式上也可以看出F(n)只和F(n-1
)有关. |
|
w****x
发帖数: 2483 | 5
说的不错.我想补充一下:
Iteration能完全代替recursion的只有tail recursion或用栈.
题目做多了很容易感觉出哪题需要用到DP,很多地方不一定要从公式推出.
DP不明显的问题上来说, 需要仔细观察你的解法中是不是有 "重复计算", 把"重复计算
"用数据结构存储最优子结构就可以了.
有的DP可以继续化简空间复杂度, 比如LCS可以把空间复杂度O(n^2)减少到O(n),因为第
n步的DP只 和前一步(第n-1步)的最优子结果有关, 从公式上也可以看出F(n)只和F(n-1
)有关. |
|
|
Z*****Z
发帖数: 723 | 7 对，能空间优化。
但是LCS，那个DP表里存的是A[i]和B[j]之间最长的CS，我还没想清楚在这个问题里那个
DP表长什么样 |
|
a*******3
发帖数: 27 | 8 第三题给个其他解法，说了查询字符串都较小，而且又是求subsequence，有个算法可
以将LCS转化成LIS来计算，转化方法在本题里面，是将短字符串中的每个字符，在T中
出现的位置，由大到小排列，然后求这个序列的LIS。
如
T=abacbdefb
a的位置有(0,2)，b的有(1,4,8),c(3),d(5),e(6),f(7)
S1 = aab =>(2,0,2,0,8,4,1),LIS=>(0,2,8)=3，故yes |
|
N*D
发帖数: 3641 | 9 题目不简单啊，LCS都出来了，要reconstruct subsequence么？
LRU cache是不是用DoubleLinkedHashMap就行了？需要写code么？
of |
|
g*******s
发帖数: 2963 | 10 这个就是传统的LCS简化把。
我问的关键是n个字符串同时比啊。。。。。
就是觉得建一个n维矩阵有点太慢了
string LongestCommonSubStr( vector strs ) |
|
|
I**********s
发帖数: 441 | 12 这些是我以前做研究时一个项目涉及到的常见的DP问题. 我为了资料全面起见加上了,
但多数不会见于面试.
BST Optimal Binary Search Tree Problem
COV Optimal Covering Problem
ILP Integer Linear Programming Problem
KS01 0/1 Knapsack Problem
LCS Longest Common Subsequence Problem
LSP Longest Simple Path Problem
MCM Matrix Chain Multiplication Problem
ODP Optimal Distribution Problem
RAP Production: Reject Allowances Problem
SCP Stagecoach Problem
SPA Shortest Path in an Acyclic Graph Problem
SPC Shortest Path in an Cyclic Graph Problem
TSP Traveling S... 阅读全帖 |
|
d*******n
发帖数: 124 | 13 我想找一个google search offline的工具，可以基于keyword search 我的document。
可是google desktop discontinue了，还有没有alternative呢。
P.S.不是类似document内部和eclipse内部的那种基于keyword或regexp的search，因为
那些都是hard match而不是soft match。 By soft match, I mean using LCS. |
|
w****k
发帖数: 755 | 14 将P和Q相同index的字符绑定，然后任意调整次序，这样得到的P‘和Q’应该和原来的
PQ调整次数相同。
于是把其中之一调整为增序，则把另一个调整为增序做bubble sort所需要的步数就是
所求。
但这里没考虑首尾互换的问题，这个思路可以启发一下大家么？我在想LIS或者LCS是否
可以考虑。 |
|
w****k
发帖数: 755 | 15 将P和Q相同index的字符绑定，然后任意调整次序，这样得到的P‘和Q’应该和原来的
PQ调整次数相同。
于是把其中之一调整为增序，则把另一个调整为增序做bubble sort所需要的步数就是
所求。
但这里没考虑首尾互换的问题，这个思路可以启发一下大家么？我在想LIS或者LCS是否
可以考虑。 |
|
d******g
发帖数: 38 | 16 等价于找等于T的并且在S中对应substring最短的LCS，不可能O(n)吧 |
|
l*********8
发帖数: 4642 | 17 han6大牛，好像有些问题。
以三维空间为例：
假如x,y坐标对应的数组分别如下：
1 2 3 4
3 2 4 1
1 2 4 3
答案应该是x坐标最小的第一个和第三个，但LCS无法求出该答案 -- 或者说我不知道怎
么得出答案：） |
|
m*****n
发帖数: 2152 | 18 说句实话，用后缀数组比dp什么的还好写，关键是可扩展。
要是比3个甚至n个string的LCS，DP立马完蛋了。
但是用后缀数组就可以很容易扩展了。 |
|
k***g
发帖数: 166 | 19 LCS是不错的想法，不过为了简化问题，我已经假设数组都是排了序的，直接两个指针
向前移动就行了吧？
主要是不太清楚怎样处理多个数组的情况
比如A,B,C,D,E,F... 我的想法是搞两个vector，一个存两个数组名字，比如A,B或者C,
F，另一个存相同元素数量。但这样复杂度是O(m^2) (m是数组数量)
还有更好的办法吗？ |
|
r****m
发帖数: 70 | 20 有朋友提到不知道怎么做DP的题目，分享一下自己的总结，希望对大家有帮助。
1. Distinct Subsequence (String S, String T)
F(i, j) = F(i-1, j) , S[i] != T[j]
F(i-1, j) + F(i-1, j-1) , S[i] ==T[j]
2. Longest Common Subsequence (String S1, String S2)
F(i, j) = F(i-1, j-1) + 1, S[i] == T[j]
Max{ F(i-1, j), F(i, j-1) }, S[i] !=T[j]
LCS可以把空间复杂度O(n^2)减少到O(n),因为第n步的DP只 和前一步(第n-1步)的
最优子结果有关 F(n) = F(n-1)
3. Edit Distance (String S1, String S2)
F(i, j) = Min { F... 阅读全帖 |
|
r****m
发帖数: 70 | 21 有朋友提到不知道怎么做DP的题目，分享一下自己的总结，希望对大家有帮助。
1. Distinct Subsequence (String S, String T)
F(i, j) = F(i-1, j) , S[i] != T[j]
F(i-1, j) + F(i-1, j-1) , S[i] ==T[j]
2. Longest Common Subsequence (String S1, String S2)
F(i, j) = F(i-1, j-1) + 1, S[i] == T[j]
Max{ F(i-1, j), F(i, j-1) }, S[i] !=T[j]
LCS可以把空间复杂度O(n^2)减少到O(n),因为第n步的DP只 和前一步(第n-1步)的
最优子结果有关 F(n) = F(n-1)
3. Edit Distance (String S1, String S2)
F(i, j) = Min { F... 阅读全帖 |
|
e********2
发帖数: 495 | 22 来自主题: JobHunting版 - F家题请教 我们学校的DP练习题：对所有线段的2个端点分别排序，然后找两个排好续的最大公共
子序列LCS. O(N^2) |
|
l******2
发帖数: 41 | 23 这题为啥要用LCS做，
和leetcode上这题基本一样吧？ |
|
w***y
发帖数: 6251 | 24 sorry 可能一开始没说清楚，我知道DP怎么做 longest common substring
这种是一个array of strings，longest common substring between two words in
the array， 除了两两组合找LCS，然后在这些结果里找longest，有什么比较巧妙的方
法么？ |
|
d*****c
发帖数: 605 | 25 为什么是prefix呢，LCS可以是两个string的中间段啊 |
|
w***y
发帖数: 6251 | 26 这是两个题目，一个是问的lcs, 一个是问的prefix |
|
f********y
发帖数: 156 | 27 空间不用 O(logn)
left 向上走，直到空， 这样得到left 的深度 d1； 同样得到 right 的深度 d2
假设 d1 > d2, left 先走 (d1- d2) 步， 然后 left & right 同步向上，遇到的node
就是 LCS |
|
r******d
发帖数: 137 | 28 我现在工作的银行有一个资深IT工程师的职位， 要求三年以上设计部署微软Office
Communication Server（LCS)和即时通讯（IM)系统经验。有兴趣的跟我联系。 |
|
r*****a
发帖数: 5 | 29 一家世界五百强贸易公司，位于得克萨斯州休斯顿，现诚聘会计人员，具体需求如下。
需求部门：财务部
岗位：全职会计
Job Responsibilities:
* Perform key verification role in daily cash management process, reviewing
all electronic payments for cash management classification and accounting
accuracy.
* Journal creation for bank account transactions.
* Perform bank reconciliations- reconciliation of the bank statement against
the GL and reconciliation of any assigned clearing accounts.
* Communicate with external banks on trade finance and financing issues.
*... 阅读全帖 |
|
r*****a
发帖数: 5 | 30 一家世界五百强贸易公司，位于得克萨斯州休斯顿，现诚聘会计人员，具体需求如下。
需求部门：财务部
岗位：全职会计
Job Responsibilities:
* Perform key verification role in daily cash management process, reviewing
all electronic payments for cash management classification and accounting
accuracy.
* Journal creation for bank account transactions.
* Perform bank reconciliations- reconciliation of the bank statement against
the GL and reconciliation of any assigned clearing accounts.
* Communicate with external banks on trade finance and financing issues.
*... 阅读全帖 |
|
r*****a
发帖数: 5 | 31 一家世界五百强贸易公司，位于得克萨斯州休斯顿，现诚聘会计人员，具体需求如下。
需求部门：财务部
岗位：全职会计
Job Responsibilities:
* Perform key verification role in daily cash management process, reviewing
all electronic payments for cash management classification and accounting
accuracy.
* Journal creation for bank account transactions.
* Perform bank reconciliations- reconciliation of the bank statement against
the GL and reconciliation of any assigned clearing accounts.
* Communicate with external banks on trade finance and financing issues.
*... 阅读全帖 |
|
r*****a
发帖数: 5 | 32 一家世界五百强贸易公司，位于得克萨斯州休斯顿，现诚聘会计人员，具体需求如下。
需求部门：财务部
岗位：全职会计
Job Responsibilities:
* Perform key verification role in daily cash management process, reviewing
all electronic payments for cash management classification and accounting
accuracy.
* Journal creation for bank account transactions.
* Perform bank reconciliations- reconciliation of the bank statement against
the GL and reconciliation of any assigned clearing accounts.
* Communicate with external banks on trade finance and financing issues.
*... 阅读全帖 |
|
r*****a
发帖数: 5 | 33 一家世界五百强贸易公司，位于得克萨斯州休斯顿，现诚聘会计人员，具体需求如下。
需求部门：财务部
岗位：全职会计
Job Responsibilities:
* Perform key verification role in daily cash management process, reviewing
all electronic payments for cash management classification and accounting
accuracy.
* Journal creation for bank account transactions.
* Perform bank reconciliations- reconciliation of the bank statement against
the GL and reconciliation of any assigned clearing accounts.
* Communicate with external banks on trade finance and financing issues.
*... 阅读全帖 |
|
n****o
发帖数: 278 | 34 The process is:
1) apply LCS with DOL ( one week or so)
2) submit H1b application, if you do Perineum Processing, it will take less
than 15 days. |
|
d********r
发帖数: 303 | 35 Liberal Chinese should stand together to proclaim their cause!
I just want to lay down these points:
1) Strongly support the free expression of All ideas, no matter how absurd it
looks. Support the view that the state shall have no right to promote any
particular kind of ideology
2) Support the interaction of all races and cultures. Promote community
diversity
3) Support the abortion right of the woman. Support stem cell research and
therapeutic cloning
4) Support the cause of environment protec |
|
g*****e
发帖数: 19 | 36 【 以下文字转载自 Overseas 讨论区 】
【 原文由 DFS 所发表 】
吓人啊，占MIT总流量的20%。
Where do people go on mit.edu? (what's this)
web.mit.edu ~ 25%
bbs.mit.edu ~ 20%
media.mit.edu ~ 10%
mit.edu ~ 7%
ocw.mit.edu ~ 4%
ai.mit.edu ~ 3%
classics.mit.edu ~ 2%
the-tech.mit.edu ~ 2%
lcs.mit.edu ~ 2%
mitsloan.mit.edu ~ 2%
www-tech.mit.edu ~ 2%
sloanspace.mit.edu ~ 2%
mitpress.mit.edu ~ 1%
cssa.mit.edu ~ 1%
libraries.mit.edu ~ 1%
usenet-addresses.mit.edu ~ 1%
mitpress2.mit.edu ~ 1%
student.mit.edu ~ 1%
cognet.mit.edu ~ 1%
wi.mit. |
|
|
G****a
发帖数: 10208 | 38 After one of the more improbable comebacks in postseason history, the St.
Louis Cardinals will kick off the National League Championship Series on
Sunday against the San Francisco Giants in a matchup of the last two World
Series winners.
The Cardinals overcame an early six-run deficit and were behind by two
entering the ninth on Friday, but scored four times in their final at bat to
shock the Washington Nationals, 9-7, in the decisive fifth game of the NLDS.
"They just don't quit. I think that j... 阅读全帖 |
|
r***e
发帖数: 2000 | 39 CVN-76 USS Ronald Reagan
DDG-57 USS Mitscher
CVN-70 USS Carl Vinson
DDG-111 USS Spruance
LPD-20 USS Green Bay
LCS-2 USS Independence
T-AO-187 USNS Henry J. Kaiser |
|
s*********b
发帖数: 815 | 40 您老没搞错吧？求交集跟LCS都那儿跟那儿啊？这个用shell就搞定了：comm -12 <(
sort file1) <(sort file2)。如果用python也简单：
from sets import Set
def intersect(words, another_words):
return Set(words) & Set(another_words) |
|
|
a****r
发帖数: 154 | 42 今年的Yankees显然不能和往年相比，人还是这些人，但是看看现在
每场多少LOB.
Yankees饭们压，难道还能指望Brosius再来个疯狂playoff.
俺觉得，M's能在NY搞个1:1回家，M's应该很满意。当然2:0更好。但
Yankees毕竟是Yankees，指望LCS秋风扫落叶还是不切现时。关键是
下一场。从以往看, Sele got shelled almost everytime against
Yanks. 但还是那局话，现在的Yanks不能和移往比。 Safedome也不
是Arlington, 那个left-batter的heaven.
Sele如果拿下这场。Yanks的心理比受重大打击。
hehe,Yankees饭的心情俺理解。但俺看好M's |
|
d**f
发帖数: 16 | 43 主投：ORLANDO HERNANDEZ
捕手：MIKE PIAZZA
一垒：WILL CLARK
二垒：EDGARDO ALFONSO
三垒：ROBIN VENTURA
游击：ALEX RODRIGUEZ
左外：DAVID JUSTICE
右外：JAY BUHNER
中场：JIM EDMONDS
DH： EDGAR MARTINEZ
PH： MARK MCGWIRE
PR： RICKI HENDERSON
CLOSER：MARIANO RIVERA
教练：JOE TORRE |
|
r****p
发帖数: 1854 | 44 小弟考古能力不够，不知道历史上LCS第七场这种逆转还出现过几次。如果你喜欢的球队
也有过这样的表现，你终生陈为他们的球迷我绝对不会re-sniff你。
我知道个人力量有限，但是我还是一直在努力的填这个已经很深了的“yankees fans
against yankees haters"这个坑，浅一点算一点。但是我那样一封不针对任何人，任何
球队，自己意淫一下的post,大家都要sniff，我就真的不明白乐。到底是什么让你们这么
恨yankees 和 yankees fans, 还是你们遵循毛主席的教诲，“与人斗，其乐无穷”？ |
|
|
E**y
发帖数: 1018 | 46 五场比赛，其中有三场先发没有挺过第五局，其中一场只有三局，另一场干脆就两局不
到，排兵布阵之差，在lcs这样的水平的比赛上，算是比较罕见的。费力打击虽然强，
也没有强到见谁打谁的程度。躲者的教练组根本应变不上。asb之后签来的sherril和
thome,一个在nlcs里面era差不多有10，另外一个就一个ab。根本就是废人两个。 |
|
m******k
发帖数: 2390 | 47 去年 LCS 都被淘汰。 最后一个Out 分别是Arod and Howard
今年 LDS 都被淘汰。 最后一个Out 分别是Arod and Howard |
|
t********y
发帖数: 86 | 48 LCS的四个队, 球迷都甩毛巾, 还都是一个方向. |
|
j*****n
发帖数: 3617 | 49 现在Marco Scutaro已经在NLCS有13个hit了。纪录是三个人共同保持的，在LCS上有14
个hit，其中NLCS一个，ALCS两个。哪三个人？大家都认识。
这个题目是早上收音机里听到的, 当时第一个答对的人得到的奖品是今天晚上的球票 :) |
|
m*r
发帖数: 37612 | 50 Scutaro batted .500 with two walks, scored six runs and drove in four.
Hideki Matsui (2004 Yankees), Albert Pujols (2004 Cardinals) and Kevin
Youkilis (2007 Red Sox) also had 14 hits in an LCS. |
|
