八月最后一天, 明天就是大官人回国的日子, 日子很长, 好也好, 坏也好, 却总有个分别的时候, 我在加拿大最艰难的时光, 是和大官人一块度过的, 一块埋怨过, 也一块憧憬过, 我曾经对自己都失去了信心, 是他给了我很多鼓励 !现在他有一个很好的归宿, 衷心的祝福他 ! 我一直以为, 怀念这种事情是对以后再也不会见面的朋友说的, 我们的人生, 现在只是divide, 然后各自conquer, 最后总有combine的一天的.
不再犹豫是我很喜欢的一首歌, 送给大官人, 共勉吧
无聊望见了犹豫达到理想不太易 即使有信心斗志却抑止 谁人定我去或留定我心中的宇宙 只想靠两手向理想挥手 问句天几高心中志比天更高 自信打不死的心态活到老 woo～我有我心底故事 亲手写上每段得失乐与悲与梦儿 woo～纵有创伤不退避 梦想有日达成找到心底梦想的世界 终可见
爱 健身 爱 美食
爱 编程 爱 音乐
爱 007开的 阿斯顿马丁
也爱 29块钱一辆 的 凡客自行车
你好 我是XX, 最终发现自己是一脱屎
在 功夫梦 中有个这样的场景, 当主人公黑人小朋友试图在去中国的飞机上用刚学的稚嫩的中文试图和旁边一个黄种人小胖聊天的时候, 小胖说, “Dude, I am from Detroit.”
诶, 好像和我要说的主题没有关系? 好像是噢, 哎, 博客不是写作文, 随意一些.
现在在多伦多机场的候机大厅, 这次的路线是 toronto–vancouver–seattle, 之前有过一次完全一样的路线, 所以完全不会陌生, 昨天出去BBQ然后明凯好心的收留我在他家过, 和他家的猫JAVA(yeah, a cat called Java!) 厮杀了一个晚上之后, 突然觉得养个小动物真是很好玩的一件事情, 当然, 他家一如既往的让人觉得温暖无比.
我会继续posting, 看看这第二次seattle的行程会有什么不一样的地方.
Go, go, go!
昨天面试结束, 十分疲倦, 虽然事后想起来还是干了很多二事, 也有几倒题目没有回答的那么完善, 但是比起之前微软的面试, 我觉得我至少把我的水平发挥出来了.
到最后一题的时候真得很累, 超级赛亚人的身体也差点坚持不住了. 西雅图的downtown很漂亮, 不过往往是边这条街很繁华, 马上下一条街就很荒凉, 就像酒店的正面这一个区域很多高楼大厦, 不过背面就很破落. 这是故意的?
谢天谢地, 这里的加拿大移民局的工作人员态度特别好, 让我很是感动, 再过半个小时, 我就可以拿到我的新的study permit了, 在美国申请加拿大的study permit, 真是头一遭, 这样就不会和海关有什么冲突了, oh yeah!
顺便说一说这个移民局, 他在一栋大厦的一层楼, 很小的一个房间, 这大概是我见过最不严肃的政府门面了把, 里面没有像在美国海关那种荷枪实弹的壮汉, 只有一个见到谁都乐呵呵笑, (尤其见到美女…)的黑人大叔, 也不像申美签的多伦多大使馆, 书包,手表,手机都能带进去. 最要命的是, 里面的吵闹程度大概可以和菜市场有的一比, 黑人大叔是不管事的, 只有那些工作人员一遍一遍的重复, 不要太吵, 要不然请你们出去.
不过貌似没人听…
to be continued
顺利拿到visa, 可以会加拿大了, 这之前去starbucks逛了逛, 去一个名叫做japanese cuisine的地方吃了中饭, 再次确认了我的一些想法:
1. 国外的sushi, 除非是很高级的, 一定是中国人开的, 国内的就不说了
2. 热门景点周围的餐馆, 最好不要进, 要不然等死你, 这点全世界都一样.
唯一的亮点是我点啤酒的时候服务员执意要看我的ID, 我又年轻了阿, 哈哈
吃完在晃眼的阳光下有些累, 要找个地方休息休息.
keep posting…hope my phone will ring this afternoon…
好久没有更新了, 我不能这么懒. 毕竟我的博客还是有厉害的人物订阅的, 前面一篇写Dynamic Programming还没有写完, 我有空就补上.
日子过得还是有些昏昏谔谔, 但是总算是出现了点规律, 工作呢还在继续努力, 昨天去面试, 做着他们公司的试卷, 3个小时都没有做完, 有一道题目令人发指的竟然写了9页纸, 我自己都有些尴尬了, 最后一题实在没力气了, 大概没吃中饭的缘故把, 直接写上”too tired to do that, sorry”, 然后交卷走人了, 当时觉得自己挺英勇的. 现在想想挺傻的, 多写些字能怎么样呢, 对吧.
生活中倒是没有太多值得庆祝或者大书特书的地方, 只是觉得多伦多的车挺难开的, A&F的衣服挺显肌肉的(又有了健身的动力), 最近和朋友网络聊天还蛮开心的, 室友大官人洗澡的时候练功竟然把旁边的墙都打穿了, 黄小琥唱歌真是很好听, inception真是太让人期待了.
遇到了孙小胖, 竟然得到他下二周要结婚的消息, 真得好恭喜他, 他们高中就在一起了, 是我见过身边最踏实的感情, 这样的爱情故事实在太稀有太难得, 我虽然遇不到但是看见身边朋友能遇到也替他们高兴, 祝他们幸福.
BTW, 大官人, 那道数组连续乘最大的问题, 我刚刚编出来了, LOL
以后会加油更新, 睡觉睡觉.
今天说一些DP(Dynamic Programming)的题目
我对DP的理解, 如果一个问题可以从optimal substructure推出, 那么就可以考虑用DP做, DP的优点, 比较简单直接好理解,
最难的部分应该是找到那个递推表达式.
1. LCS(longest common sequence)
给出数组 a[M], b[N], 找出, 他们之间最长的common sequence, 比如
a = “apple is fashion”
b = “google is not evil”
那么得到的输出结果就是
The LCS number is 7
“le is n”
可见这两句看上去没有什么关系的话还是有一定联系的, lol
如果定义 F(i, j) 是a[0]….a[i], 和 b[0]…b[j]之间的common sequence 的个数
所以
![F(i,j) =\left\{\begin{matrix}F(i-1, j-1)+1&if\quad a[i] = b[j] \\max\{F(i-1, j), F(i, j-1)\}&if\quad a[i] !=b[j]\\\end{matrix}\right.](https://hw.minilinux.net/wp-content/ql-cache/quicklatex.com-24ad657b52cc419b72181f1a6eeacd5b_l3.png "Rendered by QuickLaTeX.com")
如果两个数组的长度分别是LEN1, LEN2, 那么时间复杂度是O(LEN1*LEN2), 然后还需要O(LEN1*LEN2)的空间复杂度.
2. 操作次数问题(operation)
如果有两个字符串str1, str2, 怎么用最少的操作让str1 变成 str2
你可以利用的操作有 1. 插入(insert) 2. 替换(replace) 3. 删除(delete)
再次开动脑经, 如果记录 F(i, j) 为str1[0…i]变成str2[0….j]所需要的操作的数目.
那么就有
![F(i,j) =\left\{\begin{matrix}F(i-1, j-1)&if\quad str1[i] = str2[j] \\min\left\{\begin{matrix}F(i-1, j) (deletion)\\ F(i, j-1) (insertion)\\F(i-1,j-1) (replace)\\\end{matrix}\right.+1&if\quad str1[i] !=str2[j]\\\end{matrix}\right.](https://hw.minilinux.net/wp-content/ql-cache/quicklatex.com-3ef26a5dad6ca0c53a2e4ea2bad2c642_l3.png "Rendered by QuickLaTeX.com")
时间复杂度是 O(LEN1*LEN2)
1. Given an integer, 看这个integer是否是对称的(palindrome), 就是正着和倒着是否都一样
这个有点意思, 时间复杂度O(n)(n 是integer的位数), 这个是必须的, 但是最好的方法必须是要让空间复杂度变成O(1).
分析得仔细点就发现我上面分析的错误, 如果从十位数的位数n这个方面分析, 我们可以发现while loop是O(n)的, 但是里面的 乘法,除法运算都也是O(n)的, 所以总的时间复杂度是O(n^2)的.
至于空间复杂度, 我们再从十进制的位数上来分析, 那么也是O(n)的.
(另外这个问题我是从MITBBS上看来的一道面试题, 发帖的人给出了一个方法是把十进制的每一位放在一个array里面, 然后用stack把逆位储存在另一个array当中, 这个如果换了我当然觉得是我现在的方法空间复杂度更加简便, 但是如果从另一个层面想, 十进制的int本身(每一位)不也是相当于放在一个array当中, 只是它是由编码的bit pattern而确定值, 我这种方法只是针对十进制的int类型做得优化, 但是相对而言之前那个方法反而更加general一些, 写这些只是感觉分析程序优缺点什么的可以想得更general的情况是怎么样, 也许看上去很烂的程序也有自己的好处, 就像最坏情况是O(n^2)的QuickSort竟然在实际中会比一直都是O(nlogn)的HeapSort快一样)
感谢舒晓大神给出的指正!
继续改正, 对于用array的方法, 把所有的的位数, 放在一个array中, 然后用前后两个指针一个向后,一个向前,就是判断string是否是panlidrome的方法.
另外 如果用下面的方法, 有可能出现的问题就是有可能reverse 之后的integer会overflow, 这个问题的解决方法, 当然可以是用long long 来承接reverse之后的integer, 但是这样就显得太不general了, 我也想起了atoi函数里面当时想到的一个问题, 如果overflow了怎么办?(继续延伸, 我想到有次看到讨论如何判断int的乘法是否overflow了, 有个简单的方法是把乘法得出的结果处以任何一个乘数, 看结果是不是另一个乘数)
这个是大官人指出的可能出现的一个问题, 感谢大官人!
int IsPalindrome(int m)
{
int s = 0, temp = m;
while(temp)
{
s = s*10 + temp%10;
temp = temp/10;
}
return s==m;
}
2. Array of non-negative integers. One number appears odd number of times, all the others appear even number of times. Find the number that appears odd number of times.
看到这个题目, 立刻想到了神奇的异或(exclusive or)
int FindOddnumber(int *a, int n)
{
int s = 0;
for(int i=0; i<n; i++)
s ^= a[i];
return s;
}
如果继续问, 不能异或呢, 那么可以考虑Hashtable, 然后进一步或者Hashmap.
Q:
Difference between HashMap and HashTable?
A: The HashMap class is roughly equivalent to Hashtable, except that it is unsynchronized and permits nulls. (HashMap allows null values as key and value whereas Hashtable doesnt allow). HashMap does not guarantee that the order of the map will remain constant over time. HashMap is unsynchronized and Hashtable is synchronized.
3. Difference between override and overload
他们都是Polymorphism的一种, one name, many forms,
overload 是compile-time 的(base class, derived class)
override 是run-time 的
4. 找出一个数组中第K小的数(假设这个数组没有重复)
这个主要思路是用quicksort里面的partition函数, 如果return值 order,
order = partition(int *a, int n) 那么代表a[order]是整个数组a当中的第order+1小的数字
if order+1 < K, order = partition(a+order+1, n-order-1), 然后更新 K= K-order-1; if order+1 >K, 继续用order = partition(a, order)
if order+1 = K, bingo, 返回a[order]就好了
时间复杂度是O(n), 最坏情况O(n^2), 然后有个5个点,5个点的,排列的算法, 最坏也有O(n)(不过太麻烦..)
然后如果要求数列的前K小的数, 也可以用类似这种方法, 或者还能想到的就是维持一个Max-Heap, O(nlogK)的复杂度
5. 实现 KMP 算法
终于神雕侠侣要看完了, 全篇就围绕一个字”情”, 无论是杨过小龙女, 黄蓉和郭靖, 甚至是李莫愁这样的反面角色都充满着情这个字, 甚至是读者总结的一见杨过误终生, 都让人无比唏嘘.
不像郭靖和萧峰,甚至是张无忌, 杨过所做的一切, 都是因为一个情字, 他没有那么多的深明大义, 民族情节, 为了和姑姑在一起他甚至可以加入蒙古阵营, 抛去他的武功和身世不说, 他完全就是一个痴情的普通人而已, 一辈子做得只是想保护好自己所爱的人和她永远在一起. 这让我更加体会到他的真实. 我觉得这是金庸小说里面很吸引人的一个地方, 因为读者有时会觉得主角的问题可能自己也遇到过, 很体贴.
他强任他强，清风拂山岗。 他横任他横,明月照大江
比赛一天一天的进行, 就意味着不断的要开始进行告别了, 不管你是不是球迷都难免能感受
到那份悲凉与不舍.
在BBS上有人这样写到:
很多人在谈亨利的告别赛多么悲情多么憋屈，我倒觉得这样的悲情谢幕却好过很多甚
至没有谢幕机会的人：98年三四名决赛，所有人都在告别德波尔兄弟，却没有人去向戴
维斯和博格坎普告别；02年小组赛，巴蒂的泪水感动了无数人，但谁知道那也是萨内蒂
的最后一场世界杯；意大利对韩国赛后，马尔蒂尼穿着那款经典的紧身球衣，懊恼不已
，维埃里却无声息的走进球员通道，然后再也没有出现在世界杯上；06年三四名决赛，
菲戈与卡恩赛后紧紧拥抱的时候，巴拉克也许不知道这是他的世界杯绝唱……所以，珍
惜每场比赛吧，像艾弗森说的那样，把每场比赛当做最后一场。
我们也只有像艾弗森说的那样把, 把每天当作最后一天来过.
荷兰加油
update at July 5th,
很可爱的图, 总的来说, 三人的表现都不算差, 只是人们的期待过于高, 高到人们忘记了他们世界杯前踢了那么多联赛, 杯赛, 忘记了队长的袖标对于一个23,24岁的年轻球员的压力, 记得当年曼联和切尔西冠军杯决赛C罗罚失了点球, 他的身边有斯科尔斯, 有吉格斯, 甚至还有费迪南德, 但是在葡萄牙队, 大家都是在看着他, 因为他是队长, 输球了他连哭的权利都没有, 而且他还要去安慰自己的队友, 对于他这样的球员, 大概还是为难了一些把. 不管怎么样, 还是挺C罗.
Go, Go, Go, 荷兰!!
每年暑假的时候, mac都回推出macbook+itouch的促销计划, 不知道有多少人因为这个加入教主的怀抱当中, 今年就有我们可爱的曹大官人, 教主万岁, 早日统一!!
李将军把自己的汽车的空调弄好了, 感觉很屌的样子, 我什么时候能有车呢!!!!!
今天去牛哥家里包饺子, 我那独具匠心的包饺子能力发挥的淋漓尽致, 大家都相当惊讶, 然后自然吃饭间谈谈我们关心的话题, 挺有趣的.
生活总是一直这么鬼斧神工的变化着, 有好有坏, 还是要平常心面对把.
其实我想说的是, 月底要开车去Ottawa, Montreal, 好期待…..开车的那个部分!!!(6.29update: 有事情去不了了, 晓哥辛苦了, 希望那大家玩的开心!)
PS: 明天英格兰加油, 小组赛是道槛, 必须挺住, 我不明白为啥总不上乔科尔呢?
今天来说说排序把,
1. Selection Sort(选择排序)
void SelectionSort(int*a, int n)
{
for(int i=0; i<n; i++)
{ temp = i;
for(int j=i+1; j<n; j++)
if(a[j]<a[temp]) temp = j;
swap(&a[temp], &a[i]);
}
}
SelectionSort的想法很直接, 如果让你做排序, 一个没学过算法的人可能会想, 先把最小的挑出来放在第一个位置, 然后把次小的挑出来放在第二个位置, ……, 这样不就得了, 没错, 就是这么简单.
Time Complexity O(n^2), 无论最好还是最坏.
2. 冒泡排序(Bubble Sort)
void BubbleSort(int *a, int n)
{
for(int i=0; i<n;i++)
for(int j=0; j<n-i-1; j++)
if(a[j]>a[j+1]) swap(&a[j], &a[j+1]);
}
主要思想是: 每次两两比较, 把如果左边比右边大, 那么就交换位置, 如果小就不变, 这样第一遍之后最右边就是最大的数, 第二遍之后右边第二个就是次大的数, 做了n遍就结束了.
Time Complexity O(n^2), 而且不论输入的数组情况是怎么样的, 都是n^2.
3. Insertion Sort(插入排序)
void InsertSort(int* a, int n)
{
int temp;
for(int i =1; i<n; i++)
{ temp = a[i];
for(int j=i-1; j>=0&&temp<a[j];j--)
a[j+1] = a[j];
a[j+1] = temp;
}
Insertion Sort的主要思想在于假设我们每次面对的都是一个已经排好序的数列, 然后我们把需要加进去的元素插入在里面就好了, 如果联系到生活中很像我们打扑克牌时候的插牌方法(当然至少我是这样插牌的..), 可以很容易发现平均时间复杂度是O(n^2), 但是如果遇到数列已经排好序的情况, 那复杂度就变成了O(n), 这是最优情况.
4. MergeSort
int* MergeSort(int *a, int n)
{
if(n<=0) return;
elseif(n==1)
{
int* temp = malloc(sizeof(int)*1); //I always forget this line!
temp[0] = a[0];
return temp;
}
int n1 = n/2;
int* temp1 = MergeSort(a, n1);
int* temp2 = MergeSort(a+n1, n-n1);
int* temp = (int *)malloc(sizeof(int)*n);
int i=0, j=0, k =0;
while(i<n1||j<(n-n1))
{
if(i==n1)
temp[k++] = temp2[j++];
elseif (j==(n-n1))
temp[k++] = temp1[i++];
else
temp[k++] = (temp1[i]<temp2[j] ? temp1[i++]:temp2[j++]);
//I like this line, it rocks
}
free(temp1);
free(temp2);
return temp;
}
主要的思想是divide and conquer, 每次把数组平均分成两个部分, 然后分别排序, 然后再combine起来, 时间复杂度的计算 T(n) = 2T(n/2) + O(n), T(n) = O(nlogn), 所有情况都是这样.
MergeSort的坏处在于, 它不是in-place的, 意思是就是它不能在原数组上做好, 需要额外的空间, (就是我的code里面的那些malloc, free阿这种),
但是它的好处就是它在所有的情况都是O(nlogn)的时间复杂度, 尤其在了解到O(nlogn)是排序时间复杂度的理论下限之后, 我们可以发现这个性质是多么宝贵.
而且从MergeSort中还能推出另一个性质, 求一个数组的逆序是多少?
5. QuickSort
void QuickSort(int *a, int n)
{
if(n>2)
{
int index = Partition(a, n);
QuickSort(a, index);
QuickSort(a+index+1, n-index-1);
}
}
int Partition(int *a, int n)
{
int pivot = a[0];
int i=1, j=1;
while(j<n)
{
if(a[j]<pivot) swap(&a[j], &a[i++]);
j++;
}
swap(&a[i-1], &a[0]);
return i-1;
}
QuickSort, 顾名思义, 快速排序就是很快拉, 平均时间复杂度是O(nlogn), 然后最坏情况就是已经排好序的时候, O(n^2), (所以有人说如果你要测试一个排序程序的话, 一个很好的方法就是把一组排好序的数组作为输入序列 :)).
它所带的partition函数, 实在很屌, 可以附带出很多副产品.