{Algo}寻找最长回文串&众数问题变种

[pongba]

1. Amazon|How will you find the longest palindrome in a string? I.e. if the string is XMADAMYX, Your code should print MADAM.

2. Amazon|An array of size n, has n/2 unique elements and n/2 occurences of an element. Find the non-unique element in linear time?
#这个问题和众数问题有点类似，但不完全一样。因为它有一个更强的条件。

#想起另一个和众数问题类似的：
2'. How to find if a number is present >= (n / 2) times in an array of size n?
（众数问题是>=n/2+1）

--
刘未鹏(pongba)|C++的罗浮宫
http://blog.csdn.net/pongba
TopLanguage
http://groups.google.com/group/pongba

[pongba]

2008/6/18 pongba <pon...@gmail.com>:

1. Amazon|How will you find the longest palindrome in a string? I.e. if the string is XMADAMYX, Your code should print MADAM.

2. Amazon|An array of size n, has n/2 unique elements and n/2 occurences of an element. Find the non-unique element in linear time?
#这个问题和众数问题有点类似，但不完全一样。因为它有一个更强的条件。

#想起另一个和众数问题类似的：
2'. How to find if a number is present >= (n / 2) times in an array of size n?
（众数问题是>=n/2+1）

补充一道：

3. Microsoft|Given an expression remove the unnecessary brackets in it with out creating an ambiguity in its execution.
input output
ex1: (a+(b)+c) a+b+c
ex2: (a*b)+c a*b+c

来源：http://discuss.joelonsoftware.com/default.asp?interview.11.642622

[Yong Yuan]

数学家申请消防员职位那个笑话配2'真是太合适了。:-D 另外1和3好像符合pongba常说的没有知识就很难解的那类问题？或者有比后缀树和AST更优雅的方法？也不排除有牛牛天生神力，推导出了后缀树。不过以现在信息密度，能推出1973年年度最佳数据结构的老大，多半早就学过这些常见结论了。

2008/6/18 pongba <pon...@gmail.com>:

[chuch...@gmail.com]

思路一：第二题刚开始又往O(n)时间选择第k大元素那个方法上想了，方法很撮。就是使用四次selectK,分别选出第n/2-1,n/2,n/
2+1,n/2+2个元素，这四个里肯定至少有2个元素相等，找出就是所求。

思路二：后来发现没有很好利用n/2个元素都不想等这个 pongba 所说的更强的条件,其实可以这样：
从头开始进行两两元素比较，出现相等元素即为所求，若出现极端情况也就是n/2个相同元素刚好被间隔开来，那么任意连续3个元素找到2个相等的即可。

BTW:第一题最快的应该是用后缀树吧，不过后缀树很难写啊。传说楼天城能在比赛现场20分钟内写出后缀树

[鋆邓]

后缀数组，比后缀树简单，在 NlogN时间内完成。

话说，即使后缀数组，也要300+行的代码……

2008/6/19 Yong Yuan <y...@cs.toronto.edu>:

[pongba]

2008/6/19 chuch...@gmail.com <chuch...@gmail.com>:

思路二：后来发现没有很好利用n/2个元素都不想等这个 pongba  所说的更强的条件,其实可以这样：
从头开始进行两两元素比较，出现相等元素即为所求，若出现极端情况也就是n/2个相同元素刚好被间隔开来，那么任意连续3个元素找到2个相等的即可。

对，我说的就是这个思路:D 这应该是针对这道题目最简单的方法了。

[pongba]

两位科普一下后缀树吧，我看了包括wiki和CLRS在内的介绍，云里雾里，只知道个大概。说实话介绍得并不高明，上来就一坨功能的说明，然后又是一坨技术细节说明。跟介绍红黑树一样。见不到对背后思想的阐述。只看到繁杂的技术细节。

2008/6/19 鋆邓 <tdzl...@gmail.com>:

[dd_engi]

On Jun 19, 1:09 pm, pongba <pon...@gmail.com> wrote:
> 两位科普一下后缀树吧，我看了包括wiki和CLRS在内的介绍，云里雾里，只知道个大概。说实话介绍得并不高明，上来就一坨功能的说明，然后又是一坨技术细节说明。跟介绍红黑树一样。见不到对背后思想的阐述。只看到繁杂的技术细节。
>

理解后缀树，先理解trie以及其功能（包括字符串自动机？）。后缀树就是把一个字符串的所有后缀插入到trie里（对于连续的无分支路径要合并成一个
点），然后大牛发现这个东西可以O(N)构建出来，就非常有用了。

本题大致就是把suffix tree构造出来然后用原串的逆序进行查找匹配吧？我觉得了解思想就行了，不用强求自己编出来，实际中肯定用库嘛。

suffix array 可以用相对少一点的代码量实现大部分功能，本例也可以。某年集训队论文有。

> 2008/6/19 鋆邓 <tdzl2...@gmail.com>:
>
>
>
> > 后缀数组，比后缀树简单，在 NlogN时间内完成。
> > 话说，即使后缀数组，也要300+行的代码......

[dd_engi]

