查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

KeepItSimple&&Stupid

Nothing But Orz - Jay(A_Code_Monkey)

 
 
 
 
 
 

博客搬家

2014-11-15 15:42:22 阅读38 评论2 152014/11 Nov15

博客新地址:http://blog.csdn.net/colorwaterer

作者  | 2014-11-15 15:42:22 | 阅读(38) |评论(2) | 阅读全文>>

还是排序算法

2014-11-15 14:37:34 阅读54 评论0 152014/11 Nov15

最近面试经常会碰到一些排序上的题目,所以回去之后一直在巩固这方面的知识。

对于排序算法,我们不能仅看他的效率有多高,还要观察他所占用空间大小和稳定性。

一、排序的关键因素

1、空间

In-place sort:插入排序、选择排序、冒泡排序、堆排序、快速排序。

Out-place sort:归并排序、计数排序、基数排序、桶排序。

这就说明,当数据量过大时,选择 In 排序的比较明智的,因为 Out 排序所占用的内存和空间都比较大,而 In 排序不需要。

2、稳定性

stable sort:插入排序、冒泡排序、归并排序、计数排序、基数排序、桶排序。

unstable sort:选择排序、快速排序、堆排序。

为什么稳定性这么重要?原因很简单,假如你的排序算法经常碰到一些让你耗费大量时间去排序的数据,这明显会影响整体代码运行效率。

二、九大排序算法总结

当然,下面所讲的排序算法都是未经过优化的原始方法。

1、插入排序

插入排序的最优时间数据是已排好序的时候,复杂度为O(n),最坏时间数据是倒叙的时候,负责度是O(n^2)。

而且插入排序比较适合适用少量数据的排序。

2、冒泡排序

冒泡排序的最坏时间是O(n^2),其未作处理的最优时间也是O(n^2),但是做过处理后的最优时间是O(n)。

3、选择排序

最优和最坏时间都是O(n^2),优化后最优时间是O(n)。

作者  | 2014-11-15 14:37:34 | 阅读(54) |评论(0) | 阅读全文>>

优化快速排序的几个方法

2014-11-7 19:25:20 阅读666 评论0 72014/11 Nov7

普通的快排方法对于随机数组来说是挺快的,但是当遇到已经排好序的数组,复杂度马上就降为O(n^2)了。

所以我们需要对其进行优化。首先产生这种情况的原因是什么?是基数,当一个已经排好序的数组,我们所选的基数要么最大,要么最小,这就使得在排序过程中耗费了大量时间,那么如何筛选基数?

方法一:随机数产生区间内的某个数。

方法二:在划分算法上进行优化。

我们将同时从两端进行遍历,将需要的值进行交换即可。

方法三:短区间进行选择排序。

考虑到选择算法的最优时间是O(n),也就是对于已经近似排序好的数组,耗费的时间接近于遍历一次的时间。

方法四:考虑到随机数耗费的时间比较多,所以更好的做法就是我们人工筛选基数。

将要排序的区间进行分段。

当区间长度小于 7 时,我们采用选择排序;

当区间长度小于 40 时,我们将区间分成两段,得到左端点、右端点和中点,我们对这三个点取中数作为基数;

当区间大于等于 40 时,我们将区间分成 8 段,得到左三点、中三点和右三点,分别再得到左三点中的中数、中三点中的中数和右三点中的中数,再将得到的三个中数取中数,然后将该值作为基数。

具体代码只是在上一份的代码中加个筛选中数函数即可。

作者  | 2014-11-7 19:25:20 | 阅读(666) |评论(0) | 阅读全文>>

留恋我的ACM

2014-9-18 14:07:36 阅读85 评论0 182014/09 Sept18

时间过的真快,转眼间已经大四了,马上就要告别ACM了,这个学期最后一次比赛,比完后我也就退役了。

本想早点退役的,只是学弟们不太争气,有的迷恋游戏,贪玩,离ACM越来越远。

所以为了今年比赛成绩不是很难看,我们还在继续,我们能做的也就这些了,就是希望新一届的新生能够努力,不要迷恋游戏,好好学习,发扬宁工ACM集训队,让宁工ACM集训队有朝一日也能出现在World Final的现场赛中。

真是怀念留在集训队的日子啊

2012年11月宁波市赛铜奖

2013年5月浙江省赛铜奖

2013年6月杭州邀请赛铜奖

2013年蓝桥杯浙江省一等奖

2013年蓝桥杯全国赛二等奖

2013年亚洲区域赛铜奖

2014年蓝桥杯浙江省一等奖

