问题描述
这道题来自杭电 OJ Prbolem 1006。
Problem Description
The three hands of the clock are rotating every second and meeting each other many times everyday. Finally, they get bored of this and each of them would like to stay away from the other two. A hand is happy if it is at least D degrees from any of the rest. You are to calculate how much time in a day that all the hands are happy.
Input
The input contains many test cases. Each of them has a single line with a real number D between 0 and 120, inclusively. The input is terminated with a D of -1.
Output
For each D, print in a single line the percentage of time in a day that all of the hands are happy, accurate up to 3 decimal places.
Sample Input
0
120
90
-1
Sample Output
100.000
0.000
6.251
分析
初看这道题，很容易想到的一个办法就是模拟 12 个小时的每一秒，得到 happy time 的所有秒数，然后就能算出 happy time 的百分比了。当然，毫无疑问的，这样做会 WA，原因是精度不够，那么就要想另外的办法。 Continue reading »
tips:写得有点长，笔经面经直接看第五和第十三自然段即可。
---------------------------------------------------------------------------------------------
前一个月就一直和@小树在商量实习的事情，恰好又逢上腾讯的实习生招聘刚开始网申，遂投之。面试地点选在武汉，因为小树想考华科的研，而我因为曾经看过台湾做的一档关于武汉的旅游节目也正好想去瞧瞧。
笔试定在 14 号，12 号晚上才收到笔试邀请。我告诉 @Fan 说，我明天过来。Fan 就立马帮我查各种准备信息，我想到的没想到的 Fan 都想到了，我心里一边感激一边默念：还是女孩纸想得周到啊。第二天又因为起床太晚来不及坐公交去车站，只好硬着头皮叫房东叔叔开车送我，还好及时赶到了。
下午到达武汉。我没有叫 Fan 来车站接我，因为我坚定地认为要女孩纸来接人实在太丢人了，于是我按照 Fan 的指示，坐着传说中的武汉公交到了光谷附近。Fan 带着我找吃东西的地方，在路上向我这个路痴不停地介绍着旁边的地标建筑，我一边听，一边感叹着华科之大，因为虽然只绕着华科的校园走了一小段路，但脚已经很酸了。晚上 Fan 决定带我提前去看看考场，逛逛华科，碰上某学院正在举行 K 歌比赛的决赛，便围观了一会儿。
第二天起床，Fan 带着我去吃热干面，她说：“@Li 说热干面那个酱的味道好恶心，不知道你喜不喜欢吃”，我用实际行动告诉了她我喜欢。不过她说这家的热干面不太正宗，比较符合湖南人的口味。吃完面，提前到了考场。签完到之后就坐下了，但场景完全和我想的不一样：一间梯形大教室，几百人人挤人地坐着，好像并不是很严格，又可能是场地有限或者对我们很放心。坐旁边的哥们儿问我：“你是哪个学校的？”，我怕说出来他不认识，就说：“我是从湖南那边过来的”。他感叹我很有诚意，我解释说腾讯在湖南没有设立招聘点，我问：“你应该就是华科的吧？”，他答：“嗯。”，我又问：“黄鹤楼值得去么？”，他和昨天 Fan 说的一样：“坑爹。”。后来我们又闲扯了几句，他说他的室友一个拿到了微软的 Offer，一个拿到了 360 的，我默默感叹……
昨天@小树问我还记不记得 KMP 算法，我试着回想之后发现自己已经记不清太多细节，只记得 matrix67 大神有写过这样一篇文章，所以今天特地抽时间又看了看 KMP 算法，顺便记下来。
学过数据结构或者算法课的人应该都清楚 KMP 算法的作用：判断一个字符串（模式串，Pattern）是不是另一个字符串的子串。
大一的新生学过 C 语言之后肯定都会觉得这很容易，并可以写出像下面这样的代码来解决问题：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 | /** * 代码 #1, naive solution **/ void isSubstring(char *text, char* pattern) { int i, j; for(i = 0; text[i] != '\0'; i++) { for(j = 0; text[i + j] != '\0' && pattern[j] != '\0'; j++) { if(text[i+j] != pattern[j]) { break; } } if(pattern[j] == '\0') { printf("yes\n"); return; } } printf("no\n"); } |
这没错，但不够好。假设两个字符串的长度分别为 m 和 n，两层循环导致了这个算法的时间复杂度达到了 O(mn)，在字符串长度较长并且运气较差的情况下，这要花费太多的时间。不过这个算法的思想是正确的，我们需要做的只是简化它。
Tagged with: 算法
废话
又到周末了，无聊。当然其实还有很多事情没有做，就是拖延嘛。每到这个时候，就可以写 Blog 来消遣和打发时间了。昨天初体验 Readability 看了看 log4j 的手册，那今天就写这个了。
它是什么
说白了，就是个 log 类库。
核心组件
log4j 由这三个重要的组件一起工作来完成日志工作：
- Logger（v1.2 之前叫做 Category）：用来记录日志。
- Appender： 用来决定将日志输出到哪儿。
- Layout：用来格式化日志输出。
然后就可以开始逐个介绍它们了。 Continue reading »
定义
假设有 A，B 两个字符串，A = "ABCDE"， B = "ABDFE"，那么 A 和 B 的最长公共子序列就是 Z = "ABDE"。因为是子序列而不是子串，所以不要求构成子序列的字符在原串中是连续的。
为了方便讨论，设 S 为一个字符串 <s[1], s[2], ... s[n]>。S 串的长度为 n。s[x] 表示 S 串的第 x 个字符，而 S[x] 表示 S 串的前 x 个字符组成的串，例如 S[2] = <s[1], s[2]>，特别的，S[0] 为空串。
子序列的严谨的定义为：设 A = <a[1], a[2], a[3], ... a[m]>， B = <z[1], z[2], ... z[n]> 中的每个字符都在 A 中，且在 A 中的下标都是严格递增时， B 就是 A 的子序列。
而最长公共子序列，就是指在多个串中，共有的，长度最长的子序列。最长公共子序列可能不存在，也可能存在多个。本篇文章讨论两个串的最长公共子序列。 Continue reading »
我又要开始感叹这一年过得真快了。前几天收到提醒邮件，说博客主机即将过期，所以就又要开始选择，然后折腾了。
去年这个时候我把主机搬到了老薛的香港主机上，总体来说还不错。但是本着折腾的精神，今天把博客搬到了 homzz 的服务器上，虽然在美国，但是似乎日本 CDN 的加速效果还不错。
折腾的不止是主机。
这个学期的第一个班会上，咱班干说今年四月或者五月就要举行毕业晚会，班上要出两个节目，说是因为大概这个学期是大家都能聚在一起最后的时间了，到了大四大家也许就各奔前程，准备考研，考公务员或者去实习了。这么一听，才知道自己确实是快要毕业了。快要毕业了，没有人会愿意跟着失业。于是突然之间大家就觉悟了起来，或者说真正地忙了起来。比如我现在会经常回之前的寝室看看，然后发现以前 24 小时不出门宅寝室打 Dota 的俩哥们儿现在从早至晚地泡自习室准备研究生考试；比如之前整天忙着看综艺娱乐的哥们儿现在整天问我 Struts 2 的用法并且激动地 Coding；还比如大家在饭桌上讨论的话题大多都变成了打算考哪所学校或者去哪个城市。大家一下子就严肃了起来，相比起来我就显得不忙了。
于是我决定去听课。像往常一下，我总是能发现老师埋的彩蛋，比如 Oracle 老师叫我们去微软的官网下载 Oracle 数据库。所以去听课不是办法。
兴趣
目录
