a***e
发帖数: 413 | 1 我写了一个类似brute force的方法，请问这个应该算是O（N^2)么？多谢！
string extractor(string &s, int l,int ri)
{
string r;
int left=l,right=ri;
int len=s.length();
while(left>=0&&right
{
if (s[left]==s[right])
{
left--;
right++;
}
else
break;
}
r = s.substr(left+1,right-left-1);
return r;
}
string longestPalindrome(string s) {
int len = s.s... 阅读全帖 |
|
D****3
发帖数: 611 | 2
我原来给的解还能refactor一下。给个新的吧：
--------
其实这个java解本身就不是最优的。因为跑了很多根本没可能是最长susbtring的解。
Leetcode对python的速度比较高。我在你的算法上改进了下：
从中间开始选对称轴，向两边移动。当剩下的最长可能palindrome substring都没当前
最长的palindrome subtring长的时候，立刻返回当前最长的解。
class Solution:
def longestPalindrome(self, s):
longest, mid = "", (len(s) - 1) / 2
i, j = mid, mid
while i >= 0 and j < len(s):
args = [(s, i, i), (s, i, i + 1), (s, j, j), (s, j, j + 1)]
for arg in args:
tmp = self.longestPali... 阅读全帖 |
|
B*M
发帖数: 1340 | 3 http://en.wikipedia.org/wiki/Longest_increasing_subsequence
Efficient algorithms
The algorithm outlined below solves the longest increasing subsequence
problem efficiently, using only arrays and binary searching. It processes
the sequence elements in order, maintaining the longest increasing
subsequence found so far. Denote the sequence values as X[1], X[2], etc.
Then, after processing X[i], the algorithm will have stored values in two
arrays:
M[j] — stores the position k of the smallest val... 阅读全帖 |
|
k*******t
发帖数: 144 | 4 class Solution {
public:
int longestConsecutive(vector &num) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
unordered_map mapping;
for(int i = 0; i < num.size(); ++i)
{
mapping[num[i]] = true;
}
int longest = 0;
for(int i = 0; i < num.size(); ++i)
{
int len = 0;
int cur = num[i];
while(mapping.find(cur) != mapping.end... 阅读全帖 |
|
a***e
发帖数: 413 | 5 请问，为什么这个答案在oj能通过，但在VS2010中编译for (auto i:num)老是出错呢？
多谢
error C3531: 'i': a symbol whose type contains 'auto' must have an
initializer
int longestConsecutive(vector &num) {
unordered_map used;
for (auto i:num) used[i]=false;
int longest = 0;
for (auto i:num)
{
if (used[i])
continue;
int length = 1;
used[i] = true;
for (i... 阅读全帖 |
|
j******2
发帖数: 362 | 6 longest common prefix:
这题就只有O(n*m)的解法了吧？n=最短的一个string的长度，m=string个数。
没更简便的了吧？
longest common substring:
这题的两种解法都要掌握吗？DP比较容易，但是时间复杂度要O(n1xn2)。suffix tree
时间复杂度是O(n1+n2)，但是貌似很复杂，很想放弃了。有经验的大牛们，这题需要掌
握suffix算法吗？ |
|
w***y
发帖数: 6251 | 7 find the length of the longest valid (well-formed) parentheses substring.
For "(()", the longest valid parentheses substring is "()", which has length
= 2.
Another example is ")()())", where the longest valid parentheses substring
is "()()", which has length = 4. |
|
q*c
发帖数: 17993 | 8 10 Longest Vertical Drops in North America:
http://snowbrains.com/10-longest-vertical-drops-in-north-americ
Lone Peak, MT.
We’ve decided to put a small twist on this statistic. The rankings we are
displaying below only reflect the amount of vertical that can be accessed
via a chairlift. No hiking. Just riding chairs and skiing down. This is
more relevant for the highest percentage of skiers in North America, so we
thought we’d allow the numbers to reflect that.
#1 – REVELSTOKE, B.C.
Mt. Mack... 阅读全帖 |
|
c*********t
发帖数: 2921 | 9 Hi,
I have a question about Longest repeated substring.
Given a string "BANANA", is the longest repeated substring "ANA" or just "AN
" or "NA"?
According to the definition in Wikipedia. It seems that the longest repeated
string is "ANA".
http://en.wikipedia.org/wiki/Longest_repeated_substring_problem
http://en.wikipedia.org/wiki/Suffix_tree
I guess this is how it works for these two different answers.
For the answer ANA
BANANA
|||
|||
Here ANA is repeated twice. However these two ANA overlap |
|
e***s
发帖数: 1397 | 10 [http://campaignspot.nationalreview.com/]
The Presidency: The Longest-Held Full-Time Job of Obama's Life.
A stunning, yet accurate statement from Campaign Spot reader Tim: If Barack
Obama serves a full term as president, it will be the longest time he has
served in a full-time job. He spent about a year and change working for a
financial publication in Manhattan, then three years as a community
organizer, then three years in law school. After that, his time was divided
among several jobs that we |
|
|
|
k*i
发帖数: 220 | 13 网上查到说可以用 suffix tree:
The longest palindrome of txt[1..n] can be found in O(n) time, e.g. by
building the suffix tree for txt$reverse(txt)# or by building the
generalized suffix tree for txt and reverse(txt).
具体在建立了 suffix tree之后如何查找 longest palindrome ？
那位高人给指点一下？ |
|
I**A
发帖数: 2345 | 14 thanks，这个好理解。。
复杂度o(n^2*m) where n is length(s1) and m is length(s2)
如果我已经有了一个算法，就是得到一个string的longest repeated substring,
有没有办法调用这个function来求 longest common substring of two strings? |
|
|
c***2
发帖数: 838 | 16 There is a solution at
http://www.ihas1337code.com/search/label/binary%20tree
/** See my comments **/
int maxDepthIterative(BinaryTree *root) {
if (!root) return 0;
stack s;
s.push(root);
int depth = 1, maxDepth = 0;
BinaryTree *prev = NULL;
while (!s.empty()) {
BinaryTree *curr = s.top();
if (!prev || prev->left == curr || prev->right == curr) {
if (curr->left) {
depth++;
s.push(curr->left);
} else if (curr->right) {
depth++;
... 阅读全帖 |
|
b***u
发帖数: 12010 | 17 matrix multiplication业界都在研究怎么把constant factor降低个0.xx，难度系数和
longest subsequence是不一样的。
longest subsequence算dp里难度中等的。你硬要说面试管一年也搞不出来是太小看人了。
g家的brain teaser才变态。签了nda就不说了。 |
|
b**y
发帖数: 13 | 18 求教各位大拿，这道面试题怎么解
Find Longest Word Made of Other Words： Write a program that reads a file
containing a sorted list of words (one word per line, no spaces, all lower
case), then identifies the longest word in the file that can be constructed
by concatenating copies of shorter words also found in the file.
给你一个词典，找出长度最长的复合单词，怎么解呢，先谢谢了 |
|
b**y
发帖数: 13 | 19 求教各位大拿，这道面试题怎么解
Find Longest Word Made of Other Words： Write a program that reads a file
containing a sorted list of words (one word per line, no spaces, all lower
case), then identifies the longest word in the file that can be constructed
by concatenating copies of shorter words also found in the file.
给你一个词典，找出长度最长的复合单词，怎么解呢，先谢谢了 |
|
d****o
发帖数: 1055 | 20 the longest repeated substring problem is the problem of finding the longest
substring of a string that occurs at least twice.
比如
input: banana
ouput: ana
bruth force way是O(n^3)，我只做出来这个，弱啊。
哪位大牛来解释一下？ |
|
j******2
发帖数: 362 | 21 我的意思是：longest common substring这个问题的DP解法就是用DP来算suffix array
的长度。 |
|
j******2
发帖数: 362 | 22 看了下，好像不是很简单的啊，尽是些paper。。。
这个suffix array和suffix tree的linear算法要不要掌握啊？本来是在搞DP，结果被
这个longest common substring引得来看这个suffix tree/array，投入的时间越来越
多，但是150和leetcode上都没啥suffix tree/array的问题啊，只有个strstr还蛮简单
的。。。
不是科班出身的就是累啊，千疮百孔的。。。 |
|
c********t
发帖数: 5706 | 23 逆序+ longest common substring，好像是典型的错误。
S = “abacdfgdcaba”, S’ = “abacdgfdcaba”.
The longest common substring between S and S’ is “abacd”. Clearly, this
is not a valid palindrome. |
|
a*******n
发帖数: 64 | 24 能展开说说吗？
这个问题主要不是怎么用topo sorting and DP去找longest path
而是问如果给你找到shortest path的算法，问怎么改graph去找longest |
|
g***j
发帖数: 1275 | 25 Given an unsorted array of integers, find the length of the longest
consecutive elements sequence.
For example,
Given [100, 4, 200, 1, 3, 2],
The longest consecutive elements sequence is [1, 2, 3, 4]. Return its length
Your algorithm should run in O(n) complexity.
我在网上看到了几段code，用到了set或者map，每次要在set或者map里面找到，然后删
掉，我想问，这样的code时间是n么？find in a set难道不是logn么？当然也有用到
map的，我觉得找元素都是logn啊，那么最终的时间就是nlogn啊，比如如下code
class Solution {
public:
int longestConsecutive(vector &num) {
// Start typing... 阅读全帖 |
|
l***s
发帖数: 15 | 26 my accepted codes. seems different algorithm than the one found online
class Solution:
# @return a string
def longestPalindrome(self, s):
le = len(s)
if not s:
return ''
table=[] #record longest so far and longest ending at i
table.append(((0,0), 1))
for i in xrange(1,le):
curind=table[-1][0]
lastsofar=curind[1]-curind[0]+1
lastending=table[-1][1]
for j in xrange(i-lastending-1, i+1):... 阅读全帖 |
|
u***l
发帖数: 51 | 27 用 python 做的，如果用O(n^2) 的方法做，发现下面 a)的code可以过，但是 b)会超时
https://oj.leetcode.com/problems/longest-palindromic-substring/
a 和 b 中只有 function f 不一样，请问这两个到底是哪里产生的不同？谢谢。
OJ 显示超时的例子是 "aaaa...(很长) b(在靠中间的位置) aaaa(很长)"
###########################
a)
class Solution:
# @return a string
def longestPalindrome(self, s):
def f(s, p, q): # find longest palindrome centered at p and q
while p >= 0 and q < len(s) and s[p] == s[q]:
p -= 1; q += 1
return s[p + 1 :... 阅读全帖 |
|
b**********5
发帖数: 7881 | 28 TOKYO — The world’s longest-serving death row inmate was freed Thursday by
a Japanese court that found investigators had likely fabricated evidence in
the murder case that put the former pro boxer behind bars for nearly half a
century.
The Shizuoka District Court suspended the death sentence and ordered a
retrial for 78-year-old Iwao Hakamada, who had been convicted in the 1966
murder of a family and was sentenced to death in 1968. More than 45 of his
48 years in prison have been on death row, m... 阅读全帖 |
|
d******k
发帖数: 4295 | 29 昨晚看完球躺床上睡觉，想到了这个问题。于是早上google一下，
The Boston Redskins had a 14:03 drive during the third game of the 1935
season against the Chicago Bears. Sammy Baugh ran for 56 yards and passed
for 49, as the 'skins scored on their 23rd play of the drive.
http://wiki.answers.com/Q/What_is_the_longest_drive_in_terms_of
近年的记录似乎是Saints
Saints vs Panthers, Oct 7, 2006 -- Saints had a drive that was 24 plays, 93
yards, 10:22 off the clock, and culminating in a blocked 20-yard FG.
http://forums.footballguys.com/foru... 阅读全帖 |
|
w*****r
发帖数: 348 | 30 For the attached NAND gate, what will be the longest tphl delay?
AB=10->AB=11 or
AB=00->AB=11?
For the NOR gate, what will be the longest tplh delay?
AB=10->AB=00 or
AB=11->AB=00 ?
Can anyone help?
Thanks a lot! |
|
E********r
发帖数: 99 | 31 http://www.nsf.gov/news/news_summ.jsp?cntn_id=108992
Press Release 07-055
The Longest Carbon Nanotubes You've Ever Seen
Crafted with breakthrough manufacturing technique, centimeter-long fibers ar
e visible to the naked eye
Researchers at the University of Cincinnati have grown the world's longest c
arbon nanotube arrays.
Credit and Larger Version
May 10, 2007
Using techniques that could revolutionize manufacturing for certain material
s, researchers have grown carbon nanotubes that are the long |
|
x******a
发帖数: 6336 | 32 【 以下文字转载自 JobHunting 讨论区 】
发信人: xiaojiya (xiaojiya), 信区: JobHunting
标 题: Re: 请问longest common consecutive sequence用什么算法？
发信站: BBS 未名空间站 (Mon Jan 14 22:54:24 2013, 美东)
再请问一下，suppose两个sequences的长度都是1000，都有a,b,c,d,e五个字母构成，
每个位置是这5个字母的概率都是1/5. 那么longest common consecutive sequence的
长度期望是多少？ |
|
c******t
发帖数: 2478 | 33 【 以下文字转载自 ChinaNews 讨论区 】
发信人: FUV (扶危济贫), 信区: ChinaNews
标 题: The five longest filibusters, per Senate records
发信站: BBS 未名空间站 (Thu Mar 7 00:35:11 2013, 美东)
Strom Thurmond — 24 hours, 18 minutes: At the time, the South Carolina
senator was a Democrat, who was railing against the Civil Rights Act of 1957
. To fill the time, Thurmond read the election laws of all 48 states that
were then part of the union.
Alfonse D'Amato — 23 hours, 30 minutes: In 1986, the New York Republican
once known as "Sen... 阅读全帖 |
|
g*******y
发帖数: 1930 | 34 Hint1:
I was told by krone, that you has to combine this problem with LCA (lowest common anceaster).
Hint2:
You surely start from considering txt and reverse of txt.
Hint3:
Keep in mind that a leaf node in a suffix tree corresponds to a suffix. Obviously, if you are looking at a specific suffix, you can get a pointer to the corresponding leaf node in O(1) time.
Hint4:
Also keep in mind that finding a palindrome is somewhat unlike finding
longest common substring in which two common substrings do |
|
i****h
发帖数: 321 | 35 我只知道suffix array可以用来计算longest common prefix。。。
能给个link吗？谢谢。 |
|
m******9
发帖数: 968 | 36 他说的方法挺好的
longest palindrome, 就可以用string 和 reverseed string, 然后DP找LCS, 现场
coding也比较方便.
更好的就是你提到的suffix tree |
|
f*********5
发帖数: 576 | 37 1)create a generalized suffix tree for A[0..n] and its reverse string
B[0..n]
###u need to make sure that u can get LCA of two nodes with O(1).
This step is difficult,i think unless u understand it very well,
otherwise it is very difficult to recite..
2) for (i=1;i
find max {LCA(a[i],b[n-1-i]),LCA(a[i+1],b[n-1-i])}
3) the max LCA is just the length of longest parlindrome,
i or i+1 is just the center of the parlindrome |
|
j*****g
发帖数: 223 | 38 yours is essentially what roufoo said:
发信人: roufoo (五经勤向窗前读), 信区: JobHunting
标 题: Re: MMD, 死在了longest contiguous increasing sub-array上了.
发信站: BBS 未名空间站 (Fri Oct 29 01:57:19 2010, 美东)
if the # of rest elements is smaller than or equal to len, and a[i]>=a[i+1
]
then exit?
this only improves slightly near the end of the array. if the array is very
long, then the improvement is so small that is negligible. |
|
c***2
发帖数: 838 | 39 /* longest contiguous increasing sub-array : brute-force */
int longest_inc_sub_bf(int array[], int size, int *start)
{
int max,len,i;
int from,max_from;
int comparisons=0;
max=len=1;
max_from=from=0;
i=0;
while(1){
i=from;
while((i=array[i])){
i++;
len++;
comparisons++;
}
comparisons++;
if(len>max) {
max_from=from;
max=len;
... 阅读全帖 |
|
c***2
发帖数: 838 | 40 /* longest contiguous increasing sub-array : improvement */
int longest_inc_sub(int array[], int size, int *start)
{
int max,len,i;
int from,to,max_from;
int comparisons=0;
max=len=1;
max_from=from=to=0;
i=0;
while(1){
/* advance to next block */
to = from+len;
if(to>=size) break;
/* looking backward */
i=to;
while((i>from)&&(array[i]>=array[i-1])){
i--;
len++;
comp... 阅读全帖 |
|
i**********e
发帖数: 1145 | 41 How about this top-down approach?
Basically we cannot avoid copying the current path to longest path every
time we update maxDepth, unless we obtain the value of maxDepth by traversing the entire tree beforehand.
void findLongestPath(BinaryTree *p, int &maxDepth, vector &path
, vector &longestPath) {
if (!p) return;
path.push_back(p);
if (!p->left && !p->right && path.size() > maxDepth) {
maxDepth = path.size();
longestPath = path;
}
findLongestPath(p-... 阅读全帖 |
|
S******1
发帖数: 269 | 42 // Find the longest subarray with equal 1 and 0.
public static int[] longestSub(int[] inputArray) {
int length = inputArray.length;
int[][] record = new int[length][length];
//Initial
for (int i = 0; i < length; i++)
if (inputArray[i] == 1)
record[i][i] = 1;
else
record[i][i] = -1;
for (int i = 0; i < length; i++) {
for (int j = i; j < length; j++) {
if (i < j)
... 阅读全帖 |
|
|
c*******r
发帖数: 309 | 44 Given an array of random numbers. Find the longest consecutive sequence.
For ex
Array 100 3 200 1 2 4
Ans 1 2 3 4
Array 101 2 3 104 5 103 9 102
Ans 101 102 103 104
Can we do it in one go on array using extra space??
我想到的方式是先sort， 然后用index来存,然后记录max长度. 不断更新新的index指
针.
不过据说复杂度要控制在o(n).
没什么好的想法啊 |
|
c**j
发帖数: 103 | 45 ding! Can we do it without sorting??
请问Bayesian1， 还有link没？
加个条件： 这个题如果还要要求 答案是*连续位置的*的subarray呢？
e.g.:
input: 4,5,1,5,7,4,3,6,3,1,9
sort以后1，1，3，3，4，4，5，5，6，7，9
output{5,7,4,3,6}
check careercup:
http://www.careercup.com/question?id=11256218
Microsoft Interview Question about Algorithm asm on October 19, 2011
you have an array of integers, find the longest
subarray which consists of numbers that can be arranged in a sequence, e.g.:
a = {4,5,1,5,7,4,3,6,3,1,9}
max subarray = {5,7,4,3,6}
39
http:/... 阅读全帖 |
|
c**j
发帖数: 103 | 46 这个表面简单的题Goolge MS 都考了啊。干脆发给新话题吧，还请大牛们指教啊
2个variation
MS 要求连续位置，考虑duplicate，DP， divide conquer, sort 貌似都有难度。。
Google 没有要求连续位置，简单不少，但是不让sort。。。。。又难回去了
check careercup:
http://www.careercup.com/question?id=11256218
Microsoft Interview Question about Algorithm asm on October 19, 2011
you have an array of integers, find the longest
subarray which consists of numbers that can be arranged in a sequence, e.g.:
a = {4,5,1,5,7,4,3,6,3,1,9}
max subarray = {5,7,4,3,6}
39
http://www.careercup.com/question?id... 阅读全帖 |
|
|
m******s
发帖数: 204 | 48 原题解法CC150
1. Sort the array by size, putting the longest word at the front
2. For each word, split it in all possible ways. That is, for “test”,
split it into {“t”, “est”}, {“te”, “st”} and {“tes”, “t”}.
3. Then, for each pairing, check if the first half and the second both exist
elsewhere in the array.
4. “Short circuit” by returning the first string we find that fits
condition #3.
原题解法似乎不能涵盖所有情况：
aa aabbcc bb bbc cc
1. Sort: (aabbcc, bbc, aa, bb, cc)
2. 把aabbcc拆分成两部分, 下面是所有的情况：
(a abbcc) (aa b... 阅读全帖 |
|
C***U
发帖数: 2406 | 49 1 Make a sorted copy of the sequence A, denoted as B. O(nlog(n)) time.
2 Use Longest Common Subsequence on with A and B. DP(O(n^2)时间）
是O(n^2)时间了 比最优的要差一些了
刚才搞错了 |
|
f*********i
发帖数: 197 | 50 2 Use Longest Common Subsequence on with A and B. DP(O(n)时间）
how to do that in O(n)? |
|