2014年浙江省赛银奖

2014年西安邀请赛铜奖

2014年蓝桥杯全国赛一等奖

2014年亚洲区域赛铜奖

2014年亚洲区域赛铜奖

2014年宁波市赛金奖

最后祝愿13届新生能在将来的比赛中有所突破,不断提升自身实力和团体实力。

作者  | 2014-9-18 14:07:36 | 阅读(85) |评论(0) | 阅读全文>>

OSI参考模型

2014-8-28 17:04:39 阅读58 评论0 282014/08 Aug28

第7层 应用层(Application Layer)

应用层能与应用程序界面沟通,以达到展示给用户的目的。 在此常见的协议有: HTTP,HTTPS,FTP,TELNET,SSH,SMTP,POP3等。

第6层 表示层(Presentation Layer)

表示层能为不同的客户端提供数据和信息的语法转换内码,使系统能解读成正确的数据。同时,也能提供压缩解压、加密解密。

第5层 会话层(Session Layer)

会话层用于为通信双方制定通信方式,并创建、注销会话(双方通信)。

第4层 传输层(Transport Layer)

传输层用于控制数据流量,并且进行调试及错误处理,以确保通信顺利。而发送端的传输层会为分组加上序号,方便接收端把分组重组为有用的数据或文件。

第3层 网络层(Network Layer)

网络层的作用是决定如何将发送方的数据传到接收方。该层通过考虑网络拥塞程度、服务质量、发送优先权、每次路由的耗费来决定节点X到节点Y的最佳路径。我们熟知的路由器就工作在这一层,通过不断的接收与传送数据使得网络变得相互联通。

第2层 数据链路层(Data link Layer)

首先数据链路层的功能在于管理第一层的比特数据,并且将正确的数据发送到没有传输错误的路线中。创建还有

作者  | 2014-8-28 17:04:39 | 阅读(58) |评论(0) | 阅读全文>>

二叉查找树-红黑树(其实也没那么难)

2014-8-27 19:11:46 阅读171 评论0 272014/08 Aug27

偶然抽了两三个小时的空学了下红黑树,现在来整理一下。

红黑树,本质上还是一棵二叉查找树,但是它却有其神奇之处——查找、插入、删除的时间复杂度最坏情况下为O(log(n))。

如图就是一颗红黑树(借用一下别人的图片):

之所以这么神奇,是因为它在二叉查找树的基础上增加了着色和相关的性质使得红黑树相对平衡。

首先我们来看看红黑树的一些性质:

1、每个结点要么是红的,要么是黑的。

2、根结点是黑的。

3、每个叶结点(叶结点即指树尾端NIL指针或NULL结点)是黑的。

4、如果一个结点是红的,那么它的俩个儿子都是黑的。

5、对于任一结点而言,其到叶结点树尾端NIL指针的每一条路径都包含相同数目的黑结点。

正是红黑树的这5条性质,使得一棵n个结点的红黑树的高度始终保持在h = logn。

接下来我们就来介绍一下红黑树究竟为什么能自我平衡——旋转起来吧

为什么要旋转?因为当你对一颗红黑树进行插入和删除时,可能会违背了上面说到的5条性质。

为了保持平衡,我们需要着色和旋转。

树的旋转,分为左旋和右旋,如图(借用一下别人的图片)

1.左旋

当进行左旋后,pivot的右儿子Y会替换当前结点的位置,并且Y的左子树会成为pivot的右子树,以及pivot这棵树会成为Y的左子树。

2.右旋

当进行右旋时,类似的,pivot的左儿子Y会替换pivot的位置,并且Y的右子树会成为pivot的左子树,而pivot亦成为了Y的右子树。

作者  | 2014-8-27 19:11:46 | 阅读(171) |评论(0) | 阅读全文>>

B+*树

2014-8-6 18:30:58 阅读7 评论0 62014/08 Aug6

       B树:多路搜索树,每个结点存储M/2到M个关键字,非叶子结点存储指向关键

字范围的子结点(M:一个节点的子节点数);

所有关键字在整颗树中出现,且只出现一次,非叶子结点可以命中;

B+树:在B-树基础上,为叶子结点增加链表指针,所有关键字都在叶子结点

中出现,非叶子结点作为叶子结点的索引;B+树总是到叶子结点才命中;

B*树:在B+树基础上,为非叶子结点也增加链表指针,将结点的最低利用率

从1/2提高到2/3;

作者  | 2014-8-6 18:30:58 | 阅读(7) |评论(0) | 阅读全文>>

巧用二分法

2014-6-21 14:36:28 阅读52 评论0 212014/06 June21

题意:有N个城市,每个城市有Ai个人。

现在要开始投票,每个人有一张票。

作为领导者,你有B个箱子,你必须要将这B个箱子分发到N个城市去,每个城市至少需要一个箱子。

每个人都必须要投票,不能弃票,也就是说要把票丢进箱子里去(每个城市有Ai张票)。

现在问你,怎么分配这B个箱子才能使这些所有箱子里中票数最大的那个箱子里的票最少?

1<=N<=500,000,N<=B<=2,000,000,1<=Ai<=5,000,000。

思路:若每个城市都先分得一个箱子,那么目前的答案就是max(Ai(1<=i<=n))。所以,我们必须要给最大值的那个城市还需要至少分配一个箱子,那么答案肯定不再是那个城市(也有可能有某个城市的人数跟该城市人数一样,那么答案还是没变)。

接下来如果你还有箱子,你肯定要给次大值的那个城市至少再分配一个箱子;

接下来如果你还有箱子,你肯定要给次次大值的那个城市至少再分配一个箱子;

接下来如果你还有箱子,你肯定要给次次次大值的那个城市至少再分配一个箱子;

接下来如果你还有箱子,你肯定要给次次次次大值的那个城市至少再分配一个箱子;

。。。

直到什么时候呢?

直到原先那个最大值城市的票数的一半(奇数需要再加1)大于等于了你刚刚从大到小排列的城市的那个票数,为什么?

因为那个城市的后面的票数肯定小于等于那个城市,那么这些城市中没有一个

作者  | 2014-6-21 14:36:28 | 阅读(52) |评论(0) | 阅读全文>>

ACM算法进阶

2014-4-17 18:05:47 阅读14 评论0 172014/04 Apr17

在网上看到的,准备按着这个一项一项练习~~

第一阶段:练经典常用算法,下面的每个算法给我打上十到二十遍,同时自己精简代码,

因为太常用,所以要练到写时不用想,10-15分钟内打完,甚至关掉显示器都可以把程序打

出来.

1.最短路(Floyd、Dijstra,BellmanFord)

2.最小生成树(先写个prim,kruscal要用并查集,不好写)

3.大数(高精度)加减乘除

4.二分查找. (代码可在五行以内)

5.叉乘、判线段相交、然后写个凸包.

6.BFS、DFS,同时熟练hash表(要熟,要灵活,代码要简)

7.数学上的有:辗转相除(两行内),线段交点、多角形面积公式.

8. 调用系统的qsort, 技巧很多,慢慢掌握.

9. 任意进制间的转换

第二阶段:练习复杂一点,但也较常用的算法。

如:

1. 二分图匹配(匈牙利),最小路径覆盖

2. 网络流,最小费用流。

3. 线段树.

4. 并查集。

5. 熟悉动态规划的各个典型:LCS、最长递增子串、三角剖分、记忆化dp

6.博弈类算法。博弈树,二进制法等。

7.最大团,最大独立集。

8.判断点在多边形内。

9. 差分约束系统.

10. 双向广度搜索、A*算法,最小耗散优先.

作者  | 2014-4-17 18:05:47 | 阅读(14) |评论(0) | 阅读全文>>

n!中包含了几个因子x

2013-11-12 5:49:48 阅读31 评论0 122013/11 Nov12

先求出x的因子关系式,y=2^a0+3^a1+5^a2+……u^a(m-1)。

然后求出n!里包含了b0个2,b1个3,b2个5......u^b(m-1)。

然后对于0到m-1循环,找出最小的bi-ai(0<=i<m)即为答案。

如何求n!里包含了几个素数x?

int sum(int x, int n)

{

int s = 0;

while (n >= x)

{

n /= x;

s += n;

}

return s;

}

作者  | 2013-11-12 5:49:48 | 阅读(31) |评论(0) | 阅读全文>>

查看所有日志>>

 
 
 
 
 
 
 
 

浙江省 宁波市 双子座

 发消息  写留言

 
加油↖(^ω^)↗
 
近期心愿赶紧学算法
人生格言Nothing But Orz - Jay
交友目的 结交朋友
博客等级加载中...
今日访问加载中...
总访问量加载中...
最后登录加载中...
 
 
 
 
 
 
 
心情随笔列表加载中...
 
 
 
 
 
 
 
博友列表加载中...
 
 
 
 
 
 
 
列表加载中...
 
 
 
 
 
 我要留言
 
 
 
留言列表加载中...
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018

注册 登录  
 加关注