2016-07-21 ruki
The algorithm is based on libtess2 here and we optimizated some implementation and fixed some bugs. The differents between our algorithm and libtess2's algorithm: We change the coordinate system and the sweep direction (sweep line by horizontal here). We need not project the vertices because our graphic engine is 2d, 继续阅读 »
2015-04-24 刘太华
游戏服务端碰撞检测 最近看了一些游戏碰撞检测相关的一些内容,然后开始读了一些我们游戏里关于碰撞检测的代码,我们游戏里现在的碰撞检测按我暂时阅读完的代码, 应该分为2块,相对来说我们基本的碰撞检测算法是比较简单的, 后面也记录一下网上看到的关于分离轴多边形的碰撞检测。 继续阅读 »
2016-08-20 crane-yuan
最近在研究算法,发现其实算法也并不是特别难,只要抓住算法的核心思想,再静下心来,都可以自己实现的。在计算机领域,有一些常见的而且又经常使用的算法,这些算法我们应该掌握,比如常见的排序算法;还有一些算法就是特定领域中经常使用的算法了,这些算法我们只有必须使用时再去学习使用就行了,比如图像处理中的快速傅里叶变换算法。 算法定义 让我们来看看算法的定义吧。(以下定义摘自中文维基百科) 在数学和计算机科学/算学之中,算法/演算法/算则法(Algorithm)为一个计算的具体步骤,常用于计算、数据处理和自动推理。精确而言,算法是一个表示为有限长列表的有效方法。算法应包含清晰定义的指令用于计算函数。 算法中的指令描述的是一个计算,当其运 继续阅读 »
2016-09-02 crane-yuan
定义 希尔排序(英语:Shell sort),也称递减增量排序算法,是插入排序的一种更高效的改进版本。希尔排序是非稳定排序算法。 希尔排序是基于插入排序的以下两点性质而提出改进方法的: 插入排序在对几乎已经排好序的数据操作时,效率高,即可以达到线性排序的效率 但插入排序一般来说是低效的,因为插入排序每次只能将数据移动一位 more 算法步骤 希尔排序通过将比较的全部元素分为几个区域来提升插入排序的性能。这样可以让一个元素可以一次性地朝最终位置前进一大步。然后算法再取越来越小的步长进行排序,算法的最后一步就是普通的插入排序,但是到了这步,需排序的数据几乎是已排好的了(此时插入排序较快)。 选择步长 按照选择的步长对序列进 继续阅读 »
2017-05-21 Robert Zhang
关于最长上升子序列的O(N*logN)算法已经有不少文章表述,可惜大都不够“好”(甚至语焉不详):我认为“好”的算法描述不但应该清晰地说明计算步骤,更应该讲清思路——即,这个算法是怎样思考得出的。这种思考的过程和方式才是精华之处。我试图用我的理解对这个算法给出一个尽量“好”的推导和表述,使你我一样的普通人都可以理解它的思路。 继续阅读 »
2016-09-17 crane-yuan
题目描述 给定一个已排序的单链表,去除单链表中的重复元素,只保留一个重复的元素,并且返回新的单链表。 例如: 给出1->1->2,你的函数调用之后必须返回1->2。 输入 一个已排序的单链表,例如1->1->2。 输出 返回1->2。 代码示例 ``` 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; 继续阅读 »
2016-10-10 crane-yuan
基本问题 如何将单链表反转? 单链表结构定义 ``` 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-10-12 crane-yuan
基本问题 如何删除单链表中的倒数第n个节点? 常规解法 先遍历一遍单链表,计算出单链表的长度,然后,从单链表头部删除指定的节点。 more 代码实现 ``` java /** 删除单链表倒数第n个节点,常规解法. * * @param head * @param n * @return ListNode */ public static ListNode removeNthFromEnd(ListNode head, int n) { if(head == null) { return null ; } //get length of list ListNode p 继续阅读 »
2016-09-16 crane-yuan
题目描述 给定一个已排序的数组,去除数组中的重复元素,只保留一个重复的元素,并且返回新的数组长度。 要求: 不要给数组分配额外的空间,你必须使用常量的内存大小进行原地操作。 例如: 给出数组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) 继续阅读 »
2016-08-28 crane-yuan
定义 冒泡排序(英语:Bubble Sort)是一种简单的排序算法。它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。 more 算法步骤 冒泡排序算法的运作如下: 比较相邻的元素。如果第一个比第二个大,就交换他们两个。 对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。这步做完后,最后的元素会是最大的数。 针对所有的元素重复以上的步骤,除了最后一个。 持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。 伪代码如下: 继续阅读 »