> 3. Microsoft|Given an expression remove the unnecessary brackets in it with
> out creating an ambiguity in its execution.
> input output
> ex1: (a+(b)+c) a+b+c
> ex2: (a*b)+c a*b+c

如果只考虑四则运算，可以很暴力写几个if-else来解，根据括号前后以及内部都有什么符号，以前做OI时显然做过这种题。

[silwile]

可以先看看Programming Pearl里的Column 15，里面有讲suffix array的，虽然降得不深，但很明白。

2008/6/19 pongba <pon...@gmail.com>:

[Yong Yuan]

2008/6/19 pongba <pon...@gmail.com>:

两位科普一下后缀树吧，我看了包括wiki和CLRS在内的介绍，云里雾里，只知道个大概。说实话介绍得并不高明，上来就一坨功能的说明，然后又是一坨技术细节说明。跟介绍红黑树一样。见不到对背后思想的阐述。只看到繁杂的技术细节。

 

我写了篇帖子：http://blog.csdn.net/g9yuayon/archive/2008/06/21/2574781.aspx。思想滴没有。就是聊了一下后缀树的直观意义。跪求砸砖。Orz。

[pongba]

2008/6/22 Yong Yuan <y...@cs.toronto.edu>:

2008/6/19 pongba <pon...@gmail.com>:

两位科普一下后缀树吧，我看了包括wiki和CLRS在内的介绍，云里雾里，只知道个大概。说实话介绍得并不高明，上来就一坨功能的说明，然后又是一坨技术细节说明。跟介绍红黑树一样。见不到对背后思想的阐述。只看到繁杂的技术细节。

 

我写了篇帖子：http://blog.csdn.net/g9yuayon/archive/2008/06/21/2574781.aspx。思想滴没有。就是聊了一下后缀树的直观意义。跪求砸砖。Orz。

 

赞，先顶再看:D

[Yong Yuan]

2008/6/21 pongba <pon...@gmail.com>:

2008/6/22 Yong Yuan <y...@cs.toronto.edu>:

2008/6/19 pongba <pon...@gmail.com>:

两位科普一下后缀树吧，我看了包括wiki和CLRS在内的介绍，云里雾里，只知道个大概。说实话介绍得并不高明，上来就一坨功能的说明，然后又是一坨技术细节说明。跟介绍红黑树一样。见不到对背后思想的阐述。只看到繁杂的技术细节。

 

我写了篇帖子：http://blog.csdn.net/g9yuayon/archive/2008/06/21/2574781.aspx。思想滴没有。就是聊了一下后缀树的直观意义。跪求砸砖。Orz。

 

赞，先顶再看:D

囧rz。。。。 CLRS有啊。不记得了呢？是不是第二版的？我有第一版，不过放在地下室攒灰，好久没看了。

[hayate]

话说csdn得blog那么差，抱怨那么久也不修，为什么不换个bsp? 现在搬家也方便

2008/6/22 Yong Yuan <y...@cs.toronto.edu>:

[Yong Yuan]

2008/6/22 hayate <haya...@gmail.com>:

话说csdn得blog那么差，抱怨那么久也不修，为什么不换个bsp? 现在搬家也方便

 

推荐几个？有支持图片自动上传的么？Orz

[hayate]

什么是自动上传啊？

2008/6/22 Yong Yuan <y...@cs.toronto.edu>:

[Yong Yuan]

2008/6/22 hayate <haya...@gmail.com>:

什么是自动上传啊？

 

比如我把文章从Word拷贝到博客的时候，帖子里的图片就自动上传到博客的服务器上。图片的img标签也被自动更新。或者像Live Writer那样从Live Writer连文本带图片一键发布到博客。反正不用我一张一张地从本地硬盘上传。

[zl]

google doc不知道可不可以
把publish的内容拷到blog里...

On 6月22日, 下午12时27分, "Yong Yuan" <y...@cs.toronto.edu> wrote:
> 2008/6/22 hayate <hayate...@gmail.com>:

>
> > 什么是自动上传啊？
>
> 比如我把文章从Word拷贝到博客的时候，帖子里的图片就自动上传到博客的服务器上。图片的img标签也被自动更新。或者像Live Writer那样从Live
> Writer连文本带图片一键发布到博客。反正不用我一张一张地从本地硬盘上传。
>
>
>
> > 2008/6/22 Yong Yuan <y...@cs.toronto.edu>:
>

> >> 2008/6/22 hayate <hayate...@gmail.com>:

[hayate]

那为什么不依赖于客户端呢？

我倒是很少用BSP提供的rich editor

csdn主要是没有全文rss很让人受不了

[Yong Yuan]

2008/6/22 hayate <haya...@gmail.com>:

那为什么不依赖于客户端呢？

我倒是很少用BSP提供的rich editor

csdn主要是没有全文rss很让人受不了

CSDN 也不支持客户端上图。我用Live Writer，只能发布帖子。帖子里的图全是HTTP 404，一张都上不上去。

[hayate]

那还是csdn的问题啊，我试了一下基于wordpress的blog，可以正常上传。