2016-10-10 craneyuan
基本问题 如何将单链表反转? 单链表结构定义 ``` java /** 单链表定义 * * @author: crane-yuan * @date: 2016-9-17 下午12:11:13 */ public class ListNode { public int val; public ListNode next; public ListNode(int x) { val = x; } } ``` more 算法实现 java /** 单链表反转 * * @param head * @return ListNode */ public static ListNode rever 继续阅读 »
2016-09-03 craneyuan
定义 快速排序(英语:Quick Sort),又称划分交换排序(partition-exchange sort),一种排序算法,最早由东尼·霍尔提出。在平均状况下,排序n个项目要Ο(n log n)次比较。在最坏状况下则需要Ο(n2)次比较,但这种状况并不常见。事实上,快速排序通常明显比其他Ο(n log n)算法更快,因为它的内部循环(inner loop)可以在大部分的架构上很有效率地被实现出来。 more 算法步骤 快速排序使用分治法(Divide and conquer)策略来把一个序列(list)分为两个子序列(sub-lists)。 步骤为: 从数列中挑出一个元素,称为"基准"(pivot), 重新排序数列 继续阅读 »
2016-09-05 craneyuan
定义 基数排序(英语:Radix Sort)是一种非比较型整数排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。由于整数也可以表达字符串(比如名字或日期)和特定格式的浮点数,所以基数排序也不是只能使用于整数。 more 算法步骤 将所有待比较数值(正整数)统一为同样的数位长度,数位较短的数前面补零。 然后,从最低位开始,依次进行一次排序。 这样从最低位排序一直到最高位排序完成以后,数列就变成一个有序序列。 基数排序的方式可以采用LSD(Least significant digital)或MSD(Most significant digital),LSD的排序方式由键值的最右边开始,而MSD则相反,由 继续阅读 »
2016-08-28 craneyuan
定义 选择排序(英语:Selection sort)是一种简单直观的排序算法。它首先在未排序的序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。以此类推,直到所有元素均排序完毕。 more 选择排序的主要优点与数据移动有关。如果某个元素位于正确的最终位置上,则它不会被移动。选择排序每次交换一对元素,它们当中至少有一个将被移到其最终位置上,因此对n个元素的表进行排序总共进行至多n-1次交换。在所有的完全依靠交换去移动元素的排序方法中,选择排序属于非常好的一种。 算法步骤 选择排序算法的运作如下: 首先在未排序序列中找到最小(大)元素,存放到排序 继续阅读 »
2016-07-05 jude
这是一个基础算法系列,主题是:为什么知道原理还是写不出正确的程序呢? 第一篇已经写好,叫做我尝试去写快排,结果。。。。文章结构都差不多:原理、联想、用法、框架、分步实现、完整代码及测试用例。 原理 插入排序的原理是: - 将集合分为两个部分:已排好的部分和待排序的部分 - 每次从待排序部分抽一个元素跟已排好部分中的元素逐一比较,直到找到合适的位置,插入待排序元素 - 合适的位置可以是第一个比待排序元素小(大)的,也可能是已排好部分的下界 继续阅读 »
2016-09-16 craneyuan
题目描述 给定一个已排序的数组,去除数组中的重复元素,只保留一个重复的元素,并且返回新的数组长度。 要求: 不要给数组分配额外的空间,你必须使用常量的内存大小进行原地操作。 例如: 给出数组A=[1,1,2],你的函数调用之后必须返回长度length=2,并且A现在变成[1,2]。 输入 一个已排序的数组,例如[1,1,2]。 输出 返回数组新的长度,例如length=2。 快慢指针法 设置fast指针遍历数组,slow指针指向不重复元素的下一位。 more java public static int removeDuplicates(int[] nums) { if (nums.length < 1) 继续阅读 »
2014-01-15 W.Y.
算法原理 基数排序 (Radix Sort) 是一种非比较型整数排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。基数排序的发明可以追溯到 1887 年赫尔曼·何乐礼在打孔卡片制表机 (Tabulation Machine)上的贡献。 排序过程:将所有待比较数值(正整数)统一为同样的数位长度,数位较短的数前面补零。然后,从最低位开始,依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。 基数排序法会使用到桶 (Bucket),顾名思义,通过将要比较的位(个位、十位、百位...),将要排序的元素分配至 0~9 个桶中,借以达到排序的作用,在某些时候,基数排序法的效率高于其它 继续阅读 »
2016-12-22 AnnatarHe
生成二叉树 type Node struct { data string left *Node right *Node } nodeG := Node{data: "g", left: nil, right: nil} nodeF := Node{data: "f", left: &nodeG, right: nil} nodeE := Node{data: "e", left: nil, right: nil} nodeD := Node{data: "d", left: &nodeE, right: nil} nodeC := Node{data: "c", left: nil, right: 继续阅读 »
2016-05-22 MoreFreeze
学习了下LevelDB的实现原理,发现G厂大神Jeff Dean果然牛B,实现也很巧妙。 参考链接是这里 继续阅读 »
2014-01-15 W.Y.
算法原理 希尔排序算法是按其设计者希尔(Donald Shell)的名字命名,该算法由1959年公布,是插入排序的一种更高效的改进版本。它的作法不是每次一个元素挨一个元素的比较。而是初期选用大跨步(增量较大)间隔比较,使记录跳跃式接近它的排序位置;然后增量缩小;最后增量为 1 ,这样记录移动次数大大减少,提高了排序效率。希尔排序对增量序列的选择没有严格规定。 希尔排序是基于插入排序的以下两点性质而提出改进方法的: - 插入排序在对几乎已经排好序的数据操作时, 效率高, 即可以达到线性排序的效率 - 但插入排序一般来说是低效的, 因为插入排序每次只能将数据移动一位 算法思路: 1. 先取一个正整数 d1(d1 < n),把全部记 继续阅读 »