|
精华帖 (0) :: 良好帖 (0) :: 隐藏帖 (0)
|
|
|---|---|
| 作者 | 正文 |
|
发表时间：2008-04-23
在这之前得先筛出包含非法字符的单词
或者在调用此方法前先行检查 |
| 返回顶楼 | |
|
发表时间：2008-04-23
nmvr2600 写道 第一个题和论坛ruby版里那个“容易记的电话号码”有些类似
第二个，就是统计生日最多的哪一天，但是生日里面的年可以直接忽略掉，需要的就只有月日。月和日不要一起统计，先算月。先把生日最多的那个月份找到，再去统去到底是哪一天。呵呵，这样最后需要计算个数的人就少了很多了吧。直接去算每天出现的人数还是有点笨。如果数据量再多的话，可以借用下数理统计的知识。 第三个，使用正则表达式\b(?i)[s|t|o|p]{4}\b，搞定~~ 生日最多的那一天 不一定在生日最多的那一月里。。 
|
| 返回顶楼 | |
|
发表时间：2008-04-23
sqhe18 写道 7thbyte 写道 nmvr2600 写道 第一个题和论坛ruby版里那个“容易记的电话号码”有些类似
第二个，就是统计生日最多的哪一天，但是生日里面的年可以直接忽略掉，需要的就只有月日。月和日不要一起统计，先算月。先把生日最多的那个月份找到，再去统去到底是哪一天。呵呵，这样最后需要计算个数的人就少了很多了吧。直接去算每天出现的人数还是有点笨。如果数据量再多的话，可以借用下数理统计的知识。 第三个，使用正则表达式\b(?i)[s|t|o|p]{4}\b，搞定~~ “先把生日最多的那个月份找到”的时候，怎么都得遍历一次吧。。 再统计天的话，又部分遍历一次。。哪里减小了运算量啊。。 把月和日当成一个整体作为key，遍历一次就可以了。。 这个正则表达式可以吗。。似乎"tttt"这种字符串也能匹配上 把月和日当成一个整体作为key的话，需要遍历365个元素。 而将月和日分开的话，只需要遍历12+31个元素。 但是后一种方法需要同时在两个collection里插入，可能有点得不尝失 分开的原因主要是不管你是按月日还先算月在算日，你要想得到最多的那个key总是要排序的吧？你觉得是365个值里找出最大的那个快呢 还是12，31排这两个快。 可能这种数据规模下，效率上看不出什么问题。但是有一个明显的问题是，月日放一起的话，程序面对的始终是所有的学生。分开处理的好处就是，开始就把需要处理的规模降低到大约1/12。 |
| 返回顶楼 | |
|
发表时间：2008-04-23
foy 写道 nmvr2600 写道 第一个题和论坛ruby版里那个“容易记的电话号码”有些类似
第二个，就是统计生日最多的哪一天，但是生日里面的年可以直接忽略掉，需要的就只有月日。月和日不要一起统计，先算月。先把生日最多的那个月份找到，再去统去到底是哪一天。呵呵，这样最后需要计算个数的人就少了很多了吧。直接去算每天出现的人数还是有点笨。如果数据量再多的话，可以借用下数理统计的知识。 第三个，使用正则表达式\b(?i)[s|t|o|p]{4}\b，搞定~~ 生日最多的那一天 不一定在生日最多的那一月里。。  我错了
:D 先算日再算月好了 |
| 返回顶楼 | |
|
发表时间：2008-04-23
很好的题目。
编程之美？ 看来应该去买一本了。 |
| 返回顶楼 | |
|
发表时间：2008-04-23
Joo 写道 manbearpig1 写道 第三题，26个字母对应2开始的26个质数，对每个词求乘积，结果一样的认为是等价的
前提：不考虑乘法溢出，复杂度上界O(line_of_file * max_word_len) 这个很不错.但问题是每个字母都要转换一边是否高效? 数字不会很大怎么会溢出的? 呵呵,这么一说倒是想起来了,如果再在题目上加上对于空间或者时间的要求,可能就更难一层了 忘记曾经是哪个公司的题目中作此要求 每个字母转换一下很快，搞个长度为26的辅助数组就可以了 这个比先排序要快，对一个单词排序不开辟大量空间又比较流行的quicksort需要n*log(n)，自己算吧 |
| 返回顶楼 | |
|
发表时间：2008-04-23
manbearpig1 写道 Joo 写道 manbearpig1 写道 第三题，26个字母对应2开始的26个质数，对每个词求乘积，结果一样的认为是等价的
前提：不考虑乘法溢出，复杂度上界O(line_of_file * max_word_len) 这个很不错.但问题是每个字母都要转换一边是否高效? 数字不会很大怎么会溢出的? 呵呵,这么一说倒是想起来了,如果再在题目上加上对于空间或者时间的要求,可能就更难一层了 忘记曾经是哪个公司的题目中作此要求 每个字母转换一下很快，搞个长度为26的辅助数组就可以了 这个比先排序要快，对一个单词排序不开辟大量空间又比较流行的quicksort需要n*log(n)，自己算吧 不一定要先排序， 可以考虑用一个便于计算的方式对文本的内容先做一个粗略的筛选 注意到，同一组anagram中的单词必然长度相等，单词的所有字母的对应的byte值之和也应当相同 这是个必要非充分条件 对因为一般的文本中的单词来讲这个条件被满足的概率不大 经多粗略的筛选后，再结合排序的办法，效率就可以得到保证 |
| 返回顶楼 | |
|
发表时间：2008-04-23
第2题
1、int birthday[12][31]。 2、将数组中所有元素初始化为0。 3、循环遍历所有人，如果当前人n月m日生日，则birthday[n-1][m-1]++。 4、找出数组中最大的值。 |
| 返回顶楼 | |
|
发表时间：2008-04-23
java9981 写道 某个月份生日最多并不能保证生日最多的那一天在此月份里啊
说得对，最开始我也以为某个月份生日最多那么生日最多的那一天在此月份里，后来想想还是不对！ |
| 返回顶楼 | |
|
发表时间：2008-04-23
armorking 写道 对因为一般的文本中的单词来讲这个条件被满足的概率不大 你这个假设比较牵强阿呵呵 |
| 返回顶楼 | |
