algorithm

堆排序、优先级队列以及相关复杂度分析

堆(heap)是一种特殊的数据结构,主要用途是排序,以及构造优先级队列。

什么是堆?

堆首先是一棵完全二叉树,结点从上到下、从左到右依次排列下来,中间没有空隙结点。完全二叉树有几个重要性质,下面的算法以及复杂度分析会用到:

  • 结点数量为 n 的完全二叉树的高度为:[log2n]+1
  • 第 i 层有 2i-1个结点;也就是每层结点数量是 q = 2 的等比数列;
  • 第 i 个结点的子结点编号是 2*i 和 2*i +1 ;

其次,堆有一个重要性质:每个结点的值都小于(或是大于)其子结点。如果是小于的话,那么树的根节点是最小元素,这样的堆是小顶堆;如果是大于的话,那么根结点是最大元素,这样的堆是大顶堆。下面均以小顶堆为例进行分析。

堆排序

Tags: 

迭代法求平方根和立方根

迭代法求值在数值计算中是一种常用的方法,思路也很简单:首先得有一个迭代公式,比如 $$ z = z - \frac{z^2-x}{2z} $$, 然后给一个初值比如 z = 1.0, 然后不断滴代入公式, 然后结果会不断滴趋近于要求的值,这里就是 x 的平方根。 下面是一些求平方根和立方根的迭代公式,这些公式是某些大家一不小心找出来的或是创造出来的,至于肿么找的或是创造的,这不是 me 关心的事,O__O"…

Newton 算法

平方根 : $$ z = z - \frac{z^2-x}{2z} $$

Babylonian 算法

平方根 : $$z = (z + \frac{x}{z})\cdot\frac{1}{2} $$

立方根 : $$z = (2z + \frac{x}{z^2})\cdot\frac{1}{3} $$

Tags: 

手工开平方

手工开平方

现在有了计算器就是好,掏出计算器开平方完全不在话下,而且是高精度。比如 windows 下的 $$ \sqrt{3} $$= 1.7320508075688772935274463415059 。不过这里要介绍的是一种手工开平方的方法,可能以后永远都不会用上,但是方法就在那里,会不会不是方法的问题。

先回顾一下试除法计算商,比如 $$ \frac{71}{3} = $$ ? 对齐位置,比如用 3 去除 7, 试着商 2, 余 1。余数添上后一位变成 11,然后除以 3, 试商 3, 余 2。再添加 0,变成 20, 除以 3, 商 6 ,... 所以,$$ \frac{71}{3} = 23.6... $$

Tags: 

并查集(union-find-set)

并查集

并查集,即为 union find set,实际上就是说对于集合 set,只有两个操作, 查找 find 和合并 union。它是一种典型的数据结构,用在一些典型的地方。比如说有一些人,他们之间有些人是朋友关系,假设“朋友的朋友也是自己朋友”,那么这些人就可以分成若干伙儿,现在给出一些朋友关系,让给出有多少伙,以及每一伙儿都有哪些人。类似的问题还有很多,比如:

Tags: 

2013年微软实习生面试

面经

5 月 9-10 号这两天是微软(在杭州)面试的日子,me 是 9 号(就是今天)下午 1:00 的。每个人 2-3 面,两面是必须的,每面一对一,都是 1 个小时,也就是 me 们是 1:00 开始一面,2:00 大家再开始二面,至于有没有三面,不同人情况不一样,me 没有三面。一对一面试,在一个(大)房间中,真宽敞,O__O"…;每一面 3 道数据结构/算法题目,貌似是必须的,一个小时内结束一面。

微软面试跟网易、腾讯、阿里云、淘宝、大众点评等等不同的是,人家几乎不关心 u 有神马项目经验,甚至不关心 u 基本语法、操作系统、网络知识学的肿么样,肿之就是 3 道数据结构/算法题目,写程序!!!当然也会说点其他东西,下面慢慢说吧。

Tags: 

剑指offer上的另外一些题目

基本都是数据结构和算法的小题目,可以帮助 me 们锻炼一下编程能力,实际上更多的是分析和解决(小)问题的能力,而编程只是把已有的想法用编程语言描述了一下而已。前面的一些题目也只是描述了大致的思路而已,有些题目程序 me 也还么有写,不能认为这是无关紧要的,“眼高手低”的事情,谁都遇到过,u and me !不过现在时间有限,先把题目罗列一下,然后描述下思路才是当务之急。

Tags: 

剑指offer上的一些题目

me 发现实验室真不是学习的地方,至少 me 在实验室几乎都上网了,O__O"…。昨天去图书馆借了本剑指 offer,看了一个小时,看到了一些题目,有的题目已经见过,他上面说的解题方法也已经知道了,有些么见到。题目要么是语言有关的,要么是数据结构有关的,要么是算法有关的,赶脚都很不错,所以,写下来,围观一下。对了,不要迷信答案,比如前不久微软面试题上面有个 char *p="hello", *q="hello"; 问,p == q 吗?实际上,这是 undefined behavior !but,剑指 offer 上是说 p 和 q 相等,也就是 "hello" 只保存一份!再次说明,不一定!是一份还是两份,至少语言层面没有限定,某个编译器可以只当一份保存,另外一个编译器也可以保存两份!(如果说介对 me 们有神马启发的话,me 赶脚是多看点东西还是比较好点,一家之言难免有错,me 亦如此。)

Tags: 

链表

“今日事,今日毕。”貌似小学就听说了这句名言,本身也挺有道理,然而去做的话,却不是那么容易的事。很久之前,有多久呢?腾讯笔试貌似是上个月 13 号一个周六的事,me 记得,前一天,me 就要写一篇 blog 记录一下链表的程序,然而错过了,介个一错就是大半个月(现在都五月三号勒!)。

问题起因于一个问题:肿么判断两个链表 A 和 B,有没有交点;如果有的话,找到交点位置。

分析

如果说两个链表 A 和 B 有交点 inode 的话,那么,inode 后面的结点便是 A 和 B 共有的结点,而 inode 是最初的一个。所以呢,只需要判断 A 中是不是有一个结点在 B 链表中就可以判断了。如果要找交点位置的话,只需要找到 A 中结点在链表 B 中的第一个结点就可以。如果我们顺序滴遍历 A 中的每个结点,然后搜寻是否在 B 中,就可以一下子完成这两个任务。

Tags: 

快速排序和寻找中位数

介个,肿么说,第一句话要肿么说才好,O__O"…。腾讯实习生笔试中有一道题目,问求 n 个数的最大值和最小值,需要的最少比较次数是多少?问题绝不是简单滴 2n-2 或是 n-1 就算彻底解决了。me 怀疑它的答案可能是 3n/2。为嘛,这里不多说。(因为这本是个引子而已,并不是现在要讨论的东西。)现在 me 们关心的问题是,求 n 个数中的中位数,肿么求?有神马比较好的求法嚒?

Tags: 

Dijkstra最短路径算法

闲逛贴吧,看到一个童鞋问一个图的 Dijkstra 最短路径算法,me 思考了片刻,打算自己写一写,看看水平是不是下降勒,O__O"…,程序写的相对来说比较顺利,但是也遇到了若干个问题,比如如何表示无穷大、如何消除有无穷大的加法、如何保存路径信息、如何输出结果和如何使得开始节点可以调节(而不是硬编码写死)等,最后就有了这篇 blog。先看看人家给的图:

Tags: