Browsed by
标签:算法

Leetcode 编程训练

Leetcode 编程训练

LeetCodeLogo (1)Leetcode这个网站上的题都是一些经典的公司用来面试应聘者的面试题,很多人通过刷这些题来应聘一些喜欢面试算法的公司,比如:Google、微软、Facebook、Amazon之类的这些公司,基本上是应试教育的功利主义。

我做这些题目的不是为了要去应聘这些公司,而是为了锻炼一下自己的算法和编程能力。因为我开始工作的时候基本没有这样的训练算法和编程的网站,除了大学里的“算法和数据结构”里的好些最基础最基础的知识,基本上没有什么训练。所以,当我看到有人在做这些题的时候,我也蠢蠢欲动地想去刷一下。

于是,我花了3-4个月的业余时间,我把Leetcode的154道题全部做完了。(这也是最近我没有太多的时间来写博客的原因,你可以看到我之前做的那个活动中有几个算法题来自于Leetcode)有人说我时间太多了,这里声明一下,我基本上都是利用了晚上10点以后的时间来做这些题的。

LeetCode的题大致分成两类:

1)基础算法的知识。这些题里面有大量的算法题,解这些题都是有套路的,不是用递归(深度优先DFS,广度优先BFS),就是要用动态规划(Dynamic Programming),或是拆半查找(Binary Search),或是回溯(Back tracing),或是分治法(Divide and Conquer),还有大量的对树,数组、链表、字符串和hash表的操作。通过做这些题能让你对这些最基础的算法的思路有非常扎实的了解和训练。对我而言,Dynamic Programming 是我的短板,尤其是一些比较复杂的问题,在推导递推公式上总是有思维的缺陷(数学是我的硬伤),通过做了这些题后,我能感到我在DP的思路上有了很大的收获。

2)编程题。比如:atoi,strstr,add two num,括号匹配,字符串乘法,通配符匹配,文件路径简化,Text Justification,反转单词等等,这些题的Edge Case, Corner Case有很多。这些题需要你想清楚了再干,只要你稍有疏忽,就会有几个case让你痛不欲生,而且一不小心就会让你的代码会写得又臭又长,无法阅读。通过做这些题,可以非常好的训练你对各种情况的考虑,以及你对程序代码组织的掌控(其实就是其中的状态变量)。还记得我在《函数式编程》中说的,程序中的状态是你程序变得复杂难维护的直接原因。

我觉得每个程序员都应该花时间和精力做这些题,因为你会从这些题中得到很大的收益。做完这些题后你一定会明白下面几个道理:

阅读全文 Read More

好烂啊有点差凑合看看还不错很精彩 (74 人打了分,平均分: 4.78 )
Loading...
一些有意思的算法代码

一些有意思的算法代码

Keith Schwarz是一个斯坦福大学计算机科学系的讲师。他对编程充满了热情。他的主页上他自己正在实现各种各样的有意思的算法和数据结构,http://www.keithschwarz.com/interesting/, 目前这个网页上有88个(见下面的列表),但这位大哥要干135个,你可以看看他的To-Do List

从这个列表上,我们可以看到,他从去年7月份就在自己实现这些东西了,我把他实现的这些算法转过来,

  • 另一方面我希望这个事可以影响到一些正在学习编程的人。看看别人是怎么学习编程的,希望对你有借鉴作用。
Name Link Date Added Language Description
Binomial Heap (link) 7‑24‑2010 C++ An implementation of a binomial heap data structure for use as a priority queue.
Bounded Priority Queue (link) 7‑24‑2010 C++ An implementation of a priority queue with a fixed upper limit to its size..
Matrix (link) 7‑24‑2010 C++ A collection of classes for manipulating matrices.
VList (link) 8‑16‑2010 Java An implementation of the List abstraction backed by a VList.
Function Wrapper (link) 8‑16‑2010 C++ A C++ wrapper class around unary functions.
String (link) 8‑17‑2010 C++ An implementation of a string abstraction that uses the small string optimization.

阅读全文 Read More

好烂啊有点差凑合看看还不错很精彩 (22 人打了分,平均分: 4.86 )
Loading...
可视化的数据结构和算法

可视化的数据结构和算法

还记得之前发布过的那个关于可视化排序的文章吗?在网上又看到了一个旧金山大学David Galles做的各种可视化的数据结构和基本算法的主页,网址在这里,大家可以看看。我把这个页面的目录列在下面并翻译了一下,大家可以直接点击了。

不知道国内的教育有没有相关的教学课件,至少在我大学的时候是没有的。

基础

索引

阅读全文 Read More

好烂啊有点差凑合看看还不错很精彩 (21 人打了分,平均分: 4.81 )
Loading...
一些有意思的文章和资源

一些有意思的文章和资源

又到了向大家介绍一些最近我在网上发现的有价值的东西的时候了。(下面的链接中很多都被墙)

  • 本站的关于排序的文章有很多,对于排序算法来说,其受到要排序的个数和数据的杂乱程度的影响,我们知道比较稳定的排序算法是快速排序和归并排序,归并排序对于大量的数据排序效果是非常好的,尤其是我们可以进行并行的排序。这里有一个并行归并排序的算法的源代码,你可以参考一下 – “Parallel Merge Sort”。
  • 说到“奇技淫巧”和算法,这里有一个文章向你展示了C语言中使用位操作可能完成的各种算法,很有意思。请参看 – “The Aggregate Magic Algorithms
  • 这里有篇文章教你如何取得一个在线的哈佛大学的硕士学位,文章中说了一些相关的事宜,包括一些收费情况,并且展示了一张文凭。这里有一个网页说明了哈佛软件工程学位(Software Engineering)的所需要学习的科目,比如:Java和分布式计算,分布式/企业级计算,设计模式和Java,通讯协议,高级数据网络,Web开发,计算理论,Perl实践,Unix系统编程……我不知道我们的国家各个大学的硕士在学什么,因为我没有读过硕士,但好像现在的计算机研究生只是导师用来挣钱的免费资源,而且,实在不知道研究生在校研究什么。不管怎么样,从这看来,我们的大学好像并没有教给学生计算机的技术。比如在“如何学好C语言”和“如何学好C++语言”中我提到的那些书,那些才是大学里应该学的。我国的教育还真不是一般的落后,不过你不妨试试哈佛的在线学位。

阅读全文 Read More

好烂啊有点差凑合看看还不错很精彩 (13 人打了分,平均分: 4.38 )
Loading...
可视化的排序过程

可视化的排序过程

下面是一个日本程序员制做的一个可视化的排序过程,包括了各种经典的排序算法,你可以调整速度和需要排序的个数。酷壳以前也介绍过几篇相关的文章 一个排序算法比较的网站一个显示排序过程的Python脚本 关于各种排序算法的运行复杂度比较,请参看Wikipedia的排序算法比较

好烂啊有点差凑合看看还不错很精彩 (63 人打了分,平均分: 5.00 )
Loading...
计算机编程简史图

计算机编程简史图

这个图片太经典了,本来想翻译的,后来觉得这么经典的图片可能早已被人翻译了,简单的Google一下,果然有人翻译了。那我就把英文版和中文版都转过来吧。我们可以看到,其中很大一部分人都和Unix有着不解之缘(参见《Unix传奇上篇Unix传奇下篇》)

什么也不说了,直接上图(图片比较大,单击图片看大图)


计算机编程简史图(英文版)

阅读全文 Read More

好烂啊有点差凑合看看还不错很精彩 (15 人打了分,平均分: 4.67 )
Loading...
一些重要的算法

一些重要的算法

下面是一些比较重要的算法,原文罗列了32个,但我觉得有很多是数论里的,和计算机的不相干,所以没有选取。下面的这些,有的我们经常在用,有的基本不用。有的很常见,有的很偏。不过了解一下也是好事。也欢迎你留下你觉得有意义的算法。(注:本篇文章并非翻译,其中的算法描述大部份摘自Wikipedia,因为维基百科描述的很专业了)

  1. A*搜寻算法
    俗称A星算法。这是一种在图形平面上,有多个节点的路径,求出最低通过成本的算法。常用于游戏中的NPC的移动计算,或线上游戏的BOT的移动计算上。该算法像Dijkstra算法一样,可以找到一条最短路径;也像BFS一样,进行启发式的搜索。
  2. Beam Search
    束搜索(beam search) 方法是解决优化问题的一种启发式方法,它是在分枝定界方法基础上发展起来的,它使用启发式方法估计k 个最好的路径,仅从这k 个路径出发向下搜索,即每一层只有满意的结点会被保留,其它的结点则被永久抛弃,从而比分枝定界法能大大节省运行时间。束搜索于20 世纪70 年代中期首先被应用于人工智能领域,1976 年Lowerre 在其称为HARPY的语音识别系统中第一次使用了束搜索方法,他的目标是并行地搜索几个潜在的最优决策路径以减少回溯,并快速地获得一个解。
  3. 二分取中查找算法
    一种在有序数组中查找某一特定元素的搜索算法。搜素过程从数组的中间元素开始,如果中间元素正好是要查找的元素,则搜素过程结束;如果某一特定元素大于或者小于中间元素,则在数组大于或小于中间元素的那一半中查找,而且跟开始一样从中间元素开始比较。这种搜索算法每一次比较都使搜索范围缩小一半。

    阅读全文 Read More

好烂啊有点差凑合看看还不错很精彩 (16 人打了分,平均分: 4.81 )
Loading...
算法和数据结构词典

算法和数据结构词典

我们知道,在编程的世界里,主要就是两个事,用一定的算法去处理一定的数据。算法可以理解为业务逻辑流程,而数据自然一定是按某种结构来存放,这就是数据结构。我们知道,数据结构的修改一定会导致算法的修改,我们也知道,数据结构直接关系到了整个程序的繁简性,高效性。而算法则是关系到数据处理的时间、空间性能,以及日后的扩展和维护。这两个东西是计算机科班出生的人或是需要学习编程的人必需要注意的两件头等大事。

下面这个网站,由 Software and Systems Division, Information Technology Laboratory 创建。

http://xlinux.nist.gov/dads/

阅读全文 Read More

好烂啊有点差凑合看看还不错很精彩 (11 人打了分,平均分: 5.45 )
Loading...
一个显示排序过程的Python脚本

一个显示排序过程的Python脚本

之前向大家介绍过《一个排序算法比较的网站》,那个网站用动画演示了各种排序算法,并分析了各种排序算法。这里,要向大家推荐一个Python脚本,其可以把排序的过程给显示出来。

下图是“冒泡排序”的一个示例,其中:

  1. 折线表示了各个元素的位置变化。
  2. 折线的深浅表示了元素的大小。越深则越大。

bubble

阅读全文 Read More

好烂啊有点差凑合看看还不错很精彩 (8 人打了分,平均分: 4.88 )
Loading...
一个排序算法比较的网站

一个排序算法比较的网站

下面这个网站是一个非常丰富的排序算法的网站。

Sorting Algorithm Animations
http://www.sorting-algorithms.com/

这是一个非常不错的排序算法的网站,当你打开这个网站的时候,请不要因为看到很多个图片的大红叉而鄙视它。你先点击网页上方的Problem Size,选择一个尺寸,20,30,40还是50,都行,于是你就可以看到下面整个大表中有图片显示出来了。如下所示:

sort

阅读全文 Read More

好烂啊有点差凑合看看还不错很精彩 (15 人打了分,平均分: 5.00 )
Loading...